CHOC

CHallenge en Optimisation Combinatoire

B.2. Contexte et motivation du projet

Le challenge consiste en la résolution de deux problèmes célèbres et très difficiles de l'Optimisation Combinatoire : l'Affectation Quadratique (QAP) et une extension le Q3AP (affectation en trois dimensions).

Affectation quadratique

Le problème d'Affectation Quadratique est un problème classique d'Optimisation Combinatoire dans lequel il convient de trouver l'affectation optimale de n usines sur n sites de façon à minimiser un coût quadratique dépendant à la fois des distances inter-sites et des flux inter-usines. Ce problème a de très nombreuses applications pratiques tant en informatique qu'en productique, électronique ou architecture pour des tailles n ne dépassant pas la centaine, mais se montre extrêmement difficile à résoudre. Ainsi, malgré 30 années de recherches, la taille des applications pouvant être résolue exactement demeure très basse (autour de n = 30).

En effet, la recherche d'une solution optimale d'un problème d'Affectation Quadratique nécessite le parcours d'arborescence de millions de noeuds : pour n=25 déjà 44 millions de sommets.

En 2000, deux événements importants se sont produits aux Etats-Unis, accroissant la popularité de ce problème: l'un à l'Université de Pennsylvanie où Peter Hahn a réussi à résoudre l'instance Nugent de taille 25 avec une machine séquentielle au bout de quelques mois de calculs; l'autre au laboratoire national d'Argonne, où une équipe formée d'Anstreicher, Brixius, Goux et Linderoth de l'Université de Iowa et du Argonne National Laboratory a résolu grâce au parallélisme pour la première fois le problème Nugent de taille 30 en 7 jours sur une plate-forme composée de plus de 2000 machines (projet MetaNEOS). L'impact du parallélisme a pu être ainsi prouvé au grand public grâce à un « tapage » médiatique impressionnant: résultat sur Nugent 30 annoncé dans toute la presse américaine (Chicago Tribune, Chicago Sun Times, HPCWire, WNCSA Access Magazine, etc.) et dans un certain nombre de journaux et de revues françaises (InfoScience, Le Monde, Transfert, etc.). L'ampleur de l'impact de cette résolution a été, aussi importante que celle suscitée lors de la victoire de la machine à jouer aux Echecs DeepBlue d'IBM face au Champion du Monde « humain » Gary Kasparov.

Motivation et Etat de l'art.

Toutefois, ces résultats posent un problème de reproductibilité, aucune autre équipe dans le monde n'ayant pu ré-éditer cet exploit ! Il a en effet fallu mobiliser 7 jours de temps de calcul sur une grille de calcul composée de 2510 machines, avec 700 machines actives en moyenne, pour développer une arborescence de plus de 12 milliards de sommets, le parcours arborescent de type « diviser pour régner » étant alors très près d'une exploration de type « force brute ».

Pour pousser le plus loin possible la résolution exacte du QAP (taille n > 30), il faut améliorer théoriquement sa résolution exacte mais aussi avoir à sa disposition des outils efficaces pour implanter et gérer le parallélisme.

la méthode de résolution exacte du QAP par Branch-and-Bound (séparation en sous problèmes du problème de départ et évaluations des sous problèmes créés), la taille de l'arborescence à explorer peut être diminuée par amélioration du calcul de borne inférieure guidant le parcours arborescent et par la conception de meilleures stratégies de branchement profitant mieux du parallélisme. De plus, le calcul de cette borne inférieure intervenant en chaque sommet de l'arborescence, donc des millions de fois, il faut optimiser à la compilation ce calcul (équipe ARPA, Univ. de Versailles).

D'autre part, il faut posséder des outils efficaces pour développer facilement un parcours arborescent en parallèle et en exploitant au mieux la puissance du système parallèle où il sera implanté. La bibliothèque d'aide au développement d'applications de type Séparation et Évaluation, baptisée Bob/Bob++, développée depuis 1994 par l'équipe Opale de l'Université de Versailles, facilite déjà l'écriture d'un Branch-and-Bound parallèle. L'idée est de fournir une bibliothèque avec une interface de programmation permettant d'abstraire la gestion du parallélisme et de la machine.

Plusieurs bibliothèques de ce type ont existé comme PPBB (Univ. Paderborn) mais ne sont plus maintenues, d'autres sont encore sous forme de projet, ALPS (Univ. Lehigh), OOBB (Univ. Montréal), d'autres encore sont spécifiques à des types de Branch-and-Bound (Branch-and-Cut, Branch-and-Price) comme Symphony (Rice Univ.).

