G - Physics – 06 – F
Patent
G - Physics
06
F
G06F 15/16 (2006.01) G06F 9/06 (2006.01)
Patent
CA 2668121
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.
La présente invention concerne des la fusion d'état de résolveurs dans des résolveurs de problèmes de satisfaction de contraintes parallèles. L'état de résolveurs lors du traitement d'unité d'exécution de calcul de résolveurs de problèmes de satisfaction de contraintes parallèles est représenté sous forme d'un ensemble de graphes de support. Les graphes de support sont fusionnés en paires, donnant lieu à un nouveau graphe exempt de conflit. Le procédé de fusion est exempt de cycles, des conflits sont supprimés généralement dans tout résolveur de problèmes avec contraintes (par exemple un solveur SAT booléen) ayant certaines propriétés formelles. L'invention concerne un système qui facilite le traitement de résolveurs, le système comportant un composant de tenue de comptes pour représenter l'état de résolveurs d'entrée d'une unité d'exécution de calcul sous forme d'un ensemble de graphes, et un composant de fusion pour la fusion en paires d'au moins deux graphes d'entrée de l'ensemble de graphes dans un graphe fusionné qui représente un état final de l'unité d'exécution de calcul.
Microsoft Corporation
Smart & Biggar
LandOfFree
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.
Profile ID: LFCA-PAI-O-1623274