AREA-EFFICIENT COMPUTING STRUCTURES FOR CONCURRENT ERROR-DETECTION INSYSTOLIC ARRAYS

A method of designing testable systolic architectures is proposed in t his paper. Testing systolic arrays involves mapping of an algorithm in to a specific VLSI systolic architecture, and then modifying the desig n to achieve concurrent testing. In our approach, redundant computatio ns are introduced at the algorithmic level by deriving two versions of a given algorithm. The transformed dependency matrix (TDM) of the fir st version is a valid transformation matrix while the second version i s obtained by rotating the first TDM by 180 degrees about any of the i ndices that represent the spatial component of the TDM. Concurrent err or detection (CED) systolic array is constructed by merging the corres ponding systolic array of the two versions of the algorithm. The mergi ng method attempts to obtain the self testing systolic array at minima l cost in terms of area and speed. It is based on rescheduling input d ata, rearranging data flow, and increasing the utilization of the arra y cells. The resulting design can detect all single permanent and temp orary faults and the majority of the multiple fault patterns with high probability. The design method is applied to an algorithm for matrix multiplication in order to demonstrate the generality and novelty of o ur approach to design testable VLSI systolic architectures.