Patent ID: 7305487

Claim:
In a massively parallel computing system comprising a plurality of nodes configured in m multi-dimensions, each node including a computing device, a method for routing packets towards a plurality of destination nodes comprising the steps of: a.) inputting said packets from at least one of 2 m directions via at least one of a corresponding number of input links into a corresponding at least one of a plurality of virtual channels, each said packet comprising a packet header including one or more packet hint bits for indicating which of said 2 m directions are feasible for each of said packets to move in; b.) inputting local packets from a local of said nodes to at least one of a plurality of processor injection FIFO's; c.) generating a 2 m plurality of output status bit vectors, each of said output status bit vectors describing the availability of each said destination node's link, the availability of downstream virtual channels, and a downstream buffer space indication for all virtual channels associated with a downstream buffer space direction; d.) establishing a general arbitration policy wherein arbitration decisions are made based on a content of said 2 m plurality of output status bit vectors; e.) outputting according to said general arbitration policy said packets via at least one transfer path to corresponding output links, wherein said packets are advanced towards said destination nodes; and f.) repeating the previous steps for as long as any of said packets and said local packets are available for input, wherein said method for routing packets using hint bits from packet headers of said packets allows establishing said general arbitration policy to complete more quickly.