Counting the number of fault patterns in redundant VLSI arrays.pdfVIP

Counting the Numb er of Fault Patterns in Redundant VLSI Arrays Linda PA GLI y and Geppino PUCCI z Abstract In VLSI technology redundancy is a commonly adopted technique to provide reconguration capabilities to regular architectures This pap er proves upp er and lower b ounds on the numb er of minimal fault patterns minimal set of faulty pro cessors which aect a link redundant linear array in an unrepairable way for b oth the cases of bidirectional and unidirectional links Keywords Distributed Systems Fault Tolerance Parallel Pro cessing Performance Evaluation Preliminaries A standard technique to lower the pro duction costs of VLSI circuits is the provision of onchip redundancy and accompanying mechanisms to recongure the chip comp onents at the o ccurrence of fabrication faults Without the presence of reconguration capabilities the yield of very large VLSI chips would b e so p o or to make their pro duction unacceptable In the case of linear arrays of identical Processing Elements PEs redundant ones called spares are often placed on the chip to replace faulty PEs and therefore preserve the network connectivity Besides the regular links b etween neighb oring PEs extra links called bypass links are also included to recreate the array top ology in the reconguration phase However regardless of any amount of redundancy and conguration capabilities there are always sets of faults o ccurring at strategic p ositions which aect the chip in an unrepairable way Such sets of faults called Catastrophic Fault Patterns CFPs have b een extensively studied in for linear arrays with dierent varieties of link redundancy In this pap er we provide upp er and lower b ounds on the numb er of CFPs