An efficient reconfiguration algorithm for degradable VLSI/WSI arrays

This paper considers the problem of reconfiguring two-dimensional degradable VLSI/WSI arrays under the constraint of row and column rerouting. The goal of the reconfiguration problem is to derive a fault-free subarray T from the defective host array such that the dimensions of T are larger than some...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on computers 2000-06, Vol.49 (6), p.553-559
Main Author: Low, Chor Ping
Format: Article
Language:English
Subjects:
Algorithm design and analysis
Algorithms
Arrays
Circuit faults
Degradation
Fault tolerance
Greedy algorithms
Heuristic algorithms
Integrated circuits
Logic arrays
Optimization
Reconfiguration
Routing
Switches
Switching
Very large scale integration
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This paper considers the problem of reconfiguring two-dimensional degradable VLSI/WSI arrays under the constraint of row and column rerouting. The goal of the reconfiguration problem is to derive a fault-free subarray T from the defective host array such that the dimensions of T are larger than some specified minimum. This problem has been shown to be NP-complete under various switching and routing constraints. However, we show that a special case of the reconfiguration problem is optimally solvable in linear time. Using this result, a new fast and efficient reconfiguration algorithm is proposed. Empirical study shows that the new algorithm indeed produces good results in terms of the percentages of harvest and degradation of VLSI/WSI arrays.
ISSN:0018-9340
1557-9956
DOI:10.1109/12.862215