Concernant le résolution de problème d'Optimisation Combinatoire, il existe aussi des logiciels commerciaux permettant d'exploiter une machine parallèle (ILOG-Cplex, Xpress-MP). Ces logiciels sont tous spécialisés dans la résolution de Branch and Bound utilisant un solveur de programmation linéaire, et ils ne peuvent s'exécuter que sur des machines à mémoire partagée du type SMP.

Du point de vue de l'implémentation, la résolution de ces problèmes en parallèle consiste à ordonnancer un graphe de tâches sur un nombre borné de ressources de calcul de la machine parallèle visée. Les performances de l'application proviennent, d'une part, de l'implantation fine de la gestion du parallélisme, et d'autre part, de la qualité de l'ordonnancement calculé. L'équipe MOAIS du projet Apache (Grenoble) développe déjà depuis longtemps une bibliothèque appelée Kaapi/Athapascan permettant de décrire simplement le parallélisme de son application comme un graphe de tâches indépendamment de l'architecture matérielle utilisée. Le moteur exécutif se charge de placer les tâches sur les processeurs disponibles. L'algorithme d'ordonnancement retenu dans Kaapi est un algorithme de « vol de travail », qui a été montré comme étant efficace en théorie comme en pratique pour des applications, comme celles de CHOC, qui possèdent un parallélisme potentiel bien plus important que le parallélisme physique disponible. Cette approche permet d'obtenir des exécutions très efficaces (avec une accélération quasi linéaire) sur de nombreuses architectures (machine multiprocesseurs SMP, grappe ou grille). Kaapi permet d'utiliser des grilles de machines hétérogènes (architecture ou vitesse des processeurs) dans lesquelles les ressources apparaissent ou disparaissent au cours du temps. Les techniques utilisées pour masquer les pannes franches peuvent aussi s'appliquer afin de poursuivre un calcul distribué de manière non continu en l'arrêtant puis en le reprenant ultérieurement, éventuellement sur une autre grappe. Cette possibilité sera à même de répondre aux besoins en calcul des problèmes QAP et Q3AP de CHOC nécessitant un nombre important de machines sur une durée de calcul de quelques jours à quelques semaines.

Pour les problèmes non résolus exactement, le parallélisme peut néanmoins servir à améliorer la valeur de la meilleure solution connue. En effet, comme les metaheuristiques alors utilisées nécessitent une grande consommation en temps directement reliée à la qualité de la solution produite, elles sont très souvent parallélisées. La bibliothèque de résolution approchée ParadisEO (Univ. Lille) permet de paralléliser automatiquement les métaheuristiques et d'avoir une vue unique des modèles parallèles hybrides de toutes les classes de metaheuristiques. Les environnements de développement de métaheuristiques actuels sont spécifiques à des méthodes données tels que la recherche locale (EasyLocal++, HotFrame, JDeal), algorithmes évolutionnaires (EO, GaLib), etc. Rares sont les environnements qui intègrent le parallélisme et la distribution des métaheuristiques sauf peut-être l'ancien projet espagnol MALLBA. A notre connaissance, ParadisEO est le seul environnement open source à intégrer la plupart des metaheuristiques et leurs différents modèles parallèles ainsi que leur hybridation.

Pour obtenir de meilleurs résultats que ceux actuellement répertoriés dans la librairie QAPlib depuis plus de trente ans, il sera nécessaire de concevoir un algorithme couplant résolution approchée et résolution exacte.

Il faudra donc étudier le couplage d'une part de la bibliothèque de développement de B&B, Bob++ et d'autre part, de la bibliothèque de résolution approchée ParadisEO. Si quelques tentatives ont déjà été proposées (équipe Opale : Mimausa, popmusic), elles ne faisaient pas intervenir le parallélisme.

Affectation quadratique en trois dimensions

Le Q3AP est la modélisation d'un problème stratégique qui vient d'une nouvelle application pratique en transmission de données sans fil (comme les réseaux de senseurs) : l'implantation d'un schéma hybride ARQ (Automatic Repeat reQuest) pour enrichir la diversité de transmissions multiples par paquet en optimisant le « mapping » des symboles de transmission aux données. La solution du Q3AP peut réduire significativement le coût d'obtention d'une transmission fiable sur des canaux de communication sans fil avec distorsion du signal.

