  Local search is a successful approach for solving combinatorial optimization
and constraint satisfaction problems. With the progressing 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 algorithms. Such is the case for local search algorithms when run on
hundreds or thousands of processing units. In this paper, we discuss some
experiments we have been doing with Adaptive Search and present a new parallel
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.
