Parallel CLP on Heterogeneous Networks

The combination of Or-Parallelism and Constraint Logic Programming (CLP) has proven to be very effective in tackling large combinatorial problems in real-life applications. However, existing implementations have focused on shared-memory multiprocessors. In this paper, we investigate how we can efficiently implement Or-Parallel CLP languages on heterogeneous networks, where communication bandwidth is much lower and heterogeneity requires all communication to be in a machine-independent format. Since a recomputation-based system has the potential to solve these problems, we analyse the performance of a prototype using this approach. On a representative set of CLP programs we show that close to optimal speedups can be obtained on networks for programs generating large search spaces and that the overhead of recomputation is surprisingly low. We compare this approach with that of stack-copying and also discuss how side-effects can be dealt with during recomputation. The main conclusion of the paper is that incremental recomputation is a clean and efficient execution model for Or-Parallel CLP systems on heterogeneous networks