Article

Free access

A polynomial-time heuristic approach to approximate a solution to the false path problem

Authors:

Shiang-Tang Huang,

Tai Ming Parng,

Jyuo Min ShyuAuthors Info & Claims

DAC '93: Proceedings of the 30th international Design Automation Conference

Pages 118 - 122

https://doi.org/10.1145/157485.164622

Published: 01 July 1993 Publication History

PDF eReader

References

[1]

R.B. Hitchcock, Sr., G. L. Smith, and D. D. Cheng, "Timing analysis of computer hardware," IBM.J.Res.Develop., vol. 26, No. 1, pp. 100- 106, Jan. 1982.

Digital Library

Google Scholar

[2]

Lionel C. Bening et al, "Developments in logic network path delay analysis," in Proc. 19th Design Automation Conf., pp. 605-615,1982.

Digital Library

Google Scholar

[3]

Norman P. louppi, "Timing analysis for nMOS VLSI," in Proc. 20th Design Automation Conf., pp. 411-418, 1983.

Digital Library

Google Scholar

[4]

Norman P. louppi, "Timing analysis and performance improvement of MOS VLSI designs," IEEE Trans. Computer-Aided Design, vol. 6, No. 4, Jul. 1987.

Google Scholar

[5]

H.C. Yen, S. Ghanta, and H.C. Du, "A Path Selection Algorithm for Timing Analysis," in Proc. 25th Design Automation Conf., pp. 720- 723, 1988.

Digital Library

Google Scholar

[6]

Steve H.C. Yen, David H.C. Du, and S. Ghanta, "Efficient algorithms for extracting the k most critical paths in timing analysis," in Proc. 26th Design Automation Conf., pp. 649-653, 1989.

Digital Library

Google Scholar

[7]

Daniel Brand, and Vijay S. Iyengar"Timing analysis using functional relationships," in IEEE Int. Conf. Computer-Aided Design, pp. 126- 129, 1986.

Google Scholar

[8]

J. Benkoski, E. Vanden Meersch, L. Claesen, andH. De Man "Efficient algorithms for solving the false path problem in timing verification," in IEEE Int. Conf. Computer-Aided Design, pp. 44-47, 1987.

Google Scholar

[9]

David H.C. Du, Steve H.C. Yen, and S. Ghanta "On the general false path problem in timing analysis," in Proc. 26th Design Automation Conf., pp. 555-560, 1989.

Digital Library

Google Scholar

[10]

Patrick C. McGeer and Robert K. Brayton, "Efficient algorithms for computing the longest viable path in a combinational network," in Proc. 26th Design Automation Conf., pp. 561-567, 1989.

Digital Library

Google Scholar

[11]

S. Perremans, L. Claesen, and H. De Man, "Static timing analysis of dynamically sensitizable paths," in Proc. 26th Design Automation Conf., pp. 568-573, 1989.

Digital Library

Google Scholar

[12]

Hsi-Chuan Chen, David, and H.C. Du, "Path sensitization in critical path problem," in IEEE Int. Conf. Computer-Aided Design, pp. 208- 211, 1991.

Crossref

Google Scholar

[13]

Shiang-Tang Huang, Tai-Ming Pamg, and lyuo-Min Shyu, "A new approach to solving false path problem in timing analysis," in IEEE Int. Conf. Computer-Aided Design, pp. 216-219, 1991.

Google Scholar

Cited By

View all

Zhou SYao BChen HZhu YHutton MCollins TSrinivasan SChou NSuaris PCheng C(2007)Efficient Timing Analysis With Known False Paths Using Biclique CoveringIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2006.88573726:5(959-969)Online publication date: 1-May-2007
https://dl.acm.org/doi/10.1109/TCAD.2006.885737
Sait SZahra M(2002)Tabu search based circuit optimizationEngineering Applications of Artificial Intelligence10.1016/S0952-1976(02)00054-415:3-4(357-368)Online publication date: Jun-2002
https://doi.org/10.1016/S0952-1976(02)00054-4
Jing Zeng Abadir MBhadra JAbraham J(2000)Full chip false timing-path identification2000 IEEE Workshop on SiGNAL PROCESSING SYSTEMS. SiPS 2000. Design and Implementation (Cat. No.00TH8528)10.1109/SIPS.2000.886768(703-711)Online publication date: 2000
https://doi.org/10.1109/SIPS.2000.886768
Show More Cited By

Index Terms

A polynomial-time heuristic approach to approximate a solution to the false path problem
1. Hardware
  1. Hardware validation
    1. Functional verification
  2. Integrated circuits
    1. Logic circuits
2. Theory of computation
  1. Computational complexity and cryptography
    1. Problems, reductions and completeness

Recommendations

An approximate solution of optimal allocation problem by a nomograph

