Parallel Tree Search for Combinatorial Problems: a Comparative Study between OpenMP and MPI, .
Michaël Krajecki, Christophe Jaillet, Alain Bui · Studia informatica universalis · 2008
In this paper, a general approach for solving combinatorial problems in parallel is proposed. This study is done using the Constraint Satisfaction Problems (CSPs) formalism. The tasks are generated a priori by considering the subtrees at a particular depthlevel and represent a partition of the search space. They may be independent or the algorithms may take advantage of a collaboration mechanism between the processors. The parallel algorithm introduces few modications to the sequential one. The tasks arrangement between the processors is studied with different load balancing strategies, comparing shared memory and a message passing scheme. Then the Langford problem and optimal Golomb ruler construction are studied and parallelized. The former is a combinatorial problem and the latter a combinatorial optimization one. The applications associated with these problems are written in C, using the standard OpenMP library or the MPI message passing interface. The parallelization of these two applications proved efcient on up to 128 processors and opens up some new perspectives for these particular problems, such as solving the already solved instances of the problems more quickly and solving further open instances in the future.