Gracefully Degradable Processor Arrays
- 1 November 1985
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-34 (11) , 1033-1044
- https://doi.org/10.1109/tc.1985.1676536
Abstract
A new approach to the design of gracefully degradable processor arrays is discussed. Fault tolerance and graceful degradation are achieved by simultaneously reconfiguring the processor array and the algorithm in execution. Two types of algorithm reconfigurability are considered, namely, row reconfigurability (RR) and row-column reconfigurability (RCR). correspondingly, two array reconfiguration schemes are discussed, i.e., successive row elimination (SRE) and alternate row-column elimination (ARCE). It is shown that the computations of any algorithm executable in a processor array can always be (re) organized so that the resultant algorithm has the RR and/or RCR properties. Upper bounds on the increase in execution time of an algorithm due to reorganization of computations for reconfigurability are derived. Detailed analysis of performance and reliability is done for both SRE and ARCE reconfiguration schemes. These reconfiguration techniques are applicable to any processor array and suitable for VLSI technology.Keywords
This publication has 13 references indexed in Scilit:
- Parallelism detection and transformation techniques useful for VLSI algorithmsJournal of Parallel and Distributed Computing, 1985
- Wafer-scale integration and two-level pipelined implementations of systolic arraysJournal of Parallel and Distributed Computing, 1984
- The Diogenes Approach to Testable Fault-Tolerant Arrays of ProcessorsIEEE Transactions on Computers, 1983
- On the Analysis and Synthesis of VLSI AlgorithmsIEEE Transactions on Computers, 1982
- Wavefront Array Processor: Language, Architecture, and ApplicationsIEEE Transactions on Computers, 1982
- Fault-Tolerant Design for VLSI: Effect of Interconnect Requirements on Yield Improvement of VLSI DesignsIEEE Transactions on Computers, 1982
- Fault-tolerant wafer-scale architectures for VLSIACM SIGARCH Computer Architecture News, 1982
- Introduction to the configurable, highly parallel computerComputer, 1982
- Design of a Massively Parallel ProcessorIEEE Transactions on Computers, 1980
- A Graph Model for Fault-Tolerant Computing SystemsIEEE Transactions on Computers, 1976