Paper Info
Title
Testing and reconfiguration of VLSI linear arrays
Abstract
Achieving fault tolerance through incorporation of redundancy and reconfiguration is quite common. In this paper we study the fault tolerance of linear arrays of N processors with k bypass links whose maximum length is g . We consider both arrays with bidirectional links and unidirectional links. We first consider the problem of testing whether a set of n faulty processors is catastrophic, i.e., precludes reconfiguration. We provide new testing algorithms which improve and generalize known testing algorithms. For bidirectional arrays we provide an O ( kn ) time testing algorithm and for unidirectional arrays we provide an O ( n ) time algorithm for the case k = 1, and an O ( kn log k ) time algorithm, for the case k 1. When the fault pattern is not catastrophic we study the problem of finding an optimal reconfiguration of the array. We consider optimality with respect to two parameters: the size of the reconfigured array and the number of redundant links to activate. Considering optimality with respect to the size of the reconfigured array, we prove that the problem is NP-hard in the strong sense if the bypass links are bidirectional, while it can be solved in O ( kng ) time if the bypass links are unidirectional. Considering optimality with respect to the number of bypass links to activate, we prove that the problem can be solved in O ( kn ) time if the bypass links are bidirectional, and in O ( kng ) time if the bypass links are unidirectional.
Year
DOI
Venue
1998
10.1016/S0304-3975(97)00238-7
Theor. Comput. Sci.
Keywords
DocType
Volume
VLSI linear array,Array processors,Catastrophic fault patterns,Reconfiguration algorithms,Fault tolerance,Fault detection
Journal
197
Issue
ISSN
Citations 
1-2
Theoretical Computer Science
9
PageRank 
References 
Authors
1.36
13
3
Name
Order
Citations
PageRank
Roberto De Prisco157455.43
Angelo Monti267146.93
Linda Pagli340147.56