Browse Theses

In this research, we study the characteristics of false path and its representation and propose methods to calculate the worst delay of a circuit with known false paths. For every vertex on a false path, false path information is annotated on it. During the computation, false path information is propagated and we can know if a false path can be satisfied down below. Delays from a node, along with the false paths matched from below are stored in the cache. When a vertex is re-visited, if the false paths matched from above the node are in the cache, the method returns the delay associated with it, otherwise, a new computation is performed. Our method can be applied to different areas of timing analysis. Very often, after initial timing analysis, false paths are added to or deleted from the circuit. Incremental analysis is required for updated timing constraints. This method can be applied to incremental delay calculation with little change, while path enumeration has to conduct analysis from start again. Also our method can be used to compute the n-worst paths in a circuit. In this research, we propose two methods to handle false loops in timing analysis. In the first method, we use bipartite to replace a loop. Logic analysis is performed on side inputs to the loop to remove loop edges. Heuristics to compute edge weight of the bipartite is given to reduce the number of times a loop is visited. After the loops are broken, depth-first search algorithm can be applied to compute the longest path in the circuit. In the-second method, a loop is modeled as a special false path. We describe heuristics to reduce the number of false paths used to represent a loop. During the computation, if a node is visited twice, the loop false path is satisfied and delay is nullified. The advantage of the method is that it unifies the methodology to compute the longest delay in the presence of false paths and false loops and is easy to implement. (Abstract shortened by UMI.)