Modéliser des squelettes algorithmiques pour la parallélisation automatique avec la métaprogrammation par patrons

Cet article présente un framework pour les squelettes algorithmiques dont le but est de représenter un algorithme complet, à la fois ses parties séquentielles et celles potentiellement parallélisables, afin de permettre la prise de décisions globales sur son implémentation. Avec notre modélisation, un squelette est décrit par une structure algorithmique et un graphe de flux de données, construits à partir de la composition d'os et d'autres squelettes. Nous introduisons cette notion d'os qui représentent des schémas séquentiels ou parallèles élémentaires dont l'implémentation est disponible (à partir de la bibliothèque ou conçue par des développeurs avertis), alors que les squelettes sont automatiquement implémentés à partir de leur description. La solution proposée, implémentée avec la métaprogrammation par patrons, est capable d'agir à la fois à la compilation et à l'exécution. Elle permet d'implémenter de nouveaux os, de décrire de nouveaux squelettes, ou simplement l'instanciation d'un squelette en fournissant des muscles sous la forme de fonctions séquentielles.

Une fois qu'un squelette est instancié, on peut décider de générer un code, soit séquentiel, soit parallèle, de l'algorithme. Pour optimiser le processus de parallélisation, nous proposons des orchestrateurs, sous la forme de templates C++ qui peuvent analyser un squelette à la compilation et ajuster son exécution.

Une solution reposant sur une bibliothèque C++ est présentée, et ses mécanismes et son utilisation sont illustrés en implémentant un algorithme GRASPxELS, une métaheuristique de recherche opérationnelle classique, qui permet deux niveaux de parallélisme. Des résultats de performance montrent que cette approche présente un surcoût négligeable à l'exécution.