Gracefully degradable pipeline networks

Author

Cypher, Robert ; Laing, Ambrose K.

Author_Institution

Dept. of Comput. Sci., Johns Hopkins Univ., Baltimore, MD, USA

fYear

1997

fDate

1-5 Apr 1997

Firstpage

55

Lastpage

64

Abstract

A pipeline is a linear array of processors with an input node at one end and an output node at the other end. This paper presents k-gracefully-degradable graphs which, given any set of up to k faults, contain a pipeline that uses all the healthy processor nodes. Our constructions are designed to tolerate faulty input and output nodes, but they can be adapted to provide solutions when the input and output nodes are guaranteed to be healthy. All of our constructions are optimal in terms of the number of nodes and the maximum degree of the processor nodes

Keywords

fault tolerant computing; graph theory; multiprocessor interconnection networks; faulty input nodes; faulty output nodes; gracefully degradable pipeline networks; input node; k-gracefully-degradable graphs; linear array of processors; processor nodes; Circuit faults; Computed tomography; Computer science; Degradation; Digital communication; Fault tolerance; Finite impulse response filter; IIR filters; Multiprocessor interconnection networks; Pipelines;

fLanguage

English

Publisher

ieee

Conference_Titel

Parallel Processing Symposium, 1997. Proceedings., 11th International

Conference_Location

Genva

ISSN

1063-7133

Print_ISBN

0-8186-7793-7

Type

conf

DOI

10.1109/IPPS.1997.580847

Filename

580847