Quick links

Error Detection in Arrays Via Dependency Graphs

Report ID:
July 1991
Download Formats:


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
testing. We call the method ITRED, for Input-driven Time-Redundancy
Error Detection. Tests are 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 propose several variations of the general
approach and derive corresponding constraints on the modified
dependency graphs that guarantee correctness. One variation performs
run-time error correction using majority voting. Examples are given,
including a dynamic programming algorithm, convolution, and matrix

This technical report has been published as
Error Detection in Arrays via Dependency Graphs. Edwin Hsing-Mean
Sha and Kenneth Steiglitz, J. VLSI Signal
, 4(7), pp. 854-862, July 1993.
Follow us: Facebook Twitter Linkedin