Dynamic weighting and/or target zone analysis in timing driven placement of cells of an integrated circuit design

• US 6,415,426 B1
• Filed: 06/02/2000
• Issued: 07/02/2002
• Est. Priority Date: 06/02/2000
• Status: Expired due to Fees

• Current Assignee: Incentia Design Systems Incorporated
• Original Assignee: Incentia Design Systems Incorporated
• Inventors: Huang, Shiang-Tang, Chen, Ihao, Chang, Shing-Chong, Xiang, Xuequn
• Primary Examiner(s): Smith, Matthew
• Assistant Examiner(s): Dinh, Paul
• Application Number:
  US09/586,217
• Time in Patent Office: 760 Days
• Field of Search: 716/6-13, 716/1-2, 716/16-18
• US Class Current: 716/113
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement

Abstract

A novel global placement process and associated computer software are provided for global placement of functional cells of an integrated circuit design. The global placement process is recursive and timing driven. Functional cells are placed according to how that placement is likely to influence signal timing. Also, a novel detailed placement process and associated computer software is provided for detailed placement of functional cells of an integrated circuit design. Target zones are defined which provide indications of the timing impact of functional cell movement. A detailed search for improved cell placements is conducted in which target zones are used to assess the signal timing impact of proposed cell movements. The novel global placement produces a global cell placement result, and the novel detailed placement process produces an improved detailed placement result.

Claims

1. A method of determining placement of functional cells of a circuit design on a carrier using a computer and a computer readable storage medium, a specification of connectivity among cells of the circuit design and a specification of signal timing requirements among cells of the circuit design, the method comprising:

producing at least one information structure in the storage medium that provides indications of connectivity relationships among cells of the circuit design;

determining respective predicted criticality of respective paths among cells defined by respective connectivity relationships between respective cells of the circuit design;

allocating at least a portion of the storage medium to store proposed cell placement information for the circuit design;

providing a recursion limit; and

recursively,

determining respective proposed placement criticality of respective paths among cells of the circuit design based on a current proposed placement of the cells;

determining respective current weights corresponding to respective connectivity relationships based upon respective predicted and respective proposed placement criticality of respective paths among cells defined by such respective connectivity relationships;

associating, in the storage medium, respective current weights with corresponding respective connectivity relationships; and

modifying respective cell placement information in the storage medium based on respective connectivity relationships and respective current weights in the storage medium to produce a current proposed placement of the cells in the circuit design; and

continuing to recurs until the limit is reached.

2. The method of claim 1 further including:

providing, in the storage medium, a representation of one or more placement regions that correspond to at least a portion of the carrier; and

wherein modifying respective cell placement information results in modification of one or more respective current proposed cell placements in one or more of the placement regions.

3. The method of claim 1 further including:

providing, in the storage medium, a representation of one or more placement regions that correspond to at least a portion of the carrier; and

wherein modifying respective cell placement information results in modification of one or more respective current proposed cell placements in one or more of the placement regions in accordance with a quadratic optimization process.

4. The method of claim 1 wherein determining respective proposed physical placement criticality further includes:

analyzing respective current signal timing for respective paths among cells of the circuit design based on a current proposed physical placement of cells;

comparing the respective current signal timing for respective paths for the current proposed physical placement of cells with specified signal timing for the respective paths.

5. The method of claim 1 wherein determining respective predicted criticality further includes:

analyzing respective predicted signal timing for respective paths among cells of the circuit design based on a statistical model of cell placement;

comparing the respective predicted signal timing for respective paths for the statistical model of cell placement with specified signal timing for the respective paths.

6. The method of claim 1,

wherein determining respective current weights involves increasing the relative importance of respective proposed placement criticality with increasing convergence upon the recursion limit.

7. The method of claim 1,

wherein determining respective current weights involves increasing the relative importance of respective proposed placement criticality with increasing number of recursions.

8. The method of claim 1,

wherein providing a recursion limit includes establishing a run time limit;

and

wherein determining respective weights involves increasing the relative importance of respective current proposed placement criticality with convergence upon the run time limit.

9. The method of claim 1,

wherein providing a recursion limit includes establishing a prescribed timing quality;

and further including;

