一种检测电路中关键路径的新算法

伪路径的存在严重影响了对大规模集成电路的定时分析．为了克服该问题，文中给出一种基于SAT和GRASP求解算法的识别伪路径的方法，在此基础上引入动态期望值的手段得到一种检测组合电路中的关键路径的快速方法．实验证明，该方法可以在微机环境下对一些大规模的基准电路实现对关键路径的快速检测．对规模为几千个逻辑门的基准电路，该算法可以在半分钟内得到电路的关键路径，而且可以将关键路径时延减小，为确定精确的电路时延提供了依据。

A new detection algorithm for critical paths

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.