US 6,173,387 B2Grant

Interleaved exchange in a network mesh

Issue Date:2001-01-09

•6 Claims

•5 Drawing Sheets

Abstract

A method for exchanging information within a mesh network that has an array of nodes defined by four quadrants. The method includes the initial step of exchanging information from a set of nodes in one quadrant to a set of nodes located in an adjacent quadrant. The exchange of information simultaneously occurs in both a vertical and horizontal direction within the array. Information is then exchanged between nodes within the same quadrant and subquadrants.

Metadata

Assignee

Intel Corporation

Inventors

Brent Baxter
Stuart Hawkinson
Satyanarayan Gupta

Application Information

Application Number:US 08/773,262

Filing Date:1996-12-23

Priority Date:1994-05-11

Art Unit:7

Classifications

IPC:

G06F 1500

Field of Search:

395200023952000339580039520068395200693952007395200733952007439580013958001139580012370 943370406370410370400

Patent Drawings (5 sheets)

Description

[0002] This United States (US) Patent Application filed by inventors Baxter et al. is a continuation of U.S. patent application Ser. No. 08/571,694 now abandoned, filed by inventors Baxter et al. on Dec. 12, 1995, entitled “IMPROVEMENTS TO QUADRANT EXCHANGE ALGORITHM” which is a continuation of U.S. patent application Ser. No. 08/241,182 now abandoned, filed by inventors Baxter et al. on May. 11, 1994 entitled “IMPROVEMENTS TO QUADRANT EXCHANGE ALGORITHM” and claims the benefit thereof.

Background of the Invention

[0003] 1. Field of the Invention

[0004] The present invention relates to a method of transmitting information within a network.

[0005] 2. Description of Related Art

[0006] To increase the size, speed and scalability of computer systems, computers may be linked together within a network to process information in parallel. Such systems are commonly referred to as parallel processing networks. Parallel processing networks typically have a plurality of microprocessor based components coupled together by busses and associated hardware. Each processor based component functions as a node which can transmit information to other nodes within the network.

[0007] The nodes can be arranged as a plurality of interconnected cubes, commonly referred to as a hypercube. Hypercubes require a large number of data links, which increase the size of the system.

[0008] The nodes can also be arranged in a two-dimensional array, commonly referred to as a network mesh. FIGS. 1a-dshow a method of exchanging information within a mesh that is commonly referred to as the Direct Exchange Algorithm. In the Direct Exchange method, information is exchanging from one node to another node within the same row of the mesh. The process is repeated until the information of one node is transferred to each of the nodes within the row. For example, as shown in FIG. 1a, in the first step, the information from node 1 is transferred to node 3, node 2 transfers information to node 1, node 3 transfers information to node 4 and the information of node 4 is transferred to node 2. The process of exchanging information between nodes is repeated in accordance with the patterns shown in FIGS. 1b, 1cand 1d. The information can then be exchanged between rows and the process is repeated. Although the Direct Exchange Algorithm has a relatively high transmission rate, the number of messages and the start-up time to send the messages from each node rapidly increases with the size of the mesh.

[0009] FIGS. 2a-fand 3a-dshow other methods of exchanging information within a mesh, commonly referred to as the Binary Exchange Algorithm and the Quadrant Exchange Algorithm, respectively. Both of theses methods utilize a store and forward approach, wherein each node can both receive and forward information transmitted by another node. As shown in FIG. 2a, in the first step of the Binary Exchange method, the nodes in one half of the mesh transmit information to nodes in the other half of the mesh in a horizontal direction. The process is repeated by sending the information from one half of the mesh to the other half of the mesh in a vertical direction, as shown in FIG. 2b. As shown in FIGS. 2c-f, the information is then exchanged within quadrants and subquadrants of the mesh.

[0010] In the Quadrant Exchange method, information is exchanged within rectangular groups of nodes as shown in FIGS. 3aand 3b. As shown in FIG. 3C, the information is then exchanged within separate quadrants of the mesh. Although both the Binary and Quadrant Exchange methods can be used in large mesh networks, the start-up time and transmission rate are relatively slow. Additionally, the Quadrant method is susceptible to node contention. It would be desirable to provide an algorithm for a mesh network, that was not susceptible to node contention and had a relatively high complete information exchange rate.

Summary of the Invention

[0011] The present invention is a method for exchanging information within a mesh network that has an array of nodes defined by four quadrants. The method includes the initial steps of exchanging information from a set of nodes in one quadrant to a set of nodes located in an adjacent quadrant. The exchange of information simultaneously occurs in both a vertical and horizontal direction within the array. Information is then exchanged between nodes within the same quadrant and subquadrants.

Brief Description of the Drawings

