Parallel Local Search : Experiments with a PGAS-based programming model

Abstract. Local search is a successful approach for solving combina-torial optimization and constraint satisfaction problems. With the pro-gressing move toward multi and many-core systems, GPUs and the quest for Exascale systems, parallelism has become mainstream as the number of cores continues to increase. New programming models are required and need to be better understood as well as data structures and algo-rithms. Such is the case for local search algorithms when run on hundreds or thousands of processing units. In this paper, we discuss some experi-ments we have been doing with Adaptive Search and present a new par-allel version of it based on GPI, a recent API and programming model for the development of scalable parallel applications. Our experiments on different problems show interesting speedups and, more importantly, a deeper interpretation of the parallelization of Local Search methods