Abstract
We investigate the problem of designing reconfigurable embedding schemes for a fixed hypercube (without redundant processors and links). The fundamental idea for these schemes is to embed a basic network on the hypercube without fully utilizing the nodes on the hypercube. The remaining nodes can be used as spares to reconfigure the embeddings in case of faults. The result of this research shows that by carefully embedding the application graphs, the topological properties of the embedding can be preserved under fault conditions, and reconfiguration can be carried out efficiently.
In this dissertation, we choose the ring as the basic network of interest, and propose several schemes for the design of reconfigurable embeddings with the aim of minimizing reconfiguration cost and performance degradation. The cost is measured by the number of node-state changes or reconfiguration steps needed for processing of the reconfiguration, and the performance degradation is characterized as the dilation of the new embedding after reconfiguration. Compared to the existing schemes, our schemes surpass the existing ones in terms of applicability of schemes and reconfiguration cost needed for the resulting embeddings.
Recommended Citation
Liu, Jun-Lin and McMillin, Bruce M., "Fault-Tolerant Ring Embeddings in Hypercubes -- A Reconfigurable Approach" (1993). Computer Science Technical Reports. 60.
https://scholarsmine.mst.edu/comsci_techreports/60
Department(s)
Computer Science
Report Number
CSc-93-32
Document Type
Article - Journal
Document Version
Final Version
File Type
text
Language(s)
English
Rights
© 1993 University of Missouri--Rolla, All rights reserved.
Publication Date
December 1993
Comments
This report is substantially the Ph.D. dissertation of the first author, completed December 1993