[0012] The objects and advantages of the present invention will become more readily apparent to those ordinarily skilled in the art after reviewing the following detailed description and accompanying drawings, wherein:

[0013] FIGS. 1a-dare schematics showing information being exchanged between nodes arranged in a row in accordance with a method in the prior art;

[0014] FIGS. 2a-fare schematics showing information being exchanged between nodes arranged in a two-dimensional array in accordance with a method in the prior art;

[0015] FIGS. 3a-care schematics showing information being exchanged between nodes arranged in a two-dimensional array in accordance with a method in the prior art;

[0016] FIG. 4 is a schematic of a mesh network having an array of nodes that can transfer information;

[0017] FIG. 5 is a schematic showing a node exchanging data with four neighboring nodes;

[0018] FIG. 6ais a schematic of a four by four array of nodes showing a first step of the present method;

[0019] FIG. 6bis a schematic similar to FIG. 3ashowing a second step of the method;

[0020] FIG. 6cis a schematic similar to FIG. 3ashowing a third step of the method;

[0021] FIG. 6dis a schematic similar to FIG. 3ashowing a fourth step of the method;

[0022] FIGS. 7a-hare schematics showing the method in an eight by eight array of nodes.

Detailed Description of the Invention

[0023] The present invention is a method for exchanging information within a mesh network that has an array of nodes defined by four quadrants. The method includes the initial steps of exchanging information from a set of nodes in one quadrant to a set of nodes located in an adjacent quadrant. The exchange of information simultaneously occurs in both a vertical and horizontal direction within the array. Information is then exchanged between nodes within the same quadrant and subquadrants.

[0024] Referring to the drawings more particularly by reference numbers, FIG. 4 shows a mesh network which has a plurality of nodes labeled 1-16. Each node is capable of transmitting and receiving information from another node. As shown in FIG. 5, in the preferred embodiment, each node is a functional computer on a card 20 that can be plugged into the network. The card 20 contains a microprocessor, memory and other associated hardware required to process information. The computer cards 20 contain an interface 22 that couples the components of a card to a number of busses 24. The busses 24 interconnect the cards (nodes) and provide a medium to exchange information between the cards. The cards typically process information in parallel, wherein the mesh is a parallel processing network.

[0025] Each card generates an address for the destination node, along with the information that is to be transmitted to the other node. The address and information are then sent to a node in accordance with the algorithm of the present invention. The transmitting node may also receive information from the destination node. The receiving node stores both the address and the information sent by the transmitting node. If the receiving node has a matching address (destination node) then the node processes the information. If the address of the receiving card does not match the destination address, then the card forwards the address and information to the next node, again in accordance with the algorithm of the present invention. In the preferred embodiment, each node transfers information to a receiving node through a dedicated bus, to avoid bus contention within the system.

[0026] The network has a controller 26 which controls the exchange of information between the nodes. The controller 26 controls which node will receive the information. For example, in accordance with the algorithm of the present invention, the card 20 at node 1 may initially exchange information with node 3, then exchange information with node 9 and finally exchange information with nodes 2 and 5. In the first step, the controller 26 enables the interface of the cards at nodes 1 and 3 to exchange information. The controller 26 may initially allow information generated by node 1 to be transmitted to node 3, and the information generated by node 3 to be subsequently transmitted to node 1. The controller can control the bus and corresponding node that is to receive the information by providing a command to the card or driving active one or more control signals that enable each bus.

[0027] If the information sent by node 3 is to be processed by node 1, the card at node 1 processes the information. If the information transmitted by node 3 is not to be processed by node 1, node 1 retransmits the information generated by node 3 to node 9 in accordance with the second step of the algorithm. Node 1 also receives information from node 9, and the process is repeated with nodes 2 and 5.

[0028] FIGS. 6a-dshow the steps of exchanging information in accordance with an algorithm of the present claimed invention. The method allows the nodes located along a diagonal line of the array to exchange information from one half of the mesh to another half of the mesh. The information is exchanged in both a horizontal and vertical direction within the array. The process of vertically and horizontally exchanging information from nodes along a diagonal line may be repeated a predetermined number of times. The information is then exchanged between nodes within the same quadrant and subquadrants of the nodal array.

[0029] FIGS. 6a-6dshow the steps of exchanging information within a 4 by 4 array of nodes in accordance with an algorithm of the present invention. The lines indicate the path of information exchanged between the corresponding nodes. The first step is shown in FIG. 6a, wherein nodes 1, 6, 9 and 14 exchange information with nodes 3, 8, 11 and 16, respectively, in a horizontal direction of the array, and nodes 2, 4, 5 and 7 exchange information with nodes 10, 12, 13 and 15, in a vertical direction of the array. The exchange of information is interleaved between the nodes, so that none of the nodes both receive and transmit information with more than one node at a time. The interleaving pattern prevents node contention.

