Title
Static timing analysis using backward signal propagation
Abstract
In this paper, we address the problem of signal pruning in static timing analysis (STA). Traditionally, signals are propagated through the circuit and are pruned, such that only the signal with the latest arrival time at each node is propagated forward. This sig-nal pruning is a key to the linear run time of STA. However, it was previously observed that a signal with the latest arrival time may not be the most critical signal, as an earlier signal with a larger transition time can result in a longer delay in the down-stream logic. Hence, arrival time based pruning can result in an optimistic delay, incorrect critical paths, and discontinuities of the delay dur-ing circuit optimization. Although algorithms were proposed to remedy this issue, they rely on propagation of multiple signals and have an exponential worst-case complexity. In this paper, we pro-pose a new timing analysis algorithm, which uses a two pass tra-versal of the circuit. In the initial backward traversal, we construct delay tables which record the required time at a node as a function of the transition time at that node. This is followed by a forward traversal where signals are pruned not based on arrival times but based on slack. The proposed algorithm corrects the accuracy problems of the arrival time based pruning while at the same time maintaining the linear run time of STA. We implemented our algo-rithm and demonstrated its accuracy and efficiency.
Year
DOI
Venue
2004
10.1145/996566.996747
DAC
Keywords
Field
DocType
required time,larger transition time,critical signal,transition time,linear run time,arrival time,signal pruning,multiple signal,earlier signal,static timing analysis,latest arrival time,algorithm design and analysis,logic,performance,signal analysis,timing analysis,algorithms,reliability,critical path
Signal processing,Permission,Exponential function,Tree traversal,Algorithm design,Computer science,Algorithm,Electronic engineering,Real-time computing,Static timing analysis,Round-trip delay time,Radio propagation
Conference
ISSN
ISBN
Citations 
0738-100X
1-58113-828-8
6
PageRank 
References 
Authors
0.56
9
3
Name
Order
Citations
PageRank
Dongwoo Lee116915.92
Vladimir Zolotov21367109.07
David Blaauw38916823.47