determining current timing quality after arranging respective cells of the circuit design to produce a proposed placement of the cells;

wherein determining respective weights involves increasing the relative importance of respective proposed physical placement criticality with convergence of current timing quality upon the prescribed timing quality.

10. The method of claim 1 further including:

partitioning one or more placement regions into smaller placement regions with successive recursions;

wherein providing a recursion limit involves providing a target placement region size;

wherein modifying respective cell placements involves placing respective cells in increasingly smaller placement regions with successive recursions.

11. The method of claim 1 further including:

partitioning the one or more placement regions into smaller placement regions with successive recursions;

wherein providing a recursion limit involves providing a target partition region size and cell density within placement regions;

wherein modifying respective cell placements involves placing respective cells in increasingly smaller placement regions with successive recursions;

wherein providing a recursion limit includes establishing a target placement region size; and

wherein determining respective weights involves increasing the relative importance of respective proposed placement criticality with convergence upon the target placement size and the cell density within placement regions.

12. The method of claim 1 further including:

partitioning the placement region into smaller partition regions with successive recursions;

wherein providing a recursion limit involves providing a target partition region size;

wherein modifying respective cell placements involves placing respective cells in increasingly smaller partition regions with successive recursions;

wherein providing a recursion limit includes establishing a target partition size; and

wherein determining respective weights involves increasing the relative importance of respective proposed placement criticality with convergence upon the target partition size.

13. The method of claim 1 further including:

partitioning the placement region into smaller partition regions with successive recursions;

wherein providing a recursion limit involves providing a target partition region size and cell density within partition regions;

wherein modifying respective cell placements involves placing respective cells in increasingly smaller partition regions with successive recursions;

wherein providing a recursion limit includes establishing a target partition size; and

wherein determining respective weights involves increasing the relative importance of respective proposed physical placement criticality with convergence upon the target partition size and the cell density within partition regions.

14. The method of claim 1,

wherein determining respective proposed placement criticality further includes:

analyzing respective current signal timing for respective paths among cells of the circuit design based on a current proposed placement of cells; and

comparing the respective current signal timing for respective paths for the current proposed physical placement of cells with specified signal timing for the respective paths; and

wherein determining respective predicted criticality further includes;

analyzing respective predicted signal timing for respective paths among cells of the circuit design based on a statistical model of cell placement; and

comparing the respective predicted signal timing for respective paths for the statistical model of cell placement with specified signal timing for the respective paths.

15. The method of claim 1,

wherein at the start of a first recursion there is no current placement;

and

wherein during a first recursion determining of respective current weights involves determining based upon respective predicted criticality without consideration of respective proposed physical placement criticality.

16. A method of placement of functional cells of a circuit design on a carrier using a computer and a computer readable storage medium, the method comprising:

providing a database of information in the storage medium which indicates connectivity relationships among functional cells and proposed overall physical placement of functional cells and signal timing requirements among cells;

defining respective target zone information respectively associated with respective cells of the circuit wherein respective target zones provide respective indications of the respective timing impact of changes in placement of respective associated cells;

storing respective target zone information in the storage medium;

providing a recursion limit; and

recursively,

determining whether a new search window is required;

specifying a new search window if required;

for each of a multiplicity of respective cells in the circuit design,

conducting a respective search for an improved placement of the respective cell within the search window by respectively evaluating one or more respective proposed detailed search movements, the respective evaluations including,

for each one or more respective cells that is proposed to be moved pursuant to a respective proposed detailed search movement and that is associated with respective target zone information, respectively assessing respective timing impact of the respective proposed detailed search movement based upon the respective target zone information associated with the respective cell;

respectively determining which, if any, proposed detailed search movement for the respective cell that is subject of the respective search to implement based upon the evaluations of the one or more proposed detailed search movements; and

respectively implementing the respective detailed search movement for the respective cell that is the subject of the respective search based upon the respective determination;

updating respective target zone information in the storage medium after a plurality of cell movements;

continuing to recurs until the recursion limit is reached.

17. The method of claim 16,

wherein the respective evaluations further include,

for each one or more respective cells that is proposed to be moved pursuant to a respective proposed detailed search movement, assessing at least one of the impact on wire length or the impact on routability of the respective proposed detailed search movement.