[0030] The second step of the algorithm is shown in FIG. 6b, wherein the nodes that exchanged information horizontally in the first step, exchange information vertically, and the nodes that exchanged information vertically exchange horizontally. Accordingly, in the second step, nodes 1, 3, 6 and 8 exchange information with nodes 9, 11, 14, and 16, respectively in the vertical direction, and nodes 2, 5, 10 and 13 exchange information with nodes 4, 7, 12 and 15, respectively in the horizontal direction.

[0031] FIGS. 6cand 6d, show steps three and four of the present algorithm, respectively, wherein the nodes exchange information within the same quadrant of the mesh. In step three (FIG. 6c) the nodes all exchange information horizontally with an adjacent node in the same quadrant. In step four (FIG. 6d) the nodes all exchange information vertically with an adjacent node in the same quadrant. The steps shown in FIGS. 6a-dare then repeated.

[0032] FIGS. 7a-hshow the algorithm of the present invention being performed within an 8 by 8 array of nodes. Like the process of exchanging information in the 4 by 4 array, the nodes in one quadrant of the mesh exchange information to nodes in an adjacent quadrant of the array in both the vertical and horizontal directions. The process of exchanging information between quadrants of nodes is repeated three more times as shown in FIGS. 7b-d. The nodes then exchange information with nodes of the same quadrant and subquadrant as shown in FIGS. 7e-h. Although 4 by 4 and 8 by 8 nodal arrays are shown and described, it is to be understood that the algorithm of the present claimed invention can be used in other two-dimensional nodal arrays.

[0033] The complete time to exchange information between nodes can be defined by the following three parameters.

[0034] Latency (α): the latency is defined as the start up time required to exchange a message and includes fixed overheads associated with each message. α typically has the units of seconds.

[0035] Bandwidth (B): the bandwidth is the rate at which information can be transmitted along the communication links between the nodes. B typically has the units of bytes/sec.

[0036] Rearrangement rate (δ): the rearrangement rate is the rate at which information can be rearranged at the node for further transmission. δ typically has the units of bytes/sec.

[0037] The complete exchange of information using the algorithm of the present invention is defined by the following equation.

2^{K} α + 2^{(k - 1)} \frac{mn}{B} + K \frac{mn}{δ}

[0038] wherein;

[0039] m=the bytes of data exchanged.

[0040] n=the number of nodes in the network.

[0041] K=log₂{square root over (n)} {or k such that n=2^k·2^k}.

[0042] The first term of the equation relates to the latency of the system, the second term corresponds to the system bandwidth, and the last term defines the rearrangement rate. Table I shows the different terms of the equation for the method of the present invention (entitled Interleaved Binary Exchange) with similar terms for information exchange equations relating to the Direct Exchange algorithm, Binary Exchange algorithm and the Quadrant Exchange algorithm.

[0043] As shown in Table 1, the algorithm of the present invention provides improved performance over both the Binary Exchange and Quadrant Exchange algorithms by reducing the start-up and transmission times. The Direct Exchange algorithm provides better performance for both the transmission time and the rearrangement time, but the start-up time and number of messages increases drastically for larger mesh networks. The present invention thus provides an algorithm that improves the performance of scalable parallel processing networks over algorithms in the prior art.

[0044] While certain exemplary embodiments have been described and shown in the accompanying drawings, it is to be understood that such embodiments are merely illustrative of and not restrictive on the broad invention, and that this invention not be limited to the specific constructions and arrangements shown and described, since various other modifications may occur to those ordinarily skilled in the art.

Claims

What is claimed is:

1. A method for performing interleaved exchange of data messages between nodes of a quadrant and nodes of a different quadrant in a mesh of n=(2^k×2^k) nodes, where k=log2 (sqrt(n)) and k ≧2, the mesh having four quadrants, each of the quadrants initially having more than two nodes, each quadrant of nodes being exclusive to the corresponding quadrant, the method comprising the operations of:

(a) exchanging data messages between each node located alone a first diagonal of the mesh and a corresponding node in an adjacent quadrant in a first direction, the first diagonal being included in two of the four quadrants, and between each node located alone a second diagonal of the mesh and a corresponding node in an adjacent quadrant in a second direction, the second direction being orthogonal to the first direction, the second diagonal being adjacent to the first diagonal and being included in two of the four quadrants;

(b) exchanging data messages between each node located along the first diagonal of the mesh and a corresponding node in an adjacent quadrant in the second direction, and between each node located along the second diagonal of the mesh and a corresponding node in an adjacent quadrant in the first direction;

