Résumé: Les problèmes d’optimisation combinatoire (Combinatorial Optimization Problems COPs) sont en général NP-difficiles. La résolution d’instances de grande taille de ces problèmes prend un temps de calcul exponentiel. La parallélisation du calcul est l’une des issues les plus efficaces en terme d’amélioration des performances d’exécution, notamment l’utilisation du parallélisme à grande échelle basé sur les grilles de calcul (Grid Computing) ou le calcul pair-à-pair (Peer-to-Peer Computing). Une grille de calcul, généralement utilisée pour un calcul intensif, est formée d’un nombre important de machines de calcul interconnectées par des réseaux haut débit. Le calcul pair-à-pair, est basé sur l’exploitation des cycles CPU non utilisés ou totalement oisifs sur tout le réseau. Ces deux outils sont un moyen efficace pour atteindre une grande performance de calcul pour des applications scientifiques de grande taille. Le projet s’inscrit dans le cadre de la résolution exacte des problèmes d’optimisation de grande taille sur un système de calcul large échelle pair-à-pair. Il consiste en l'implémentation d’un nouvel algorithme parallèle basé sur un modèle Master/Worker ou Fermier/Travailleur hiérarchique avec des communications directes entre tous les processus du modèle, i.e., (Superviseur, Master et Worker). Les communications directes permettent d’une part éliminer les goulots d’étranglements qui se créent souvent au niveau des processus fermiers. Dans ces applications, les communications inter-travailleur transitent par le processus Fermier. D’autre part, les communications directes permettent de décentraliser l’espace de stockage d’unités de travail sur l’ensemble des processus Fermiers. Dans ce travail l’étudiant(e) va exploiter l’une des propriétés des réseaux P2P (communications directes entre pairs) et qui vont être mises en œuvre avec les communications de groupes en utilisant la plate-forme de calcul parallèle concurrent et distribué (ProActive). L’algorithme implémenté sera appliqué au problème du flow-shop de permutation (PFS). L’application sera implémentée sur la plateforme pair-à-pair ProActive.

Langue: Français
Collation: 123 p. ill. ;30 cm.
Diplôme: Ingénieur d'état
Etablissement de soutenance: Alger, Université des Sciences et de la Technologies Houari Boumediene. Faculté d'Electronique et d'Informatique
Spécialité: Réseaux et Systèmes
Index décimal 621 .Physique appliquée (électrotechnique, génie civil, génie mécanique, ingénierie appliquée, principes physiques en ingénierie)
Thème Informatique

Mots clés:
GRID computing
Optimisation combinatoire

Note: Bibliogr. pp.116-123