Efficient algorithms for computing the longest viable path in a combinational network

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Efficient algorithms for computing the longest viable path in a combinational network

Full text

Pdf (906 KB)

Source

Annual ACM IEEE Design Automation Conference archive
Proceedings of the 26th ACM/IEEE Design Automation Conference table of contents

Las Vegas, Nevada, United States

Pages: 561 - 567

Year of Publication: 1989

ISBN:0-89791-310-8

Authors

P. C. McGeer	Department of Electrical Engineering and Computer Sciences, University of California, Berkeley
R. K. Brayton	Department of Electrical Engineering and Computer Sciences, University of California, Berkeley

Sponsors

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

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 43, Citation Count: 34

Additional Information:

abstract 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/74382.74476 What is a DOI?

ABSTRACT

We consider the elimination of false paths in combinational circuits. We give the single generic algorithm that is used to solve this problem, and demonstrate that it is parameterized by a Boolean function called the sensitization condition. We give two criteria which we argue that a valid sensitization condition must meet, and introduce four conditions that have appeared in the recent literature, of which two meet the criteria and two do not. We then introduce a dynamic programming procedure for the tightest of these conditions, the viability condition, and discuss the integration of all four sensitization conditions in the LLLAMA timing environment. We give results on the IWLS and ISCAS benchmark examples and on carry-bypass adders.

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	J. Benkoski, E. Vanden Meesch, L. Claesen, and H. De Man. Efficient Algorithms for Solving the False Path Problem in Timing Verification. In IEEE International Conference on Computer- Aided Design, 1987.
	2	Daniel Brand and Vijay S. Iyengar. Timing Anal ysis Using Functional Analysis. Technical Report RC 11768, IBM Thomas J. Watson Research Center, Yorktown Heights, New York, 10598, 1986.
	3	R. K. Brayton, R. Rudell, A. L. Sagiovanni- Vincentelli, and A. Wang. Mis: a multiple-level logic optimization system. IEEE Teansactions on CAD, 1987.
	4	Randal E. Bryant, Graph-based algorithms for Boolean function manipulation, IEEE Transactions on Computers, v.35 n.8, p.677-691, Aug. 1986 [doi>10.1109/TC.1986.1676819]
	5	Robert B. Hitchcock, Sr., Timing Verification and the Timing Analysis program, Proceedings of the 19th conference on Design automation, p.594-604, January 1982
	6	V. M. Hrapcenko. Depth and delay in a network. Soviet Math. DokL, 1978.
	7	N. J ouppi. TV: an nMOS Timing Analyzer. In Third Caltech VLSI Conference, 1983.
	8	S. Malik, A. R. Wang, R. K. Brayton, R. Rudell, and A. L. Sagiovanni-Vincentelli. Logic verification using binary decision diagrams in a logic synthesis environment. In IEEE International Conference on Computer-Aided Design, 1988.
	9	Patrick C. McGeer , Robert K. Brayton, Provably correct critical paths, Proceedings of the decennial Caltech conference on VLSI on Advanced research in VLSI, p.119-142, June 1989, Cambridge, Massachusetts, United States
	10	John K. Ousterhout. Crystal: a Timing Analyzer for nMOS VLSI Circuits. In Third Callech VI, SI Conference, 1983.
	11	J. P. Roth. Diagnosis of automata failures: a calculus and a method. IBM J. Res. Develop, 1966.