(d) performing operations (a), (b) and (c) for each of the quadrants, each of the quadrants substituting the mesh in operations (a), (b) and (c); and

(e) repeating operation (d) for each of subquadrants in the quadrants, each of the quadrants having four subquadrants, each of the subquadrants substituting a quadrant in operation (d), until each of the subquadrants has 2×2 nodes.

2. The method of claim 1 wherein the time required for said complete exchange of data messages between the n nodes is expressed as:

2^kα+2^(k−1)(mn/B)+k(mn/δ)

where:

m=number of bytes in each data message;

α=the latency, which is the start-up time required to exchange a data message;

B=the bandwidth, which is the rate at which data messages can be transmitted along communication links, in bytes per second; and

δ=the rearrangement rate, which is the rate at which data can be rearranged at a node for subsequent transmission, in bytes per second.

3. The method of claim 1 wherein each node of the mesh comprises a processor.

4. The method of claim 3 wherein the mesh of processors exchange data messages to perform parallel processing.

5. The method of claim 1 wherein each node of the mesh comprises a computer.

6. The method of claim 5 wherein the mesh of computers exchange data messages to perform parallel processing.

Patent Citations (5)

Patent	Date	Inventor	Cited By
US4709327	1987-11-01	Hillis et al.	Examiner
US5038386	1991-08-01	Li	Examiner
US5103393	1992-04-01	Harris et al.	Examiner
US5170393	1992-12-01	Peterson et al.	Examiner
US5333279	1994-07-01	Dunning	Examiner

Non-Patent Literature (16)

Lai et al., “Placement of the Processors of a Hypercube”, Jun. 1991, 714-722.Examiner
Lai et al., “Placement of the Processors of a Hypercube,” IEEE Transactions on Computers, vol. 40, No. 6, pp. 714-722.Examiner
Shahid H. Bakhari, Complete Exchange on the iPSC-860, Nasa CR-187498, ICASE Report No. 91-4, Jan. 1991, 32 pages.Applicant
Shahid H. Bokhari & Harry Berryman; Complete Exchange on a Circuit Switched Mesh; 0-8186-2775-Jan. 1992 1992 IEEE; pp. 300-306.Applicant
William Stallings; Computer Organization and Architecture, Designing for Perfomance, Fourth Edition; 1996; pp. 597-603; Prentice Hall, Upper Saddle River, NJ.Applicant
Richard Dorf; The Electrical Engineering Handbook, Chapter 89, Parallel Processors; 1993; pp. 2052-2060; CRC Press, Boca Raton, FL.Applicant
John P. Hayes; Computer Architecture and Organization; 1978; pp. 230-236 & 405-409; McGraw-Hill Book Company.Applicant
Jean-Loup Baer; Computer Systems Architecture; 1980; pp. 527-555; Computer Science Press, Inc., Rockville, MD.Applicant
Dan I. Moldovan; Parallel Processing, From Applications to Systems; 1993; pp. 191-227, 235-239, 287-296, 330-334 & 376-384; Morgan Kaufman Publishers, San Mateo, CA.Applicant
M. Barnett, R. Littlefield, D.G. Payne. R. Van De Geijn; Efficient Communication Primitives on Mesh Architectures with Hardware Routing; 6th SIAM Conference on Parallel Processing for Scientific Computing; Mar. 22-24, 1993; pp. 943-948.Applicant
W.J. Dally; A VLSI Architecture for Concurrent Data Structures; Kluwer Academic Publishers; 1987, pp. 1-242.Applicant
S.L. Johnsson & C-H. Ho; Optimum Broadcasting and Personalized Communication in Hypercubes; IEEE Trans. on Comp., C-38(9); Sep. 1989; pp. 1249-1268.Applicant
William Dally and Charles Seitz; Deadlock-Free Message Routing in Multiprocessor Interconnection Networks; IEEE vol. C-36, No. 5, May 1987; pp. 547-553.Applicant
M. Barnett, R. Littlefield, D.G. Payne. R. Van De Geijn; Global Combine on Mesh Architectures with Wormhole Routing; Proceedings of the 7th International Parallel Processing Symposium held Apr. 13-16, 1993 IEEE; pp. 156-162.Applicant
S.H. Bokhari; Multiphase Complete Exchange on a Circuit Switched Hypercube; Intel. Conf. on Parallel Processing; 1991, pp./ 1525-1529.Applicant
David S. Soctt; Efficient All-to-All communication Patterns in Hypercube and Mesh Topologies; The 6th Distributed Memory Computing Conference Proceedings, Apr. 28-May 1, 1991; 0-8186-2290-3/91.0000/0398 IEEE; pp. 398-403.Applicant

Abstract