Introduction, Etat de l’art & incertitudes
Dans le cadre du projet Clariprint, le temps de calcul est une composante fondamentale de la réussite du projet. Ce dernier conditionne d’une part la qualité de l’expérience utilisateur, d’autre part la capacité à multiplier les fournisseurs et donc la performance économique. Nous avons travaillé sur de nombreuses voies permettant de réduire les temps de réponse. L’augmentation de la puissance de calcul des ordinateurs se réalise maintenant grâce à la multiplication des unités de calculs (cœurs) au détriment des performances unitaires liées notamment à la fréquence des transistors. Nous avons donc choisi de travailler sur cette voie afin de permettre de réduire les temps de réponse.
La réussite du projet Clariprint est fortement lié au langage CLAIRE. Issue d’un projet de recherche de Yves Caseau (ENS), ce dernier propose une solution performante et élégante pour élaborer des algorithmes hybrides dans le domaine de l’optimisation combinatoire. Nous avons ainsi industrialisé cet outil directement issu de la recherche notamment en effectuant un long travail notamment sur le gestionnaire de mémoire (garbage collector). Cependant CLAIRE ne propose pas d’outil de programmation concurrente. Nous avons donc recherché à inclure du parallélisme dans un langage de haut niveau comme CLAIRE. Pour tenter d’aboutir, nous avons analysé en premier lieu l’adéquation logique entre les concepts utilisés dans les algorithmes de programmation par propagation de contraintes ou hypothétique, avec les différentes logiques de programmation concurrente. Nous avons, à partir de cette analyse élaboré plusieurs scenarii. Nous avons ensuite émis différentes propositions syntaxiques ou fonctionnelles. Nous avons ensuite étudié la faisabilité technique des propositions et retenu plusieurs candidates. Enfin, plusieurs prototypes nous ont permis d’évaluer la pertinence des choix opérés, d’évaluer les performances comparées et de faire évoluer notre approche du sujet.
Programmation concurrente, contraintes et arbres de recherche.
La programmation par parcours semble bien adaptée à la programmation concurrente. Avec un algorithme basique, la recherche du meilleur chemin peut être parallélisée à chaque nœud.
Cependant deux problèmes principaux apparaissent dans ce cadre ( cf. ALPS). Les techniques généralement utilisées pour accélérer le parcours de l’arbre procèdent par partage de connaissance entre le parcours des branches, notamment des bornes. De plus le nombre de branches peut-être grand et cela peut causer un engorgement sur un système ayant un nombre de processeur fini.
Travaux
Les travaux ont été réalisés en 4 phases.
Phase 1 : évaluation des API techniques disponibles
Nous avons mené une première étude des solutions possibles fournies en standard par les systèmes d’exploitations ou par des bibliothèques.
Nous avons ainsi identifié et mis en concurrence quatre approches :
- traitement par lot sur des processus séparés
- la scission de processus (fork)
- l’utilisation de fils d’exécution multiples (thread)
- le microthreading via les fonctions anonymes.
Cette étude a porté d’une part sur la compatibilité avec la gestion mémoire et de pile d’appels du noyau de CLAIRE et d’autre part sur la fiabilité et robustesse de la solution. CLAIRE étant destiné à la réalisation d’applications utilisant massivement la propagation de contraintes, l’idée de partager de manière globale la mémoire en définissant des zones de partage lors de l’écriture était lourd à implémenter. Nous avons ainsi écarté les solutions basées sur les fils (thread) d’exécution pour les solutions utilisant des processus indépendants.
Suivants ces recherches, nous avons ajouté les contraintes suivantes aux critères de sélection :
- un espace mémoire commun et/ou dupliqué
- une pile d’appels séparée.
Nous avons donc décidé d’exploiter l’api « fork », disponible sur tous les systèmes de type UNIX. Cette api propose de nombreux avantages dans les système modernes utilisant le « copy on write » des zones mémoires. En effet dans ce cas, lors de la duplication du processus, la mémoire n’est pas automatiquement recopiée mais fait référence au processus original. Le système ne déclenche une copie que si le nouveau processus écrit dans une zone mémoire, et concentre cette copie que sur la zone ciblée.
L’impact mémoire de la création de processus fils est ainsi réduit au strict minimum.
Phase 2 : Recherche d’éléments syntaxiques
Le langage CLAIRE a été conçu dans un but d’élégance, de compacité afin de proposer une solution permettant d’exprimer des algorithmes complexes avec une bonne abstraction des problématiques techniques. Dans ce cadre nous avons recherché la meilleure méthode d’intégration de la parallélisation. Les structures de contrôles candidates communes à la parallélisation automatiques sont les boucles itératives. CLAIRE propose des structures de boucles classiques (while, for), et propose des structures spécifiques au raisonnement hypothétique (branch). Pour une première implémentation de boucle parallélisée, nous avons ajouté une structure de contrôle dédié : ffor (forked for)
Syntaxe :
for <variable d'itération> in <ensemble> by <nombre max de processus concourants> <bloc d'instruction>Comme tout langage fonctionnel, CLAIRE renvoie une valeur à l’évaluation d’une boucle. Le « for » renvoie la valeur de retour du dernier bloc évalué (dernière itération). Pour le ffor nous avons imaginé une solution différente ouvrant la voie à la sélection de branches. Le résultat d’un ffor consiste à la liste ordonnée des évaluations.
ffor:list<tuple(integer,typeof<block>)>Phase 3 : Prototypes
Le nouvel élément syntaxique a été intégré à CLAIRE 3.5. Ce prototype nous a permis d’évaluer la pertinence logique et technique. Dans un premier temps, nous avons testé plusieurs implémentations sur des problèmes simplifiés comme celui des N-Dames (Franz Nauck). Cette phase nous a permis d’évaluer et d’améliorer notre approche du sujet comme de mettre en évidences de nouveaux problèmes.
Après avoir sélectionné une solution candidate, nous avons expérimenté plusieurs prototypes de Clariprint parallélisé. Ces différents prototypes ont été confrontés à des jeux de données réelles dans un cadre de production simulé. Nous avons ainsi procédé à de nombreux ajustement visant à assurer la robustesse.
Phase 4 : Tests de performances et robustesse
Les tests doivent nous permettre d’évaluer les gains en performances comme de valider la robustesse de l’implémentation choisie.
Nous avons mis en place une série de tests basée sur le problème des n-dames (Franz Nauck).
Nous avons confronté une solution classique écrite en claire à une solution utilisant la parallélisation. Nous avons confronté le temps de calcul de l’ensemble des solutions possibles
| Taille de l’échiquier | CLAIRE Classique | CLAIRE // |
| 6 | 1080ms | 310ms |
| 7 | 1166ms | 321ms |
| 8 | 4312ms | 1103ms |
| 9 | 1228ms | 387ms |
| 10 | 18 815ms | 5204ms |
| 11 | 4 930ms | 1345ms |
| 12 | 386 980ms | 67621ms |
Nous avons ensuite mis en place une version de l’application CLARIPRINT utilisant les fonctionnalités.
Conclusion
Cette première implémentation de programmation concurrente est un succès et ouvre de nombreuses voie d’optimisation des algorithmes de parcours d’arbre.
Recherche complémentaires :
- Optimisation des recherches de solution par partage de données inter-processus (bornes, solution à des sous-problèmes …)
- Contrôle dynamique de charges et du nombre des fils d’exécution.
Références :
- Jad Nohra and Alex J. Champandard : The Secrets of Parallel Pathfinding on Modern Computer Hardware
- Xi Yun, Susan L. Epstein : Adaptive Parallelization for Constraint Satisfaction Search
- Yves Caseau , François Laburthe : CLAIRE a brief overview (1996)
- Grama,A.,Kumar,V.:State of the art in parallel search techniques for discrete optimization problems.
- Lars Otten and Rina Dechter : Load Balancing for Parallel Branch and Bound
- Gomes, C., B. Selman, N. Crato and H. Kautz 2000 : Heavy-tailed phenomena in satisfiablity and constraint satisfaction problems.
- Hamadi, Y. and L. Sais 2009. ManySAT: a parallel SAT solver
- T. K. Ralphs : Parallel branch and cut (2006)
- Kurt Anstreicher , Nathan Brixius , Jean-Pierre Goux , Jeff Linderoth : Solving Large Quadratic Assignment Problems on Computational Grids (2000)
- Y. Xu , T. K. Ralphs , L. Ladányi , M. J. Saltzman : ALPS: A framework for implementing parallel search algorithms (2005)
- OpenMPI : Open Source High Performance Computing
- Wikipedia: Fork Bomb