Il s'écrit comme la minimisation d'une fonction quadratique sur le polytope d'affectation en 3 dimensions. Le plus grand problème résolu en séquentiel pour ce problème NP-difficile, considéré comme une extension du QAP, est de taille n=13, en environ 7 jours par P. Hahn et al. (projet financé aux Etats-Unis par la NSF). Sa parallélisation a été soumise à l'équipe Opale, la taille des problèmes à résoudre pratiquement étant n = 8, 16, 32, 64, 128.

Une première étude a montré que deux niveaux de parallélisme pourraient y être exploités, l'un pour le parcours de l'arbre B&B, l'autre pour le calcul de borne inférieure. Nous voulons utiliser la capacité d'ordonnancement d'un graphe de tâches de Kaapi, pour paralléliser la résolution du problème Q3AP, sur ces deux niveaux en même temps. Beaucoup de travaux précédents ont eu en perspective ce style de parallélisation sans jamais voir le jour. En effet, beaucoup de problèmes ont la particularité d'être très consommateurs en temps de calcul à la racine de l'arbre, puis de l'être beaucoup moins à mesure que les sous-problèmes considérés sont profonds dans l'arbre. Cette particularité limite l'accélération obtenue si le calcul de la borne et le parcours de l'arbre ne sont pas parallélisés en même temps.

Contribution à l'avancée de la recherche dans ce domaine

D'une part, de premiers essais nous ont amené à voir que de très bonnes performances pouvaient être obtenues sur des grilles sans toutefois nous permettre de dépasser la taille n=25 dans la résolution du QAP (ACI-GRID DOC-G).

