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.