Avec l'émergence de nouvelles architectures distribuées, comme les grappes de calcul distantes et les architectures de calcul volontaire, il apparaît important de définir des algorithmes et des intergiciels bien adaptés à ces architectures. En effet, l'utilisation de ces plate-formes introduit plusieurs nouvelles contraintes par rapport à un contexte de grappes locales homogènes : hétérogénéité des machines, hétérogénéité des réseaux, volatilité des noeuds de calcul, etc. Dans ce contexte, plusieurs travaux montrent que pour les algorithmes itératifs il peut être préférable d'utiliser les algorithmes IACA (Itérations Asynchrones avec Communications Asynchrones) pour lesquels les communications sont recouvertes par du calcul et la perte des messages de données est tolérée. Les travaux présentés dans cette thèse concernent la conception et la mise en oeuvre d'une plate-forme dédiée à l'exécution d'algorithmes IACA sur des architectures distribuées, hétérogènes et volatiles. Cette plate-forme, JACEP2P-V2, est tolérante aux pannes et décentralisée. Elle offre un mécanisme de communications asynchrones et un mécanisme de détection de la convergence globale adapté aux caractéristiques des algorithmes IACA. De plus, nous reportons des expérimentations sur grappes hétérogènes volatiles et distantes afin de tester l'efficacité et la robustesse de notre plate-forme. Les résultats obtenus, avec plus de 1000 coeurs de calculs, sont très encourageants et montrent que JACEP2P-V2 est extensible et performante. Nous terminons ce document par la présentation d'une étude comparative de plusieurs méthodes de résolutions de systèmes non linéaires (comme la multi-décomposition et la relaxation d'ondes) implémentées avec JACEP2P-V2.
La majorité des problèmes d'optimisation combinatoire sont très
complexes (souvent NP difficiles). Pour résoudre ces problèmes, il
existe deux classes de méthodes: les méthodes exactes et les méthodes
approchées. Les méthodes exactes donnent la solution optimale au
problème combinatoire mais génèrent des calculs de très grande
taille. En effet, ils doivent explorer tout l'espace de recherche pour
s'assurer de l'optimalité de la solution trouvée. par conséquence, ils
ne sont applicables que sur les instances de petites tailles. Pour
résoudre les instances de grandes tailles dans des délais
raisonnables, il faut utiliser les méthodes approchées, comme les
métaheuristiques, qui donnent des solutions rapprochées de la solution
optimale. Même si les techniques de métaheuristiques permettent de
réduire considérablement le temps de calcul nécessaire pour
l'exploration de l'espace de solutions, ce coût reste exorbitant
lorsque des instances de problèmes de grande taille sont
traitées. D'où l'intérêt de la parallélisation des méthodes
métaheuristiques et de leur exécution sur les architectures parallèles
et distribuées comme les supercalculateurs, les grilles de calcul et
les réseaux pair-à-pair.
Dans la littérature, trois modèles pour la parallélisation des
métaheuristiques sont souvent utilisés: les îles/le modèle
multi-départ, évaluation parallèle de la population / voisinage, et
l'évaluation parallèle d'une solution unique. Ces modèles sont
adaptés pour le calcul sur les grilles qui sont somposées d'un grand
nombre de ressources de calcul interconnectées par des réseaux à
forte latence. Pour profiter de la grande quantité des ressources
fournies par la grille, les trois modèles parallèles doivent être
simultanément utilisées d'une manière hiérarchique.
De nos jours, avec l'émergence de plusieurs types d'unité de calcul
multicoeurs, comme les nouveaux processeurs multicoeurs et les
GPUs, le majeur défit du calcul à haute performance est la bonne
exploitation de cet énorme quantité de ressources de calcul pour
résoudre les problèmes scientifiques à grande échelle. D'où
l'importance de la conception d'algorithmes et la mise en oeuvre de
techniques de programmation qui permettent d'utiliser efficacement ces
ressources et faire face à ces défis scientifiques dans le contexte de
l'optimisation combinatoire quasi-optimale.
Mots clefs : optimisation combinatoire, calcul parallèle sur grille, métaheuristiques, méthodes exactes