Lock-free state merging in parallelized constraint...

Details Lock-free state merging in parallelized constraint... Lock-free state merging in parallelized constraint...

2006-11-20

2009-06-02

Chiang, Jack (Department: 2825)

Computer-aided design and analysis of circuits and semiconductor

Nanotechnology related integrated circuit design

C703S022000, C706S010000, C706S011000, C706S019000, C706S026000

Reexamination Certificate

active

07543266

ABSTRACT:
Solver state merging in parallel constraint satisfaction problem (CSP) solvers. Solver state during processing of a computational thread of parallel CSP solvers is represented as a set of support graphs. The support graphs are merged in a pairwise fashion, yielding a new conflict-free graph. The merge process is free of cycles, conflicts are removed, and thread processing is lock-free. The architecture can be applied, generally, in any CSP solver (e.g., a Boolean SAT solver) having certain formal properties. A system is provided that facilitates solver processing, the system comprising a bookkeeping component for representing input solver state of a computational thread as a set of graphs, and a merge component for pairwise merging of at least two input graphs of the set of graphs into a merged graph that represents final state of the computational thread.

REFERENCES:
patent: 4918621 (1990-04-01), Nado et al.
patent: 5276775 (1994-01-01), Meng
patent: 5469367 (1995-11-01), Puri et al.
patent: 6038392 (2000-03-01), Ashar et al.
patent: 7203917 (2007-04-01), Ganai et al.
patent: 2003/0084411 (2003-05-01), Moskewicz et al.
patent: 2005/0021486 (2005-01-01), Naveh
patent: 2005/0216871 (2005-09-01), Prasad et al.
patent: 2005/0222827 (2005-10-01), Emek et al.
patent: 2005/0278702 (2005-12-01), Koyfman et al.
patent: WO2006020729 (2006-02-01), None
Marques-Silva et al., GRASP: A Search Algorithm for propositional Satisfiability, May 199, IEEE, vol. 48, pp. 506-521.

Affiliated with

Also associated with

Rating

Lock-free state merging in parallelized constraint... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Lock-free state merging in parallelized constraint..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Lock-free state merging in parallelized constraint... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-4129369