Augmented Shuffle-Exchange Multistage Interconnection Networks
Kumar, Reddy · Computer · 1987
Multistage interconnection networks, or MINs, have long been studied for use in telephone switching and multiprocessor systems. Since the early 70's several MINs have been proposed to meet the communication needs of multiprocessor systems in a cost-effective manner. These MINs are typically designed for N = m{sup n} inputs and N outputs and contain n stages of (N/m) crossbar switching elements of size m x m. The switches in adjacent stages are connected in such a way that a path can be found from any input to any output. Such MINs have many properties that make them attractive for multiprocessor systems, including O(NlogN) hardware cost as opposed to the O(N/sup 2/) hardware cost of crossbar switches, the ability to provide up to N simultaneous connections, and O(logN) path lengths. Moreover, they can employ simple and distributed routing algorithms - algorithms that make a central routing controller unnecessary and also result in relatively low communication latency times.