Title :
A gracefully degradable VLSI system for linear programming
Author :
Bertossi, Alan A. ; Bonuccelli, Maurizio A.
Author_Institution :
Dept. of Comput. Sci., Pisa Univ., Italy
fDate :
6/1/1989 12:00:00 AM
Abstract :
The use of a fault-tolerant VLSI system for storing and solving linear programming problems is presented. The system can bear multiple faults in processing elements and/or links and still function with an acceptable performance degradation. It is based on an interconnection pattern consisting of a complete binary tree in which spare links between cousin nodes are added so as to reconfigure it as a ternary tree. At any given time of a computation, faulty processing elements and/or links are circumvented by using such spare links. It is shown that the total silicon area required by this structure is only a constant factor higher than that of a complete binary tree. The result is used to give an efficient implementation of the simplex algorithm in which the time required to perform a single pivot step matches a previously established lower bound for tree machines in spite of faults
Keywords :
VLSI; computational complexity; fault tolerant computing; linear programming; complete binary tree; cousin nodes; fault-tolerant VLSI system; faulty processing elements; gracefully degradable; interconnection pattern; linear programming problems; multiple faults; simplex algorithm; ternary tree; Binary trees; Costs; Degradation; Fault tolerance; Linear programming; Production; Silicon; Systolic arrays; Vectors; Very large scale integration;
Journal_Title :
Computers, IEEE Transactions on