Programme STIC INRIA - Universités Tunisiennes

- MODELISATION ET DEPLOIEMENT DES SYSTEMES PARALLELES A LARGE ECHELLE -

(plan de travail 2005)


Ce document présente notre projet 2005 dans le cadre du Programme STIC INRIA - Universités Tunisiennes. Le titre du projet est : MODELISATION ET DEPLOIEMENT DES SYSTEMES PARALLELES A LARGE ECHELLE

Mots clés : Modélisation algorithmique - Calcul Scientifique - Parallélisme - Performance – Gestion de ressources - Programmation et déploiement de codes – Gestion de masses de données - Systèmes distribués à large échelle.



Résumé du projet :

L'objectif visé, à travers la consolidation et l’extension des liens déjà tissés entre les équipes engagées, notamment dans le cadre de projets CMCU est de contribuer à la création de pôles d’excellence dans le domaine du parallélisme et des systèmes distribués à large échelle. Ce projet correspond à des évolutions scientifiques importantes par rapport à ce que les intervenants ont pu faire dans les années passées et dans le cadre du CMCU 0199/F1407 (2001-2003). Il s'agit maintenant d'étudier des problèmes liés au passage à l'échelle (on vise à faire coopérer plusieurs dizaines de milliers de machines) tout en capitalisant sur nos travaux antérieurs en matière de parallélisme. Il s'agit aussi pour la partie Tunisienne de s'investir plus profondément dans la thématique des grilles qui représente une thématique d'importance et émergente.

Le projet vise également la formation doctorale, le rapprochement et le transfert vers l'industrie en Tunisie. Les thèmes retenus et grâce à l'expertise et la complémentarité des acteurs, permettront, de par leurs impacts pratiques, de concevoir des outils de développement performants, de qualité et opérationnels. Pour la première année (2004-2005), nous avons d'ores et déjà obtenu le soutien de IBM (Olivier Hess, IBM Deep Computing EMEA / ATS – P.S.S.C à Montpellier) et nous leur avons proposé de se déplacer en Tunisie pour effectuer du transfert. Une machine IBM a été installée en Tunisie il y a quelques années.

Les deux principaux thèmes de recherche sont :

Le projet de recherche présenté ici se propose d'apporter une contribution sur les plans aussi bien théorique que pratique dans le domaine de la modélisation, la programmation des systèmes parallèles à large échelle (déployés sur plusieurs milliers de machines). Nous visons en particulier la conception et la mise en oeuvre (déploiement) d'outils applicatifs simples et pratiques, basés sur les récents développements théoriques associés aux systèmes à large échelle.

Les porteurs du projet sont :

Le document est organisé en trois parties. Dans la première partie nous résumons rapidement les résultats scientifiques et apports de la coopération CMCU 2001-2003 ce qui permet de mettre en perspective nos projets scientifiques. Dans la deuxième partie nous motivons notre demande. La troisième partie fixe nos pistes d'actions.



I- Résumé des principaux faits marquants de la coopération antérieure (CMCU 2001-2003)

Le projet CMCU (code 0199/F1407) auquel certains des chercheurs du présent projet ont participé a très clairement eu un impact significatif sur la production scientifique des participants au projet, une dynamisation de la formation doctorale en Informatique en Tunisie et un effet structurant sur l’équipe de recherche tunisienne. Ceci a pu se produire grâce à une spécialisation des sujets traités et grâce à une immersion progressive dans la communauté internationale et francophone, notamment par le biais de l'organisation en Tunisie, par les membres de la CMCU, du colloque RENPAR (rencontre francophone du parallélisme) conjointement aux colloques SymPa’8 et ASF, et qui a rassemblé à Hammamet (avril 2002) plus de 150 spécialistes.

Le précédent projet a apporté des moyens au développement d'une politique de recherche de haut niveau en Informatique au sein de l’équipe tunisienne, politique cohérente et ambitieuse. Elle a permis aux collègues français d'accueillir dans des laboratoires français et dans de bonnes conditions matérielles des étudiants et chercheurs tunisiens. Un total de 16 mois a permis de recevoir 5 étudiants juniors et 4 chercheurs seniors en France. Durant ces visites, des déplacements pour des séminaires ont de plus été effectués, accentuant de la sorte les échanges scientifiques des visiteurs. Plusieurs missions dans le sens France-Tunisie ont permis de suivre les travaux de recherche communs et l’organisation de séminaires spécialisés.

Le projet CMCU 01/F 1407 (2000-2003) portait sur la programmation des systèmes parallèles et distribués. Il s'agissait par exemple d'étudier les environnements de programmation parallèle. L'objectif etait de décharger au maximum le programmeur des problèmes rencontrés lors de la programmation parallèle, problèmes qui peuvent être résolus de manière automatique. Cette solution conduit également à une meilleure portabilité des applications puisque les programmes font complètement abstraction de la machine parallèle utilisée. Ainsi beaucoup de modèles de programmation ont été proposés dans ce sens.

D'autres domaines relativement classiques ont aussi été étudiés comme la conception et le développement d'algorithmes parallèles : ordonnancement et placement de calculs sur les processeurs, gestion des communications entre les processeurs.

Toutes ces études sous-entendaient que le système parallèle sous-jacent était homogène c'est à dire qu'il était constitué de noeuds de calcul identiques (même processeur, même carte mémoire...). Il sous-entendait également que les noeuds étaient toujours disponibles, que l'identité des noeuds était connue, qu'il y avait de la confiance dans le système (un noeud « malicieux » ne pouvait pas donner une « mauvaise réponse »).

Notre demande actuelle vise à obtenir des moyens pour lever ces contraintes. Il s'agit d'un axe de recherche complètement nouveau par rapport aux précédentes préoccupations du groupe mais en parfaite synergie avec différentes actions d'importance en France (actions ACI Masses de Données, Grid'5000, GridExplorer...) dont certaines équipes INRIA sont partie prenante.

Au final, les chiffres marquants des trois années passées (2001 – 2003) peuvent se résumer ainsi et permettent d'apprécier le travail réalisé :