D'autre part, la puissance de calcul des systèmes parallèles mis à la portée des chercheurs a nettement augmentée aussi bien en puissance qu'en diversité (GRID 5000, machines de l'IDRIS ou de Teranova) et doit nous permettre maintenant d'atteindre de meilleures performances.

Dans le projet ACI-GRID DOC-G, nous avons effectué le portage des bibliothèques Bob++ et ParadisEO au dessus de Athapascan. Athapascan est la couche C++/Template historique. La nouvelle version Kaapi/Athapascan proposée maintenant change ce point vue. En effet, une nouvelle version de Bob++ doit voir le jour, s'appuyant directement sur Kaapi.

Nous n'avons fait aussi qu'effleurer la possibilité de parallélisation multi-niveaux par le biais du problème de Voyageur de commerce (TSP). La méthode de résolution de ce problème étant d'une énorme complexité, il nous a été impossible de porter la totalité de la méthode au dessus de Bob++.

En revanche, le problème Q3AP, directement écrit au dessus de Bob++ nous permettra d'étudier plus en avant cette possibilité de parallélisation multi-niveaux.

Résoudre des instances non encore résolues de ces problèmes d'Affectation Quadratique de grande taille avec des outils pertinents et affûtés permettrait grâce au retentissement espéré :

de prouver l'impact du parallélisme sur la résolution exacte par Branch-and-Bound des problèmes d'optimisation,
de populariser des bibliothèques développées en France : Bob++, ParadisEO, Kaapi permettant d'avoir dans une même plate-forme une méthode exacte parallèle multi-niveaux et un résolution heuristique parallèle hybride.
d'apporter la solution optimale donc une forte diminution de coût à des problèmes pratiques souvent d'importance stratégique.

B.3. Description du projet

Notre objectif est :

de pousser le plus loin possible la résolution exacte de ces problèmes (QAP taille n > 30, Q3AP n> 13),
d'améliorer la valeur de la meilleure solution connue pour les problèmes non résolus grâce au parallélisme,
de proposer des bibliothèques à l'efficacité testée et éprouvée permettant d'utiliser facilement des architectures parallèles : bibliothèques d'aide à la parallélisation du Branch-and-Bound, des metaheuristiques (Algorithmes évolutionnaires, Recherche locale avancée tel que la recherche Tabou et le Recuit Simulé, méthodes coopératives), bibliothèques multithreads pour l'ordonnancement et l'équilibrage de charge.

Contribution aux objectifs du programme « Calcul intensif et Grilles de calcul »

CHOC s'inscrit dans la thématique des « Grands défis applicatifs ».

La résolution de tels problèmes s'attaque à l'explosion combinatoire du nombre de solutions possibles à considérer ! Visites de sous-ensembles de solutions dans les méthodes exactes Branch-and-Bound, ou visites de bonnes solutions dans les metaheuristiques sont si nombreuses que le parallélisme en permettant une exploration simultanée va en accélérer la résolution.

Encore faut il posséder des bibliothèques portables et extensibles utilisant le mieux possible les performances des systèmes parallèles où sont implantées ces applications.

De plus ces bibliothèques doivent rendre à l'utilisateur l'exploitation du parallélisme transparent et lui faciliter l'écriture de sa méthode qu'elle soit exacte, approchée ou encore hybride.

Travaux à mener dans le cadre du projet

Les premiers travaux à mener dans le cadre du projet concernent les méthodes de résolution:

Amélioration des méthodes de résolution :
- QAP : Amélioration de la technique d'évaluation, des stratégies de branchement pour la méthode de Branch-and-Bound (B&B).
- Q3AP : Conception d'un algorithme parallèle.
Optimisation à la compilation du calcul de la borne inférieure : méthode hongroise.
Etude d'un algorithme hybride couplant méthode approchée et exacte.

Les seconds travaux concernent les bibliothèques :

Enrichissement des bibliothèques d'aide au développement de méthodes exactes ou approchées : Bob++, ParadisEO Kaapi
Etude du couplage de Bob++ avec ParadisEO.

Les derniers consistent en l'implantation et les tests sur les différents systèmes parallèles les plus performants actuellement (Teranova, Grid5000, etc).

B.4. Retombées scientifiques et techniques

Impacts escomptés, Communautés concernées

Le QAP est un des problèmes phares de l'Optimisation Combinatoire. La résolution pour la première fois d'un problème de taille > 30 est susceptible d'avoir un retentissement international qui ne se limitera pas à la communauté Recherche Opérationnelle et à celle du Parallélisme, comme l'a montré l'impact de la résolution de Nugent 30.

D'abord, elle permettra de prouver que le parallélisme peut venir à bout de l'explosion combinatoire. Elle montrera qu'en utilisant des outils efficaces comme les bibliothèques d'aide au développement de Branch-and-Bound ou de metaheuristiques, un utilisateur peut à la fois écrire facilement des algorithmes qui non seulement seront automatiquement parallélisés mais exploiteront au mieux le parallélisme des systèmes informatiques sur les quels ils sont implantés grâce aux diverses bibliothèques.

Toutes les bibliothèques testées lors de ce projet constituent un environnement de programmation pour un utilisateur qui lui permet de développer ces algorithmes sans se soucier de leur parallélisation.

De plus Kaapi est un intergiciel qui permet d'adapter automatique l'application aux ressources matérielles disponibles. La tolérance aux pannes de Kaapi permettra de mener à bien des calculs nécessitant plusieurs jours de calcul sur de grandes architectures.

Actuellement la Recherche Opérationnelle est utilisée dans des sociétés de conseil, des grandes entreprises, etc., pour résoudre de nombreux problèmes d'Optimisation Combinatoire dont la solution ne doit pas être apportée en temps réel. Toutes ces sociétés possèdent des machines de travail en réseau et quelquefois une machine parallèle. On peut imaginer que l'économie de coût obtenue en obtenant une solution optimale par rapport à celui d'une bonne solution approchée soit assez importante pour justifier soit la mise en commun de leur puissance de calcul (grille), soit l'achat de temps calcul sur une machine parallèle.

Ensuite, résoudre ce challenge permettrait :

de valider :
- la technique dite de RLT-1 (relaxation linéaire de niveau 1) utilisée sur ces deux programmes quadratiques en variables 0-1, le QAP et le Q3AP, pour calculer les évaluations dans le Branch-and-Bound,
- la stratégie de branchement utilisée, maximisant le potentiel de parallélisme à exploiter tout en permettant d'éliminer rapidement des sous-ensembles de mauvaises solutions,
de montrer comment l'hybridation d'une metaheuristique et d'un B&B permet de trouver de très bonnes solutions.

Enfin, un programme de Q3AP mis à disposition permettrait de trouver la meilleure solution améliorant un coût technique (moins d'erreurs de transmission) pour un problème d'importance stratégique (réseau de senseurs, communications sans fil). Un programme de QAP améliorerait quant à lui, un coût financier ou technique d'aussi grande importance. Citons pour preuve deux exemples : implantation de services dans les hôpitaux pour minimiser le coût de circulation inter-services (estimé par l'Assistance Publique chaque année à deux ans du coût de construction de l'hôpital), implantation de machines dans une salle en minimisant la longueur des connections.

Projets similaires ou concurrents

Plusieurs équipes travaillent dans le monde sur le QAP. A notre connaissance, l'équipe Opale est la seule à continuer la parallélisation d'une méthode B&B pour le QAP. Clausen (Danemark) a résolu le Nugent 25 en 1998. Le projet Metaneos, obtenteur de la solution de problèmes QAP avec n=30, était composé de chercheurs en Programmation Quadratique pour la partie B&B (Amstreicher, Autriche) et d'informaticiens pour la partie Parallélisme (Plate-forme Condor). Il semble maintenant terminé.

Le Q3AP est étudié en séquentiel par une équipe américaine (P.Hahn, M.Guignard-Spielberg) avec laquelle l'équipe Opale et le laboratoire GILCO (V.-D. Cung) collaborent (sans financement) et qui nous a soumis sa parallélisation.

Plusieurs équipes travaillent sur des bibliothèques pour développer des B&B et participent

régulièrement au Working Group International PAREO, « Parallel Optimization », de la Société Européenne de Recherche Opérationnelle EURO dont le leader est Bertrand Le Cun (http://www.prism.uvsq.fr/~blec/PAREO/) : MetaNEOS / (Argonne NL & Univ. Wisconsin), PUBB (Univ. Tokyo), PPBB-Lib (Univ. Paderborn), ZRAM (Eth Zürich), Mallba (Univ. Barcelone), OOBB (Univ. Montréal).

La plupart de ses bibliothèques ne sont plus maintenues actuellement.

Certaines bibliothèques concernent d'autres techniques pour l'évaluation et sont donc plus dédiées au Branch-and-Price/Cut ; de plus, certaines concernent la programmation mixte MIP (mixed integer programming, variables entières et continues) et utilisent la Programmation Linéaire pour leurs évaluations : COIN (IBM), PARINO (Georgia Tech.), PICO (Sandia Lab. & Rutgers Univ.), Symphony (Rice Univ.).

Les logiciels commerciaux, solveurs de MIP, proposent des parallélisations de Branch and Bound seulement sur machine à mémoire partagée : CPLEX (iLog), XPRESS-MP (Dash Associates).

Pour les metaheuristiques, il n'existe pas de solveurs commerciaux. Les logiciels académiques, soit ne supportent pas toutes les méthodes, soit ne supportent pas le parallélisme et la distribution. Le framework ParadisEO intègre une vue générique de toutes les metaheuristiques, de leur parallélisation et aussi de leur hybridation.

De nombreux environnements de programmation parallèle existent pour l'exploitation des grilles de calcul de grandes tailles (MPI, Condor-MW, XtremWeb, ProActive). A la différence de ces environnements, Kaapi intègre des algorithmes d'ordonnancement et des protocoles pour la tolérance aux pannes ayant des surcoûts à l'exécution très faibles. Cela est dû d'une part à une spécialisation de protocoles généraux au modèle de programmation, et d'une part à la possibilité de ne reprendre que le calcul du processeur défaillant. A la différence de Condor-MW qui a été utilisé par l'équipe américaine pour battre le record Nugent 30 sur 2510 processeurs, Kaapi possède des algorithmes distribués pour l'équilibrage de charge et pour les mécanismes de tolérance aux pannes. Les applications utilisant Kaapi, dont Bob++, passent mieux à l'échelle sans modification du code.

Les résultats obtenus sur le QAP seront bien entendu transmis à la QAPlib (http://www.seas.upenn.edu/qaplib/) qui maintient depuis plus de vingt ans les meilleurs résultats sur une base de données d'instances du QAP.

Les différentes bibliothèques seront disponibles à partir du site web conçu pour le projet CHOC et maintenu en distribué par les équipes participantes.

Après soumission, des liens d'accès seront donnés sur les différents réseaux d'optimisation ou sur les sites des sociétés de RO répertoriant les ressources (INFORMS société américaine, EURO société européenne, ROADEF société française).

Les équipes de CHOC s'engagent à maintenir les liens à travers le site du projet.

B.5.Retombées industrielles et économiques escomptées (le cas échéant)

Nous voyons trois retombées pour la diffusion du parallélisme :

encourager le sociétés utilisant la RO à paralléliser leur méthode,
encourager l'inclusion d'option parallélisme dans les logiciels commerciaux,
encourager les grands groupes industriels et les laboratoires universitaires à acheter des machines parallèles.

Comme dit précédemment, la solution exacte des problèmes de QAP et Q3AP apporte une économie de coût très importante soit financière, soit technique.

B.6. Organisation et pilotage du projet

Compétences des partenaires, nombre de publis

PRiSM, Université Versailles et GILCO, INPG, Grenoble

Equipe OPALE (Catherine Roucairol PF, Bertrand Le Cun MCF, Abdelaziz Djerrah thésard)
Laboratoire GILCO (Van-Dat Cung PF).

L'équipe OPALE de PRiSM-Versailles est spécialiste de la résolution exacte parallèle des problèmes d'Optimisation Combinatoire. Bertrand Le Cun est le contributeur principal de la bibliothèque Bob L'équipe du laboratoire GILCO, à Grenoble est spécialisée en Optimisation en productique et logistique. Van-Dat Cung a travaillé sur le portage de Bob sur CHARM++ ainsi que la première version parallèle du code QAP.

Ces équipes ont déjà collaboré à travers le projet ACI-GRID DOC-G avec l'équipe MOAIS de l'IMAG- Grenoble. Il s'agissait à l'époque de gérer la partie équilibrage de charge avec Athapascan, maintenant La bibliothèque Bob++ a donc été parallélisée en utilisant l'environnement de programmation parallèle Athapascan basé sur le moteur d'exécution Kaapi. Les applications Bob++ s'exécutent de manière transparente sur des architectures parallèles. L'efficacité obtenue sur plusieurs centaines de processeurs a montré l'intérêt des algorithmes d'ordonnancement utilisés

L'équipe ARPA de Versailles est spécialiste de compilation, et nous bénéficierons gracieusement de leur appui pour optimiser à la compilation certaines procédures de calcul.

Ces équipes participent régulièrement au Working Group International PAREO, « Parallel Optimization », de la Société Européenne de Recherche Opérationnelle EURO dont le leader est Bertrand le Cun (http://www.prism.uvsq.fr/~blec/PAREO/). E-G.Talbi et C.Roucairol sont éditeurs de livres à paraître chez Wiley, respectivement « Parallel Optimization » en 2005 et « Parallel Branch-and-Bound : algorithms, libraries » en 2006.

Strategies for the Parallel Implementation of Metaheuristics
V.-D. Cung, S.L. Martins, C.C. Ribeiro and C. Roucairol, in Essays and Surveys in Mathematics, Guest Editors C.C. Ribeiro and P. Hansen, Kluwer Academic Publishers, 263-308, 2001.
Solving Quadratic Assignment Problem on Cluster with a Bound of Reformulation Linearization Technique
A. Djerrah, S. Jafar, V.-D. Cung, P. Hahn.
17ème Congrès Mondial IMACS Calcul Scientifique, Mathématiques Appliquées et Simulation
11 - 15 Juillet 2005 Paris, France.
Solving Large Quadratic Assignment problems On Cluster and Grid with Bob/Athapascan.
A. Djerrah, V.-D. Cung and C. Roucairol.
Fourth International Workshop of the EURO Working Group on Parallel Processing in Operations Research (PAREO),
16-21 janvier 2005, Mont-Tremblant, Montral, Canada.
Résolution du Problème d'Affectation Quadratique sur Grille de calcul.
A. Djerrah, V.-D. Cung et T. Mautor.
5ème congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision (ROADEF)
26, 27 et 28 février 2003, Avignon, France.
Recent development of the Bob++ Library
B. Le Cun
Fourth International Workshop of the EURO Working Group on Parallel Processing in Operations Research (PAREO),
16-21 janvier 2005, Mont-Tremblant, Montral, Canada.
Evaluation the impact of Metacomputing on Combinatorial Optimization.
Van-Dat Cung et Bertrand Le Cun
Semi plenary session in EURO2001, 9-11 Juillet 2001
Software modelizations for Combinatorial Optimization Algorithms
Bertrand Le Cun
PAREO2002, 20-24 Mai 2002 Guadeloupe

ID, IMAG, (T Gautier), Université de Grenoble

Le projet MOAIS s'intéresse à la programmation d'applications pour lesquelles l'adaptation au nombre de ressources est importante pour l'augmentation des performances. Outre l'optimisation de l'application elle-même, l'exploitation effective d'un grand nombre de ressources est fondamentale. Cela inclut les applications de simulation interactive à grande échelle qui ont jouées un rôle important pour le développement du calcul parallèle à hautes performances. La programmation indépendamment des architectures de ces applications nécessite, d'une part, d'abstraire l'architecture, et, d'autre part, d'adapter l'exécution aux ressources disponibles grâce à des algorithmes d'ordonnancement. Le centre de la recherche du projet MOAIS est l'étude des algorithmes d'ordonnancement.

M. Daoudi, T. Gautier, A. Kerfali, R. Revire and J.-L. Roch. « Algorithmes parallèles à grain adaptatif et applications ». In Technique et Science Informatique (TSI), Hermès (2005).
T. Gautier, R. Revire and F. Zara« Efficient and easy parallel implementation of large numerical simulation ». In Proceedings of ParSIM03/EuroPVM/MPI, (2003).
T. Gautier and H.R. Hamidi.« Automatic Re-scheduling of Dependencies in a RPC-bases Grid ».In Proceedings of the 18th annual ACM International Conference on Supercomputing (ICS'04), pages 89-94, Saint-Malo, France. ACM Press. June 2004.
T. Gautier and H.R. Hamidi. « Re-scheduling invocations of services on RPC-based Grid » Intern. J. Comput. Languages, Systems and Structures, Special Issue on Semantics and Cost Models for High-Level Parallel Programming, to appear (2005).
S. Jafar, T. Gautier, A.W. Krings and J.-L. Roch. « Theft-Induced Checkpointing for Reconfigurable Dataflow Applications ».In Proceedings IEEE Electro/Information Technology Conference, EIT2005. May 22-25, Lincoln, Nebraska, 2005, U.S.A.
S. Jafar, T. Gautier, A.W. Krings and J.-L. Roch. « A checkpoint/recovery model for heterogeneous dataflow computations using work-stealing ». In Proceedings of the EuroPar'05 Conference, Lecture Notes in Computer Sciences, Springer, vol. 3648, pp. 675-684 (2005).

LIFL, (E.Talbi), Université de Lille

L'équipe DOLPHIN a pour objectif la modélisation et la résolution parallèle de problèmes d'optimisation combinatoire (multi-objectifs) de grande taille. Des méthodes parallèles coopératives efficaces sont développées à partir de l'analyse de la structure du problème traité. Les problèmes ciblés appartiennent aussi bien à la classe des problèmes génériques (ordonnancement flow-shop, élaboration de tournées, etc.) que des problèmes industriels issus des télécommunications et de la génomique. L'équipe participe activement au projet ACI Grid'5000 (Responsable du noeud Lillois), et au projet ACI-GRID « GRID2 » E-G Talbi est responsable du thème « Optimisation et data mining sur Grilles ».

E-G. Talbi, "Parallel Combinatorial Optimization", John Wiley & Sons, USA, 2005.
E-G. Talbi, « A taxonomy of hybrid metaheuristics », Journal of Heuristics, Vol.8, No2, pp.541-564, Sept 2002.
S. Cahon, N. Melab and E-G. Talbi, « ParadisEO: A Framework for the Reusable Design of Parallel and Distributed Metaheuristics, Journal of Heuristics, Vol.10, No.3, pp.357-380, May 2004.
S. Cahon, N. Melab, E-G. Talbi, « Building with ParadisEO reusible parallel and distributed evolutionary algorithms », Parallel Computing, Vol.30 , No.5-6, pp.677-697, June 2004.
E-G. Talbi, V. Bachelet « COSEARCH: A parallel cooperative metaheuristic », Journal of Mathematical Modelling and Algorithms JMMA, accepté, à paraître 2005.
E-G. Talbi, E. Alba, Metaheuristics and parallelism in Parallel Metaheuristics, Edited by E. Alba, John Wiley and Sons, USA, 2005.
C. Cotta, E-G. Talbi, E. Alba, Parallel hybrid approaches in Parallel Metaheuristics, Edited by E. Alba, John Wiley and Sons, USA, 2005.
M-S. Mezmaz, N. Melab and E-G. Talbi, Towards a Coordination Model for Parallel Cooperative P2P Multi-objective Optimization, Lectures Notes in Computer Science LNCS, Proc. of European Grid Conf. (EGC'2005), Amsterdam, Netherlands, Feb. 2005
S. Cahon, N. Melab, E-G. « An enabling framework for parallel optimization on the computational Grid», IEEE/ACM Int. Conf. Cluster Computing and Grid CCGrid'2005, Cardiff, UK, May 2005.

Travaux dans CHOC (objectifs, délivrables produits, contenu du travail)

Bibliothèques

Kaapi : tolérance aux fautes, ordonnancement avec priorité sur machines hétérogènes.
Finalisation de Bob++ et portage au dessus de Kaapi.
Portage de ParadisEO sur Kaapi.
Coopération Bob++/ParadisEO.
Code QAP/Q3AP au dessus de ParadisEO et Bob++

Le mode de gouvernance suivra les 4 sous-projets décrits ci dessus. Plusieurs réunions de travail seront organisées pour fixer les interfaces des bibliothèques afin d'en déduire les tâches à réaliser. Ces réunions pourront être faites par des visites mutuelles ou par vidéo-conférence.

Il est bien entendu que les différents ingénieurs experts recrutés dans l'équipe Opale-PRiSM (Versailles) et l'équipe Dolphin-INRIA (Lille), devra bien évidemment fortement coopérer avec l'équipe Kaapi et l'équipe du laboratoire GILCO (Grenoble).

B.7. Proprièté intellectuelle

Apports faits au projet CHOC par les partenaires

Les logiciels développés dans le cadre de ce projet Kaapi, Bob++, ParadisEO sont des logiciels « open source ». Le framework ParadisEO est en open-source sous la licence L-GPL.

Principe de l'accord concernant la propriété intellectuelle et les droits d'exploitation.

Nous joignons en annexe un texte diffusé par l'INRIA sur la propriété intellectuelle. Deux des partenaires sont des projets INRIA (DOLPHIN et MOASIS).

Les règles de propriété intellectuelle seront fixées au sein d'un document contractuel de partenariat indépendant de la présente proposition (protocole d'accord), une fois que la présente proposition sera acceptée par l'organisme auprès duquel le projet fait l'objet de la présent proposition. En tout état de cause, les principes de propriété intellectuelle qui s'appliqueront sont les suivants :

désigne toute connaissance brevetée ou non, savoir-faire, secret de fabrique ou tout autre type d'information sous quelque forme que ce soit, appartenant à ou détenue par l'un des partenaires antérieurement au projet ou acquise par lui indépendamment de l'exécution du projet, mais nécessaires à la réalisation du projet ou à l'exploitation des résultats du projet.

désigne toute connaissance brevetée ou non, savoir faire, secret de fabrique ou tout autre type d'information, sous quelque forme que ce soit, résultant directement des travaux du projet et obtenus par le personnel d'un seul partenaire, sans le concours du personnel de l'autre partenaire.

désigne toute connaissance brevetée ou non, savoir faire, secret de fabrique ou tout autre type d'information, sous quelque forme que ce soit, résultant directement des travaux du projet et obtenus conjointement par le personnel des deux partenaires

Chaque partenaire conserve la propriété totale et exclusive de ses connaissances antérieures.

Cependant, pour les seuls besoins du projet et pour la seule durée du projet, chaque partenaire pourra, sur demande expresse et sous obligation de confidentialité, utiliser sans contrepartie financière les Connaissances Antérieures de l'autre partenaire.

Chaque partenaire sera propriétaire de ses Résultats Propres, qu'il aura générés seul, sans le concours du personnel de l'autre partenaire, et décidera seul de l'opportunité et de la nature des mesures de protection à prendre, à ses seuls nom et frais.

Les Résultats Communs seront la propriété conjointe des partenaires, qui décideront ensemble de l'opportunité et de la nature des mesures de protection à prendre, en leurs noms conjoints et à leur frais partagés. Le partenaires élaboreront un règlement de copropriété avant toute exploitation.

Chaque partenaire dispose librement de ses Connaissances Antérieures.

Chaque partenaire s'engage à concéder à l'autre partenaire, sur demande expresse de celui-ci, des licences sur ses Connaissances Antérieures nécessaires à la valorisation des Résultats Propres ou Communs du projet, à des conditions financières préférentielles.

Chaque partenaire pourra librement exploiter et utiliser les Résultats Propres dont il est propriétaire, directement ou par voie de concession de licence.

Les Résultats propres d'un partenaire nécessaires à l'exploitation des Résultats Propres de l'autre partenaire feront l'objet d'une licence à négocier à des conditions financières préférentielles.

Les partenaires copropriétaires des Résultats Communs, régleront les modalités d'exploitation dans le cadre du règlement de copropriété sus mentionné.