Mapping nested loop algorithms into fault-tolerant systolic array architectures

Progress in VLSI and WSI technologies has resulted in the manufacture of special purpose VLSI chips with multiple copies of low-cost processors. These processors can be used to design high performance systems such as systolic arrays. This paper proposes a new systematic approach which can be used to detect and correct errors in systolic array architectures. The approach relies on Space-Time mapping of algorithms into systolic arrays. Fault-tolerant algorithms are designed by introducing redundant computations at the algorithmic level. This is done by deriving several versions of a given algorithm, each of which can be mapped into respective systolic architecture. Fault-tolerant systolic array is constructed by merging the corresponding systolic array of several versions of the algorithm.