On the Scalability of Constraint Programming on Hierarchical Multiprocessor Systems

Recent developments in computer architecture progress towards connected systems with a large core count, which expose more parallelism to applications, creating a hierarchical setup at the node and cluster levels. Declarative approaches such as those based on constraints are attractive to parallel programming because they concentrate on the logic of the problem. They have been successfully applied to hard problems, which usually involve searching through large problem spaces. Search lends itself naturally to parallelisation by exploiting different branches of the search tree, but scalability may be hard to achieve due to the highly dynamic load balancing requirements. In this paper we present a high-level declarative approach based on constraints and show how it benefits from efficient work-stealing based dynamic load balancing, targeted at large-scale. Our study leverages the implementation of a hierarchical work stealing scheme using a different programming model, GPI. Experimentation brought encouraging results on up to 512 cores on large instances of satisfaction and optimisation problems.