II- Motivations un projet INRIA - Universités Tunisiennes

Les deux principales motivations pour cette demande sont l'approfondissement des échanges (mise en place de journées de formation doctorale par exemple) et la mise en oeuvre de nouvelles orientations scientifiques liées à l'évolution de la discipline et à l'apparition d'activités émergentes du coté tunisien.

Le contour de ce projet est sensiblement modifié par rapport aux configurations antérieures tant au niveau des acteurs que des thématiques scientifiques retenues.

L'approfondissement des échanges concerne par exemple la mise en oeuvre de thèses en cotutelle (demande de soutiens à nos ministères) à la suite des résultats obtenus en DEA par les étudiants suivis pendant le projet CMCU 2001-2003. Les travaux réalisés ont permis également la soutenance de l'habilitation à diriger les recherches de Mohamed Jemni en 2004.

L'approfondissement des échanges correspond aussi à pouvoir mettre en oeuvre une politique de transferts techniques : mise en oeuvre de formations courtes sur l'utilisation, l'installation de logiciels et de matériels. Par exemple, l'émergence du concept de calculs sur une grille fait qu'une connaissance approfondie des couches bas niveau des systèmes d'exploitation des PC (Windows et Linux) ainsi que les logiciels d'administration des grilles est souhaitable. Nous avons constaté des manques sur les compétences techniques au cours de nos précédentes coopérations.

