Method and apparatus for generating steiner trees using simultaneous blockage avoidance, delay optimization and design density management
US7127696B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Dec 17, 2003 |
| Grant date | Oct 24, 2006 |
| Priority date | — |
| Expiry date | Jan 5, 2025 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F30/394
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A mechanism for constructing Steiner trees using simultaneous blockage avoidance, delay optimization, and design density management are provided. An initial tiled timing-driven Steiner tree is obtained for an integrated circuit design. The Steiner tree is broken into 2-paths for which plates are generated designated the permissible area in which a Steiner point may migrate. Each 2-path is optimized by calculating a cost for each tile in the plate as a function of an environmental cost, a tile delay cost, and a trade-off value. A minimum cost tile is then selected as the point to which the Steiner point in the 2-path, if any, is to migrate. Once each 2-path is processed in this manner, routing is performed so as to minimize the cost at the source. This process may be iteratively repeated with new trade-off values until all of the nets have zero or positive slew.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.