A new detection algorithm for critical paths
Zhenjun Du, Guangsheng Ma · Harbin Gongcheng Daxue Xuebao/Journal of Harbin Engineering University · 2005
False paths greatly affect the timing analysis of a computer chip. To overcome this problem, an approach of identifying false paths based on Satisfiability(SAT) and generic search algorithm for the satisfiability problem(GRASP) algorithms was adopted and a new detection algorithm for critical paths in combinatorial circuits based on the identification approach was presented. Experiments show that this method can quickly detect critical paths of large-scale circuits on a personal computer. For some benchmark circuits with several thousand gates, the critical paths can be detected within 30 seconds and the delays derived can be actually smaller than the longest topological delays. The algorithm offers an approach for exact timing analysis of chips.