A new family of fixed degree Cayley networks for multiprocessor design

Author

Vadapalli, Premkumar ; Srimani, Pradip K.

Author_Institution

Dept. of Comput. Sci., Colorado State Univ., Fort Collins, CO, USA

fYear

1994

fDate

26-29 Oct 1994

Firstpage

394

Lastpage

401

Abstract

We propose a new family of trivalent network graphs with constant node degree 3 for design of massively parallel systems. These graphs are shown to be regular, to have logarithmic diameter in the number of nodes, and to be maximally fault tolerant. We investigate different algebraic properties of these networks (including fault tolerance) and propose simple and optimal routing algorithms. We also show that the proposed graph belongs to the well known family of Cayley graphs

Keywords

fault tolerant computing; graph theory; multiprocessing systems; Cayley graphs; algebraic properties; constant node degree; fault tolerance; fixed degree Cayley networks; logarithmic diameter; massively parallel systems; maximally fault tolerant; multiprocessor design; optimal routing algorithms; trivalent network graphs; Circuit topology; Computer applications; Computer networks; Computer science; Fault tolerance; Hypercubes; Multiprocessor interconnection networks; Network topology; Routing; Very large scale integration;

fLanguage

English

Publisher

ieee

Conference_Titel

Parallel and Distributed Processing, 1994. Proceedings. Sixth IEEE Symposium on

Conference_Location

Dallas, TX

Print_ISBN

0-8186-6427-4

Type

conf

DOI

10.1109/SPDP.1994.346143

Filename

346143