Simultaneous placement and routing (SPAR) method for integrated circuit physical design automation system
First Claim
1. A method of optimizing a cell placement for an integrated circuit chip, comprising the steps of:
- (a) routing said placement, wherein said placement includes congested areas and non-congested areas;
(b) Identifying said congested areas generated by said routing;
(c) selectively applying a congestion reduction algorithm only within said congested areas to alter said placement in said congested areas, wherein said congestion reduction algorithm comprises;
(c1) assessing individual cell cost values within said areas of increased congestion; and
(c2) relocating at least one cell having a highest cost value;
(d) computing a fitness of said placement; and
(e) if said fitness is below a predetermined value, repeating steps (b) to (d).
3 Assignments
0 Petitions
Accused Products
Abstract
An initial placement of cells for an integrated circuit chip is decomposed into a hierarchial order of groups of cells. The groups are routed simultaneously using parallel processors, and the results are recomposed to provide a global routing that provides a detailed mapping of cell interconnect congestion in the placement. Areas of high congestion are identified, and a congestion reduction algorithm is applied using the parallel processors to alter the placement in these areas simultaneously. The overall fitness of the placement is then computed, and if it has not attained a predetermined value, the steps of identifying congested areas and applying the congestion reduction algorithm to these areas are repeated. The cumulative error created by altering the placement without repeating the global routing is estimated, and if it exceeds a predetermined value, the global routing is also repeated.
96 Citations
32 Claims
-
1. A method of optimizing a cell placement for an integrated circuit chip, comprising the steps of:
-
(a) routing said placement, wherein said placement includes congested areas and non-congested areas; (b) Identifying said congested areas generated by said routing; (c) selectively applying a congestion reduction algorithm only within said congested areas to alter said placement in said congested areas, wherein said congestion reduction algorithm comprises; (c1) assessing individual cell cost values within said areas of increased congestion; and (c2) relocating at least one cell having a highest cost value; (d) computing a fitness of said placement; and (e) if said fitness is below a predetermined value, repeating steps (b) to (d). - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20)
-
-
21. A physical design automation system for optimizing a cell placement for an integrated circuit chip, comprising:
-
a router for routing said placement, wherein said placement includes congested and non-congested areas; a computer for performing operations of; identifying said congested areas generated by said router; selectively applying a congestion reduction algorithm only within said congested areas to alter said placement in said congested areas, wherein said congestion reduction algorithm comprises; assessing individual cell cost values within said areas of increased congestion; and relocating at least one cell having a highest cost value; and computing a fitness of said placement; and a controller for controlling the computer to repeat performing said operations until said fitness attains a predetermined value. - View Dependent Claims (22, 23, 24, 25, 26, 27)
-
-
28. A method for optimizing cell placement over a global area on an integrated circuit chip, comprising the steps of:
-
fixing an initial cell placement within said global area; routing wiring between cells placed by said fixing step; determining wiring congestion for isolated areas within said global area; identifying congested isolated areas having greater wiring congestion than other non-congested isolated areas; selectively applying a congestion reduction algorithm only within said congested isolated areas, wherein said congestion reduction algorithm comprises; accessing individual cell cost values within said areas of increased congestion; and relocating at least one cell having a highest cost value; computing a fitness of said cell placement; and repeating said determining, identifying, selectively applying, and computing steps until said fitness improves to within a predetermined range. - View Dependent Claims (29, 30, 31, 32)
-
Specification