Partitionnement Déterministe pour Résoudre les Problèmes de Programmation Par Contraintes en utilisant le Framework Parallèle Bobpp

Résumé : Cet article présente une stratégie de partitionnement déterministe pour paralléliser le parcours des espaces de recherche, dans le but de résoudre les problèmes de Programmation Par Contraintes (PPC). Ce travail est réalisé dans le cadre d'un projet industriel nommé PAJERO, dont le but est de proposer un solveur de PPC parallèle qui doit répondre toujours la même solution en utilisant le mode séquentiel ou parallèle. Il est clair que l'exploration parallèle des espaces de recherche modifie l'ordre dans lequel les nœuds solutions sont visités. Dans le contexte où la première solution trouvée est retournée à l'utilisateur, l'utilisation de plusieurs cœurs de calcul peut modifier la solution retournée. Dans la littérature, plusieurs stratégies non déterministes ont été proposées pour paralléliser l'exploration des espaces de recherche. La plupart de ces stratégies sont basées sur la technique de vol de travail (Work Stealing). Celle-ci est utilisée pour partitionner dynamiquement l'espace de recherche en sous-espaces, puis à affecter chaque sous-espace à un cœur de calcul. Notre étude consiste à rendre l'algorithme de recherche parallèle déterministe par rapport à l'algorithme séquentiel. Nous considérons que l'algorithme de recherche séquentielle est déterministe. La solution proposée est simple et élégante. Elle consiste à introduire un ordre total sur les nœuds, dans le but de retourner toujours la même solution que la première solution retournée en séquentiel, quel que soit le nombre de cœurs utilisés. Pour évaluer cette stratégie de partitionnement déterministe, nous avons effectué des expériences en utilisant un solveur de PPC nommé Google OR-Tools au-dessus de notre framework parallèle Bobpp. Les performances sont illustrées par la résolution des problèmes de PPC modélisés en utilisant le format FlatZinc.
Type de document :
Communication dans un congrès
Pascal Felber, Laurent Philippe, Etienne Riviere, Arnaud Tisserand. ComPAS 2014 : conférence en parallélisme, architecture et systèmes, Apr 2014, Neuchâtel, Suisse. 2014
Liste complète des métadonnées

https://hal.inria.fr/hal-01003040
Contributeur : Tarek Menouer <>
Soumis le : mercredi 11 juin 2014 - 09:48:31
Dernière modification le : jeudi 11 janvier 2018 - 06:21:31
Document(s) archivé(s) le : jeudi 11 septembre 2014 - 10:50:20

Fichiers

Identifiants

  • HAL Id : hal-01003040, version 1
  • ARXIV : 1406.2844

Collections

Citation

Tarek Menouer, Bertrand Le Cun. Partitionnement Déterministe pour Résoudre les Problèmes de Programmation Par Contraintes en utilisant le Framework Parallèle Bobpp. Pascal Felber, Laurent Philippe, Etienne Riviere, Arnaud Tisserand. ComPAS 2014 : conférence en parallélisme, architecture et systèmes, Apr 2014, Neuchâtel, Suisse. 2014. 〈hal-01003040〉

Partager

Métriques

Consultations de la notice

173

Téléchargements de fichiers

294