-- Site/ Recherche --

Présentation | Publications | Thèse


THÈSE DE DOCTORAT




Présentation synthétique

Résolution parallèle de problèmes combinatoires en mémoire partagée

  • Laboratoire d'accueil :
    CReSTIC, équipe LICA <br><br>
  • Soutenue publiquement le 13 décembre 2005
    mention très honorable
  • Composition du Jury :
    • Présidente du jury :
      • Professeur Catherine Roucairol, Université de Versailles Saint-Quentin en Yvelines
    • Rapporteurs :
      • Professeur Hervé Guyennet, Université de Franche-Comté
      • Professeur Peter Kropf, Université de Neuchâtel, Suisse
    • Examinateur :
      • Professeur Van-Dat Cung, ENSGI-INPG, Grenoble
    • Directeurs :
      • Professeur Alain Bui, Université de Reims Champagne-Ardenne
      • Professeur Michaël Krajecki, Université de Reims Champagne-Ardenne
  • Mots clés :
    problèmes combinatoires, optimisation, CSP n-aires, parallélisme, équilibre de charge, mémoire partagée, échange de messages, OpenMP, pThreads, MPI.

^Top


Résumé

Mes travaux s'inscrivent dans le cadre de la recherche combinatoire et de l'optimisation combinatoire. Les problèmes sont modélisés sous la forme de CSP. L'arbre de recherche est élagué à la volée, par l'utilisation conjointe des contraintes et d'une fonction d'évaluation incrémentale.

Pour la parallélisation, des tâches sont générées en développant l'arbre de recherche à une certaine profondeur, et seules celles qui sont utiles sont conservées. Elles sont irrégulières, et leur répartition entre les processeurs nécessite donc un équilibrage dynamique : différentes stratégies sont envisageables, qu'on peut considérer selon les modèles de programmation en mémoire partagée ou par échange de messages. Dans le cadre des problèmes d'optimisation, je propose une stratégie originale d'équilibre de la charge, qui permet d'éliminer dynamiquement des tâches en cours de résolution avant que les processeurs n'aient à les tester. Par ailleurs, différents niveaux de collaboration sont envisagés entre les processeurs pour la résolution des tâches. Nous avons également mis en évidence un phénomène de contention mémoire dans le cas de la programmation en mémoire partagée, et je propose une méthode d'arrangement de la mémoire, à faible coût, pour y remédier.

Les problèmes pratiques que nous avons abordés sont considérés comme des challenges par la communauté académique : il s'agit d'une part du problème de Langford, problème de permutation dans lequel on compte le nombre d'arrangements acceptables pour les conditions imposées, et d'autre part du problème de la construction de règles de Golomb optimales, problème d'optimisation qui a de nombreuses applications pratiques, comme par exemple dans le domaine des radio-télécommunications. Les différents apports que nous avons amenés nous ont permis de montrer qu'il est possible de résoudre ces problèmes efficacement, par l'utilisation de machines parallèles ou de grilles de calcul. Nous avons en particulier établi deux nouveaux records mondiaux en résolvant les instances L(2,23) et L(2,24) du problème de Langford.

Pour la suite de ces recherches nous envisageons d'allier, pour la résolution des problèmes d'optimisation combinatoire, des méthodes de recherche incomplètes basées sur les métaheuristiques, en particulier comme prétraitement permettant de générer les tâches sur la base d'une borne immédiatement très rentable. Par ailleurs je souhaite généraliser les considérations sur l'arrangement de la mémoire, pour l'intégrer à un moteur générique de résolution afin d'en assurer une meilleure efficacité en mémoire partagée.


^Top


Thématiques abordées

Mes activités de thèse concernent principalement la parallélisation en mémoire partagée de problèmes combinatoires. L'objectif est de développer une parallélisation efficace pour la résolution des problèmes combinatoires, qui sont irréguliers, en considérant des stratégies adaptées d'équilibre de charge dynamique.

  1. Cas particulier du n-body problem :
    • déplacement de soldats sur un terrain militaire représenté par une grille rectangulaire, avec interactions (combats, ...) et intégration d'un objectif de campagne
  2. Résolution des CSP en mémoire partagée :
    • Partage de l'arbre de recherche
    • Modélisation des problèmes de Langford et de Golomb
  3. Problèmes combinatoires ; cas particulier des problèmes d'optimisation combinatoire :
    • Modélisation sous la forme d'un CSP
    • Algorithmes génériques de résolution (problèmes de décision / d'optimisation)
    • Découpage en tâches en développant l'arbre de recherche
    • Equilibre de charge dynamique : stratégies adaptées, en particulier dans le cas des problèmes d'optimisation :
      • génération des tâches dans un ordre spécifique favorable
      • algorithme DTJ (Dynamic Tasks Jumping) permettant d'effectuer des sauts dynamiques entre les tâches obsolètes
  4. Contention mémoire dans le cas de la parallélisation de problèmes combinatoires en mémoire partagée avec OpenMP :
    • mesure et analyse du phénomène (irrégularité des temps d'exécution)
    • nouveau modèle d'allocation mémoire permettant de résoudre le problème


^Top


Téléchargement

^Top