Design of Bounded-degree Circuits for Parallel-processing

Document Type

Article

Publication Date

6-1994

Publication Title

IFIP Transactions a-Computer Science and Technology

Volume

23

First page number:

191

Last page number:

201

Abstract

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 the popular circuits have a degree of the node which is a function of the network size. From the implementation viewpoint, networks with unbounded 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 networks with constant degree of the node is addressed. A transformation applied to a circuit with a varying degree is essentially the replacement of each node with a topology with constant degree. The resulting hybrid circuit usually yields an efficient realization while preserving the advantageous features of designs with unbounded degree. New circuits such as: star-connected cycles, pancake-connected cycles, and bubble-sort connected cycles are introduced as examples of large circuits with constant degree of the node. The proposed networks lend themselves to an efficient VLSI implementation without compromising their efficiency in performing certain parallel algorithms.

Keywords

Computer algorithms; Computer network resources; Computer networks; Distributed operating systems (Computers); Graph theory; Integrated circuits—Very large scale integration Routing (Computer network management); Parallel processing (Electronic computers)

Disciplines

Computer and Systems Architecture | Computer Engineering | Digital Circuits | Digital Communications and Networking | Electrical and Computer Engineering | Systems and Communications | VLSI and Circuits, Embedded and Hardware Systems

Language

English

Permissions

Use Find in Your Library, contact the author, or interlibrary loan to garner a copy of the item. Publisher policy does not allow archiving the final published version. If a post-print (author's peer-reviewed manuscript) is allowed and available, or publisher policy changes, the item will be deposited.

UNLV article access

Search your library

Share

COinS