CITED BY 34

	Mukund Sivaraman , Andrzej J. Strojwas, Timing analysis based on primitive path delay fault identification, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.182-189, November 09-13, 1997, San Jose, California, United States
	Hsi-Chuan Chen , David H. C. Du , Li-Ren Liu, Critical path selection for performance optimization, Proceedings of the 28th conference on ACM/IEEE design automation, p.547-550, June 17-22, 1991, San Francisco, California, United States
	S. Kim , R. M. Owens , M. J. Irwin, Experiments with a performance driven module generator, Proceedings of the 29th ACM/IEEE conference on Design automation, p.687-690, June 08-12, 1992, Anaheim, California, United States
	Edgar Bolender , Hans Martin Lipp, The exact solution of timing verification, Proceedings of the conference on European design automation, p.132-137, November 1992, Congress Centrum Hamburg, Hamburg, Germany
	Karl S. Brace , Richard L. Rudell , Randal E. Bryant, Efficient implementation of a BDD package, Proceedings of the 27th ACM/IEEE conference on Design automation, p.40-45, June 24-27, 1990, Orlando, Florida, United States
	David Blaauw , Rajendran Panda , Abhijit Das, Removing user specified false paths from timing graphs, Proceedings of the 37th conference on Design automation, p.270-273, June 05-09, 2000, Los Angeles, California, United States
	Li-Ren Liu , David H. C. Du , Hsi-Chuan Chen, An efficient parallel critical path algorithm, Proceedings of the 28th conference on ACM/IEEE design automation, p.535-540, June 17-22, 1991, San Francisco, California, United States
	Krishna P. Belkhale , Alexander J. Suess, Timing analysis with known false sub graphs, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.736-740, November 05-09, 1995, San Jose, California, United States
	S. W. Cheng , H.-C. Chen , D. H. C. Du , A. Lim, The role of long and short paths in circuit performance optimization, Proceedings of the 29th ACM/IEEE conference on Design automation, p.543-548, June 08-12, 1992, Anaheim, California, United States
	Patrick C. McGeer , Robert K. Brayton, Timing analysis in precharge/unate networks, Proceedings of the 27th ACM/IEEE conference on Design automation, p.124-129, June 24-27, 1990, Orlando, Florida, United States
	M. Kassab , E. Cerny , S. Aourid , T. Krodel, Propagation of last-transition-time constraints in gate-level timing analysis, Proceedings of the conference on Design, automation and test in Europe, p.796-802, February 23-26, 1998, Le Palais des Congrés de Paris, France
	How-Rern Lin , TingTing Hwang, Dynamical identification of critical paths for iterative gate sizing, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.481-484, November 06-10, 1994, San Jose, California, United States
	Shiang-Tang Huang , Tai Ming Parng , Jyuo Min Shyu, A polynomial-time heuristic approach to approximate a solution to the false path problem, Proceedings of the 30th international conference on Design automation, p.118-122, June 14-18, 1993, Dallas, Texas, United States
	Jing-Jia Liou , Angela Krstic , Li-C. Wang , Kwang-Ting Cheng, False-path-aware statistical timing analysis and efficient path selection for delay testing and timing validation, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA
	Jacques Benkoski , Andrzej J. Strojwas, The role of timing verification in layout synthesis, Proceedings of the 28th conference on ACM/IEEE design automation, p.612-619, June 17-22, 1991, San Francisco, California, United States
	Champaka Ramachandran , Fadi J. Kurdahi, Combined topological and functionality based delay estimation using a layout-driven approach for high level applications, Proceedings of the conference on European design automation, p.72-78, November 1992, Congress Centrum Hamburg, Hamburg, Germany
	Mehrdad Nourani , Christos A. Papachristou, False path exclusion in delay analysis of RTL structures, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.10 n.1, p.30-43, 2/1/2002
	V. Chandramouli , J. P. Whittemore , K. A. Sakallah, AFTA: a formal delay model for functional thinking analysis, Proceedings of the conference on Design, automation and test in Europe, p.350-355, February 23-26, 1998, Le Palais des Congrés de Paris, France
	Hoon Chang , Jacob A. Abraham, VIPER: an efficient vigorously sensitizable path extractor, Proceedings of the 30th international conference on Design automation, p.112-117, June 14-18, 1993, Dallas, Texas, United States
	M. Ringe , T. Lindenkreuz , E. Barke, Path verification using Boolean satisfiability, Proceedings of the conference on Design, automation and test in Europe, p.965-966, February 23-26, 1998, Le Palais des Congrés de Paris, France
	Soohong Kim , Robert M. Owens , Mary J. Irwin, PERFLEX: a performance driven module generator, Proceedings of the conference on European design automation, p.154-159, November 1992, Congress Centrum Hamburg, Hamburg, Germany
	R. Peset Llopis, Path sensitization of combinational circuits and its impact on clocking of sequential systems, Proceedings of the conference on European design automation, p.210-215, September 18-22, 1995, Brighton, England
	Yun-Cheng Ju , Resve A. Saleh, Incremental techniques for the identification of statically sensitizable critical paths, Proceedings of the 28th conference on ACM/IEEE design automation, p.541-546, June 17-22, 1991, San Francisco, California, United States
	R. Peset Llopis, Exact path sensitization in timing analysis, Proceedings of the conference on European design automation, p.380-385, September 19-23, 1994, Grenoble, France
	H. G. Yang , D. M. Holburn, A hierarchical approach to timing verification in CMOS VLSI design, Proceedings of the conference on European design automation, February 25-28, 1991, Amsterdam, The Netherlands
	Jacques Benkoski , Ronald B. Stewart, TATOO: an industrial timing analyzer with false path elimination and test pattern generation, Proceedings of the conference on European design automation, February 25-28, 1991, Amsterdam, The Netherlands
	Kurt Keutzer , Sharad Malik , Alexander Saldanha, Is redundancy necessary to reduce delay, Proceedings of the 27th ACM/IEEE conference on Design automation, p.228-234, June 24-27, 1990, Orlando, Florida, United States
	Clayton B. McDonald , Randal E. Bryant, Symbolic functional and timing verification of transistor-level circuits, Proceedings of the 1999 IEEE/ACM international conference on Computer-aided design, p.526-530, November 07-11, 1999, San Jose, California, United States
	Hoon Chang , Jacob A. Abraham, An Efficient Critical Path Tracing Algorithm for Designing HighPerformance Vlsi Systems, Journal of Electronic Testing: Theory and Applications, v.11 n.2, p.119-129, Oct. 1997
	Hakan Yalcin , John P. Hayes, Event propagation conditions in circuit delay computation, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.2 n.3, p.249-280, July 1997
	Azam Beg , P. W. Chandana Prasad , Ajmal Beg, Applicability of feed-forward and recurrent neural networks to Boolean function complexity modeling, Expert Systems with Applications: An International Journal, v.34 n.4, p.2436-2443, May, 2008
	C.-J. Shi , A. Vannelli , J. Vlach, Performance-Driven Layer Assignment by Integer Linear Programming and Path-Constrained Hypergraph Partitioning, Journal of Heuristics, v.3 n.3, p.225-243, November 1997
	Suchismita Roy , P. P. Chakrabarti , Pallab Dasgupta, Event propagation for accurate circuit delay calculation using SAT, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.12 n.3, p.1-23, August 2007
	Lei Cheng , Deming Chen , Martin D. F. Wong , Mike Hutton , Jason Govig, Timing constraint-driven technology mapping for FPGAs considering false paths and multi-clock domains, Proceedings of the 2007 IEEE/ACM international conference on Computer-aided design, November 05-08, 2007, San Jose, California