Parallel Impletation of Constraint Solving.
A. Ruiz-Andino, L. Araujo, F. Saez, J. J. Ruz.
Proc. of the 5th Parallel Computing Technologies (PaCT) 99,
LNCS 1662, Springer-Verlag, pp. 466--471, (1999).

Many problems from artificial intelligence can be described as
constraint satisfaction problems over finite domains (CSP(FD)), that is,
a solution is an assignment of a value to each problem variable such that
a set of constraints is satisfied. Arc-consistency algorithms remove
inconsistent values from the set of values that can be assigned to a
variable (its domain), thus reducing the search space. We have developed
a parallelisation scheme of arc-consistency to be run on MIMD multiprocessor.
The set of constraints is divided into N partitions, which are executed
in parallel on N processors. We discuss an important factor affecting
performance, the criterion to establish the partition in order to balance
the run-time workload. The parallelisation scheme has been implemented
on a CRAY T3E multiprocessor with up to thirty-four processors.
Empirical results on speedup and behaviour are reported and discussed.