Des savoir-faire techniques en administration et en déploiement (de code et d'architectures) sont à acquérir aussi bien du côté français que du côté tunisien. Dans ce cadre, nous pouvons compter sur les expériences de l'IMAG de Grenoble qui dispose actuellement de plusieurs grappes. Sur cette base, nous chercherons alors à construire des solutions opérationnelles (algorithmes implémentés, logiciels testés, validés).

Dans cette optique, nous avons aussi obtenu le soutien de IBM – france.

Notre interlocuteur chez IBM (Olivier Hess, IBM Deep Computing EMEA / ATS – P.S.S.C à Montpellier) nous a donné son accord pour que des membres de son service puissent participer en Tunisie (en fonction des disponibilités et sur des séjours courts de 3 / 4 jours) à des missions de transfert technologique : présentations d'architectures et de solutions logicielles notamment Linux, aide à la constitution de solutions clusters et de grilles.



De plus, des orientations scientifiques nouvelles doivent aussi être mise en oeuvre dans le nouveau projet. L'idée est de couvrir de nouveaux champs disciplinaires en nous appuyant sur nos acquis. Les orientations scientifiques que nous envisageons et sur lesquelles nous souhaitons mettre une incise sont plus particulièrement :

Ces orientations se déclinent dans les sous thèmes suivants :



2.1 Thématiques et projets retenus

2.1.1 Introduction

Les grilles correspondent à un concept apparu en 2000 dans la communauté. La France a lancé en 2001-2002 des projets scientifiques qui sont coordonnés conjointement par le Ministère, le CNRS et l'INRIA. Les projets phares français sont rassemblés dans des ACI (Actions Concertées Incitatives) parmi lesquelles nous trouvons l'ACI grilles et l'ACI masse de données (http://acimd.labri.fr).

Les grilles et les systèmes pair à pair (P2P) stockent et véhiculent des masses de données considérables : jusqu'à l'ordre du PetaOctet (1000000 GigaOctet) en stockage (Data Grid, grands systèmes P2P) et du TeraOctet/seconde (1000 GigaOctets) en débit moyen (grands systèmes P2P). Physiquement, les grilles sont constituées en mutualisant les ressources de plusieurs milliers de PCs, d'assistants PDA, de portables connectés par Internet. Dans ce cas il faut gérer les problèmes de déconnexion entre les machines dans un environnement non fiable. Elles sont aussi constituées par l'interconnexion de machines situées dans de grands centres de calcul, dans ce cas il y a de la confiance dans les connexions et des débits réseaux importants sont disponibles.

La motivation centrale pour construire de tels dispositifs matériels et logiciels est d'offrir à la communauté scientifique un accès à des ressources mutualisées. A terme, il s'agit aussi d'offrir à la société civile des moyens pour utiliser les ressources de la société numérique de l'information.

Data Grid Explorer (http://www.lri.fr/~fci/GdX) est un exemple de projet labellisé en France en juin 2003 qui vise à mettre en oeuvre un grand instrument d'émulation des grilles pour les communautés a) des systèmes distribués à grande échelle, b) des réseaux et c) des utilisateurs des Grilles ou des systèmes P2P (pair à pair). Ce grand émulateur est constitué d'une base de données de conditions expérimentales, d'un grand cluster et d'outils de conduite et d'analyse d'expériences. L'intérêt de l'émulation est la capacité de reproductibilité des conditions expérimentales et des résultats.

Les grappes de PC (voir http://www.clustercomputing.org/) peuvent être vues quant à elles comme des "petites grilles" de quelques centaines de machines. L'IMAG de Grenoble, partenaire du projet a un savoir faire important en la matière, acquis en partie grâce à l'installation à Grenoble d'un système qui a été composé dès 2001 de 104 processeurs Ithanium bi-processeurs et d'une "grille locale" (CiGri) de plus de 500 machines réparties sur 5 sites comme réseaux de grappes.

Ainsi, notre projet va pouvoir bénéficier de l'expertise de l'IMAG quant au déploiement de systèmes performants ce qui nous permettra d'assurer un transfert à la pointe de la technologie comme cela est annoncé dans nos objectifs généraux.

Il y a de fortes synergies entre les sous-thèmes proposés comme cela est représenté dans la figure 1 où les flèches indiquent les interactions entre les sous-projets.






Figure 1 : Vue d'ensemble du projet

Nous étudierons le mouvement et le stockage de données (problème du tri sur disques, problème de la fouille) dans ces systèmes de façon analytique et expérimentale à partir de déploiements en vue de production. Il y a donc des liens immédiats entre les travaux proposés par Cérin, Jemni, Slimani (voir les détails plus bas).

Que ce soient les grilles ou les clusters, ces systèmes sont parallèles. Ils sont déployés en grand nombre ce qui implique qu'il faut être capable de gérer de l'ordre de 10000 machines, par exemple le PC du particulier. Le déploiement d'algorithmes à cette échelle ne peut pas se faire de manière simple en ré-utilisant directement le travail de l'algorithmique et de la programmation parallèle "classique".

Par exemple, comme la charge des 10000 machines mutualisées varient dans le temps (le système parallèle n'est pas dédié), il faut être capable de sélectionner parmi un ensemble d'algorithmes celui qui répondra de la meilleure façon pour une taille de problème et un ensemble de ressources disponibles. C'est la notion de poly-algorithmes que nous nous proposons d'étudier. Cette notion est déclinée pour des problèmes matriciels, elle pourra l'être aussi pour le problème du tri que nous avons étudié dans le cadre de la précédente CMCU. Il y a donc des interactions fortes entre les recherches de Trystram, Mahjoub, Emad, Cérin (voir les détails plus bas).

Par ailleurs, les 10000 machines visées sont de fait hétérogènes : elles ont des capacités disque et mémoire différentes, des processeurs différents, des systèmes d'exploitation différents, des débits vis à vis d'Internet différents. Nous nous intéresserons à la problématique de la répartition des charges de travail et à l'ordonnancement du travail dans un contexte hétérogène donné, par exemple celui où les processeurs ne vont pas tous à la même vitesse. Les travaux proposés de Mahjoub, Trystram, Cérin, Jemni sont complémentaires.

Contrairement aux approches statiques qui prédéterminent les calculs comme cela à été fait pour le tri dans le passé, nous envisageons des approches « à la volée » c.à.d. que l'on prend une décision de placement, d'ordonnancement quand on observe qu'un paramètre (charge du processeur par exemple) varie de manière significative.

Feautrier et Jemni terminent l'encadrement de la thèse de Yosr Slama qui touche aux machines à mémoires distribuées. Les extensions naturelles de ces travaux algorithmiques sur des matrices creuses sont réutilisables et un portage comme bibliothèques utilisables dans un noeud collaborant au sein d'une grille est possible à notre avis.

La méthodologie de la parallélisation automatique de code pour machines à mémoire partagée (Feautrier, Jemni) pourrait par ailleurs être utilisée dans l'automatisation de la notion de poly-algorithme (Trystram, Nasri).

Les travaux théoriques de Marrakchi sur des problèmes spécifiques d'algorithmique hétérogène sont un travail en amont qui permettent de comprendre l'influence du caractère hétérogène sur les algorithmes (Emad, Cérin).

L'axe consacré à l'ordonnancement (Marrakchi, Trystram) peut s'inscrire également dans la problématique de gestion et allocation de ressources pour Grille (Nasri, Trystram, Mahjoub).

Ces exemples montrent la cohésion des actions envisagées et les interactions entre les personnes.

Les travaux sur l’optimisation de requêtes dans le cadre des grilles de données (Slimani, Najjar, Mami) permettent d’étudier l’effet de l’hétérogénéité des débits des réseaux sur le coût d’exécution d’une requête de base de données.

Les travaux sur le problème de placement de répliques de fichiers dans les grilles (Slimani, Lahmaidi) ont pour objectif de définir des protocoles de placement initial de répliques qui minimisent le coût de communication. Toujours dans ce cadre, les travaux de placement de bases de données (Slimani, Haddad) se proposent de définir des méthodes de placement de bases de données relationnelles qui permettent de réduire les coûts d’accès, notamment pour l’exécution d’opérations de jointure.

Voilà maintenant dans le détail les différents sous-projets.

Sous projet I : Stockage sur grappes et grilles : applications à la fouille de données

Le domaine relatif à la technologie des bases de données souffre, aujourd’hui, d’une explosion du volume d’informations manipulées (croissance de 30% en moyenne par an) et de la complexité des opérations mises en œuvre. L’émergence de nouvelles applications, tels que les systèmes décisionnels (OLCP et OLAP des entrepôts de données), nécessitent un grand nombre d’opérations de jointures et utilisant des bases de données volumineuses (de l’ordre de 10 To). Ceci impose de disposer d’une puissance de traitement considérable, qui plaide fortement en faveur de l’utilisation de systèmes parallèles à grande échelle.

L'opération de jointure peut s'implémenter par un tri qui est un problème important pour lequel nous avons acquis une solide expérience dans le cadre d'un cluster hétérogène (les processeurs vont à des vitesses différentes).

Par ailleurs, il est connu que bien que la vitesse des processeurs double tous les 18 mois et que les capacités des disques augmentent de l'ordre de 30% par an, leurs temps d'accès ne diminuent que de l'ordre de 10% (à peine) par an. Il est donc de plus en plus coûteux en temps d'accéder à une donnée. Une des solutions pour pallier à ce goulet d'étranglement est d'effectuer les requêtes disques en parallèles et de distribuer les données sur de nombreux disques.

1- Stockage

a) Tris sur disques

Les principaux acteurs sur cette thématique sont : Christophe Cérin, Mohamed Jemni, Hazem Fkaier.

Nous souhaitons par ailleurs poursuivre notre travail sur le tri disque et nous avons fait une demande de cotutelle de thèse pour Hazem Fkaier via le canal du ministère. Le tri est un problème fondamental de l'informatique. Trier à l'échelle d'une grille est un problème difficile qui n'a pas encore été abordé à notre connaissance.

Ce thème représente la continuité des travaux entamés par Hazem Fkaier, Christophe Cérin et Mohamed Jemni autour de la gestion de la hiérarchie mémoire - application à des algorithmes de tri séquentiels et parallèles, internes et externes en milieux homogène et hétérogène.

L’objectif principal des travaux effectués était la conception d'algorithmes parallèles de tri efficaces en milieu homogène (les processeurs ont la même vitesse d’exécution) ou en milieu hétérogène (les processeurs sont à des vitesses différentes). Les algorithmes étudiés entrent dans la famille des algorithmes de tri par échantillonnage et ils sont basés sur le partage des données suivant des pivots choisis parmi un nombre de candidats pris aléatoirement.

L’approche est basée principalement sur un méta-schèma de partitionnement qui donne (et préserve) à chaque processeur une quantité de travail proportionnelle à sa vitesse. Les algorithmes développés garantissent ensuite des bornes à l'équilibrage des charges, c'est à dire au travail effectué par chacun des processeurs en cours d'exécution.

L’ensemble de ces travaux a été couronné par un DEA accompli (par Hazem Fkaier) et soutenu en janvier 2003 et trois publications internationales (IPDPS'2003, CCGRID'2003 et SBAC'2004).

Les perspectives des travaux sont nombreuses et variées et soulèvent des problèmes difficiles que nous essayons d’aborder dans le futur proche et qui peuvent constituer une partie du sujet de thèse de Hazem Fkaier à co-encadrer par Christophe Cérin et Mohamed Jemni. Nous pouvons citer les questions suivantes :

2- Bases de données distribuées à large échelle

a) Optimisation de requêtes distribuées dans les systèmes à grande échelle

Les principaux acteurs sont : Mami Najla, Najjar Faiza, Haddad, Slimani Yahya

Afin de traiter efficacement une requête déclarative de haut niveau (exprimée en SQL par exemple), un SGBD relationnel doit générer un plan procédural, qui décrit, à un certain niveau de détail, l’ordre d’exécution des différentes opérations et leur implantation sur la machine cible. Il choisit ensuite « le plan » qui vérifie un certain modèle de coût. Dans un environnement distribué à grande échelle, le traitement d’une requête nécessite souvent la transmission des données et/ou des opérations ainsi qu’éventuellement des résultats intermédiaires entre les sites d’un réseau.

Dans ce cadre, le problème d’optimisation se pose avec plus d’acuité que dans le cas d’un système centralisé. Le point essentiel est que, dans une requête faisant intervenir plusieurs sites (homogènes dans le cas classique, mais hétérogènes en réalité), il y aura plusieurs façons de déplacer les données et/ou les opérations dans le réseau pour exécuter la requête. Aussi, il est important de trouver une stratégie efficace.

Cette problématique d’optimisation a été largement étudiée (notamment par F. Najjar dans le cadre de sa thèse soutenue en 1999) dans le cas d’environnements homogènes (sites ayant les mêmes capacités de calcul, de stockage et d’accès aux données). Par contre, très peu de travaux ont été faits dans le cas hétérogène. Aussi, nous envisageons d’étudier, dans le cadre de ce thème de recherche, le problème de l’optimisation de requêtes distribuées dans le cadre de systèmes parallèles à grande échelle, en tenant compte du facteur hétérogénéité. Pour cela, il s’agira de définir un modèle de coût qui tient compte de paramètres classiques (coût CPU, coût E/S, coût de communication) mais dans un contexte hétérogène. A partir de ce modèle, il faudra proposer de nouvelles stratégies d’exécution parallèle des opérations de jointures, qui tiennent compte de l’hétérogénéité des sites, des réseaux de communication et de la localité des données (données partitionnées ou répliquées).

Sur le plan pratique, il s’agira de valider les propositions (modèle et stratégies d’exécution parallèle) par des expérimentations en grandeur nature sur des applications OLAP qui, en général, utilisent des requêtes relationnelles complexes en lecture. La partie expérimentation se fera sous différents environnements (MPI, OPEN MP) sur la machine RS/6000 de la Faculté des Sciences de Tunis et sur les grilles de calcul du laboratoire ID de Grenoble ou celles qui nous seront ouvertes (GridExplorer ?)

b) Fouilles de données (Datamining) et parallélisme

Les principaux acteurs sont Ben Hadj Hamida Moez, Ben Tetaka (Tekaya) Soundess (Sondess), Rezgui Jihene, Hamrouni Tarek, Gasmi Ghada, Sadok Benyahia, Arour-Bouabid Khedija, Tlili Raja, Slimani Yahya.

Les techniques de saisie et de stockage d'informations permettent d'accumuler des masses considérables de données. Ces masses de données renferment de la connaissance cachée qu'il faudra extraire à l'aide de techniques d'analyse. Cette extraction est faite à l'aide d'algorithmes qui produisent de la connaissance sous forme de règles associatives. Le coût d'extraction de cette connaissance est d'ordre exponentiel. Cette complexité est due à la conjonction de deux facteurs essentiels : le volume de données à explorer et l'aspect hautement itératif des algorithmes de génération de règles associatives. Une des voies qui permettrait d’améliorer les performances des algorithmes d’extraction, serait de les paralléliser. Une autre voie, complémentaire au parallélisme, consisterait à trouver des structures de données compactes pour représenter de grands ensembles de données. Actuellement, les membres de ce sous thème ont proposé deux structures de données qui se sont avérées très efficaces du point de vue taux de compactage ; ces structures ont été testées sur différentes bases de données et les résultats expérimentaux sont très encourageants.

Ce thème de recherche a pour objectif de fédérer un certain nombre de travaux de recherche anciens et actuels menés par certains membres du projet autour de la parallélisation d’algorithmes de datamining (2 stages de DEA et 6 stages de Mastère). Il s’agit d’explorer un certain nombre de voies pour générer, à partir de bases de données transactionnelles très volumineuses, un ensemble de règles associatives. Cette génération doit satisfaire deux critères importants : performance du point de vue coût de génération et minimalité des ensembles générés (absence de redondance dans les règles générées). Comme voies de recherche en cours d’étude, nous pouvons citer :

L’approche de parallélisation que nous utilisons dans le cadre de nos recherches est une approche basée sur le calcul (parallélisation du traitement), alors que les travaux actuels utilisent une parallélisation par les données (partition de la base de données entre différents sites). En fonction des résultats qui seront obtenus, nous envisageons d’explorer une autre approche hybride, qui combinerait l’approche basée sur les traitements et celle basée sur les données. Toutes les propositions qui seront faites dans le cadre de ce thème seront validées par des études théoriques de parallélisation et de complexité ainsi que par des expérimentations sur la plate-forme de la Faculté des Sciences de Tunis (machine IBM RS/6000) et les grilles de calcul du laboratoire ID de Grenoble.

A noter que ce thème de recherche bénéficie du concours de deux chercheurs qui font partie d’une équipe de recherche du Département des Sciences de l’Informatique de la Faculté des Sciences de Tunis (Equipe ERPAH) et qui préparent une habilitation (K. Arour et S. Benyahia). Ce thème de recherche bénéficie également des compétences de Christophe Cérin et Michel Koskas, membres de GridExplorer et porteurs du projet Zeta Data. Ce projet vise l'introduction de nouvelles structures de données (arbres de radicaux) dans les algorithmes de génération de règles d'associations et se veut une application cible pour le projet GridExplorer.

c) Grilles de calcul et tolérance aux fautes

Les principaux acteurs sont : Lahmaidi Wahida, Slimani Yahya, Gregory Mounie, Denis Trystram

De nombreuses recherches ont été consacrées ces dernières années au partage efficace de la puissance de calcul distribuée à une grande échelle. Ces recherches ont permis de proposer un environnement de programmation (système Globus), qui permet de gérer des grilles de calcul totalement hétérogènes constituées de plusieurs centaines d'ordinateurs et supercalculateurs.

Par contre, peu de travaux ont été consacrés à la gestion de données à très grande échelle. Or, cet aspect est en train de prendre actuellement une importance croissante. L’objectif de ce thème de recherche est d’étudier le problème de disponibilité des données dans le cadre de grilles de calcul, en introduisant un aspect tolérance aux fautes basé sur la technique de réplication.

Comme dans le cas des systèmes classiques, la technique de réplication a été utilisée, dans le cadre des grilles de calcul, pour d'une part, améliorer les performances d'accès aux données, et pour assurer de la tolérance aux fautes, d'autre part. La problématique de réplication de données dans une grille peut se formuler comme suit : un ensemble de données peut se trouver réparti dans un ou plusieurs sites disposant de capacités de stockage et d'accès très hétérogènes. Les utilisateurs de cet ensemble de données peuvent ne pas avoir de ressources de stockage suffisantes pour disposer d'une copie intégrale de ces données.

Un sous-ensemble (qu'il faudra déterminer) de ces données sera stocké localement de manière à accélérer l'accès aux données. Il faut donc définir un protocole de réplication de données qui puisse satisfaire un certain nombre de propriétés telles que : créer des copies d'une partie ou de la totalité d'un ensemble de données, gérer les différentes copies, sélectionner la meilleure copie du point de vue des performances, assurer une disponibilité continue des données, etc. Une fois le protocole défini et validé théoriquement, il sera expérimenté sur différentes grilles de PC fonctionnant sous Linux (grille de la Faculté des Sciences de Tunis et grille du laboratoire ID de Grenoble).

d) Gestion des ressources dont les données sur disques dans le cas de grilles de calcul

Les principaux acteurs sont : El Moutakel Tahar, Yahya Slimani, Denis Trystram, Christophe Cérin.

Du point de vue capacité de traitement, une grille de calcul offre une puissance de calcul très importante. Cette puissance de calcul nécessite la mise en place d'outils d'administration et de gestion de ressources, pour l'obtention d'une haute performance. L'objectif de ce thème de recherche est d'étudier et de proposer des stratégies d’allocation de ressources, pour permettre une meilleure gestion des ressources dans une grappe de calculateurs homogènes interconnectés par un réseau à très haut débit. L'idée est de considérer que du point de vue utilisateur, une grille représente une machine virtuelle (globalisation des ressources).

L’utilisateur est ainsi amené à exprimer ses besoins en terme de ressources pour ses applications, sans se soucier de leur disponibilité ou de leur localisation physique. Ainsi, les stratégies classiques de gestion de ressources se trouvent inadaptées pour répondre à des demandes de ressources dans le cas de systèmes distribués à large échelle. On est donc en présence d’une gestion de ressources globale, qui intègre un certain nombre de mécanismes liés à différentes ressources (processeur, mémoire, disque). Ces mécanismes seront amenés à coopérer entre eux en vue de répondre aux demandes d'allocation des ressources, tout en respectant deux contraintes essentielles : la performance et la disponibilité.

Après un état de l’art sur la gestion de ressources dans les systèmes distribués à large échelle, nous envisageons de proposer un modèle d'allocation de ressources pour grilles de calcul, dans lesquelles les composants sont homogènes. D'un point de vue expérimental, l'observation et la fouille de grands corpus de données donnant l'activité de machines au sein d'une grappe ou d'une grille pourra donner des tendances sur l'évolution dans le temps des ressources et permettra d'affiner les techniques.

En conclusion, nous pouvons rappeler que cette partie est essentiellement consacrée aux problématiques des données (disques) et elle constitue une problématique commune avec le cadre général du sous-projet II.



Sous projet II: Gestion de ressources pour grappes et grilles.

1- Algorithmes parallèles

L'objectif consiste ici à concevoir des techniques efficaces d'algorithmique parallèle, permettant de paralléliser des familles d'algorithmes de résolution de problèmes génériques. Ces techniques sont établies spécifiquement et doivent être généralisées et testées pour évaluer leur robustesse. Des implémentations dans divers environnements (grappes/grilles homogènes et hétérogènes) sont à réaliser afin de valider l'approche.

Il est projeté d'appliquer cette approche sur les problèmes suivants.

a) Poly-algorithmes matriciels parallèles sur grilles (Activité post-doc + stage mastère)

