DocumentCode :
1472265
Title :
Refactoring of Timing Graphs and Its Use in Capturing Topological Correlation in SSTA
Author :
Chung, Jaeyong ; Abraham, Jacob A.
Author_Institution :
Dept. of Electr. & Comput. Eng., Univ. of Texas, Austin, TX, USA
Volume :
31
Issue :
4
fYear :
2012
fDate :
4/1/2012 12:00:00 AM
Firstpage :
485
Lastpage :
496
Abstract :
Reconvergent paths in circuits have been a nuisance in various computer-aided design (CAD) algorithms, but no elegant solution to deal with them has been found yet. In statistical static timing analysis (SSTA), they cause difficulty in capturing topological correlation. This paper presents a technique that in arbitrary block-based SSTA reduces the error caused by ignoring topological correlation. We interpret a timing graph as an algebraic expression made up of addition and maximum operators. We define the division operation on the expression and propose algorithms that modify factors in the expression without expansion. As a result, the algorithms produce an expression to derive the latest arrival time with better accuracy in SSTA. Existing techniques handling reconvergent fanouts usually use dependency lists, requiring quadratic space complexity. Instead, the proposed technique has linear space complexity by using a new directed acyclic graph search algorithm. Our results show that it outperforms an existing technique in speed and memory usage with comparable accuracy. More important, the proposed technique is not limited to SSTA and is potentially applicable to various issues due to reconvergent paths in timing-related CAD algorithms.
Keywords :
computational complexity; correlation theory; directed graphs; electronic design automation; network topology; statistical analysis; algebraic expression; arbitrary block-based SSTA; arrival time; circuits reconvergent paths; computer-aided design algorithm; directed acyclic graph search algorithm; linear space complexity; memory usage; quadratic space complexity; reconvergent fanouts; speed usage; statistical static timing analysis; timing graphs refactoring; timing-related CAD algorithm; topological correlation; Algorithm design and analysis; Correlation; Delay; Heuristic algorithms; Logic gates; Random variables; Common path pessimism; process variation; reconvergent paths; static timing analysis;
fLanguage :
English
Journal_Title :
Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on
Publisher :
ieee
ISSN :
0278-0070
Type :
jour
DOI :
10.1109/TCAD.2011.2176731
Filename :
6171045
Link To Document :
بازگشت