Patent ID: 7080156

Claim:
A computer-implemented method of routing a message in an interconnection fabric including a plurality of nodes configured in a two-dimensional array, the plurality of nodes comprising a source node, each node having a plurality of ports, said method comprising: dividing the plurality of nodes into six regions such that each region includes one or more of the plurality of nodes, wherein the six regions comprise: a first region defined by a first plurality of nodes along a first axis passing through the source node; a second region defined by a second plurality of nodes along a second axis passing through the source node, the first axis and the second axis dividing the interconnection fabric into four quadrants; a third region defined by a third plurality of nodes contained within a first of the four quadrants; a fourth region defined by a fourth plurality of nodes contained within a second of the four quadrants; a fifth region defined by a fifth plurality of nodes contained within a third of the four quadrants; and a sixth region defined by a sixth plurality of nodes contained within a fourth of the four quadrants; receiving a message at a first node via a receiving port provided in the first node, wherein the first node has a first node address and the message includes an originating address for the message, a destination address for the message, and a target region for the destination address; and if the first node address does not correspond to the destination address, then: determining an output port from the plurality of ports provided in the first node based on the originating address, the destination address, the first node address, the target region, and the receiving port of the first node; and transmitting the message to a second node coupled to the determined output port.