Method for timing-directed circuit optimizations

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

Claim 2

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.

Claim 3

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.

Claim 4

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.

Claim 5

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.

Claim 6

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.