Efficient construction of catastrophic patterns for VLSI reconfigurable arrays with bidirectional links

Patterns of faults that are catastrophic for regular architectures, particularly the systolic arrays, have been studied. For a given link configuration, there are many fault patterns which are catastrophic. Among those, there is a particular fault pattern, called the reference fault pattern, which is crucial for the development of testing techniques; furthermore, the efficiency of any testing algorithm can be further improved in the presence of efficient algorithms for constructing the reference fault pattern. The authors develop a new algorithm for the construction of the reference fault pattern for VLSI reconfigurable arrays in which the links are bidirectional. The complexity of the new algorithm is O(kN) which is a significant improvement over the existing O(N² ) algorithm, where k is the number of bypass links, and N is the length of the largest bypass link