US 8,799,840 B1 · Branch and bound techniques for computation of critical timing conditions

Abstract

In one embodiment of the invention, a method for electronic circuit design is disclosed. The method includes analyzing a hierarchy of a netlist of a circuit to determine primary inputs and primary outputs of the circuit at an upper level, and internal vertices of the circuit at lower levels between the primary inputs and the primary outputs; forming a timing graph of the circuit including a plurality of timing delay edges representing timing delay between the primary inputs, the internal vertices and the primary outputs to form a plurality of paths of a path space from the primary inputs to the primary outputs; and in response to the timing delay of the plurality of timing delay edges, dynamically pruning paths of the plurality of paths using branch and bound techniques on bounds of timing delay that are a function of one or more circuit parameters to reduce the path space down to one or more critical timing paths of the circuit with a worse case metric of timing delay between the primary inputs and the primary outputs. Additionally or alternatively, timing in the circuit may be analyzed to determine a bound of timing delay of the circuit for one or more parameter corners in a parameter space and if the bound of timing delay is worse than a threshold time delay then one or more parameter corners may be pruned from the parameter space using branch and bound techniques.

Claims46

Dependent claims

A method of analyzing an electronic circuit design, the method comprising:

analyzing a hierarchy of a netlist of a circuit to determine one or more primary inputs (PI) and one or more primary outputs (PO) of the circuit at an upper level, and one or more internal vertices of the circuit at lower levels between the one or more primary inputs (PI) and the one or more primary outputs (PO);
forming a plurality of paths in a path space from the one or more primary inputs (PI) to the one or more primary outputs (PO) through the one or more internal vertices, wherein the plurality of paths represent a plurality of timing delays as a function of a plurality of circuit parameters and process corners;
dynamically pruning portions of the plurality of paths in the path space using branch and bound techniques on bounds of timing delay to reduce the path space down to one or more critical timing paths of the circuit with a worse case metric of timing delay between the one or more primary inputs (PI) and the one or more primary outputs (PO), wherein the dynamically pruning of portions of the plurality of paths using branch and bound techniques includes searching over all complete paths in the path space that end at each of the one or more primary outputs for the one or more critical timing paths of the circuit;
and
wherein one or more of the analyzing, the forming, and the dynamically pruning are performed with a processor.

2 more elements

A system for analyzing an electronic circuit design, the system comprising:

one or more processors to execute machine readable instructions to analyze a circuit design;
and
a storage device coupled to the one or more processors, the storage device to store the machine readable instructions including
machine readable instruction to analyze a hierarchy of a netlist of a circuit to determine one or more primary inputs (PI) and one or more primary outputs (PO) of the circuit at an upper level, and one or more internal vertices of the circuit at lower levels between the one or more primary inputs (PI) and the one or more primary outputs (PO);
machine readable instruction to form a plurality of paths in a path space from the one or more primary inputs (PI) to the one or more primary outputs (PO) through the one or more internal vertices, wherein the plurality of paths represent a plurality of timing delays as a function of a plurality of circuit parameters and process corners;
and
machine readable instructions to dynamically prune portions of the plurality of paths in the path using branch and bound techniques on bounds of timing delay to reduce the path space down to one or more critical timing paths of the circuit with a worse case metric of timing delay between the one or more primary inputs (PI) and the one or more primary outputs (PO), wherein the dynamically pruning of portions of the plurality of paths using branch and bound techniques includes searching over all complete paths in the path space that end at each of the one or more primary outputs for the one or more critical timing paths of the circuit.

4 more elements

A machine readable product for analyzing an electronic circuit design, the machine readable product comprising:

a machine readable storage device having stored therein
machine readable instruction to analyze a hierarchy of a netlist of a circuit to determine one or more primary inputs (PI) and one or more primary outputs (PO) of the circuit at an upper level, and one or more internal vertices of the circuit at lower levels between the one or more primary inputs (PI) and the one or more primary outputs (PO);
machine readable instruction to form a plurality of paths in a path space from the one or more primary inputs (PI) to the one or more primary outputs (PO) through the one or more internal vertices, wherein the plurality of paths represent a plurality of timing delays as a function of a plurality of circuit parameters and process corners, wherein the plurality of paths represent a plurality of timing delays as a function of a plurality of circuit parameters and process corners;
and
machine readable instructions to dynamically prune portions of the plurality of paths in the path using branch and bound techniques on bounds of timing delay to reduce the path space down to one or more critical timing paths of the circuit with a worse case metric of timing delay between the one or more primary inputs (PI) and the one or more primary outputs (PO), wherein the dynamically pruning of portions of the plurality of paths using branch and bound techniques includes searching over all complete paths in the path space that end at each of the one or more primary outputs for the one or more critical timing paths of the circuit.

2 more elements

Dependencies are inferred from the claim text.

Branch and bound techniques for computation of critical timing conditions

Life of this patent

Branch and bound techniques for computation of critical timing conditions

Life of this patent

Abstract

Claims46