Load-balancing methods for parallel constraint solving

Program parallelization becomes increasingly important when new parallel and multi-core architectures provide ways to improve performance. In this paper, we address parallel search in constraint programming (CP) by proposing several load-balancing methods. We show how these methods improve the execution-time scalability of constraint programs. Scalability is the greatest challenge of parallelism and it is particularly an issue in constraint programming, where load-balancing is difficult. We address this problem by proposing CP-specific load-balancing methods and evaluating them using benchmark problems. Our experimental results show that the methods behave differently well depending on the type of problem.