The performance of a multiprocessor system depends heavily on its ability to provide conflict free paths among its processors. In this paper, we explore the possibility of using 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 nonblocking 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 Bassalygo-Pinsker network requires O(N log N) processing elements, O(N log N) interprocessor links and it takes O(log N) steps to route any single connection request where each step involves a small number (/spl ap/72) 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(log/sup 3/ N) steps on a perfect shuffle processor with O(N) processing elements. These results improve the crosspoint, depth and routing time complexities of the previously reported strictly nonblocking networks.>

Strictly nonblocking networks may hold the key for high performance multiprocessor systems. While a number of strictly nonblocking networks have been reported in the literature, their use in multiprocessors is hampered by a lack of efficient distributed routing at algorithms to set paths in these networks. As a step in this direction, the paper presents two distributed routing algorithms for D.G. Cantor's (1971) strictly nonblocking network. For N inputs, the first routing algorithm takes O(t)+O(logt log N) steps/sup 1/ to routing t requests in parallel. While this algorithm performs quite well for i=O(log/sup 2/ N), for larger valves of t, we present a randomized version of the same algorithm with an expected time complexity of O(log/sup 2/ N) for any number of requests. These results, when combined with the crosspoints and depth complexities of a Cantor network, give a strictly nonblocking network with O(N log/sup 2/ N) crosspoints, O(logN) depth and O(log/sup 2/N) routing time.