Optimisation combinatoire sur accélérateurs

ou comment aider à prendre les bonnes décisions plus vite...

Ce projet est à l'interface des domaines de la recherche opérationnelle et de l'algorithmique parallèle. L'objectif est d'étudier l'apport des accélérateurs pour les problèmes clés de la RO et plus spécifiquement les problèmes difficiles d'optimisation combinatoire.

La Recherche Opérationnelle (RO) est une discipline à l'interface de l'informatique (algorithmique), des mathématiques et de la gestion. L'objet de la RO est de proposer des méthodes scientifiques pour la résolution de problèmes pratiques d'optimisation dans les grands systèmes (industriels, administration, organisations…); voir par exemple le livre blanc de la Recherche Opérationnelle où des applications comme l'optimisation de la distribution de l'énergie chez EDF ou la planification des personnels navigants chez Air France sont décrits. La RO est une discipline clé dans de nombreuses industries et le retentissement de ses enjeux applicatifs dans le monde académique est visible par exemple dans les interventions récentes de Cédric Villani (Médaille Fields) sur France Inter ou dans le quotidien Le Monde qui mentionnent la RO ou le récent prix Nobel d'économie (octobre 2012) sur les problèmes de couplage pour des marchés où les modèles standards ne fonctionnent pas.

Les verrous actuels en RO sont sur les problèmes dits difficiles (en théorie de la complexité) et de grande taille. L'enjeu est de réduire considérablement le temps de calcul pour la résolution de ces problèmes. Par exemple, le récent challenge Roadef proposé par Google (plus de 80 équipes internationales) nécessitait la résolution de plusieurs problèmes fondamentaux d'optimisation combinatoire comme le bin packing. Historiquement, les recherches sur ces problèmes portent sur le développement d'algorithmes plus performants. L'enjeux aujourd'hui, avec l'omniprésence des machines multi-cores et la disponibilité à faible coût des accélérateurs, est de tirer parti de ces nouvelles ressources pour repousser les limites de résolution de ces problèmes.

En première approximation, l'exploitation des architectures parallèles est bien assez maîtrisée depuis de nombreuses années : d'une part, le corpus d'algorithmes parallèles est conséquent ; d'autre part, les points durs que sont la synchronisation entre entités concurrentes et l'ordonnancement des activités (tâches) sur les ressources de calcul possèdent des approches heuristiques généralement efficaces en pratique. Néanmoins, il reste des points durs à résoudre provenant de la complexité du matériel. En effet, les architectures parallèles modernes, multi-cores ou accélérateurs, possèdent une hiérarchie mémoire importante (cache L1, L2, L3, banc mémoire...). L'exploitation effective reste alors hors de portée des approches citées. Les solutions à ce problème passent par une simplification (au prix d'un compromis simplicité / performance) de l'architecture et doit être abordées sur trois axes : 1/ conception d'algorithmes tenant compte des contraintes d'accès à la mémoire ; 2/ utilisation d'un modèle de programmation de haut niveau et 3/ utilisation de techniques d'ordonnancement nouvelles tenant compte de la localité des données sur les différentes mémoires physique.

L'équipe MOAIS possède une expertise sur ces trois points et, plus particulièrement, développe un support exécutif qui, couplé à des algorithmes d'ordonnancement adaptés, permet d'exprimer simplement un grand ensemble de tâches fines avec dépendances, et qui seront exécutées sur une architecture hétérogène (multi-CPUs, multi-GPUs).

Des travaux existent depuis de nombreuses années sur l'algorithmique parallèle pour des méthodes génériques avancées de résolution en RO (voir par exemple les travaux de Bertrand Le Cun sur l'algorithme de Branch and Bound parallèle). Notre propos est de nous intéresser aux briques de base de la recherche opérationnelle pour mettre en place des méthodes accélérées pour ces éléments de bases qui apparaissent souvent dans les problèmes de RO.