Les principaux acteurs sont : Wahid Nasri, Zaher Mahjoub et Denis Trystram,

Dans sa thèse (soutenue en juin 2002), Nasri a proposé un algorithme dit « mixte » pour le produit matriciel combinant, à la fois l’algorithme récursif de Strassen (à un seul niveau de récursivité) et l’algorithme standard. Après avoir réparti les processeurs groupes et décomposé les matrices d’entrée, un ordonnancement particulier se charge de répartir les tâches aux processeurs et choisit l’algorithme de calcul approprié (standard ou Strassen), et ce afin de maximiser la performance globale. La formalisation de cette idée conduit à l’approche poly-algorithmique.

En effet, la diversité des supports d’exécution parallèle fait que, pour un problème donné, un seul algorithme ne peut fournir dans tous les cas la meilleure performance possible. De ce fait, afin de maximiser cette dernière, l’idée analysée consiste en un « mariage » de multiples algorithmes (e.g. standard, Winograd, Strassen…) pour résoudre un même problème où chaque algorithme peut dominer les autres pour certaines tailles du problème et/ou certains nombre de processeurs et/ou certains modèles de communication. A partir de certains préliminaires prometteurs, on projette d’approfondir cette approche et de la généraliser à divers noyaux de calcul matriciel (produit et inversion de matrices denses et creuses).

