Article

Free access

A parallel branch and bound algorithm for test generation

Authors:

P. BanerjeeAuthors Info & Claims

DAC '89: Proceedings of the 26th ACM/IEEE Design Automation Conference

Pages 339 - 343

https://doi.org/10.1145/74382.74439

Published: 01 June 1989 Publication History

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.

References

[1]

H. Fujiwara and S. Toida, "The Complexity of Fault Detection: Art Approach to Design for Testability," Proc. 12th Ira. Syrup. Fault Tolerant Computing, pp. 101-108, June 1982.

[2]

J.P. Roth, "Diagnosis of Automata Failures: A Calculus and a Method," IBM J. Res. Develop., vol. 10, pp. 278- 291, luly 1966.

Digital Library

[3]

P. Goel, "An Implicit Enurneradon Algorithm to Generate Tests for Combinational Logic Circuits," IEEE Trans. on Comp., vol. C-30, pp. 215-222, March 1981.

[4]

H. Fujiwara and T. Shimono, "On the Acceleration of Test Generation Algorithms," IEEE Trans. on Comp., vol. C-32, pp. 1137-1144, December 1983.

[5]

K.T. Cheng and V. D. Agrawal, "A Simulation-based Directed Search Method for Test Generation," Proc. lnt. Conf. Comp. Design (ICCD-87), pp. 48-51, October 1987.

[6]

A. Motohara, K. Nishimura, H. Fujiwara, and I. Shirakawa, "A Parallel Scheme for Test-pattern Generation," Proc. int. Conf. on CAD (1CCAD-86), pp. 156-159, November 1986.

[7]

G.A. Kramer, "Employing Massive Parallelism in Digital ATPG Algorithms," Proc. of the 1983 Int. Test Conf., pp. 108-114.

[8]

V.N. Rao and V. Kumar, "Parallel Depth First Search, Part I: Implementation," International Journal of Parallel Programming, vol. 16, 1987.

Digital Library

[9]

S. L Chandra and J. H. Pate|, "Experimental Evaluation of Testability Measures for Test Generation," IEEE Trans. on CAD, vol. 8, pp. 93-98, January 1989.

Digital Library

[10]

S.J. Chandra and }'. H. Patel, "Test Generation in a Parallel Processing Environment," Proc. IEEE Int. Conf. on Computer Design (ICCD-88), October 1988.

[11]

J.S. Conery, "The AND/OR Process Model for Parallel interpretation of Logic Programs," Technical Report 204, Un&ersity of California. Irvine, June 1983.

[12]

B.W. Watt, G. J. Li, and C, F. Yu, "Mulfiprocessing of Combinatorial Search Problems," IEEE Computer, vol. 18, pp. 93-108, June 1985.

Digital Library

[13]

L.H. Goldstein and E. L. Thigpen, "SCOAP: Sandia ControUability/Observability Analysis Program," Proc. of ACMIIEEE Design Automation Conf., 1980.

Digital Library

[14]

R. G. Bennett,s, Design of Testable Logic Circuits, Addison Wesley Publishing Company, London 1984.

[15]

S.C. Seth, L. Pan, and V. D. Agrawal, "PREDICT - Probabilistic Estimation of Digital Circuit Testability," Proc. Int. Syrup. on Fault Tolerant Computing, pp. 220- 225, June 1985.

[16]

A. Ivanov and V. K. Agarwal, "Testability Measures - What Do They Do for ATPG?," Proc. 1986 International Test Conf., pp. 129-138, September 1986.

[17]

F. Brglez and H. Fujiwara, "Neutral Netlist of Ten Combinational Benchmark Circuits and a Target Translator in FORTRAN," Special session on ATPG and fault simulation, Proc. of IEEE International Symposium on Circuits and Systems, June 1985.

[18]

S. Patil and P. Banerjee, "A Parallel Branch and Bound Algorithm for Test Generation," CSG Technical Report, Computer S ystems Group, Coordinated Science Laboratory, University of Illinois, November 1988.

Cited By

Yeh KHuang J(2020)DSSP-ATPG: A Deterministic Search-Space Parallel Test Pattern Generator2020 IEEE International Test Conference in Asia (ITC-Asia)10.1109/ITC-Asia51099.2020.00033(124-129)Online publication date: Sep-2020
https://doi.org/10.1109/ITC-Asia51099.2020.00033
Yeh KHuang JWang L(2016)CPP-ATPGJournal of Electronic Testing: Theory and Applications10.1007/s10836-016-5615-z32:5(625-638)Online publication date: 1-Oct-2016
https://dl.acm.org/doi/10.1007/s10836-016-5615-z
Yeh KHuang JChao HWang L(2013)A circular pipeline processing based deterministic parallel test pattern generator2013 IEEE International Test Conference (ITC)10.1109/TEST.2013.6651913(1-8)Online publication date: Sep-2013
https://doi.org/10.1109/TEST.2013.6651913
Show More Cited By