Le premier problème étudié sera le sac à dos : étant donné un ensemble d'objets ayant chacun un volume et un profit, on cherche à sélectionner une partie de ces objets à mettre dans un sac à dos de volume borné afin de maximiser le profit du sac ainsi constitué. Ce problème de sac-à-dos est "difficile" mais fondamental en RO, en particulier parce qu'il intervient en tant que sous-problème dans de nombreuses applications par exemple lorsqu'il s'agit de gérer un budget temps en production ou monétaire pour la constitution de portefeuille. Une des technique de base de résolution est le formulation en programmation linéaire en nombres entier et l'utilisation de solveurs pour résoudre le problème. Lors de la résolution, de nombreux problèmes de sacs à dos doivent être résolus très rapidement et de manière exacte. Il existe de nombreuses techniques permettant de résoudre efficacement ce problème pour des problèmes de taille limitée et les avancées dans de nombreuses applications passeront par l'accélération de ces techniques de résolution, notamment via la parallélisation sur processeurs et accélérateurs. Boyer, El Baz et Elkihel ont initié en 2012 des travaux pour ce problème avec l'utilisation d'une carte graphique comme accélérateur. Nous poursuivrons ces travaux sur une généralisation de ce problème et emploierons la programmation hybride et l'utilisation simultanée de plusieurs accélérateurs.

Un autre problème clé de ce projet est le Bin Packing : on veut placer des objets dans un minimum de conteneurs. Chaque objet et chaque conteneur ont un volume donné. Ce problème à des applications très variées comme par exemple l'ordonnancement de tâches sur des machines ou la confection d'emplois du temps. Dans ce deuxième exemple, les objets peuvent être les cours et les conteneurs, les salles. Les problèmes d'affectation de ressources (temps, argent, énergie, eau...) ou de logistique contiennent souvent comme sous problème un bin packing.

Nous considèrerons ces problèmes de base et leurs extensions en particulier avec une donnée compacte : Une instance d'un problème classique d'optimisation combinatoire est composée d'une liste de n objets avec une liste d'attributs pour chaque objet. Dans ce cas, le codage d'une instance peut se faire en O(n L), où L est la taille du codage du plus grand attribut. Toutefois, il arrive fréquemment que le codage d'une instance puisse se faire de manière plus compacte, par exemple, lorsque les objet peuvent être agrégées en un petit nombre de types distincts. Lorsque c'est le cas, il suffit de décrire les attributs d'un seul objet caractéristique par type et de donner le nombre d'objets de chaque type. Lorsque la donnée est codée de cette façon, il s'agit d'un problème en high-multiplicity (HM). Dans ce cas, la description complète d'une solution pour chacun des n objets n'est que pseudo-polynomial dans la taille de l'instance. Pour ce type de problème, même démontrer l'appartenance à NP peut s'avérer difficile. Ce type de situation se rencontre dans les environnements manufacturiers répétitifs ou dans des applications où le nombre d'objets est réduit en agrégeant des objets différentes mais avec des caractéristiques proches. Le problème obtenu n'est qu'une approximation du problème original mais peut s'avérer plus facile à résoudre. Ces problèmes sont fortement structurés : On peut s’attendre à des gains de performance importants en utilisant des algorithmes parallèles. Ils présentent actuellement un challenge pratique et théorique important pour le domaine.

On souhaite donc évaluer l'apport à utiliser un ou plusieurs accélérateurs pour résoudre ces problèmes et repousser les limites (temps raisonnable, taille des problèmes) avec les contraintes liées aux accélérateurs actuels. On ne peut pas directement adapter les algorithmes séquentiels les plus efficaces pour ces problèmes à cause des contraintes technologiques des accélérateurs. Le challenge est de développer de nouveaux algorithmes dédiés à la parallélisation pour ces problèmes ; par exemple mixer des méthode de diviser pour régner et programmation dynamique pour des systèmes parallèles hybrides.

