Electronic design automation tool for the design of a semiconductor integrated circuit chip

• US 5,461,576 A
• Filed: 09/01/1993
• Issued: 10/24/1995
• Est. Priority Date: 09/01/1993
• Status: Expired due to Term

• Current Assignee: Synopsys Incorporated
• Original Assignee: ArcSys, Inc. (Synopsys Incorporated)
• Inventors: Tsay, Ren-Song, Chang, Chwen-Cher
• Primary Examiner(s): Teska, Kevin J.
• Assistant Examiner(s): Walker, Tyrone V.
• Application Number:
  US08/115,995
• Time in Patent Office: 783 Days
• Field of Search: 364/488, 364/489, 364/490, 364/491, 364/578
• US Class Current: 716/113
• CPC Class Codes: G06F 2119/12 Timing analysis or timing optimisation
• CPC Class Codes: G06F 30/327 Logic synthesis; Behaviour synthesis, e.g. mapping logic, HDL to netlist, high-level language to RTL or netlist
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement

Abstract

An electronic design automation tool embodiment uses a single slack graph structure throughout a process to provide communication between a placer (performing placement) and a timing constraint generator (performing slack distribution). The tool includes a slack graph generator, a timing calculator, a timing analyzer, a timing constraint generator and a net bounding box generator. A list of net constraints and a list of complete path constraints are fed to the slack graph generator during operation. Timing calculations from the delay calculator and zero net RC delays from a clustering process in a placer also provide input to the slack graph generator. The list of net constraints, a list of pin-to-pin constraints and a set of specifications for system clocking are input to the timing analyzer. The timing constraint generator receives a composite slack graph from the timing calculator, slack graph generator and timing analyzer. A refined slack graph is output to the net timing constraint generator for mincut placement and placement on an iterative basis. The net timing constraint can be presented in many format, such as limit on net bounding box.

Claims

1. An electronic design automation tool for the physical circuit design of a semiconductor integrated circuit (IC) chip from circuit and timing requirements, comprising:

a slack graph generator and processor for receiving a list of complete path constraints, a list of net constraints, a list of current-iteration edge delays, and for outputting for subsequent timing constraint generation a plurality of slack graphs with current-iteration slack values that represent a particular tentative physical placement of circuit nodes on said IC chip and their consequential signal propagation distances from one another expressed in time;

a timing calculator for receiving an initial placement information for the physical location of said circuit nodes on said IC chip and a refined placement information from a placer, and for calculating said list of current-iteration edge delays given said particular tentative physical placement of said circuit nodes;

a timing analyzer for receiving a set of specifications for system clocking, a list of combinational pin-to-pin constraints, a list of net constraints, and for outputting a plurality of slack graphs during an initialization stage in lieu of said slack graphs from the slack graph generator and processor, wherein each of said slack graphs represent a particular tentative physical placement of circuit nodes on said IC chip and their consequential signal propagation distances from one another expressed in time;

a timing constraint generator for generating a composite slack graph from slack graph inputs from the timing calculator, the slack graph generator and processor and the timing analyzer and including optimization means for minimizing a sum effect of all placement perturbations of the tentative physical to previously physically placed cells on said IC chip, expressed in formula form as;

##EQU4## where ##EQU5## is roughly proportional to a change in wire length (Δ

1) between nodes to achieve the required timing, Ri is estimated from the driving resistance, loading capacitance and per unit wire capacitance and resistance, such optimization being viewed as a component placement problem in which x_i, x_i is the component location, 1/R_i² is the equivalent connectivity c_ij between components i and j, and s_j S_ij are pin offsets and the optimum edge delay improvement Δ

d_ij, as determined by the timing constraint generator, is used directly as a placement constraint; and

a net bounding box generator for inputting said composite slack graph and for converting delay constraints into placement constraints to drive a placement process in said placer on an iterative basis, wherein the net bounding box generator generates net length constraints from Δ

d_ij for speed placement optimization;

wherein a last modified one of said slack graphs represents an ultimate description of the physical placement of circuit nodes that satisfies an input circuit design netlist and timing requirement.

2. An electronic design automation tool for the design of a semiconductor integrated circuit chip, comprising:

