DESIGN OF BOUNDED-DEGREE CIRCUITS FOR PARALLEL-PROCESSING

The design of large circuits to interconnect many processors with low number of I/O ports and short diameter has been one of the major goals of researchers. Unfortunately, the underlying topologies of most of t he popular circuits have a degree of the node which is a function of t he network size. From the implementation viewpoint, networks with unbo unded degree of the node pose two problems. First, there is a limit on the number of I/O channels allocated to a processor. Second, the I/O unit of the processor modules may need to be modified as the result of network expansion. In this paper, the design of high performance netw orks with constant degree of the node is addressed. A transformation a pplied to a circuit with a varying degree is essentially the replaceme nt of each node with a topology with constant degree. The resulting hy brid circuit usually yields an efficient realization while preserving the advantageous features of designs with unbounded degree. New circui ts such as: star-connected cycles, pancake-connected cycles, and bubbl e-sort connected cycles are introduced as examples of large circuits w ith constant degree of the node. The proposed networks lend themselves to an efficient VLSI implementation without compromising their effici ency in performing certain parallel algorithms.