Les attendus du projet sont

  • de disposer d'une bibliothèque d'algorithmes fondamentaux accélérés pour les briques de base de la RO.
  • de développer une expertise forte dans le domaine au niveau français,
  • de consolider des collaborations à l’international et de communiquer sur ce domaine
  • et bien sur, de proposer des résultats de recherche originaux qui feront l’objet de présentations dans des conférences et d’articles.

Partenariats

Ce projet réunit des équipes complémentaires du site grenoblois. L'équipe ROSP (Recherche Opérationnelle pour les Systèmes de Production) du laboratoire G-SCOP apporte une compétence sur les problématique d’optimisation combinatoire et de Recherche Opérationnelle et les problèmes pratiques et challenges industriels. L'équipe MOAIS du LIG est spécialisée dans l'algorithmique parallèle, la programmation parallèle, l'ordonnancement, les accélérateurs (Many core).

Participants :

  • Nadia Brauner (Pr UJF),
  • Van Dat Cung (Pr G-INP)
  • Michael Gabay (doctorant)
  • Thierry Gautier (CR INRIA)
  • Grégory Mounié (MdC INP)
  • Rémi Piotaix (Stagiaire)
  • Brice Videau (Post doc)

Bibliographie

  1. N. Brauner, S. Gravier, L.-P. Kronek, F. Meunie. LAD models, trees and an analog of the fundamental theorem of arithmetic Discrete Applied Mathematics. (disponible en ligne http://dx.doi.org.gate6.inist.fr/10.1016/j.dam.2012.12.004), 2012.
  2. J. Darlay, N. Brauner and J. Moncel. Dense and Sparse Graph Partition. Discrete Applied Math, 160(16-17):2389-2396, 2012.
  3. N. Brauner, G. Finke, V. Lehoux-Lebacque, C. Rapine, H. Kellerer, C. Potts, V. Stru- sevich. Operator Non-Availability Periods. 4OR: A Quarterly Journal of Operations Research, 7(3):239-253, 2009.
  4. N. Brauner and G. Finke and V. Lehoux-Lebacque and C. Potts and J. Whitehead. Scheduling of coupled tasks and no-wait robotic cells. Computers & Operations Research, 36(2): 301-307, 2009.
  5. F. Broquedis, T. Gautier, V. Danjean. libKOMP, an Efficient OpenMP Runtime System for Both Fork-Join and Data Flow Paradigms. IWOMP, :102-115, Rome, Italy, jun 2012.
  6. T. Gautier, J.V. F. Lima, N. Maillard, B. Raffin. XKaapi: A Runtime System for Data-Flow Task Programming on Heterogeneous Architectures, IPDPS’2013, Boston, USA, 2013.
  7. T. Gautier, J.V. F. Lima, N. Maillard, B. Raffin. Locality-Aware Work Stealing on Multi-CPU and Multi-GPU Architectures, 6th Workshop on Programmability Issues for Heterogeneous Multicores (MULTIPROG), HiPEAC, Berlin, Germany, 2013.
  8. E. Hermann, B. Raffin, F. Faure, T. Gautier, J. Allard. Multi-GPU and multi-CPU parallelization for interactive physics simulations, EUROPAR 2010, Ischia Naples, Italy, 2010.
  9. J.V.F. Lima, T. Gautier, N. Maillard, V. Danjean. Exploiting Concurrent GPU Operations for Efficient Work Stealing on Multi-GPUs. 24rd International Symposium on Computer Architecture and High Performance Computing (SBAC-PAD), Columbia University, New York, USA, oct 2012.
  10. J. Toss, T. Gautier. A New Programming Paradigm for GPGPU. EUROPAR 2012, Rhodes Island, Greece, aug 2012.
  11. C. Rapine, N. Brauner, G. Finke, V. Lebacque. Single Machine Scheduling with Small Operator-Non-Availability Periods, Journal of Scheduling, 15:127-139, 2012.