Algorithms and models for distributed test generation
J. Sienicki · 1996
Combinational circuit test generation is an NP-complete problem. The presence of memory elements make sequential circuit test generation even more difficult. Sequential test vectors must be applied in the order of generation, so distributed processes cannot share vectors. The order in which faults are targeted for test generation greatly affects the test generator efficiency. This is because a fault may have to propagate through memory elements before reaching a primary circuit output. The number of test vectors needed to propagate the fault depends on the state of the machine when the test is applied. This work presents several new distributed algorithms for sequential circuit automatic test generation based on AT&T's Gentest test generator. All algorithms run on a workstations network using a fault partitioning strategy. Processor target faults in their own partition for test generation, but perform fault simulation on all faults. Detected faults are shared among processors. The algorithms presented here differ from normal fault parallel by using a parallelization strategy called state space parallelism. Faults that are undetected on one processor are tried on a different process, whose current state may be more amenable to test generation for that fault. Two types of communication strategies are investigated: synchronous and asynchronous. The synchronous algorithms require all processors to finish processing their faults before communication takes place causing faster processors to wait for slower ones. The asynchronous algorithms do not require faster processors to wait for slower ones by broadcasting detected faults as soon as they are detected. Mathematical models, simulations, and experimental results show that several methods of parallelism produces superlinear speedups in several benchmark circuits, and near-linear speedups in most others. Results are also presented for methods to reduce the number of test vectors generated, as well as increase the efficiency of processor usage.