Title :
Fibonacci circulants-a new interconnection topology
Author_Institution :
Coll. of Natural Sci., Seonam Univ., Chonbuk, South Korea
Abstract :
The paper proposes a novel interconnection network called Fibonacci circulants for large scale parallel processing systems. The FC(f3m+2,3) is a regular and vertex transitive (not edge transitive), and has a Hamiltonian cycle. It connects the (3m+2)-th Fibonacci number, f3m+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 (22m)/(f3m+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 f3m+2 processing nodes. The FC(f3m+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;
Conference_Titel :
TENCON 99. Proceedings of the IEEE Region 10 Conference
Conference_Location :
Cheju Island
Print_ISBN :
0-7803-5739-6
DOI :
10.1109/TENCON.1999.818449
