Browse Prior Art Database

Fully Adaptive Minimal Deadlock Free Packet Routing in Hypercubes, Meshes, and Other Networks

IP.com Disclosure Number: IPCOM000108663D
Original Publication Date: 1992-Jun-01
Included in the Prior Art Database: 2005-Mar-22
Document File: 2 page(s) / 79K

Publishing Venue

IBM

Related People

Felperin, S: AUTHOR [+4]

Abstract

This article deals with the problem of packet-switched routing in parallel machines. Disclosed are several new routing algorithms for different interconnection networks.

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

Fully Adaptive Minimal Deadlock Free Packet Routing in Hypercubes, Meshes, and Other Networks

       This article deals with the problem of packet-switched
routing in parallel machines.  Disclosed are several new routing
algorithms for different interconnection networks.

      While the new techniques apply to a wide variety of networks,
routing algorithms are disclosed for hypercube, the 2-dimensional
mesh, and the shuffle-exchange.  The techniques presented for
hypercubes and meshes are fully adaptive and minimal.  A similar
technique can be devised for tori.

      A fully-adaptive and minimal routing is one in which ALL
possible minimal paths between a source and a destination are of
potential use at the time a message is injected into  the network.
Minimal paths followed by messages ultimately depend on the local
congestion encountered in each node of the network.

      In the shuffle-exchange network, the routing scheme also
exhibits adaptivity but paths could be up to 3 log(N) long for an N
node machine.  The shuffle-exchange algorithm is the first adaptive
and deadlock-free method that requires a small (and independent of N)
number of buffers and queues in the routing nodes for that network.

      Furthermore, all of the new techniques are completely free of
deadlock situations.  In dynamic message injection models, the
routing methods are also ensured to be free of livelock if messages
competing for resources are handled with fairness.

      In  contrast  to  other approaches in which adaptivity,
deadlock and livelock freedom can be guaranteed at the expense of
complex architectures, the algorithms presented in this disclosure
require a very moderate amount of rout...