Index Terms

A parallel branch and bound algorithm for test generation
1. Computer systems organization
  1. Architectures
    1. Parallel architectures
2. Hardware
  1. Hardware test
    1. Design for testability
  2. Very large scale integration design

Recommendations

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 ...
A parallel branch and bound algorithm for integer linear programming models (processing)
Evaluation of a Parallel Branch-and-Bound Algorithm on a Class of Multiprocessors

We propose and evaluate a parallel "decomposite best-first" search branch-and-boundalgorithm (dbs) for MIN-based multiprocessor systems. We start with a new probabilisticmodel to estimate the number of evaluated nodes for a serial best-first ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

DAC '89: Proceedings of the 26th ACM/IEEE Design Automation Conference

June 1989

839 pages

ISBN:0897913108

DOI:10.1145/74382

Chairman:
Donald E. Thomas
Carnegie Mellon Univ., Pittsburgh, PA

Copyright © 1989 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

IEEE-CS\TCDA: TC Design Automation
SIGDA: ACM Special Interest Group on Design Automation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 1989

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

DAC89

Sponsor:

IEEE-CS\TCDA
SIGDA

DAC89: The 26th ACM/IEEE-CS Design Automation Conference

June 25 - 28, 1989

Nevada, Las Vegas, USA

Acceptance Rates

DAC '89 Paper Acceptance Rate 156 of 465 submissions, 34%;

Overall Acceptance Rate 1,770 of 5,499 submissions, 32%

Upcoming Conference

DAC '25

Sponsor:
sigda

62nd ACM/IEEE Design Automation Conference

June 22 - 26, 2025

San Francisco , CA , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

26
Total Citations
View Citations
303
Total Downloads

Downloads (Last 12 months)47
Downloads (Last 6 weeks)14

Reflects downloads up to 16 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Yeh KHuang J(2020)DSSP-ATPG: A Deterministic Search-Space Parallel Test Pattern Generator2020 IEEE International Test Conference in Asia (ITC-Asia)10.1109/ITC-Asia51099.2020.00033(124-129)Online publication date: Sep-2020
https://doi.org/10.1109/ITC-Asia51099.2020.00033
Yeh KHuang JWang L(2016)CPP-ATPGJournal of Electronic Testing: Theory and Applications10.1007/s10836-016-5615-z32:5(625-638)Online publication date: 1-Oct-2016
https://dl.acm.org/doi/10.1007/s10836-016-5615-z
Yeh KHuang JChao HWang L(2013)A circular pipeline processing based deterministic parallel test pattern generator2013 IEEE International Test Conference (ITC)10.1109/TEST.2013.6651913(1-8)Online publication date: Sep-2013
https://doi.org/10.1109/TEST.2013.6651913
Abu-Khzam FMouawad A(2012)A Decentralized Load Balancing Approach for Parallel Search-Tree OptimizationProceedings of the 2012 13th International Conference on Parallel and Distributed Computing, Applications and Technologies10.1109/PDCAT.2012.16(173-178)Online publication date: 14-Dec-2012
https://dl.acm.org/doi/10.1109/PDCAT.2012.16
Weerapurage DEblen JRogers GLangston M(2011)Parallel vertex coverProceedings of the Ninth Australasian Symposium on Parallel and Distributed Computing - Volume 11810.5555/2461246.2461250(25-32)Online publication date: 17-Jan-2011
https://dl.acm.org/doi/10.5555/2461246.2461250
Belkhale KBanerjee P(2006)Parallel algorithms for VLSI circuit extractionIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/43.7949810:5(604-618)Online publication date: 1-Nov-2006
https://dl.acm.org/doi/10.1109/43.79498
Ramkumar BBanerjee P(2006)ProperTESTIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/43.63122016:5(555-569)Online publication date: 1-Nov-2006
https://dl.acm.org/doi/10.1109/43.631220
Wolf JKaufman LKlenke RAylor JWaxman R(2006)An analysis of fault partitioned parallel test generationIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/43.50613915:5(517-534)Online publication date: 1-Nov-2006
https://dl.acm.org/doi/10.1109/43.506139
Krauss PGanz AAntreich K(1997)Distributed Test Pattern Generation for Stuck-At Faults in Sequential CircuitsJournal of Electronic Testing: Theory and Applications10.1023/A:100826642238011:3(227-245)Online publication date: 1-Dec-1997
https://dl.acm.org/doi/10.1023/A%3A1008266422380
Klenke RAylor JWolf J(1996)An analysis of fault partitioning algorithms for fault partitioned ATPGProceedings of 14th VLSI Test Symposium10.1109/VTEST.1996.510862(231-239)Online publication date: 1996
https://doi.org/10.1109/VTEST.1996.510862
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Figures

Tables

Media

View Table of Conten