b) Algorithmes de résolution de problèmes combinatoires et numériques

Les principaux acteurs sont : Zaher Mahjoub, Hasni Hamadi et Mohamed Jemni.

Les problèmes d’optimisation combinatoire (POC) se rencontrent souvent en divers domaines e.g. en sciences de l’ingénieur, en gestion industrielle, en économie, etc… Considérés comme « durs » ou « difficiles », leur résolution exacte est en général d’un coût prohibitif (exponentiel en la taille du problème). On a donc recours, la plupart du temps, à des algorithmes d’approximation, dits heuristiques, ayant la particularité de déterminer une solution approchée non optimale mais de coût polynomial.

Cependant, les multiples algorithmes heuristiques de résolution de POC, connus actuellement, en particulier le recuit simulé (RS), la recherche tabou (RT), les algorithmes génétiques (AG) et les algorithmes hybrides (AH), ont des qualités et des performances différentes. La parallélisation de ces algorithmes permet, non seulement, de traiter des problèmes de plus grande taille en accélérant la détermination de solutions satisfaisantes, mais aussi d’améliorer, dans certains cas, la qualité des solutions obtenues.

A travers cet axe, nous visons, comme objectifs, d’effectuer, en premier lieu, un état de l’art sur les principaux algorithmes méta-heuristiques pour les POC (RS, RT, AG, AH) ainsi que les récents travaux sur leur parallélisation. La deuxième phase consistera à concevoir une méthodologie efficace de parallélisation d’algorithmes spécifiques (simples ou hybrides) à adapter et à implémenter en milieux homogène et hétérogène. Des problèmes types seront choisis à ce propos. Une étude de performances comparées doit clôturer le travail afin de dégager les caractéristiques intrinsèques de chaque algorithme testé.

