Patent ID: 6173387
Filing Date: 2001-01-09
Classification: G06F

Abstract:
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.sup.k.times.2.sup.k) nodes, where k=log2 (sqrt(n)) and k .gtoreq.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;(c) repeating operations (a) and (b) for 2.sup.(k-2) -1 times, each time using different first and second diagonals;(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.times.2 nodes.