Dynamic search-space pruning techniques in path sensitization

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Dynamic search-space pruning techniques in path sensitization

Full text

Pdf (81 KB)

Source

Annual ACM IEEE Design Automation Conference archive
Proceedings of the 31st annual Design Automation Conference table of contents

San Diego, California, United States

Pages: 705 - 711

Year of Publication: 1994

ISBN:0-89791-653-0

Authors

João P. Marques Silva	Department of Electrical Engineering and Computer Science, University of Michigan
Karem A. Sakallah	Department of Electrical Engineering and Computer Science, University of Michigan

Sponsors

IEEE-CAS : Circuits & Systems
SIGDA: ACM Special Interest Group on Design Automation
EDAC : Electronic Design Automation Consortium

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 12, Citation Count: 10

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/196244.196621 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	M. Abramovici, M. A. Breuer and A. D. Friedman, Digital Systems Testing and Testable Design, Computer Science Press, 1990.
	2	F. Brglez, and H. Fujiwara, "A Neutral List of 10 Combinational Benchmark Circuits and a Target Translator in FORTRAN," in Proc. Int. Syrup. on Circ. and Sys., 1985.
	3	R. Dechter, "Learning While Searching in Constraint-Satisfaction Problems," Technical Report CSD-860049, University of California at Los Angeles, June 1986.
	4	T. Fujino and H. Fujiwara, "An Efficient Test Generation Algorithm Based on Search Space Dominance," in Proc. 22nd Fault Tolerant Cornput. Syrup., pp. 246-253, 1992.
	5	H. Fujiwara and T. Shimono, "On the Acceleration of Test Generation Algorithms," IEEE Trans. on Computers, vol. 32, no. 12, pp. 1137- 1144, December 1983.
	6	John Giraldi , Michael L. Bushnell, EST: The new frontier in automatic test-pattern generation, Proceedings of the 27th ACM/IEEE conference on Design automation, p.667-672, June 24-27, 1990, Orlando, Florida, United States [doi>10.1145/123186.123434]
	7	E Goel, "An Implicit Enumeration Algorithm to Generate Tests for Combinational Logic Circuits," IEEE Trans. on Computers, vol. 30, no. 3, pp. 215-222, March 1981.
	8	T. Kirkland , M. R. Mercer, A topological search algorithm for ATPG, Proceedings of the 24th ACM/IEEE conference on Design automation, p.502-508, June 28-July 01, 1987, Miami Beach, Florida, United States [doi>10.1145/37888.37963]
	9	A. Lioy, "Adaptive Backtrace and Dynamic Partitioning Enhance APTG," in Proc. Int. Conf. Computer Design, pp. 62-65, 1988.
	10	W. Kunz and D. Pradhan, "Accelerated Dynamic Learning for Test Pattern Generation in Combinational Circuits," IEEE Trans. on Computer- Aided Design, vol. 12, no. 5, pp. 684-694, May 1993.
	11	S. Mallela and S. Wu, "A Sequential Circuit Test Generation System," in Proc. Int. Test Conf., pp. 57-61, 1985.
	12	Ralph Marlett, An effective test generation system for sequential circuits, Proceedings of the 23rd ACM/IEEE conference on Design automation, p.250-256, July 1986, Las Vegas, Nevada, United States
	13	J. Rajski and H. Cox, "A Method to Calculate Necessary Assignments in Algorithmic Test Pattern Generation," in Proc. Int. Test Conf., pp. 25- 34, 1990.
	14	J. E Roth, "Diagnosis of Automata Failures: a Calculus and a Method". IBM J. Res. Develop., vol. 10, pp. 278-291, July 1966.
	15	M. H. Schulz, E. Trischler and T. M. Sarfert, "SOCRATES: A Highly Efficient Automatic Test Pattern Generation System," IEEE Trans. on Computer-Aided Design, vol. 7, no. 1, pp. 126-137, January 1988.
	16	M. H. Schulz, and E. Auth, "Improved Deterministic Test Pattern Generation with Applications to Redundancy Identification," IEEE Trans. on Computer-AidedDesign, vol. 8, no. 7, pp. 811-816, July 1989.
	17	J. E M. Silva and K. A. Sakallah, "Search-Space Pruning Heuristics for Path Sensitization in Test Pattern Generation," Technical Report CSE- TR-178-93, University of Michigan, October 1993.
	18	J. E M. Silva and K. A. Sakallah, "Efficient and Robust Test Generation-Based Timing Analysis," in Proc. Int. Syrup. on Circ. and Sys., 1994, in press.
	19	R. M. Stallman and G. J. Sussman, "Forward Reasoning and Dependency-Directed Backtracking in a System for Computer-Aided Circuit Analysis," in Artificial Intelligence, 9, pp. 135-196, 1977.
	20	R. E. Tarjan, "Finding Dominators in Directed Graphs," in SlAM J. Comput., vol. 3, pp. 62-89, 1974.
	21	J. A. Waicukauski, E A. Shupe, D. J. Giramma and A. Matin, "ATPG for Ultra-Large Structured Designs," in Proc. Int. Test Conf., pp. 44-51, 1990.

CITED BY 10

	Ilker Hamzaoglu , Janak H. Patel, New Techniques for Deterministic Test Pattern Generation, Journal of Electronic Testing: Theory and Applications, v.15 n.1-2, p.63-73, August-October 1999
	Paulo F. Flores , Horácio C. Neto , João P. Marques-Silva, An exact solution to the minimum size test pattern problem, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.6 n.4, p.629-644, October 2001
	João P. Marques Silva , Karem A. Sakallah, GRASP—a new search algorithm for satisfiability, Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design, p.220-227, November 10-14, 1996, San Jose, California, United States
	Wolfgang Kunz , João Marques-Silva , Sharad Malik, SAT and ATPG: algorithms for Boolean decision problems, Logic Synthesis and Verification, Kluwer Academic Publishers, Norwell, MA, 2001
	Gi-Joon Nam , Karem A. Sakallah , Rob A. Rutenbar, Satisfiability-based layout revisited: detailed routing of complex FPGAs via search-based Boolean SAT, Proceedings of the 1999 ACM/SIGDA seventh international symposium on Field programmable gate arrays, p.167-175, February 21-23, 1999, Monterey, California, United States
	Shuo Sheng , Michael S. Hsiao, Success-Driven Learning in ATPG for Preimage Computation, IEEE Design & Test, v.21 n.6, p.504-512, November 2004
	João P. Marques-Silva , Karem A. Sakallah, GRASP: A Search Algorithm for Propositional Satisfiability, IEEE Transactions on Computers, v.48 n.5, p.506-521, May 1999
	Michael S. Hsiao , Shuo Sheng , Rajat Arora , Ankur Jain , Vamsi Boppana, Verification of large scale nano systems with unreliable nano devices, Nano, quantum and molecular computing: implications to high level design and validation, Kluwer Academic Publishers, Norwell, MA, 2004
	D. Tadesse , D. Sheffield , E. Lenge , R. I. Bahar , J. Grodstein, Accurate timing analysis using SAT and pattern-dependent delay models, Proceedings of the conference on Design, automation and test in Europe, April 16-20, 2007, Nice, France
	Shuo Sheng , Michael Hsiao, Efficient Preimage Computation Using A Novel Success-Driven ATPG, Proceedings of the conference on Design, Automation and Test in Europe, p.10822, March 03-07, 2003