Browse Prior Art Database

Means for Improving the Performance of a Combining Network

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

Publishing Venue

IBM

Related People

Stone, HS: AUTHOR

Abstract

This article shows how to decrease the delay through a combining network, at the cost of reducing its peak rate of combining. A combining- network, as described in [*], is a multi-level switching network in which internal nodes can combine two input requests into a single output request under certain circumstances. The network as a whole has N inputs and N outputs. The peak combining capacity is the ability to combine N simultaneous inputs to produce exactly 1 output.

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

Means for Improving the Performance of a Combining Network

       This article shows how to decrease the delay through a
combining network, at the cost of reducing its peak rate of
combining.  A combining- network, as described in [*], is a
multi-level switching network in which internal nodes can combine two
input requests into a single output request under certain
circumstances.  The network as a whole has N inputs and N outputs.
The peak combining capacity is the ability to combine N simultaneous
inputs to produce exactly 1 output.

      In many applications, it is not necessary to achieve that peak
capacity, and it is sufficient to use a combining network with some
nodes that are not able to combine requests.  When two input requests
cannot be combined, they are passed sequentially through the node by
deferring one while processing the other.  If no nodes can combine,
then the peak combining capacity is just 1 as compared to the
capacity of N when all nodes can combine.

      A node that has no combining has a much shorter delay than one
that has combining.  We describe a means that allows nodes to be made
combining nodes or noncombining nodes as a function of time.  This
produces a shorter network delay when peak combining capacity can be
diminished.

      Assume that at the first level of a combining network, there
are N inputs.  Given any two combinable requests, the most probable
point at which they combine is the last level of the network.
Approximately half of the N(N-1)/2 combinable pairs combine at this
level, and the number of pairs that combine per level drops by a
factor of 2 at each level as you move from the last level to the
first level. Consequently, combining in the bottom level is more
profitable than combining in the first level, because there is a
greater probability that random requests combine there than at the
first level.

      Now consider the capacity of a combining network when only the
last k levels have combining switches and the remaining levels have
no combining.  The combining capacity is 1 for k = 0 and doubles for
each increment of k.

      In a typical parallel computer application, combinable requests
...