Par ailleurs, nous souhaitons approfondir dans ce thème les algorithmes de simulation de couplage entre fluide et structure que nous avons étudiés dans des stages de fin d'étude d'ingénieurs.

Les équations aux dérivées partielles sont utilisées pour modéliser beaucoup de phénomènes physiques, en particulier, les équations de Stokes qui modélisent l’écoulement d’un fluide dans un domaine 2D borné. La résolution par méthodes numériques de ces équations est utile dans divers domaine, nous citons par exemple, le domaine bio-mécanique où on fait des simulations qui traitent le couplage entre fluide et solide tel que sang-veine.

Dans ce cadre nous nous intéressons à approcher la vitesse d’un fluide et sa pression par la méthode spectrale avec joint. Cette méthode bien qu’efficace par son résultat est gourmande en mémoire et puissance de calcul. D’un autre coté, elle se prête bien à la programmation parallèle puisqu’elle est basée sur le principe de décomposition de domaine.

L’objectif visé est de développer une application parallèle de simulation de couplage entre fluide et structure basée sur la méthode spectrale avec joint après le développement d’une application séquentielle et l’étude de ses différentes stratégies de parallélisation sur une grappe et une grille de calcul.

c) Algorithmes parallèles pour le produit d’une chaîne de matrices (PCM)

Les principaux acteurs sont Z. Mahjoub et Leila Moussa-Toulgui.

Le produit d’une chaîne de matrices (PCM) est un problème se posant dans diverses applications scientifiques e.g. en robotique, en animation assistée par ordinateur, en contrôle de processus, en programmation mathématique etc. De ce fait, la conception d’algorithmes parallèles efficaces pour le PCM est une d’une grande importance pratique. Les matrices constituant la chaîne étant non carrées et compte tenu de l’associativité du produit matriciel, la complexité temporelle de l’évaluation du PCM dépend fortement du choix de la séquence des produits successifs. En effet, un mauvais choix peut aboutir à une complexité de l’ordre du cube de la complexité optimale. Etant donné qu’il y a un nombre exponentiel (en la taille de la chaîne) de séquences, leur énumération exhaustive est inabordable en pratique. Une résolution par décomposition récursive du PCM selon le paradigme ‘Divide & Conquer’ (DC) conduit à un algorithme de complexité exponentielle également. C’est la programmation dynamique (PD) qui est l’approche adéquate ici. En effet, son application conduit à une décomposition itérative optimale du problème et l’algorithme conçu est (dans le cas général) de complexité cubique . Une fois la séquence optimale générée, reste le problème de l’évaluation effective du produit. Le problème du PCM comporte ainsi deux sous-problèmes : (i) la détermination de la séquence optimale (DSO) et (ii) l’évaluation du produit de la chaîne (EPC). C’est surtout la complexité élevée de l’EPC qui rend son traitement parallèle nécessaire.

D’un autre côté, et cela constitue un aspect tout à fait nouveau et qui n’a jamais été traité dans la littérature, compte tenu du fait que pour des chaînes de grande taille, la réduction de la complexité spatiale peut être aussi importante que celle de la complexité temporelle, nous nous intéressons également au problème de la détermination de la chaîne optimale en espace. En effet, que ce soit en traitement séquentiel ou parallèle, un coût élevé des E/S et des transferts de données peut avoir un effet négatif sur la performance finale de l’algorithme de l’EPC (même si le coût en opérations est optimal).

