×

Lock-free state merging in parallelized constraint satisfaction problem solvers

  • US 7,543,266 B2
  • Filed: 11/20/2006
  • Issued: 06/02/2009
  • Est. Priority Date: 11/20/2006
  • Status: Active Grant
First Claim
Patent Images

1. A computer-implemented system that facilitates constraint solver processing, comprising:

  • a bookkeeping component for representing input solver state of a computational thread as a set of graphs, the input solver state received from parallel solvers operating on the computational thread;

    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;

    a propagation component for constraint propagation to generate completeness in the merged graph, wherein the propagation component facilitates non-chronological backtracking as part of the constraint propagation to directly change an earlier assumption without changing an intermediate assumption and the propagation component facilitates adding more than one learned constraint during constraint propagation of the merged graph for the parallel solvers, which are parallel SAT solvers, wherein the representing input set of support graphs to be merged by the merge component are conflict-free support graphs.

View all claims
  • 2 Assignments
Timeline View
Assignment View
    ×
    ×