Reconfiguration algorithm for fault-tolerant arrays with minimum number of dangerous processors

Author

Chen, C. ; Feng, A. ; Kikuno, T. ; Torii, K.

Author_Institution

Dept. of Inf. & Comput. Sci., Osaka Univ., Japan

fYear

1991

fDate

25-27 June 1991

Firstpage

452

Lastpage

459

Abstract

An algorithm for a reconfiguration problem (called the SPA problem) for n*n ordinary processors using spare processors is presented. The SPA problem is to find an assignment of spare processors to faulty processors that minimizes the number of dangerous processors. Here, dangerous processors are nonfaulty processors for which there remains no spare processor to be assigned if one more fault occurs. An O(n/sup 2/) algorithm is developed for a basic SPA problem where 2n spare processors are provided. An extension of the SPA problem is defined, and several interesting properties are clarified in order to solve it. In the extension, the spare processors ae assumed to become faulty.<>

Keywords

computer architecture; fault tolerant computing; systolic arrays; SPA problem; assignment; fault-tolerant arrays; minimum number of dangerous processors; reconfiguration algorithm; reconfiguration problem; spare processors; systolic arrays; Computer architecture; Digital systems; Fault detection; Fault tolerance; Fault tolerant systems; Hypercubes; Real time systems; Sufficient conditions;

fLanguage

English

Publisher

ieee

Conference_Titel

Fault-Tolerant Computing, 1991. FTCS-21. Digest of Papers., Twenty-First International Symposium

Conference_Location

Montreal, Quebec, Canada

Print_ISBN

0-8186-2150-8

Type

conf

DOI

10.1109/FTCS.1991.146700

Filename

146700