Ainsi, l’étude envisagée comporte deux phases. La première consiste à concevoir diverses versions séquentielles des algorithme de DSO en temps et en espace et ce, en appliquant sur l’algorithme standard (ayant la structure de trois boucles imbriquées) des techniques de transformation unimodulaires de nids de boucles parfaits, basées sur une analyse de dépendance au sein du nid original (cf thème 2d). Une fois générée une (ou plusieurs) séquence(s) établissant le meilleur compromis espace-temps et conduisant à un arbre (binaire) d’évaluation le plus adéquat (selon des critères à fixer), on aborde la seconde phase consistant à concevoir des algorithmes efficaces pour l’EPC. A ce niveau, seront appliquées diverses approches faisant intervenir divers paradigmes dont celui des tâches malléables, le but étant d’aboutir à un équilibrage de charge optimisant coût de calcul et coût de communication.

Précisons que diverses instances du problème du PCM sont à étudier : cas de matrices pleines et cas de matrices creuses (certaines matrices de la chaîne pouvant être carrées). Des implémentations sur des plate-formes parallèles adéquates, homogènes et hétérogènes (grappes, grilles) appuyées par des séries d’expérimentations devront valider l’étude théorique.



2. Déploiement de code, gestion de ressources

a) Algorithmique pour problèmes creux - Gestion de structure de données creuses

Les principaux acteurs sont Olfa Hamdi Larbi, Zaher Mahjoub, Nahid Emad, Paul Feautrier

En calcul global, on est conduit, pour une même application, à traiter une même matrice creuse sur des machines d’architectures différentes ou bien à la partitionner en blocs et traiter ces blocs sur des machines d’architectures différentes. L’objectif ici est de détecter (semi) « automatiquement » le meilleur format de compression d’une matrice creuse pour une architecture (ou un modèle de parallélisme) et une méthode numérique données. Ce travail entre dans le cadre de la programmation générative, approche qui consiste à générer des composants logiciels ou des systèmes paramétrés à la demande et ce afin d’améliorer leur réutilisabilité, comportant à la fois des techniques d’implantation et des exemples de démarches méthodologiques.

Après avoir dressé un l’état de l’art sur les diverses techniques de stockage pour matrices creuses (à structure régulière ou non), on s’intéresse actuellement aux diverses facettes de la programmation générative et des bibliothèques actives pour les algorithmes de résolution de problèmes creux. Ce type d'approche est utilisé dans des algorithmes hybrides asynchrones et elle est largement étudiée par l'équipe "Calcul Numérique intensif" du laboratoire PriSM (Versailles). Une autre approche possible peut être la notion de poly-algorithmes que nous étudions par ailleurs.

b) Répartition de charges en milieu hétérogène

Les principaux acteurs sont Wahid Nasri, Zaher Mahjoub, Olivier Beaumont et Denis Trystram

Les réseaux hétérogènes de stations de travail deviennent de plus en plus présents dans les institutions universitaires, les centres de recherche, les compagnies, les usines,… Cependant, la majeure limitation de la programmation au sein d’une plate-forme hétérogène provient de la difficulté d’équilibrer les charges entre processeurs : on est ainsi confronté au problème général d’ordonnancement où il s’agit de minimiser le temps de fin d’exécution (makespan). Ce problème étant NP-complet, on doit donc choisir ou développer des heuristiques garanties, bien adaptées à cet environnement de travail particulier.

Dans ce cadre, il s’agit de proposer, pour les modèles de communication 1-port et multi-ports, des heuristiques d’ordonnancement de tâches de coûts différents et avec coûts de communication différents, en adoptant l’approche maître-esclaves.

Un travail entamé dans le cadre d’un stage de DEA a permis d’adapter une heuristique procédant, dans le cas 1-port (resp. multi-port), à la construction d’un ordonnancement « à l’envers » (resp. « à l’endroit »). La poursuite de cette étude a comme objectifs le raffinement des deux heuristiques, l’évaluation de leurs complexités, ainsi que la détermination de bornes inférieures pour le makespan. De cette manière nous pourrons estimer leurs qualités respectives. Des séries de tests de simulation permettront de vérifier la validité des résultats théoriques.

c) Parallélisation automatique de programmes : génération de code pour machines à mémoire partagée

Les principaux acteurs sont Yosr Slama (4ème année de thèse), Mohamed Jemni et Paul Feautrier

Ce thème représente la continuité d’une longue coopération entre l’équipe tunisienne et l’équipe de Versailles qui entre dans le cadre de la recherche en parallélisation automatique des programmes. Cette coopération a été consolidée depuis 2000 par le co-encadrement de la thèse en cotutelle de Yosr Slama par Paul Feautrier (de l’Université de Versailles) et Mohamed Jemni et Zaher Mahjoub (de la Faculté des Sciences de Tunis). Les travaux entamés concernent en particulier la génération automatique de programmes parallèles destinés aux machines à mémoire partagée en se basant sur une fonction de placement.

Dans la littérature, peu de travaux s’intéressent à cette problématique et se basent plutôt sur les fonctions d’ordonnancement. Cependant, le placement présente des avantages par rapport à un ordonnancement, en particulier la rapidité de sa détermination et l'amélioration de la localité, dans le sens où un placement est toujours conçu pour minimiser les échanges de données entre les différents processeurs.

L'approche que nous proposons, consiste essentiellement en deux phases : la génération des boucles et la génération des synchronisations. En effet, il s'agit d'abord de partir du programme source et de la fonction du placement pour générer une boucle parallèle énumérant les processeurs et renfermant, dans un ordre séquentiel, l'ensemble des instructions exécutées par un même processeur. Cette phase consiste en fait à générer un sous-espace d’itération destination pour chaque instruction du programme source, à partir de son placement, puis à fusionner ces sous-espaces en un seul espace, de façon à préserver le taux de parallélisme extrait au moment de la construction du placement. Puis, pour garantir que le programme obtenu soit sémantiquement correct, des opérations de synchronisation seront insérées dans le programme cible pour satisfaire toute dépendance non respectée. Une dernière phase consiste par la suite à optimiser le nombre de synchronisations afin de diminuer leurs coûts.

