Method for optimizing track assignment in a grid-based channel router
US5841664A · kind A · utility
Assignee
Inventors
Key dates
| Filing date | Mar 12, 1996 |
| Grant date | Nov 24, 1998 |
| Priority date | — |
| Expiry date | Mar 12, 2016 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F30/394
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A method for optimal track assignment in a grid-based channel router. Initially, interconnection information is extracted from a global routing result. Multiple pin nets derived from the interconnection information are decomposed into simpler mapped segments. A channel grid map is then built and marked with existing objects. Next, a vertical constraint graph specifying the relative positions of the mapped segments is constructed. A first track is computed. A track assignment loop is repeated until all requisite connections are realized. The track assignment loop includes the steps of breaking cycles and long paths and collecting a set of feasible links. One or more weighting functions are assigned to each such feasible link. A dynamic programming approach is used to select an optimal set of feasible links according to the weighting functions. In addition, an optimal set of feasible links corresponding to unpreferred layers is collected by applying dynamic programming. Finally, the chosen feasible links are physically realized on the current track.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.