Scalable Parallel Arc Consistency Algorithms for Shared Memory Computers

摘要

Constraint satisfaction problems (CSPs) are prevalent in artificial intelligenceapplications. One approach to assist in solving CSPs is to preprocess the problem by eliminating variable assignments which can never result in a solution. This can be done by using consistency algorithms to pre-process a network of constraints before the tree search. In this paper we introduce three scalable Static Parallel Arc Consistency algorithms (SPAC-1, SPAC-2, SPAC-3) designed for any general-purpose shared memory Multiple Instruction-stream, Multiple Data-stream (MIMD) computer. We ensure arc consistency of a finite domain binary constraint network. Through actual machine experimentation we measure work performed by the SPAC algorithms and compare it with work performed by existing sequential algorithms, AC-1 and AC-3. Results show that our parallel arc consistency algorithms can be effectively used to pre-process a constraint network.