Browse Prior Art Database

Adaptive Deadlock-Free Worm-Hole Routing with All Minimal Paths in K-Dimensional Tori

IP.com Disclosure Number: IPCOM000108849D
Original Publication Date: 1992-Jun-01
Included in the Prior Art Database: 2005-Mar-23
Document File: 1 page(s) / 50K

Publishing Venue

IBM

Related People

Gravano, L: AUTHOR [+3]

Abstract

A technique for worm-hole routing on k-dimensional tori is presented. This technique is adaptive, since messages follow paths that depend on local congestion encountered in the network. The algorithm is ensured to be free of both deadlock and livelock. This property is guaranteed while using a small number of resources in the routing node. In addition, all paths with the minimal number of hops from the source to the destination are available for potential routing. This class of routing algorithms is called fully-adaptive minimal.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 78% of the total text.

Adaptive Deadlock-Free Worm-Hole Routing with All Minimal Paths in K-Dimensional Tori

      A technique for worm-hole routing on k-dimensional tori is
presented.  This technique is adaptive, since messages follow paths
that depend on local congestion encountered in the network.  The
algorithm is ensured to be free of both deadlock and livelock.  This
property is guaranteed while using a small number of resources in the
routing node.  In addition, all paths with the minimal number of hops
from the source to the destination are available for potential
routing.  This class of routing algorithms is called fully-adaptive
minimal.

      Five virtual channels per bidirectional link are necessary to
implement the routing technique in hardware, for tori of arbitrary
size and dimension.  Furthermore, it is possible to reduce the number
of channels to 3 in the first dimension of the k-dimensional torus,
yielding a total of 10*(k-1) + 6 channels per routing node.

      The method can also be used for packet routing models. In this
case, fully-adaptive minimal routers that are deadlock- and
livelock-free are obtained with a remarkably low number of buffers
per physical link.  In particular, a 2-dimensional torus requires
only 16 buffers per node.  None of the packet routing algorithms make
use of a central queue to realize any of its properties.  Moreover,
the techniques also work for packets of arbitrary sizes (i.e.,
messages could be too long to fit within a sin...