A graphical procedure is presented to obtain an approximate solution to the minimization problem of the follwing form: Minimize the function $$\varphi (t_0 ,t_1 ,...,t_{n - 1} ,t_n ) = g(t_0 ,t_1 ) + g(t_1 ,t_2 ) + ... + g(t_{n - 1} ,t_n )$$ subject to ...
On the general false path problem in timing analysis
DAC '89: Proceedings of the 26th ACM/IEEE Design Automation Conference

The false path problem is often referred to as the problem of detecting the longest sensitizable path (A path which is not a false path is a sensitizable path). The term “false path” is not clearly defined. In this paper, we first give a clear and ...
Fast Polynomial Time Approximate Solution for 0-1 Knapsack Problem
0-1 Knapsack problem (KP) is NP-hard. Approximate solution is vital for solving KP exactly. In this paper, a fast polynomial time approximate solution (FPTAS) is proposed for KP. FPTAS is a local search algorithm. The best approximate solution to KP can ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

DAC '93: Proceedings of the 30th international Design Automation Conference

July 1993

768 pages

ISBN:0897915771

DOI:10.1145/157485

Chairman:
Alfred E. Dunlop
AT&T Bell Labs., Murray Hill, NJ

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 1993

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

DAC93

Sponsor:

EDAC
SIGDA
IEEE-CAS

DAC93: The 30th ACM/IEEE Design Automation Conference

June 14 - 18, 1993

Texas, Dallas, USA

Acceptance Rates

Overall Acceptance Rate 299 of 1,119 submissions, 27%

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

13
Total Citations
View Citations
139
Total Downloads

Downloads (Last 12 months)17
Downloads (Last 6 weeks)4

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Zhou SYao BChen HZhu YHutton MCollins TSrinivasan SChou NSuaris PCheng C(2007)Efficient Timing Analysis With Known False Paths Using Biclique CoveringIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2006.88573726:5(959-969)Online publication date: 1-May-2007
https://dl.acm.org/doi/10.1109/TCAD.2006.885737
Sait SZahra M(2002)Tabu search based circuit optimizationEngineering Applications of Artificial Intelligence10.1016/S0952-1976(02)00054-415:3-4(357-368)Online publication date: Jun-2002
https://doi.org/10.1016/S0952-1976(02)00054-4
Jing Zeng Abadir MBhadra JAbraham J(2000)Full chip false timing-path identification2000 IEEE Workshop on SiGNAL PROCESSING SYSTEMS. SiPS 2000. Design and Implementation (Cat. No.00TH8528)10.1109/SIPS.2000.886768(703-711)Online publication date: 2000
https://doi.org/10.1109/SIPS.2000.886768
Sait SYoussef HZahra M(1998)Tabu search based circuit optimizationProceedings of the 8th Great Lakes Symposium on VLSI (Cat. No.98TB100222)10.1109/GLSV.1998.665299(338-343)Online publication date: 1998
https://doi.org/10.1109/GLSV.1998.665299
Kukimoto YGosti WSaldanha ABrayton ROtten RYasuura H(1997)Approximate timing analysis of combinational circuits under the XBD0 modelProceedings of the 1997 IEEE/ACM international conference on Computer-aided design10.5555/266388.266458(176-181)Online publication date: 13-Nov-1997
https://dl.acm.org/doi/10.5555/266388.266458
Yalcin HHayes JSakallah KRutenbar ROtten R(1997)An approximate timing analysis method for datapath circuitsProceedings of the 1996 IEEE/ACM international conference on Computer-aided design10.5555/244522.244541(114-118)Online publication date: 1-Jan-1997
https://dl.acm.org/doi/10.5555/244522.244541
Kukimoto Gosti Saldanha Brayton (1997)Approximate timing analysis of combinational circuits under the XBDO modelProceedings of IEEE International Conference on Computer Aided Design (ICCAD) ICCAD-9710.1109/ICCAD.1997.643404(176-181)Online publication date: 1997
https://doi.org/10.1109/ICCAD.1997.643404
Yalcin HHayes JSakallah K(1996)An approximate timing analysis method for datapath circuitsProceedings of International Conference on Computer Aided Design10.1109/ICCAD.1996.569410(114-118)Online publication date: 1996
https://doi.org/10.1109/ICCAD.1996.569410
Wessels DMuzio J(1996)The dangers of simplistic delay modelsJournal of Electronic Testing: Theory and Applications10.1007/BF001360768:1(61-69)Online publication date: 1-Feb-1996
https://dl.acm.org/doi/10.1007/BF00136076
Belkhale KSuess ARudell R(1995)Timing analysis with known false sub graphsProceedings of the 1995 IEEE/ACM international conference on Computer-aided design10.5555/224841.225157(736-740)Online publication date: 1-Dec-1995
https://dl.acm.org/doi/10.5555/224841.225157
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

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

Cited By

Index Terms

Recommendations

An approximate solution of optimal allocation problem by a nomograph

On the general false path problem in timing analysis

Fast Polynomial Time Approximate Solution for 0-1 Knapsack Problem