In the context of combinatorial search and optimization, we present a parallel implementation of a constraint-based local search algorithm and investigate its performance on hardware with several hundreds of processors. We choose as constraint solving algorithm for these experiments the "adaptive search" method, an efficient sequential local search method for solving CSPs. The implemented algorithm is a parallel version of adaptive search in a multiple independent-walk manner, that is, each process is an independent search engine and there is no communication between the simultaneous computations. Performance evaluation on a variety of classical CSPs benchmarks shows that speedups are very good for a few tens of cores, and good up to a few hundreds of cores. More interestingly, experiments on highly combinatorial problems such as the Costas Array Problem show nearly linear speedups up to more than 8000 cores. Current work consists in investigating more complex parallelization schemes and also to develop probabilistic models that can predict the parallel speedups from the runtime distribution of the sequential runs.

Biography:
Philippe Codognet received a Ph.D. in Computer Science from the University of Bordeaux-I in 1989. From 1990 to 1998 he was a researcher at INRIA, the French National Research Center in Computer Science, and on sabbatical leave in 1997/8 at Sony Computer Science Laboratory in Paris. Since 1998, he is professor of Computer Science at University Pierre & Marie Curie (UPMC) in Paris.

After working as scientific attache' at the French Embassy in Tokyo from 2003 to 2007, he is on leave at CNRS (French National Center for Scientific Research) since 2007 and founded the Japanese-French Laboratory for Informatics (JFLI), a joint laboratory established in Tokyo in January 2009 and regrouping CNRS, UPMC, University of Tokyo, Keio University and the National Institute of Informatics (Japan).

More than one hundred publications in international journals and conferences describe his researches in programming languages, logic, constraint programming, combinatorial search, virtual agents and multimedia.