A parallel branch and bound algorithm for test generation

For circuits of VLSI complexity, test generation time can be prohibitive. Most of the time is consumed by hard-to-detect (HTD) faults, which might remain undetected even after a large number of backtracks. The problems inherent in a uniprocessor implementation of a test generation algorithm are identified, and a parallel test generation method which tries to achieve a high fault coverage for HTD faults in a reasonable amount of time is proposed. A dynamic search space allocation strategy which allocates disjoint search spaces to minimize the redundant work is proposed. The search space allocation strategy tries to utilize the partial solutions generated by other processors to increase the probability of searching in a solution area. The parallel test generation algorithm has been implemented on an Intel iPSC/2 hypercube. It is shown that parallel processing of HTD faults does indeed result in high fault coverage, which is otherwise not achievable by a uniprocessor algorithm. The parallel algorithm exhibits superlinear speedups in some cases due to search anomalies