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

A new detection algorithm for critical paths

作　　者：杜振军[1] 马光胜[2] 冯刚[2] 

机构地区：[1]哈尔滨工业大学计算机科学与技术博士后流动站 [2]哈尔滨工程大学计算机科学与技术学院,黑龙江哈尔滨150001

出　　处：《哈尔滨工程大学学报》2005年第4期518-521,共4页Journal of Harbin Engineering University

基　　金：国家自然科学基金资助项目(69973014和60273081);黑龙江省自然科学基金资助项目(F0209);哈工程大学基础研究资助基金资助项目(HEUF04088)

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

关 键 词：关键路径 定时分析 通路敏化 

分 类 号：TP391.72[自动化与计算机技术—计算机应用技术]