Simultaneous placement and routing (SPAR) method for integrated circuit physical design automation system
US5875117A · kind A · utility
Assignee
Inventors
Key dates
| Filing date | Apr 23, 1996 |
| Grant date | Feb 23, 1999 |
| Priority date | — |
| Expiry date | Apr 23, 2016 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F30/392
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
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.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.