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

摘要

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

主权项

1.一种便于约束解算机处理的计算机实现的系统(100)，包括：用于将计算线程的输入计算机状态(104)表示为一组支持图的薄记组件(102)；以及用于将所述一组支持图中的至少两个输入图成对地合并成表示所述计算线程的最终状态的合并图的合并组件(106)。