Computer Science > Distributed, Parallel, and Cluster Computing
[Submitted on 11 Jun 2014]
Title:Partitionnement Déterministe pour Résoudre les Problèmes de Programmation Par Contraintes en utilisant le Framework Parallèle Bobpp
View PDFAbstract:This paper presents a deterministic parallelization to explore a Constraint Programming search space. This work is an answer to an industrial project named PAJERO, which is in need of a parallel constraint solver which always responds with the same solution whether using sequential or parallel machines. It is well known that parallel tree search changes the order in which the exploration of solution space is done. In the context where the first solution found is returned, using a different number of cores may change the returned solution. In the literature, several non deterministic strategies have been proposed to parallelize the exploration of Constraint Programming search space. Most of them are based on the Work Stealing technique used to partition the Constraint Programming search space on demand and during the execution of the search algorithm. Our study focuses on the determinism of the parallel search versus the sequential one. We consider that the sequential search algorithm is deterministic, then propose an elegant solution introducing a total order on the nodes in which the parallel algorithm always gives the same solution as the sequential one regardless of the number of cores used. To evaluate this deterministic strategy, we ran tests using the Google OR-Tools Constraint Programming solver on top of our parallel Bobpp framework. The performances are illustrated by solving Constraint Programming problems modeled in FlatZinc format.
Submission history
From: Tarek Menouer [view email] [via CCSD proxy][v1] Wed, 11 Jun 2014 09:50:52 UTC (415 KB)
References & Citations
Bibliographic and Citation Tools
Bibliographic Explorer (What is the Explorer?)
Litmaps (What is Litmaps?)
scite Smart Citations (What are Smart Citations?)
Code, Data and Media Associated with this Article
CatalyzeX Code Finder for Papers (What is CatalyzeX?)
DagsHub (What is DagsHub?)
Gotit.pub (What is GotitPub?)
Papers with Code (What is Papers with Code?)
ScienceCast (What is ScienceCast?)
Demos
Recommenders and Search Tools
Influence Flower (What are Influence Flowers?)
Connected Papers (What is Connected Papers?)
CORE Recommender (What is CORE?)
arXivLabs: experimental projects with community collaborators
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.