Incremental slack margin propagation

Patent metadata

Field	Value
Publication number	US-9280625-B2
Application number	US-201514860450-A
Country	US
Kind code	B2
Filing date	Sep 21, 2015
Priority date	Dec 2, 2011
Publication date	Mar 8, 2016
Grant date	Mar 8, 2016

Abstract

Techniques and systems are described for improving the efficiency of timing calculations in numerical sequential cell sizing and for improving the efficiency of incremental slack margin propagation. Some embodiments cache timing-related information associated with a source driver that drives an input of a sequential cell that is being sized, and/or timing-related information for each output of the sequential cell that is being sized. The cached timing-related information for the source driver can be reused when sizing a different sequential cell. The cached timing-related information for the outputs of the sequential cell can be reused when evaluating alternatives for replacing the sequential cell. Some embodiments incrementally propagate slack margins in a lazy fashion (i.e., only when it is necessary to do so for correctness or accuracy reasons) while sizing gates in the circuit design in a reverse-levelized processing order.

First claim

What is claimed is:

1. In an electronic design automation (EDA) tool in a computer, a method for incrementally propagating slack margins in a circuit design while optimizing the circuit design by processing gates in the circuit design in a reverse-levelized order, the method comprising:
after the EDA tool in the computer replaces a first gate with an alternative gate, the EDA tool in the computer marking outputs of source drivers that drive inputs of the alternative gate as out-of-date;
in response to the EDA tool in the computer determining that an output of a source driver is marked out-of-date, the EDA tool in the computer performing at least the following operations: (1) computing a new arrival time at the output of the source driver, (2) propagating the new arrival time to inputs of gates that are driven by the output of the source driver, and (3) removing an out-of-date mark from the output of the source driver;
in response to the EDA tool in the computer determining that an input of a second gate is marked out-of-date or that a slack margin was not computed for an output of the second gate, the EDA tool in the computer performing at least the following operations: (1) propagating arrival times from the input to the output of the second gate, and (2) marking the output of the second gate as having an out-of-date slack margin; and
in response to the EDA tool in the computer determining that an output of a third gate is marked as having an out-of-date slack margin, the EDA tool in the computer performing at least the following operations: (1) computing new slack margins for the output of the third gate based on the old arrival time, new arrival time, and old slack margin at the output of the third gate, and (2) computing new slack margins for each input of the third gate based on a new margin at the output of the third gate and an arrival time from each input of the third gate to the output of the third gate.

2. The method of claim 1 , wherein processing gates in the circuit design in a reverse-levelized order comprises:
assigning a level to each gate in the circuit design, wherein the assigned level is greater than the levels assigned to gates in the fan-out cone of the gate; and
processing gates in increasing order of their assigned levels.

3. The method of claim 1 , wherein a slack margin at a pin in the circuit design represents an extent to which a change in a slack value at the pin affects a slack value at a timing end-point.

4. A non-transitory computer-readable storage medium storing instructions of an electronic design automation (EDA) tool that, when executed by a computer, cause the computer to perform a method for incrementally propagating slack margins in a circuit design while optimizing the circuit design by processing gates in the circuit design in a reverse-levelized order, the method comprising:
after replacing a first gate with an alternative gate, marking outputs of source drivers that drive inputs of the alternative gate as out-of-date;
in response to determining that an output of a source driver is marked out-of-date, performing at least the following operations: (1) computing a new arrival time at the output of the source driver, (2) propagating the new arrival time to inputs of gates that are driven by the output of the source driver, and (3) removing an out-of-date mark from the output of the source driver;
in response to determining that an input of a second gate is marked out-of-date or that a slack margin was not computed for an output of the second gate, performing at least the following operations: (1) propagating arrival times from the input to the output of the second gate, and (2) marking the output of the second gate as having an out-of-date slack margin; and
in response to determining that an output of a third gate is marked as having an out-of-date slack margin, performing at least the following operations: (1) computing new slack margins for the output of the third gate based on the old arrival time, new arrival time, and old slack margin at the output of the third gate, and (2) computing new slack margins for each input of the third gate based on a new margin at the output of the third gate and an arrival time from each input of the third gate to the output of the third gate.

5. The non-transitory computer-readable storage medium of claim 4 , wherein processing gates in the circuit design in a reverse-levelized order comprises:
assigning a level to each gate in the circuit design, wherein the assigned level is greater than the levels assigned to gates in the fan-out cone of the gate; and
processing gates in increasing order of their assigned levels.

6. The non-transitory computer-readable storage medium of claim 4 , wherein a slack margin at a pin in the circuit design represents an extent to which a change in a slack value at the pin affects a slack value at a timing end-point.

7. An electronic design automation (EDA) apparatus, comprising:
a processor; and
a non-transitory computer-readable storage medium storing instructions of an EDA tool that, when executed by the processor, cause the EDA apparatus to perform a method for incrementally propagating slack margins in a circuit design while optimizing the circuit design by processing gates in the circuit design in a reverse-levelized order, the method comprising:
after replacing a first gate with an alternative gate, marking outputs of source drivers that drive inputs of the alternative gate as out-of-date;
in response to determining that an output of a source driver is marked out-of-date, performing at least the following operations: (1) computing a new arrival time at the output of the source driver, (2) propagating the new arrival time to inputs of gates that are driven by the output of the source driver, and (3) removing an out-of-date mark from the output of the source driver;
in response to determining that an input of a second gate is marked out-of-date or that a slack margin was not computed for an output of the second gate, performing at least the following operations: (1) propagating arrival times from the input to the output of the second gate, and (2) marking the output of the second gate as having an out-of-date slack margin; and
in response to determining that an output of a third gate is marked as having an out-of-date slack margin, performing at least the following operations: (1) computing new slack margins for the output of the third gate based on the old arrival time, new arrival time, and old slack margin at the output of the third gate, and (2) computing new slack margins for each input of the third gate based on a new margin at the output of the third gate and an arrival time from each input of the third gate to the output of the third gate.

8. The EDA apparatus of claim 7 , wherein processing gates in the circuit design in a reverse-levelized order comprises:
assigning a level to each gate in the circuit design, wherein the assigned level is greater than the levels assigned to gates in the fan-out cone of the gate; and
processing gates in increasing order of their assigned levels.

9. The EDA apparatus of claim 7 , wherein a slack margin at a pin in the circuit design represents an extent to which a change in a slack value at the pin affects a slack value at a timing end-point.

Assignees

• Synopsys Inc

Inventors

• Mottaez Amir H
• Iyer Mahesh A

Classifications

• G06F2119/12

  Timing analysis or timing optimisation · CPC title

• G06F30/00

  Computer-aided design [CAD] · CPC title

• G06F30/398

  Design verification or optimisation, e.g. using design rule check [DRC], layout versus schematics [LVS] or finite element methods [FEM] (optical proximity correction [OPC] design processes G03F1/36) · CPC title

• G06F17/5031 Primary

  Physics · mapped topic

• G06F30/327 Primary

  Logic synthesis; Behaviour synthesis, e.g. mapping logic, HDL to netlist, high-level language to RTL or netlist · CPC title