Fault detection in multiprocessor systems and array processors

Off-line testing of large multiprocessor networks or VLSI chips with many outputs requires a large volume of memory for reference data storage. Space compaction combined with time compression of test responses can essentially reduce an overhead required for testing and diagnosis. In this paper, we discuss the problem of optimal design for space compressors (compactors), to minimize the number of observation points for detection of single faulty components in multiprocessor networks. A space compactor is assumed to be followed by a time compressor, to detect a fault not necessarily manifesting itself for a single test pattern. We formulate the rules of design for a space compaction matrix for the topology of the circuit-under-test (CUT) modeled by an arbitrary acyclic graph. Tree arrays and Fourier transform networks are considered as examples. The lower and upper bounds on the number of space compactor outputs are obtained, and optimal space compaction matrices are determined for above mentioned CUT topologies. Simple procedures for design of off-line testing devices with built-in self-testing are presented. Estimations on a complexity of proposed designs are given