Efficient nonblocking switching networks for interprocessor communications in multiprocessor systems

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 comb...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on parallel and distributed systems 1995-02, Vol.6 (2), p.132-141
Main Authors: Fong-Chih Shao, Yavuz Oruc, A.
Format: Article
Language:English
Subjects:
Applied sciences
Bandwidth
Communication switching
Computer science
control theory
systems
Computer systems and distributed systems. User interface
Exact sciences and technology
Fasteners
Graph theory
Intelligent networks
Multiprocessing systems
Network topology
Parallel algorithms
Routing
Software
Software engineering
Telecommunications
Telecommunications and information theory
Teleprocessing networks. Isdn
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.< >
ISSN:1045-9219
1558-2183
DOI:10.1109/71.342124