Patent ID: 7477608

Claim:
A method for routing packets on a linear array of N processors connected in a nearest neighbor configuration, comprising the steps of: for each end processor of the array, connecting unused outputs to corresponding unused inputs; for each axis required to directly route a packet from a source processor to a destination processor, determining whether a result of directly sending a packet from an initial processor to a target processor is greater than N/2 moves, the initial processor being the source processor in a first axis, the target processor being the destination processor in a last axis; directly sending the packet from the initial processor to the target processor, irrespective of the result; and indirectly sending at least one of a first dummy packet from and to the initial processor so as to wrap around each end processor, and a second dummy packet from and to the target processor so as to wrap around each end processor, when the result is greater than N/2 moves.