Integrating a boolean SAT solver into a router
US7904867B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Apr 4, 2007 |
| Grant date | Mar 8, 2011 |
| Priority date | — |
| Expiry date | Apr 4, 2029 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F30/3323
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
One embodiment of the present invention provides a system that routes a set of pairs of points during the design of an integrated circuit (IC) chip. The system comprises a routing engine which is configured to search for a path to connect a current pair of points in the set of pairs of points, wherein the path comprises a set of rectangles and vertices. The routing engine uses a routing database, which keeps track of previously routed nets that can obstruct the routing of the current pair of points. The system further comprises a satisfiability (SAT) solver which is capable of solving a set of constraints, wherein the set of constraints are associated with the routability of the set of pairs of points. The SAT solver additionally comprises a SAT database which maintains the set of constraints and a current partial solution to the set of constraints. The SAT database is used to update the routing database if the current partial solution changes.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.