Efficient Nonblocking Switching Networks for Interprocessor Communications in Multiprocessor Systems

Absfruct- The performance of a multiprocessor system de-pends heavily on its ability to provide conflict free paths among its processors. In this paper, we explore the possibility of us-ing a nonblocking network with O ( N log N) edges (crosspoints) to interconnect the processors of an N processor system. We combine Bassalygo and Pinsker's implicit design of strictly non-blocking networks with an explicit construction of expanders to obtain a strictly nonblocking network with-765.18N + 352.8N log N edges and 2 + log(N/5) depth. We present an efficient parallel algorithm for routing connection requests on this network and implement it on three parallel processor topologies. The implementation on a parallel processor whose processing elements are interconnected as in the Bassalyg-Pinsker network requires O ( N log N) processing elements, O ( N log N) interpro-cessor links and it takes O(1ogN) steps to route any single connection request where each step involves a small number ( ~ 7 2) of bit-level operations. A contracted or folded version of the same implementation reduces the processing element count to O ( N) without increasing the link count or the routing time. Finally, we establish that the same algorithm takes O(10g3 N) steps on a perfect shuffle processor with O ( N) processing ele-ments. These results improve the crosspoint, depth and routing time complexities of the previously reported strictly nonblocking networks. Index Terms-Bassalygo-Pinsker network, Clos network, Can-tor network, extensive graph, expander, parallel routing algo-rithm, strictly nonblocking network. I