FAULT-TOLERANT DESIGN METHODOLOGY FOR SYSTOLIC ARRAY ARCHITECTURES

A systematic approach to the design of fault-tolerant VLSI systolic ar rays is proposed. The approach comprises three steps. First, redundanc ies are introduced at the computation level by deriving different vers ions of the computation structure. This involves the modification of t he dependency matrix (D) of an algorithm to reflect a given fault-tole rance requirement. Second, the dependency matrix of the respective ver sion is mapped into arbitrarily large size VLSI systolic arrays, using space-time (S-T) mapping techniques. Finally, a fault-tolerant (FT) s ystolic array is constructed by merging the corresponding systolic arr ay of the different versions of the computation. The scheme is applica ble to any systolic array implementation and suitable for VLSI technol ogy. The method is illustrated using the matrix multiplication algorit hm.