Integrating a boolean SAT solver into a router

Details Integrating a boolean SAT solver into a router Integrating a boolean SAT solver into a router

2011-03-08

2011-03-08

Siek, Vuthe (Department: 2825)

Computer-aided design and analysis of circuits and semiconductor

Integrated circuit design processing

Physical design processing

Reexamination Certificate

active

07904867

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.

REFERENCES:
patent: 2007/0101303 (2007-05-01), Lien et al.
Nam et al., “Hybrid Routing for FPGAs by Integrating Boolean Satisfiability with Geometric Search”, Field-Programmable Logic and Applications: Reconfigurable Computing Is Going Mainstream, vol. 2438, pp. 360-369, 2002.
Silva et al., “GRASP—A New Search Algorithm for Satisfiability”, IEEE/ACM International Conference on Computer-Aided Design 1996, pp. 220-227.

Affiliated with

Also associated with

Rating

Integrating a boolean SAT solver into a router does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Integrating a boolean SAT solver into a router, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Integrating a boolean SAT solver into a router will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2742036