Browse Prior Art Database

Flexible Route Decoder for an Omega Switch Network

IP.com Disclosure Number: IPCOM000099574D
Original Publication Date: 1990-Feb-01
Included in the Prior Art Database: 2005-Mar-15
Document File: 3 page(s) / 139K

Publishing Venue

IBM

Related People

Brantley, WC: AUTHOR [+5]

Abstract

Multi-stage interconnection networks have been used in various forms of communication networks for many years. More recently such networks are the subject of intense interest for use in parallel processors. In either case, large networks are typically built from many small MxN identical switching elements. MxN denotes M input ports that can have data switched to one or more of N output ports. In the parallel processing case, the network serves to make connections between processor, memory and IO elements.

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

Flexible Route Decoder for an Omega Switch Network

       Multi-stage interconnection networks have been used in
various forms of communication networks for many years. More recently
such networks are the subject of intense interest for use in parallel
processors.  In either case, large networks are typically built from
many small MxN identical switching elements.  MxN denotes M input
ports that can have data switched to one or more of N output ports.
In the parallel processing case, the network serves to make
connections between processor, memory and IO elements.

      Communication paths through a network of this type may be
established via a centralized or distributed routing method.  In
packet networks the distributed routing method is more common.
Distributed routing is accomplished by having some additional
information travel along with the packet.  That information
determines path selections at each stage in the network.  A routing
information decode function is present in each switch element.  Its
function is to SELECT from the routing information the portion which
applies to that stage and to INTERPRET it in some way.  The routing
information that is selected at a particular stage is commonly
determined by its position within header or control fields traveling
with the message and by the topology location of the switch element
that is decoding the information.  This implies that the routing
information entering the network must be FORMATTED in some strictly
predefined way.

      In a parallel processor, transmission consisting of
instructions and data are initiated by processors, memories, and IO.
The processor/memory/IO element or some processor/memory/IO local
hardware determines the destination of transmissions.  Thus, prior to
transmitting, the processor/memory/IO must FORMAT appropriate routing
information.

      Problem

      The above-defined processes, FORMAT, SELECT and INTERPRET, can
all be done in software or in microcode, to permit greater
flexibility.  In parallel processors, to maximize performance, these
processes are more commonly done in hardware.  The hardware formatter
and decoder may be partially configurable at system initialization
time.  The design of the FORMAT function is a complex problem in
software and to a greater degree in hardware.

      The difficulty in designing the FORMAT function arises from the
seemingly unlimited variety of network topologies and network sizes
that can be considered when configuring multi-stage interconnection
networks.  Such flexibility is possible because of the modularity of
the MxN switching element from which they are built.  Further
complication comes from the possibility of future machine
reconfiguration and from the possibility of dynamically changing
system operating conditions.  Changes in system operating conditions
may arise from the need to adapt the machine configuration for
special processing needs or to circumvent fail...