并行化的约束满足问题解算机中的无锁状态合并

摘要

并行约束满足问题(CSP)解算机中的解算机状态合并。并行CSP解算机的计算线程的处理期间的解算机状态被表示为一组支持图。这些支持图以成对的方式合并，从而产生一新的无冲突图。该合并过程是无循环的，冲突被移除并且线程处理是无锁的。该体系结构一般可应用于具有特定形式特性的任何CSP解算机(例如，布尔SAT解算机)。提供了一种便于解算机处理的系统，该系统包括用于将计算线程的输入解算机状态表示为一组图的薄记组件，以及用于将该组图中的至少两个输入图成对合并成表示该计算线程的最终状态的合并图的合并组件。

主权项

一种便于约束解算机处理的计算机实现的系统(100)，包括：用于将计算线程的输入解算机状态(104)表示为一组支持图的薄记组件(102)，所述输入解算机状态接收自运行在所述计算线程上的并行解算机；用于将所述一组支持图中的至少两个输入图成对地合并成表示所述计算线程的最终状态的合并图的合并组件(106)；以及用于约束传播以生成所述合并图的完整性的传播组件，所述传播组件便于作为所述约束传播的一部分来进行不按时间顺序的回溯以便在不改变中间假设的情况下直接改变早先的假设，并便于在并行解算机的合并图的约束传播期间添加不止一个学习到的约束，所述并行解算机是并行约束满足问题解算机，其所述合并图是无冲突的。