Experiments with massively parallel constraint solving

Abstract

The computing industry is currently facing a major architectural shift. Extra computing power is not coming anymore from higher processor frequencies, but from a growing number of computing cores and processors. For AI, and constraint solving in particular, this raises the question of how to scale current solving techniques to massively parallel architectures. While prior work focusses mostly on small scale parallel constraint solving, we conduct the first study on scalability of constraint solving on 100 processors and beyond in this paper. We propose techniques that are simple to apply and show empirically that they scale surprisingly well. These techniques establish a performance baseline for parallel constraint solving technologies against which more sophisticated parallel algorithms need to compete in the future. 1 Context and Goals of the Paper A major achievement of the digital hardware industry in the second half of the 20th century was to engineer processors whose frequency doubled every 18 months or so. It has now been clear for a few years that this period of ”free lunch”, as put by [Sutter, 2005], is behind us. The forecast of the industry is still that the available computational power will keep increasing exponentially, but the increase will from now on be in terms of number of processors available, not in terms of frequency per unit. This shift from ever higher frequencies to ever more processors1 is perhaps the single most significant development in the computing industry today. Besides the high-performance computing facilities readily accessible by many AI practitioners in academia and the industry, novel architectures provide large-scale parallelism: • Multi-Core processors are now the norm. Chip makers are predicting that the trend will from now on intensify from just a few cores to many [Held et al., 2006], a shift which raises significant challenges for software development