EFFICIENT CONSTRUCTION OF CATASTROPHIC PATTERNS FOR VLSI RECONFIGURABLE ARRAYS

Patterns of faults occurring at strategic locations may render an enti re VLSI system unusable regardless of its component redundancy and of its reconfiguration capabilities. The characterization of such pattern s is obviously crucial for the identification, testing and detection o f catastrophic events. The fault patterns that are catastrophic for re gular architectures, particularly the systolic arrays, have been exten sively studied. For a given link configuration, there are many fault p atterns which are catastrophic. Among those, there is a particular fau lt pattern, called the reference fault pattern, which is crucial for t he development of testing techniques; furthermore, the efficiency of a ny testing algorithm can be further improved in the presence of effici ent algorithms for constructing the reference fault pattern. In this p aper, we establish several new properties of catastrophic fault patter ns; based on these properties, as well as the existing ones, we develo p a new algorithm for the construction of the reference fault pattern. The complexity of the new algorithm is O(kg) which is a significant i mprovement over the existing O(g2) algorithm, where k is the number of bypass links, and g is the length of the largest bypass link.