Method for timing-directed circuit optimizations
AssigneeTexas Instruments Incorporated
InventorsSanjive Agarwala, Patrick W. Bosshart
Life of this patent
Estimating the term…
Abstract
Shown is a method of optimizing the performance of a logic circuit. The circuit is represented as a set of vertices, with each element output being represented as a vertex whose element is selected for local optimization on a depth first traversal basis. As each element is optimized, its path length is calculated by partial path lengths, which are known to be either valid or invalid as a result of prior local optimizations. Specifically, invalid path lengths to the associated vertex from circuit inputs are re-computed and added to valid path lengths from the associated vertex to a circuit output.
Claims5
A method of performing a time-driven optimization on a logic circuit represented as a set of input vertices, element vertices for associated circuit elements, and output vertices, and a set of edges connecting ordered pairs of vertices, comprising the steps of:
- calculating a backward delay value at each vertex of the logic circuit;
- for a given output vertex of the logic circuit, selecting a set of element vertices on all paths from that output vertex to an input vertex;
- selecting an element vertex from said set of element vertices for local computation, on a depth first traversal basis;
- calculating a path length at said selected element vertex, wherein said path length includes a local computation of edge delays of the element associated with said selected element vertex;
- optimizing the circuit element associated with said selected element vertex by changing one or more characteristics of said circuit element;
- updating the edge delays of the edges associated with said selected element vertex as a result of the local optimization;
- invalidating the backward delay values at element vertices immediately succeeding said selected element vertex;
- invalidating backward delay values at all predecessor vertices of said immediately succeeding vertices;
- and
- repeating said selecting, calculating, optimizing, updating, and invalidating steps with respect to each element vertex of said set of element vertices.
A method of using a computer to perform a time-driven optimization on a logic circuit represented as a set of input vertices, element vertices for associated circuit elements, and output vertices, and a set of edges connecting ordered pairs of vertices, comprising the steps of:
- calculating a forward delay value at each vertex of the logic circuit;
- for a given input vertex, selecting a set of element vertices on all paths from that input vertex to an output vertex;
- selecting one element vertex from said set of element vertices for local computation, on a depth first traversal basis;
- calculating a path length at said selected element vertex, wherein said path length includes a computation of edge delays of the element associated with said selected element vertex;
- optimizing the circuit element associated with said selected element vertex by changing one or more characteristics of said circuit element;
- updating the edge delays of the edges associated with said selected element vertex as a result of the local optimization;
- invalidating the forward delay values at element vertices preceding said selected element vertex;
- and
- repeating said selecting, calculating, optimizing, updating, and invalidating steps with respect to each element vertex of said set of element vertices.
A method for optimizing a logic circuit represented as a set of input vertices, element vertices for associated circuit elements, and output vertices, plus directional edges connecting ordered pairs of vertices, comprising the steps of:
- (a) calculating forward delays for each element vertex from each input vertex which connects to said each element vertex by a path of said edges, and storing said forward delays in a forward delay table;
- (b) for each element vertex along the paths made of sets of said edges from an input vertex to all output vertices which connect to said input vertex:
- (1) calculating backward delay for said element vertex;
- (2) determining if the forward delay for said element vertex in said forward delay table is valid and, if not, calculating the forward delay for said element vertex;
- (3) optimizing said element vertex by changing one or more characteristics of said associated circuit element;
- and
- (4) if said element vertex is changed by said optimization, invalidating the forward delays in said forward delay table for all element vertices preceding said element vertex;
- (c) repeating foregoing step (b) for each input vertex.
Dependencies are inferred from the claim text.