考虑门逻辑功能的最长路径搜索算法  

The Longest Path Search Algorithm Considering Gate Logic Functions

作　　者：燕昭然[1] 杨华中[1] 罗嵘[1] 汪蕙[1] 

机构地区：[1]清华大学电子工程系,北京100084

出　　处：《微电子学》2004年第3期285-288,共4页Microelectronics

基　　金：国家重点基础研究发展规划(G1999032903);国家自然科学基金(60025101;90270001);"863"计划超大规模集成电路设计重大专项(2002AA1Z1460)资助项目

摘　　要：　在静态时序分析中,寻找最长时延路径以及最坏情况下时延是最重要的任务。考虑门的逻辑功能,提出了一种精度更高的最长路径搜索算法。由于门的时延大小不仅取决于输入信号的过渡(transition)时间和负载电容大小,还取决于输出信号的状态(上升或下降)以及其它管脚状态(高电平或低电平),因此,该算法极大地提高了静态时序分析的精度。文章还给出了区段搜索算法,可以找出时延在给定范围内的所有路径。这两个搜索算法对每条边至多遍历一次,时间复杂度依然为线性。Finding the longest path and the worst delay is the most important task in static timing analysis. In this paper, a more accurate longest path search algorithm is presented with logic function of gates taken into consideration. Since the gate delay is not only determined by transition time of input signals and load capacitance, but also by the state (rising or falling) of input signals and other pins' states (logic 1 or logic 0), the accuracy of static timing analysis is greatly improved. Also, a range path search algorithm is implemented to find out all paths whose delays are in given range. Since both search algorithms pass through each edge once at most, its time complexity is also linear.

关 键 词：静态时序分析 最长路径搜索 时序验证 

分 类 号：TN702[电子电信—电路与系统]