18. The method of claim 16,

wherein respective target zone information further provides an indication of which movements of a respective associated cell will have an unacceptable signal timing impact.

19. The method of claim 16,

wherein respective target zone information defines a respective region of the overall physical placement within which a respective associated cell can be moved without incurring a significant signal timing impact.

20. The method of claim 16 wherein defining respective target zones includes:

generating respective RC delay values associated with respective connectivity paths specified for the respective cells of the proposed cell placement;

performing a delay trace of the connectivity paths and associated RC values of the proposed cell placement so as to identify respective critical paths;

defining respective target zones for respective cells disposed on respective critical paths such that respective target zones provide respective indications of how movement of respective associated cells will influence timing performance of the circuit design.

21. The method of claim 16 wherein updating respective target zones includes:

generating respective updated RC delay values associated with respective connectivity paths specified for the respective cells of the proposed cell placement;

performing a local delay trace if a first number of cell movements has occurred since the last local delay trace;

performing an incremental delay trace if a second number of cell movements has occurred since the last incremental delay trace where the second number is greater than the first number; and

performing a global delay trace if a third number of cell movements has occurred since the last global delay trace where the third number is greater than the second number.

22. The method of claim 16 wherein defining respective target zones includes:

identifying respective cells with one or more respective pins disposed on a respective critical path of the circuit design;

for individual respective identified critical path cells,

determining respective desired interconnect delay timing limits associated with respective critical path pin pairs that respectively include at least one respective critical path pin; and

defining a respective associated target zone region within which respective placement of such individual respective critical path cell is likely to satisfy critical path timing requirements in view of respective determined desired interconnect delay timing limits.

23. The method of claim 16 wherein defining respective target zones includes:

identifying respective cells with one or more respective pin disposed on a respective critical path of the circuit design;

for individual respective identified critical path cells,

determining respective desired timing delay limits associated with respective nets that respectively include respective at least one critical path pin wherein respective timing delay limits include respective net loading delays; and

defining a respective associated target zone region within which respective placement of such individual respective critical path cell is likely to satisfy critical path timing requirements in view of respective determined timing delay limits.

24. The method of claim 16 wherein defining respective target zones includes:

identifying respective cells with one or more respective pins disposed on a respective critical path of the circuit design;

for individual respective identified critical path cells,

determining respective desired interconnect delay timing limits associated with respective critical path pin pairs that respectively include at least one respective critical path;

determining respective net loading delay limits associated with respective critical path pins;

determining respective desired timing delay limits respectively associated with respective critical path pins, wherein for each respective individual critical path pins, respective desired timing delay limits encompasses both a respective pin pair interconnect delay limit and a respective net loading delay limit associated with such respective individual critical path pin; and

defining a respective associated target zone region within which placement of such individual respective critical path cell is likely to satisfy respective desired timing delay limits of the one or more critical path pins associated with such respective individual critical path cell.

25. The method of claim 16 wherein defining respective target zones includes:

identifying respective cells with at least one respective pin disposed on a respective critical path of the circuit design;

for respective identified critical path cells,

determining respective pin pair interconnect delay limits respectively associated with respective critical path pins;

determining respective net loading delay limits respectively associated with respective critical path pins;

determining respective desired timing delay limits respectively associated with respective critical path pins, wherein the respective desired timing delay limits for individual critical path pins respectively encompass both respective corresponding pin pair interconnect delay limits and respective corresponding net loading delay limits; and

defining respective candidate zones respectively associated with respective critical path pins, wherein respective individual candidate zones for respective individual critical path pins respectively define respective individual placement regions within which placement of respective associated critical path pins is most likely to satisfy respective desired timing requirements respectively associated with such respective critical path pins;

defining a respective target zone for such respective identified critical path cell as including a respective overlap placement region in which respective candidate zones of all of the one or more critical path pins respectively associated with such critical path cell overlap.

26. The method of claim 16 wherein,

if a respective cell proposed to be moved is associated with a respective target zone, then assessing where the respective movement of such cell would place the cell relative to its target zone and by also assessing at least one of the impact on wire length or the impact on routability associated with such proposed cell movement.