Method and apparatus for interleaved exchange in a network mesh

• US 6,948,048 B2
• Filed: 07/02/2002
• Issued: 09/20/2005
• Est. Priority Date: 05/11/1994
• Status: Expired due to Fees

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Baxter, Brent, Gupta, Satyanarayan, Hawkinson, Stuart
• Primary Examiner(s): Tran, Denise
• Application Number:
  US10/188,956
• Publication Number:
  US 20030033500A1
• Time in Patent Office: 1,176 Days
• Field of Search: 712/13, 712/18, 712/33, 712/36, 712 42- 43, 709/223, 709/225, 709/238, 709/250, 709244-245, 711/157, 370/406, 370/428, 710/100
• US Class Current: 712/18
• CPC Class Codes: G06F 15/17337 Direct connection machines, e.g. completely connected computers, point to point communication networks coupling between buses G06F13/4004

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.

Claims

1. A method in a mesh network to exchange data to perform parallel processing, the method comprising:

providing a plurality of computer cards each having an interface to transfer information as a processor node in the mesh network and arranged in a square two dimensional matrix of processor nodes in the mesh network;

providing a plurality of dedicated busses coupled to the plurality of computer cards to interconnect the plurality of computer cards and to allow the exchange of data there between;

associating each of the plurality of computer cards in the mesh network with an address; and

each of the plurality of computer cards

generating information to transfer to a destination processor node,

generating an address for the destination processor node, and

transferring the information and the address to another computer card in accordance with the node order specified by an interleaved binary exchange algorithm with a multi-stage information transfer cycle, in at least one stage of the information transfer cycle information is concurrently transferred in only a vertical direction between some processor nodes diagonally aligned in the mesh network and in only the horizontal direction between other processor nodes diagonally aligned in the mesh network.

2. The method of claim 1, wherein

the processor nodes associated with the plurality of computer cards are arranged into four non-overlapping quadrants and each quadrant is arranged into four non-overlapping subquadrants, and

the interleave binary exchange algorithm is as shown in FIGS. 6a through 6d.

3. The method of claim 1, wherein

the processor nodes associated with the plurality of computer cards are arranged into four non-overlapping quadrants and each quadrant is arranged into four non-overlapping subquadrants, and

the interleave binary exchange algorithm is as shown in FIGS. 7a through 7h.

4. The method of claim 1, wherein

each computer card includes,

a processor to process data,

a memory to store data, and

a bus interface to couple the processor to one of the plurality of busses and to couple the memory to one of the plurality of busses.

5. The method of claim 1, wherein

each computer card

receives generated information and address from another computer card as specified by the interleaved binary exchange algorithm,

compares its address with the generated address to determine if the generated information should be processed by it, and

transfers the generated address and the generated information to the next computer card as specified by the interleaved binary exchange algorithm.

6. The method of claim 5, wherein

the processor nodes associated with the plurality of computer cards are arranged into four non-overlapping quadrants and each quadrant is arranged into four non-overlapping subquadrants, and

the interleave binary exchange algorithm is as shown in FIGS. 6a through 6d.

7. The method of claim 5, wherein

the processor nodes associated with the plurality of computer cards are arranged into four non-overlapping quadrants and each quadrant is arranged into four non-overlapping subquadrants, and

the interleave binary exchange algorithm is as shown in FIGS. 7a through 7h.

8. A method comprising:

generating information by selected nodes of an array of nodes; and

transferring the information in accordance with a node order specified by an interleaved binary exchange algorithm with a multi-stage information transfer cycle, the transferring of the information comprises

transferring information in a vertical direction between a first group of nodes aligned diagonally along the array of nodes;

transferring information in the horizontal direction between a second group of nodes aligned diagonally along the array of nodes differing from the first group of nodes, the transfer in the horizontal direction being concurrent with the transfer in the vertical direction, and

the first group of nodes being adapted to intitially transfer information in only the vertical direction and the second group of nodes being adapted to initially transfer information in only the horizontal direction concurrently with the transfer of information in the vertical direction.

9. The method of claim 8, wherein prior to transferring information, including a destination address for the information, the method further comprising:

arranging the plurality of nodes that comprises computer cards into 2ⁿ non-overlapping quadrants and each quadrant being arranged into 2ⁿ non-overlapping subquadrants, where n≧

m.

10. The method of claim 9, wherein n and m are equal to two.

11. The method of claim 8, wherein the first group of nodes represents one-half of the plurality of nodes.

12. The method of claim 8, wherein the second group of nodes represents the other half of the plurality of nodes.

13. The method of claim 8, wherein each of the plurality of nodes being a computer card that comprises (1) a processor, (2) a memory, and (3) a bus interface coupling the processor to one of a plurality of dedicated buses and coupling the memory to one of the plurality of dedicated buses.

14. The method of claim 8, wherein the transferring of information and the destination addresses further comprising:

transferring information and destination addresses in the horizontal direction between the first group of nodes; and

transferring information and destination address in the vertical direction between the second group of nodes.

15. The method of claim 14 further comprising:

transferring information and destination addresses in the horizontal direction between nodes in the same subquadrant; and

transferring information and destination addresses in the vertical direction between nodes in the same subquadrant.

16. A method comprising:

generating information by a first node of a plurality of nodes forming an array of nodes; and

transferring the information in accordance with a node order specified by an interleaved binary exchange algorithm with a multi-shape information transfer cycle by

transferring information in a vertical direction for a first group of nodes of the plurality of nodes diagonally aligned within the array of nodes,

transferring information in the horizontal direction between a second group of nodes of the plurality of nodes diagonally aligned within the array of nodes concurrently with the transferring of information in the vertical direction, the second group of nodes being different from the first group of nodes, and

the first group of nodes being adapted to initially transfer information in only the vertical direction and the second group of nodes being adapted to initially transfer information in only the horizontal direction concurrently with the transfer of information in the vertical direction.

17. The method of claim 16, wherein the information comprises a destination address for the information.

18. The method of claim 17, wherein each of the plurality of nodes is a computer card.

19. The method of claim 17, wherein prior to generating information by the first node, the method further comprising:

arranging the plurality of nodes into four overlapping quadrants, each quadrant being arranged into four non-overlapping subquadrants.

20. The method of claim 16, wherein the transferring of information in the vertical direction is conducted by a first half of the plurality of nodes.

21. The method of claim 20, wherein the tranferring of information in the horizontal direction is conducted by a second half of the plurality of nodes.

22. The method of claim 21, wherein the first half of the plurality of nodes having no common node with the second half of the plurality of nodes.

23. A method comprising:

generating information by a first node of a plurality of nodes of an array of nodes;

transferring the information in accordance with a node order specified by an interleaved binary exchange algorithm with a multi-stage information transfer cycle by

transferring information in a vertical direction a first group of nodes of the plurality of nodes formed diagonally using the array of nodes, and

transferring information in the horizontal direction between a second group of nodes of the plurality of nodes diagonally along the array of nodes concurrently with the transferring of information in the vertical direction, the second group of nodes being different from the first group of nodes,

the interleaved binary exchange algorithm defined by

 

2^kα

+2<sup>(k−

1)</sup>(mn/B)+k(mn/δ

)

 

where;

m=number of bytes of information;

α

=a latency, which is a start-up time required to exchange information;

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

δ

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