A ce propos, l’approche de génération des synchronisations proposée suppose que le code source est en assignation unique i.e. ne contient que des dépendances de flux. Il s’agit donc d’abord de ramener à cette forme les programmes qui ne le sont pas. C’est l’outil « f2saf » qui le fait. Des contacts avec des chercheurs du Prism a permis d’implémenter cette partie.

Actuellement, la première phase (de génération du code) a été finalisée sur le plan théorique et pratique. Un article résumant ces travaux vient d’être accepté à aiccssa'03 (Tunis, 2003). Quant à la deuxième phase (de génération des synchronisations), la première partie a été achevée sur le plan théorique et est en cours de développement sur le plan pratique.



III- Propositions d'actions – objectifs visés



ANNEXES : PUBLICATIONS RECENTES (2001-2004)



  1. O.Beaumont, V.Boudet, P.F.Dutot, Y.Robert & D.Trystram, Fondements théoriques pour la conception d’algorithmes efficaces pour la gestion de ressources, Tutoriel RenPar’14, Hammamet, Tunisie, 2002

  2. C.Cérin, An out-of-core sorting algorithm for clusters with processors at different speeds, IPDPS'02, Fort Lauderdale, USA, 2002.

  3. C.Cérin, H.Fkaier & M.Jemni, Accessing Hardware Performance Counters in order to Measure the Influence of Cache on the Performance of Integer Sorting, Int. Workshop on Performance Modeling, Evaluation and Optimization of Parallel and Distributed Systems (PMEO-PDS'03), en conjonction avec IPDPS'2003, Nice, avril 2003.

  4. C.Cérin, H.Fkaier & M.Jemni, A Synthesis of Parallel Out-of-Core Sorting Programs on Heterogeneous Clusters, Third IEEE/ACM International Symposium on Cluster Computing and the Grid (CCGRID'2003), Tokyo, mai 2003.

  5. N. Emad, O.Hamdi & Z. Mahjoub, On Sparse Matrix–Vector Product Optimization, Accepted Com. AICCSA’05, Cairo, January 2005.

  6. O.Hamdi & Z.Mahjoub, Parallélisation de nids de boucles non parfaits. Cas de l’algorithme de la fermeture-réduction transitive de graphes orientés sans circuit, RENPAR’01, Paris, avril 2001.

  7. M.Jemni, Z.Mahjoub, D.Trystram, D.Litaize & D.Hagimont (ed), Actes de RenPar’14, SmpA’8 et ASF, Hammamet, Tunisie, 2002.

  8. Lepere & D.Trystram, A new clustering algorithm for scheduling with large communication delays, IPDPS’02, Fort Lauderdale, USA, 2002.

  9. R.Lepere, G.Mounie & D.Trystram, An approximation algorithm for scheduling trees of malleable tasks, European Jr of Operational Research, 142, 242-249, 2002.

  10. Z.Mahjoub, W.Nasri & D.Trystram, Parallélisation d’un algorithme récursif d’inversion de matrices triangulaires sur une plate-forme hétérogène, CARI’02, Yaoundé, 2002.

  11. Z.Mahjoub, W.Nasri & D.Trystram, Fast parallel matrix multiplication on clusters, PPAM’02, Neuchatel, 2002.

  12. M.Marrakchi, conception et analyse d’ordonnancements efficaces pour algorithmes parallèles d’algèbre linéaire, Thèse de doctorat d’état, Université Tunis El Manar, 2001.

  13. G.Mounie & D.Trystram, Ordonnancement de tâches malléables, Tutoriel à l’Ecole thématique sur la globalisation des ressources informatiques, Aussois, France, 2002.

  14. W.Nasri, Parallélisation d’un algorithme de produit matriciel rapide sur une grappe de PC, RenPar’02, Hammamet, 2002 .

  15. W.Nasri, Parallélisation d’algorithmes matriciels récursifs par le paradigme « Diviser pour paralléliser » dans des environnements homogène et hétérogène, thèse de doctorat, Université Tunis El Manar, 2002.

  16. W.Nasri & Z.Mahjoub, Optimal parallelization of a recursive algorithm for triangular matrix inversion, Parallel Computing, 27(1767-1782), 2001.

  17. W.Nasri & Z.Mahjoub, Design and implementation of a general divide and conquer algorithm for triangular matrix inversion, Int. Jr of Parallel and Distributed Systems and Networks, 5(1), 35-42, 2002.

  18. Y.Slama, Parallélisation automatique de programmes pour machines à mémoire partagée, RenPar’02, Hammamet, 2002.

  19. Y.Slama, M.Jemni & P.Feautrier, Parallel Code Generation Respecting Allocation, ACS/IEEE Inter. Conf. on Computer Systems and Applications, juillet 2003, Tunis.

  20. Y.Slimani, Datamining et parallélisme, Tutoriel , RenPar’02, Hammamet, 2002.

  21. Y.Slimani & al, Discovering association rules using the formal concept analysis, EGC’02, Montpellier, 2002.

  22. W.Zimmermann, W.Loewe & D.Trystram, On scheduling send-graphs and receive graphs under the LogP model, Information Processing Letters, 82, 83-92, 2002.

  23. Christophe Cérin, Michel Koskas, Jean-Sébatien Gay, Gael Le Mahec, Efficient Data-Structures and Parallel Algorithms for Association Rules Discovery, Parallel Computing Systems (PCS'2004), Colima, Mexico, Sept. 30, 2004.

  24. Christophe Cérin, Michel Koskas, Mohamed Jemni, Hazem Fkaier, Improving Parallel Execution Time of Sorting on Heterogeneous Clusters, 16th Symposium on Computer Architecture and High Performance Computing (SBAC'04), Foz do Iguaçu - PR – Brazil, October 27-29, 2004.