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

在静态时序分析中,寻找最长时延路径以及最坏情况下时延是最重要的任务。考虑门的逻辑功能,提出了一种精度更高的最长路径搜索算法。由于门的时延大小不仅取决于输入信号的过渡(transition)时问和负载电容大小,还取决于输出信号的状态(上升或下降)以及其它管脚状态(高电平或低电平),因此,该算法极大地提高了静态时序分析的精度。文章还给出了区段搜索算法,可以找出时延在给定范围内的所有路径。这两个搜索算法对每务边至多遍历一次,时问复杂度依然为线性。

The Longest Path Search Algorithm Considering Gate Logic Functions

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.