Self-routing permutation networks for communications and computer systems
Sungchang Lee · 1992
This dissertation is focused on self-routing permutation networks (SRPN's) capable of routing any of n! possible permutations of its n inputs to its n outputs. There has been constant desire for the interconnection networks to achieve higher bandwidth both in communications and computer systems. For this reason, the permutation networks have been of interest since they have the maximum switching capability assuming one-to-one connections. Also, the ability of self-routing is highly desirable for the fast switching and the VLSI implementation and so on. This research presents self-routing permutation networks which have better characteristics than the existing SRPN's in terms of the network delay and the hardware needed. First, a self-routing permutation network named BNB SRPN which implements the binary radix routing is presented. The structure of the network is based on the generalized baseline network, a modified model of the original baseline network. The network reduces both the hardware and the delay time compared with other comparable networks by using 1-bit information in routing decisions with a simple algorithm, which also results in a good hardware regularity. Secondly, a cost-effective self-routing network is presented, which is derived from the BNB SRPN. The network's hardware complexity, $O(N \log N)$, is the same as that of the Benes network which is not self-routing. Thirdly, the theory of realizing a modular structure is presented. In the previously presented networks including ours, trees of size (up to) N were used to collect the information from the inputs and to distribute the routing control signals. The large trees are obstructions in VLSI implementation as the network size N grows. Also, the large trees limit the maximum clock rate when the network is operated with a clock since the largest tree determines the maximum delay in a stage. The theory to localize the routing decision is provided; thus the large trees are broken into smaller trees resulting in modular structure. It is also shown that the modular structure results in the reduction of the total delay through the network when the clock operation is assumed. Finally, the performance of the network is analyzed under the assumptions of random requests and circuit switching using the discrete parameter Markov chain model. Also, another approximate analysis is presented. The analysis shows the inherent switching capability of the network, and the result is also applicable to other binary radix routing based networks. The analysis results are provided and compared with those of the crossbar network and the delta network.