Published Articles >> Table of Contents >> Abstract

Ninth International Conference on Parallel and Distributed Systems (ICPADS'02)   p. 11
TCN: Scalable Hierarchical Hypercubes
Trong-Yen Lee, National Taipei University of Technology
Pao-Ann Hsiung, National Chung Cheng University
Sao-Jie Chen, National Taiwan University

Full Article Text:

DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ICPADS.2002.1183371
Send link to a friend

Abstract
Hierarchical hypercubes, such as Extended Hypercube (EH), Hyperweave (HW), and Extended Hypercube with Cross Connections (EHC), have been proposed to overcome the scalability limitation of conventional hypercubes through the use of fixed dimension hypercubes of processing elements (PEs) as basic modules interconnected by network controllers (NC) which are themselves interconnected into hypercubes. The scalability of all these three hierarchical hypercube networks is still limited, because the average network communication load in each NC increases as the number of interconnected PEs become very large. In this work, a generalization scheme is proposed for improving network scalability, namely Transformer Cube Network (TCN). For illustration purpose, generalized TCN is presented only for EH, though the same scheme can be applied to HW and EHC as well. Several characteristics of TCN, such as topological properties, message routing complexity, fault tolerance, and scalability are analyzed. We present a communication algorithm for one-to-one message passing in a fault-free case. Further, the application of TCN to a class of divide-and-conquer problems is shown to have a time complexity of O(log2N), where N is the total number of PEs.
Back to Top Additional Information
Citation:  Trong-Yen Lee, Pao-Ann Hsiung, Sao-Jie Chen, "TCN: Scalable Hierarchical Hypercubes," icpads, p. 11,  Ninth International Conference on Parallel and Distributed Systems (ICPADS'02),  2002