a slack graph having data storage for a plurality of representations for a netlist with nodes and edges between nodes, netlist connectivity of said nodes required to form a circuit, edge delay times, next target edge delays and slack times for edges and nodes, wherein the edge slack time is the difference between a required signal arrival time at a destination node and the sum of actual signal arrival times at a source node and an edge delay, and the node slack time is the difference between actual signal arrival time, given the current placement iteration, and target signal arrival time at a node;

a first iterative optimizer means including a placer connected to receive a plurality of next-target edge delays from the slack graph for adjusting a representation of the physical placement of said nodes, wherein said placement affects said edge delay times with a placer objective of achieving said next target edge delays between said placed nodes;

a timing calculator connected to receive a current-iteration physical node placement information from the placer for calculating the resulting edge delay times between said place-adjusted nodes;

a slack graph generator and processor connected to receive said calculated edge delay times from the timing calculator and for annotating and updating said slack graph edge delay times with said current-iteration calculated edge delay times and for correspondingly adjusting said slack time representations; and

a second iterative optimizer means including a timing constraint generator connected to receive said slack graph from the slack graph generator and processor for timing resource allocation by comparing an overall netlist design delay to an overall circuit delay computed from accumulated edge delay times of said current-iteration physical node placement information and, based on said comparison, for generating to the slack graph a new set of said target edge delays for recirculation through the slack graph to the placer for a next iteration, and wherein timing constraints on each of a plurality of nodes and a plurality of edge delays between said each of said nodes are individually precomputed and represented as slack and an arrival time improvement is computed for each;

wherein the first and second iterative optimizers respectively optimize placement and optimize intermediate edge delays on a global, overall circuit design level.

3. The tool of claim 2, further comprising:

a complete path constraints file means connected to provide an input of a user'"'"'s design with constraints to the slack graph generator and processor, wherein an initial data set of said representations is generated and loaded into the slack graph, which, in turn, is fed for the first time to the timing constraint generator.

4. The tool of claim 3, further comprising:

a net constraints file means connected to provide an input of a user'"'"'s design with constraints to the slack graph generator and processor.

5. The tool of claim 2, further comprising:

a net bounding box generator connected to receive said slack graphs from the timing constraint generator for converting target edge delays into placement constraints and to the placer for producing a placement for a next iteration.

6. The tool of claim 2, further comprising:

a timing analyzer for merging input information from included system clock specification file means and pin-to-pin timing constraints file means and for generating an initial data set of said representations to said slack graph and the timing constraint generator.

7. An electronic design automation tool for the physical circuit design of a semiconductor integrated circuit (IC) chip from circuit and timing requirements, comprising:

a slack graph generator and processor for receiving a list of complete path constraints, a list of net constraints, a list of current-iteration edge delays, and for outputting for subsequent timing constraint generation a plurality of slack graphs with current-iteration slack values that represent a particular tentative physical placement of circuit nodes on said IC chip and their consequential signal propagation distances from one another expressed in time;

a timing calculator for receiving an initial placement information for the physical location of said circuit nodes on said IC chip and a refined placement information from a placer, and for calculating said list of current-iteration edge delays given said particular tentative physical placement of said circuit nodes;

a timing analyzer for receiving a set of specifications for system clocking, a list of combinational pin-to-pin constraints, a list of net constraints, and for outputting a plurality of slack graphs during an initialization stage in lieu of said slack graphs from the slack graph generator and processor, wherein each of said slack graphs represent a particular tentative physical placement of circuit nodes on said IC chip and their consequential signal propagation distances from one another expressed in time; and

a timing constraint generator for generating a composite slack graph from slack graph inputs from the timing calculator, the slack graph generator and processor and the timing analyzer and including optimization means for minimizing a sum effect of all placement perturbations of the tentative physical to previously physically placed cells on said IC chip, expressed in formula form as;

##EQU6## where ##EQU7## where is roughly proportional to a change in wire length (Δ

1) between nodes to achieve the required timing, Ri is estimated from the driving resistance, loading capacitance and per unit wire capacitance and resistance, such optimization being viewed as a component placement problem in which x_i, x_j is the component location, 1/R_i² is the equivalent connectivity c_ij between components i and j, and s_j, s_ij are pin offsets and the optimum edge delay improvement Δ

d_ij, as determined by the timing constraint generator, is used directly as a placement constraint;

wherein a last modified one of said slack graphs represents an ultimate description of the physical placement of circuit nodes that satisfies an input circuit design netlist and timing requirement.