Squelettes algorithmiques parallèles pour les métaheuristiques

Concevoir un logiciel parallèle est une tâche difficile, mais qui est devenue essentielle dans l'informatique moderne. C'est notamment vrai en recherche opérationnelle où de nombreux algorithmes peuvent bénéficier grandement d'une parallélisation. Cela a conduit au développement de frameworks logiciels qui facilitent la conception parallèle d'algorithmes de recherche opérationnelle, basés sur les programmations orientée objet et générique. De nouvelles possibilités de conception sont apparues avec les avancées de la métaprogrammation générique, en particulier dans le langage C++.

Notre objectif est de concevoir une bibliothèque capable de produire des implémentations parallèles efficaces d'un algorithme à partir de la connaissance de sa structure et sans aucun surcoût à l'exécution. Nous proposons d'utiliser les squelettes algorithmiques afin de décrire des algorithmes de recherche opérationnelle et de les rendre prêts pour une parallélisation. Dans ce but, des techniques de métaprogrammation sont utilisées, premièrement pour fournir les moyens de décrire un algorithme de recherche opérationnelle comme une composition de squelettes algorithmiques, et deuxièmement pour, à la compilation, analyser et transformer le squelette en un code efficace à l'exécution.

Dans un premier temps, nous nous concentrons sur les métaheuristiques, car étant des structures génériques, elles s'adaptent naturellement aux squelettes algorithmiques.