Fault-tolerant ring embeddings in hypercubes -- A reconfigurable approach

Author

Jun-Lin Liu

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"--Abstract, page iii.

Advisor(s)

McMillin, Bruce M.

Committee Member(s)

Dekock, Arlan R.
Ho, C. Y. (Chung You), 1933-1988
Sager, Thomas J.
Randolph, Timothy W.

Department(s)

Computer Science

Degree Name

Ph. D. in Computer Science

Comments

A report which is substantially this dissertation is available here for download.

Publisher

University of Missouri--Rolla

Publication Date

Fall 1993

Pagination

xii, 117 pages

Note about bibliography

Includes bibliographical references (pages 108-116).

Rights

© 1993 Jun-Lin Liu, All rights reserved.

Document Type

Dissertation - Restricted Access

File Type

text

Language

English

Thesis Number

T 6657

Print OCLC #

31067150

Recommended Citation

Liu, Jun-Lin, "Fault-tolerant ring embeddings in hypercubes -- A reconfigurable approach" (1993). Doctoral Dissertations. 914.
https://scholarsmine.mst.edu/doctoral_dissertations/914