Mesh network with method and apparatus for interleaved binary exchange

• US 6,460,128 B1
• Filed: 06/12/2001
• Issued: 10/01/2002
• 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): Kim, Matthew
• Assistant Examiner(s): Tran, Denise
• Application Number:
  US09/879,030
• Publication Number:
  US 20020056023A1
• Time in Patent Office: 476 Days
• Field of Search: 712/11, 712/16-18, 712/33, 712/36, 712/42, 709/223, 709/225, 709/238, 709/244, 709/253, 370/406, 370/428, 711/157, 710/100
• US Class Current: 712/11
• 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 two dimensional network mesh of processor nodes to perform parallel processing, the two dimensional network mesh comprising:

a plurality of processor nodes arranged in a square two dimensional matrix of nodes;

a plurality of busses coupled to the plurality of processors to interconnect the plurality of processor nodes to allow the exchange of data between the plurality of processor nodes;

a network controller to control the exchange of data between the plurality of processor nodes; and

, wherein a control method for the exchange of data between the plurality of processor nodes used by the network controller is an interleaved binary exchange algorithm with a multi-stage information transfer cycle, in at least one stage of the information transfer cycle information is transferred in a vertical direction between some nodes and in the horizontal direction between other nodes.

2. The two dimensional network mesh of claim 1, wherein

the two-dimensional network mesh of processor nodes is 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 two dimensional network mesh of claim 1, wherein

the two-dimensional network mesh of processor nodes is 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 two dimensional network mesh of claim 1, wherein

each processor node of the two-dimensional network mesh of processor nodes 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 interconnecting the plurality of processor nodes to process data and to couple the memory to one of the plurality of busses interconnecting the plurality of processor nodes to store data.

5. The two dimensional network mesh of claim 1 wherein, in at least one stage of the multi-stage information transfer cycle, nodes transfer information in a different direction than their horizontally and vertically adjacent neighboring nodes.

6. The two dimensional network mesh of claim 5 wherein, in at least one stage of the multi-stage information transfer cycle, nodes transfer information in the same direction as their diagonally adjacent neighboring nodes.

7. The two dimensional network mesh of claim 1 wherein, at each stage of the multi-stage information transfer cycle, information is transferred at substantially the same time between nodes.

8. The two dimensional network mesh of claim 1 wherein, in a first stage of the information transfer cycle a first set of nodes transfer information in a horizontal direction, and a second set of nodes transfer information in a vertical direction, and in a second stage of the information transfer cycle, the first set of nodes transfer information in a vertical direction.

9. The two dimensional network mesh of claim 1 wherein, in at least one stage of the information transfer cycle, information is transferred in the same direction between nodes.

10. The two dimensional network mesh of claim 1 wherein, in a first information transfer stage, information is transferred in a vertical direction between interleaved nodes and in the horizontal direction between other interleaved nodes, and, in a second information transfer stage, information is transferred in the same direction between some adjacent nodes.

11. The two dimensional network mesh of claim 1 wherein, at any given information transfer stage, a node communicates with just one other node.

12. A mesh network to perform parallel processing, the mesh network mesh comprising:

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;

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

a network controller to control the exchange of data between the plurality of computer cards; and

,

wherein the network controller uses an interleaved binary exchange algorithm with a multi-stage information transfer cycle to control the exchange of data between the plurality of computer cards, in at least one stage of the information transfer cycle, information is transferred in a vertical direction between some nodes and in the horizontal direction between other nodes.

13. The mesh network of claim 12, 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.

14. The mesh network of claim 12, 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.

15. The mesh network of claim 12, wherein each computer card further 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.

16. The mesh network of claim 12 wherein, in at least one stage of the multi-stage information transfer cycle, nodes transfer information in a different direction than their horizontally and vertically adjacent neighboring nodes.

17. The mesh network of claim 16 wherein, in at least one stage of the multi-stage information transfer cycle, nodes transfer information in the same direction as their diagonally adjacent neighboring nodes.

18. The mesh network of claim 12 wherein, in a first information transfer stage, information is transferred in a vertical direction between interleaved nodes and in the horizontal direction between other interleaved nodes, and, in a second information transfer stage, information is transferred in the same direction between some adjacent nodes.