On the design of optimal fault - Tolerant systolic array architectures

In this paper we present a novel approach for designing highly reliable and optimal fault - tolerant systolic array architectures. In our approach, fault - tolerant algorithms are designed by introducing redundant computations at the algorithmic level, so that when these algorithms are mapped into specific VLSI systolic array architectures, the architectures will be inherently fault - tolerant. We introduce redundant computations in the original algorithm by creating different versions of the algorithm. The respective dependency matrix (D) of the different versions of the algorithm are obtained and these are merged to give one dependency matrix that reflects a given fault - tolerant requirement. This resultant dependency matrix is mapped into an optimal fault - tolerant systolic array using our proposed Space - Time (S-T) systematic approach for mapping algorithms into optimal systolic architectures.