Skip to Content
Find More Like This
Return to Search

Deadlock-free class routes for collective communications embedded in a multi-dimensional torus network

United States Patent

8,364,844
January 29, 2013
View the Complete Patent at the US Patent & Trademark Office
A computer implemented method and a system for routing data packets in a multi-dimensional computer network. The method comprises routing a data packet among nodes along one dimension towards a root node, each node having input and output communication links, said root node not having any outgoing uplinks, and determining at each node if the data packet has reached a predefined coordinate for the dimension or an edge of the subrectangle for the dimension, and if the data packet has reached the predefined coordinate for the dimension or the edge of the subrectangle for the dimension, determining if the data packet has reached the root node, and if the data packet has not reached the root node, routing the data packet among nodes along another dimension towards the root node.
Chen; Dong (Yorktown Heights, NY), Eisley; Noel A. (Yorktown Heights, NY), Steinmacher-Burow; Burkhard (Boeblingen, DE), Heidelberger; Philip (Yorktown Heights, NY)
International Business Machines Corporation (Armonk, NY)
12/ 697,015
20110119399
January 29, 2010
STATEMENT OF GOVERNMENT RIGHTS This invention was made with government support under Contract No. B554331 awarded by the Department of Energy. The Government has certain rights in the invention