Carleton University
Technical Report TR-204
March 1992
Recognition of Catastrophic Faults in Reconfigurable Arrays with Arbitrary Link Redundancy
Abstract
Fault tolerance through the incorporation of redundancy and reconfiguration is quite common. The distribution of faults can have severe impact on the effectiveness of any reconfiguration scheme; in fact, patterns of faults occurring at strategic locations may render an entire system unusable regardless of its component redundancy and of its reconfiguration capabilities. The characterization of such patterns is crucial for the identification and detection of such catastrophic events. A complete characterization was given for reconfigurable systolic arrays with 2-link redundancy; i.e., a bypass link of fixed length is provided to each element of the array in addition to the regular link. In this paper, we study the more general case of arbitrary (but regular) link redundancy. In particular, we focus on the problem of deciding whether a pattern of k faults is catastrophic for a k-link redundant system; i.e., in addition to the regular link of length g1 = 1, each element of the array is provided with k-1 bypass links of length. g2, g3, … , 9k, respectively.
We study this problem and prove some fundamental properties which any catastrophic fault pattern must satisfy. We then show that these properties together constitute a necessary and sufficient condition for a fault pattern to be catastrophic for k-link redundant system. As a consequence, we derive a provably correct recognition algorithm whose worse-case time complexity is O(kgk)i this also improves on the previous algorithm for k = 2.