Complexity and performance of statistically switched interconnection networks (clos, crossbar, benes, vlsi)
William A. Payne · 1986
This thesis explores the VLSI layout complexity and performance of statistically switched interconnection networks. Particularly it investigates the use of the strictly non-blocking class of interconnection networks. The non-blocking class is the most topologically efficient of all of the networks. However they are also the most area inefficient, and they require difficult algorithms for very fast setup. Very fast setup algorithms are necessary when the network is used for statistical switching. The thesis examines a method of performing high speed path control (i.e., self-routing) on the single-staged crossbar network. A new graph topology namely the butterfly, is used in order to improve the performance of the switch. The theoretical VLSI layout area bounds along with practical VLSI effects are discussed. The corresponding signal net lengths are also described. The thesis also investigates the VLSI area complexity of the Clos family of interconnection networks. This includes a study of the topologies which minimize the area, as well as an analysis of when the Clos networks are more prevalent with respect to area than the crossbar. Self-routing algorithms for the Clos network are also examined. The algorithm is described along with its implementation in VLSI. A special Clos network is introduced which allows for bit routing. Finally the performance of non-blocking networks when they are used for statistical switching is examined. This includes an analysis of both the throughput and delay of the networks. The throughput and delay under the condition of unbalanced traffic is also studied. The performance of the self-routing algorithms of the crossbar and Clos network is also examined.