NDLI: A Polynomial-Time Heuristic Approach to Approximate a Solution to the False Path Problem

Content Provider	IEEE Xplore Digital Library
Author	Shiang-Tang Huang Tai-Ming Parng Jyuo-Min Shyu
Copyright Year	1993
Description	Author affiliation: Dept. of Electrical Engineering, National Taiwan University, Taipei, Taiwan, R.O.C. (Shiang-Tang Huang)
Abstract	In this paper we present a new approach to solving the false path problem. The method is based on our previous work on Timed Boolean Calculus. Given a logic circuit, we first derive timed boolean expressions to model its dynamic behavior. Then, for each term in the expressions, we compute its corresponding sensitizability function, expressed in conjunction normal form; and use an expression in product form to approximate the function. Finally we remove the redundant terms whose sensitizability functions are not satisfiable and determine the maximal delays from the terms remained. Complexity analysis shows that our method identifies false paths and computes delays for sensitizable paths in polynomial time, while experimental results on ISCAS benchmark circuits prove its better efficiency and effectiveness.
Starting Page	118
Ending Page	122
File Size	370378
Page Count	5
File Format	PDF
ISBN	0897915771
ISSN	0738100X
DOI	10.1109/DAC.1993.203930
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	1993-06-14
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Association for Computing Machinery, Inc. (ACM)
Subject Keyword	Polynomials Timing Calculus Logic circuits Delay effects Central Processing Unit Performance analysis Logic gates NP-complete problem Computational efficiency
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

A polynomial-time heuristic approach to solving the false path problem

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

Test Generation and Computational Complexity

A new approach to solving false path problem in timing analysis

Utilizing register transfer level false paths for circuit optimization with a logic synthesis tool

Generalized quantum Turing machine and its use to find an algorithm solving NP-Complete problem

A two-level two-way partitioning algorithm

Fast and accurate statistical static timing analysis

Improving the Efficiency of Static Timing Analysis with False Paths

A Polynomial-Time Heuristic Approach to Approximate a Solution to the False Path Problem

Similar Documents

A polynomial-time heuristic approach to solving the false path problem

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

Test Generation and Computational Complexity

A new approach to solving false path problem in timing analysis

Utilizing register transfer level false paths for circuit optimization with a logic synthesis tool

Generalized quantum Turing machine and its use to find an algorithm solving NP-Complete problem

A two-level two-way partitioning algorithm

Fast and accurate statistical static timing analysis

Improving the Efficiency of Static Timing Analysis with False Paths

A Polynomial-Time Heuristic Approach to Approximate a Solution to the False Path Problem