Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Deadlock Free Routing Schemes on Multistage Interconnection Networks

IP.com Disclosure Number: IPCOM000110568D
Original Publication Date: 1992-Dec-01
Included in the Prior Art Database: 2005-Mar-25
Document File: 2 page(s) / 108K

Publishing Venue

IBM

Related People

Bruck, J: AUTHOR [+8]

Abstract

Disclosed are two schemes for deadlock-free routing on a multistage network. We consider a bidirectional multistage interconnection network. Each switch chip in the network contains two half-switches that route packets in opposing directions. The switch chip can route a packet incoming on any of its input ports to any of its output ports, thus allowing to change the routing direction. Packets are routed using virtual cut-through, and blocked packets are stored in the switch in which congestion occurs. Each switch contains a small buffer associated with each input and output, as well as a large central queue. Packets may either pass directly from an input buffer to an output buffer, or they can go from an input buffer to the central queue and then to an output buffer.

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

Deadlock Free Routing Schemes on Multistage Interconnection Networks

       Disclosed are two schemes for deadlock-free routing on a
multistage network.  We consider a bidirectional multistage
interconnection network. Each switch chip in the network contains two
half-switches that route packets in opposing directions.  The switch
chip can route a packet incoming on any of its input ports to any of
its output ports, thus allowing to change the routing direction.
Packets are routed using virtual cut-through, and blocked packets are
stored in the switch in which congestion occurs.  Each switch
contains a small buffer associated with each input and output, as
well as a large central queue.  Packets may either pass directly from
an input buffer to an output buffer, or they can go from an input
buffer to the central queue and then to an output buffer.  Successive
flits of a packet may be stored in buffers at several consecutive
switches on the packet's path.
Deadlock Avoidance

      To focus on network-related issues, we make the following
assumptions.  We assume that any packet deposited into a processor's
transmit-buffer is eventually injected into the network, and that any
packet ejected from the network into a processor's receive-buffer is
eventually cleared from that buffer.  A routing algorithm is
deadlock-free if any packet deposited into a transmit-buffer of any
processor eventually reaches the receive-buffer at its destination.

      We define a node cycle in the network to be a set of switches
(s0,s1, ...,sn-1,sn=s0), such that si+1 can be the successor of si on
the path of some packet, for i=0,...,n-1.  A routing algorithm is
node acyclic if it does not introduce node cycles to the route of any
packet.  Dally and Seitz have shown [*] that node acyclic routing
algorithms are deadlock-free.  Similarly, we define an edge cycle in
the network to be a set of edges (e0,e1,...,en-1,en=e0), such that
for each i=1,...,n-1, edges ei-1 and ei can be successive edges on a
route of a packet.  A routing algorithm is edge acyclic if it does
not contain edge cycles in the route of any packet.  Edge acyclic
routing algorithms are also deadlock-free.
Scheme 1: Straight Routing

      Straight routing is routing on the network in one direction,
that is, moving away from the source towards the destination.  On the
network, straight routing includes node cycles.

      One way to eliminate node cycles in straight routing on the
network is to separate the two dire...