Run-Time error detection in arrays based on the data-dependency graph

This paper describes a methodology based on dependency graphs for doing concurrent run-Time error detection in systolic arrays and wavefront processors. It combines the projection method of deriving systolic arrays from dependency graphs with the idea of input-Triggered test-ing. We call the method ITRED, for Input-driven Time-Redundancy Error Detection. Tests arc triggered by inserting special symbols in the input, and so the approach gives the user flexibility in trading off throughput for error coverage. Correctness of timing is proved at the dependency graph level. The method requires no extra PE's and little extra hardware. We present the general approach and derive corresponding constraints on the modified dependency graphs that guarantee correctness.