DocumentCode :
450625
Title :
A Parallel Branch and Bound Algorithm for Test Generation
Author :
Patil, Srinivas ; Banerjee, Prith
Author_Institution :
Computer Systems Group, Coordinated Science Laboratory, University of Illinois at Urbana-Champaign, Urbana, IL
fYear :
1989
fDate :
25-29 June 1989
Firstpage :
339
Lastpage :
344
Abstract :
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. We identify the problems inherent in a uniprocessor implementation of a test generation algorithm and propose a parallel test generation algorithm which tries to achieve a high fault coverage for HTD faults in a reasonable amount of time. A dynamic search space allocation strategy is used which ensures that the search spaces allocated to different processors are disjoint. The parallel test generation algorithm has been implemented on an Intel iPSC/2 hypercube. Results are presented using the ISCAS combinational benchmark circuits which conclusively prove that parallel processing of HTD faults does indeed result in high fault coverage which is otherwise not achievable by a uniprocessor algorithm in limited CPU time. The parallel algorithm exhibits superlinear speedups in some cases due to search anomalies.
Keywords :
Benchmark testing; Circuit faults; Circuit simulation; Circuit testing; Hypercubes; Logic circuits; Parallel algorithms; Parallel processing; Permission; Very large scale integration;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Design Automation, 1989. 26th Conference on
ISSN :
0738-100X
Print_ISBN :
0-89791-310-8
Type :
conf
DOI :
10.1109/DAC.1989.203420
Filename :
1586404
Link To Document :
بازگشت