Browse Prior Art Database

Method for handling sequential loops in path-based STA

IP.com Disclosure Number: IPCOM000008679D
Publication Date: 2002-Jul-02
Document File: 6 page(s) / 84K

Publishing Venue

The IP.com Prior Art Database

Abstract

Disclosed is a heuristic method for handling sequential loops in path-based static timing analysis (STA). Benefits include improved functionality and an improved design environment.

This text was extracted from a Microsoft Word document.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 25% of the total text.

Method for handling sequential loops in path-based STA

Disclosed is a heuristic method for handling sequential loops in path-based static timing analysis (STA). Benefits include improved functionality and an improved design environment.

Background

              Static timing analysis (STA) is widely used in VLSI design to verify that signals are generated in one place in the circuit, propagate, and are sampled correctly by clocked elements in another place in the circuit.

              A path(timing path) connects between a signal source and its sink, eventually traversing transparent sampling elements. A critical path is a path that misses its sampling requirement and, therefore, has a negative margin or a margin less than the one required by the user.

              Within STA, the circuit is represented by a timing graph. The arcs represent the rules of propagation. The nodes store the results of analysis. Events represent the timing of electric signals traversing the circuit. The timing graph is not guaranteed to be acyclic. Sequential loops or, in a more general form, sequential strongly connected components (SCCs) might be a notable portion of the design.

              A loop’s margin is defined to be the difference between the event at the loop entry point and the event at the same point after traversing the loop. A loop is a critical loop if it has a negative margin.

              Several approaches exist for STA. For path-based analysis, depth first search (DFS) is the native choice for traversal and is used in several STA tools.

              Pruning is an optimization used to reduce the runtime of DFS traversals by deciding to cease the propagation of noncritical paths at a node before they reach the sink, where one approach is to base a decision on margin estimation. It is based on information returned from previous paths that have already traversed through the given node.

Assumptions

              In the description of the disclosed method, the design is assumed to be represented by a timing graph. The analysis is performed using a DFS approach with pruning, based on margin estimation. Each node contains the following data, to be used in the pruning process:

·        Worst event is the event that visited this node with the worst timing.

·        Worst margin is the worst margin caused by an event passing this node at the outgoing cone of the node.

              When the timing graph contains no critical loops, the worst margin is caused by the worst event at the node.

              Margin estimation is performed using the following steps:

1.      Calculate the difference between the visiting event and the worst event written on the node.

2.      Add the difference to the worst margin written from the node. This is the estimated margin.

3.      If, according to the estimated margin, the path is not critical, it is pruned.

Problem Statement

              Pruning is based on the fact that two events on the same node have the same outgoing cone. The criticality of the second passing event can be estimated from the timing of the first event and the margin it caused. This assumption is wrong for loops...