Fibonacci circulants-a new interconnection topology

Author

Kim, Yong-Seok

Author_Institution

Coll. of Natural Sci., Seonam Univ., Chonbuk, South Korea

Volume

1

fYear

1999

fDate

1999

Firstpage

455

Abstract

The paper proposes a novel interconnection network called Fibonacci circulants for large scale parallel processing systems. The FC(f_3m+2,3) is a regular and vertex transitive (not edge transitive), and has a Hamiltonian cycle. It connects the (3m+2)-th Fibonacci number, f_3m+2, m⩾0 nodes with 2m links per node. It is an improvement over a comparable hypercube or multiply-twisted cube that the number of nodes with the same diameter and node degree is (2^2m)/(f_3m+2)≅0.85(0.94) ^m. And its diameter and maximum node degree are both 2m, that is two-thirds of a comparable Fibonacci cube with f_3m+2 processing nodes. The FC(f_3m+2,3) has a simple routing algorithm, and a Fibonacci tree as a spanning tree

Keywords

multiprocessor interconnection networks; network routing; parallel architectures; trees (mathematics); Fibonacci circulants; Fibonacci cube; Fibonacci number; Fibonacci tree; Hamiltonian cycle; interconnection network; interconnection topology; large scale parallel processing systems; maximum node degree; processing nodes; routing algorithm; spanning tree; vertex transitive; Communication system control; Computer science; Control systems; Drives; Hypercubes; Ink; Large-scale systems; Parallel processing; Routing; Topology;

fLanguage

English

Publisher

ieee

Conference_Titel

TENCON 99. Proceedings of the IEEE Region 10 Conference

Conference_Location

Cheju Island

Print_ISBN

0-7803-5739-6

Type

conf

DOI

10.1109/TENCON.1999.818449

Filename

818449