Orthogonal fault-tolerant systolic arrays for matrix multiplication

A systematic approach for designing one class of fault-tolerant systolic arrays (FTSAs) with orthogonal interconnects and unidirectional data flow, Orthogonal Unidirectional Systolic Array (OUSA), for multiplication of rectangular matrices is presented in this paper. The method employs space-time redundancy to achieve fault-tolerance. By conducting proposed systematic design procedure, four different systolic arrays of OUSA type are obtained. All the arrays can tolerate single transient errors and majority of multiple errors with high probability. In order to provide high bandwidth in data access, a special hardware called address generator unit, was designed. Hardware complexity and performance gains achieved at higher (system, algorithm and architecture) design levels were analyzed. The obtained results show that with n2 + 2n processing elements the total execution time of the fault-tolerant algorithm is 6n + 3 time units, the hardware overhead due to involving fault-tolerance is in the range from 6.25% down to 0.8%, while time overhead is 50%. In addition, by involving hardware implemented address generation unit we reduce the total execution time of the algorithm almost five times, compared to software address calculations.