US 7,607,118 B1 · Techniques for using edge masks to perform timing analysis

Abstract

Techniques are provided for more efficient timing analysis of user designs for programmable ICs. Initially, a graph is created that represents nodes and edges in a user design. Each edge in the graph is assigned a binary edge mask, each bit of which indicates whether it is reachable from a source or destination type relevant to user specified timing constraints. A timing analysis tool then performs multiple depth-first search operations to compute delays along time critical paths relevant to the user specified timing constraints. Because each edge contains an edge mask to indicate whether it connects to a particular source or destination point, the timing analysis tool does not analyze areas of the graph that do not lead to a relevant source or destination point. These techniques prevent the timing analysis tool from analyzing paths in the graph that are not relevant to the analysis of the time critical paths.

Claims60

Dependent claims

A method for performing timing analysis on a user design that has been placed on a programmable integrated circuit, the method comprising:

generating edge masks to annotate edges in a graph that represents at least a portion of the user design, the edge masks indicating whether a source or destination point is reachable from a corresponding one of the edges;
performing at least one depth first search along a time critical path in the graph between the source and the destination points, the at least one depth first search being prevented by the edge masks from analyzing paths that do not lead to the source point or the destination point;
and
modifying the placement of the user design on the programmable integrated circuit in response to the at least one depth first search.

1 more element

A method for analyzing a user design to be implemented as an integrated circuit, the method comprising:

receiving a graph including nodes and edges, wherein the graph represents at least a portion of a user design;
specifying sources and destinations in the graph, wherein each of the sources includes at least one of the nodes initiating a path and each of the destinations includes at least one of the nodes terminating a path;
generating edge masks to annotate the edges in the graph, wherein each edge mask indicates whether the sources or the destinations in the graph are reachable via a corresponding edge;
selecting at least one source and at least one destination for analysis;
and
analyzing a path between the selected sources and destinations, wherein the analysis comprises:
selecting a first edge for analysis;
performing the analysis on the selected first edge when the corresponding edge mask indicates that at least one of the selected sources and at least one of the selected destinations is reachable via the first edge;
and
ignoring the first edge when the corresponding edge mask indicates that the selected sources and selected destinations are not reachable via the first edge;
and
modifying the implementation of the user design on the integrated circuit in response to the analysis on the selected first edge.

9 more elements

Dependencies are inferred from the claim text.

Techniques for using edge masks to perform timing analysis

Life of this patent

Techniques for using edge masks to perform timing analysis

Life of this patent

Abstract

Claims60