DocumentCode :
806778
Title :
Algorithms and properties of a new two-level network with folded hypercubes as basic modules
Author :
Duh, Dyi-Rong ; Chen, Gen-Huey ; Fang, Jywe-Fei
Author_Institution :
Dept. of Electron. Eng., Hwa Shia Junior Coll., Taipei, Taiwan
Volume :
6
Issue :
7
fYear :
1995
fDate :
7/1/1995 12:00:00 AM
Firstpage :
714
Lastpage :
723
Abstract :
In this paper, a new two-level interconnection network, called a hierarchical folded-hypercube network (HFN, for short), is proposed. The HFN takes folded hypercubes as basic modules which are connected in a complete manner. We investigate the topological properties of the HFN, including the diameter, cost, average distance, embedding, connectivity, container, κ-wide diameter, and node-fault diameter. We show that the HFN can emulate algorithms which are executable on the ring or the mesh-connected computer with the same time complexities in big-O notation. Moreover, the HFN can embed a folded hypercube having the same number of nodes with constant dilation. We compute the diameter, node connectivity, best container, κ-wide diameter, and node-fault diameter of the HFN. We present optimal routing and broadcasting algorithms for the HFN. The semigroup computation and descend/ascend algorithms can be executed as well on the HFN
Keywords :
computational complexity; fault tolerant computing; hypercube networks; broadcasting algorithms; connectivity; descend/ascend algorithms; embedding; folded hypercubes; hierarchical folded-hypercube network; node connectivity; node-fault diameter; optimal routing; time complexities; topological properties; two-level interconnection network; two-level network; Broadcasting; Computer architecture; Computer science; Containers; Costs; Hypercubes; Integrated circuit interconnections; Multiprocessing systems; Routing; Topology;
fLanguage :
English
Journal_Title :
Parallel and Distributed Systems, IEEE Transactions on
Publisher :
ieee
ISSN :
1045-9219
Type :
jour
DOI :
10.1109/71.395400
Filename :
395400
Link To Document :
بازگشت