You are here

FAU Collections » FAU Research Repository » FAU Theses and Dissertations

Analysis of a novel class of fault-tolerant multistage interconnection networks

Download pdf | Full Screen View

Date Issued:
1993
Summary:
Multistage interconnection networks (MINs) have become an important subset of the interconnection networks which are used to communicate between processors and memory modules for large scale multiprocessor systems. Unfortunately, unique path MINs lack fault tolerance. In this dissertation, a novel scheme for constructing fault-tolerant MINs is presented. We first partition the given MINs into even sized partitions and show some fault-tolerant properties of the partitioned MINs. Using three stages of multiplexers/demultiplexers, an augmenting scheme which takes advantage of locality in program execution is then proposed to further improve the fault-tolerant ability and performance of the partitioned MINs. The topological characteristics of augmented partitioned multistage interconnection networks (APMINs) are analyzed. Based on switch fault model, simulations have been carried out to evaluate the full access and dynamic full access capabilities of APMINs. The results show that the proposed scheme significantly improves the fault-tolerant capability of MINs. Cost effectiveness of this new scheme in terms of cost, full access, dynamic full access, locality, and average path length has also been evaluated. It has been shown that this new scheme is more cost effective for high switch failure rate and/or large size networks. Analytical modeling techniques have been developed to evaluate the performance of AP-Omega network and AP-Omega network-based multiprocessor systems. The performance of Omega, modified Omega, and AP-Omega networks in terms of processor utilization and processor waiting time have been compared and the results show that the new scheme indeed, improves the performance both in network level and in system level. Finally, based on the reliability of serial/parallel network components, models for evaluating the terminal reliability and the network reliability of AP-Omega network using upper and lower bound measures have also been proposed and the results show that applying locality improve APMINs' reliability.
Title: Analysis of a novel class of fault-tolerant multistage interconnection networks.
89 views
24 downloads
Name(s): Huang, Chien-Jen
Florida Atlantic University, Degree grantor
Mahgoub, Imad, Thesis advisor
College of Engineering and Computer Science
Department of Computer and Electrical Engineering and Computer Science
Type of Resource: text
Genre: Electronic Thesis Or Dissertation
Date Issued: 1993
Publisher: Florida Atlantic University
Place of Publication: Boca Raton, Fla.
Physical Form: application/pdf
Extent: 127 p.
Language(s): English
Summary: Multistage interconnection networks (MINs) have become an important subset of the interconnection networks which are used to communicate between processors and memory modules for large scale multiprocessor systems. Unfortunately, unique path MINs lack fault tolerance. In this dissertation, a novel scheme for constructing fault-tolerant MINs is presented. We first partition the given MINs into even sized partitions and show some fault-tolerant properties of the partitioned MINs. Using three stages of multiplexers/demultiplexers, an augmenting scheme which takes advantage of locality in program execution is then proposed to further improve the fault-tolerant ability and performance of the partitioned MINs. The topological characteristics of augmented partitioned multistage interconnection networks (APMINs) are analyzed. Based on switch fault model, simulations have been carried out to evaluate the full access and dynamic full access capabilities of APMINs. The results show that the proposed scheme significantly improves the fault-tolerant capability of MINs. Cost effectiveness of this new scheme in terms of cost, full access, dynamic full access, locality, and average path length has also been evaluated. It has been shown that this new scheme is more cost effective for high switch failure rate and/or large size networks. Analytical modeling techniques have been developed to evaluate the performance of AP-Omega network and AP-Omega network-based multiprocessor systems. The performance of Omega, modified Omega, and AP-Omega networks in terms of processor utilization and processor waiting time have been compared and the results show that the new scheme indeed, improves the performance both in network level and in system level. Finally, based on the reliability of serial/parallel network components, models for evaluating the terminal reliability and the network reliability of AP-Omega network using upper and lower bound measures have also been proposed and the results show that applying locality improve APMINs' reliability.
Identifier: 12345 (digitool), FADT12345 (IID), fau:9247 (fedora)
Collection: FAU Electronic Theses and Dissertations Collection
Note(s): College of Engineering and Computer Science
Thesis (Ph.D.)--Florida Atlantic University, 1993.
Subject(s): Integratged circuits--Very large scale integration
Fault-tolerant computing
Computer architecture
Parallel processing (Electronic computers)
Held by: Florida Atlantic University Libraries
Persistent Link to This Record: http://purl.flvc.org/fcla/dt/12345
Sublocation: Digital Library
Use and Reproduction: Copyright © is held by the author, with permission granted to Florida Atlantic University to digitize, archive and distribute this item for non-profit research and educational purposes. Any reuse of this item in excess of fair use or other copyright exemptions requires permission of the copyright holder.
Use and Reproduction: http://rightsstatements.org/vocab/InC/1.0/
Host Institution: FAU
Is Part of Series: Florida Atlantic University Digital Library Collections.