Method for timing-directed circuit optimizations

• US 5,629,859 A
• Filed: 09/12/1994
• Issued: 05/13/1997
• Est. Priority Date: 10/21/1992
• Status: Expired due to Term

• Current Assignee: Texas Instruments, Inc.
• Original Assignee: Texas Instruments, Inc.
• Inventors: Bosshart, Patrick W., Agarwala, Sanjive
• Primary Examiner(s): Teska, Kevin J.
• Assistant Examiner(s): LOUIS JACQUES, JACQUES H
• Application Number:
  US08/304,625
• Time in Patent Office: 974 Days
• Field of Search: 364/488, 364/489, 364/490, 364/491, 326/41, 326/44, 326/101, 326/39, 326/38, 326/37, 395/143, 395/133, 395/500, 340/825.83, 371/22.1, 371/22.3, 371/22.5
• US Class Current: 716/108
• CPC Class Codes: G06F 30/327 Logic synthesis; Behaviour synthesis, e.g. mapping logic, HDL to netlist, high-level language to RTL or netlist

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.

Claims

1. 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.

2. 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.

3. 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.

4. A method as in claim 3 wherein said step of invalidating the forward delays further includes the step of updating any altered edge delays caused by said optimization.

5. A method as in claim 3 wherein said optimizing step further includes computing a new path length for each path in which the element is involved and determining if the optimization change is acceptable, if not, rejecting said optimization change.