Rapport scientifique du LIFL

Olejnik

Description

Rapport scientifique du LIFL Laboratoire d'Informatique Fondamentale de Lille URA CNRS 369 30 mai 1997 UNIVERSITE DES SCIENCES ET TECHNOLOGIES DE LILLE LIFL - URA 369 CNRS - Bât. M.3 - UFR IEEA - 59655 VILLENEUVE D'ASCQ CEDEX Tél. : Fax :

• lille lifl - ura


• responsable du dea informatique


• directeur adjoint


• collège des ingénieurs


• ufr ieea


• lifl


• ura


• président de la cse informatique

Sujets

• Petitot
• Olejnik
• Laboratoire d'Informatique Fondamentale de Lille
• De Keyser
• Ad-Din

Informations

• Publié par: pefav
• Publié le: 01 mai 1997
• Nombre de lectures: 70
• Langue: Français

Extrait

Rapport scientifique du LIFL

Laboratoire d'Informatique Fondamentale de Lille

URA CNRS 369

30 mai 1997

UNIVERSITE DES SCIENCES ET TECHNOLOGIES DE LILLE LIFL  URA 369 CNRS  Bât. M.3  UFR IEEA  59655 VILLENEUVE D'ASCQ CEDEX Tél. : [phone] Fax : [phone] [e-mail] http://www.lifl.fr/

2

L ABORATOIRE D 'I NFORMATIQUE F ONDAMENTALE DE L ILLE

R APPORT SCIENTIFIQUE DU LIFL

3

4

L ABORATOIRE D 'I NFORMATIQUE F ONDAMENTALE DE L ILLE

L.I.F.L. URA 369 CNRS

Directeur : JeanMarc Geib Directeur adjoint : JeanPaul Delahaye Secrétaire de direction : Michèle Driessens Secrétaire : Annie Kaczmarek Bibliothécaire et secrétaire DEA : Bénédicte Fievet Responsable financier : Michel Petitot Responsable équipe technique : Samuel Degrande Responsable Communication : Richard Olejnik

Responsable du DEA Informatique : JeanLuc Dekeyser Président de la CSE Informatique (27) : Sophie Tison Directeur de l'UFR : JeanPierre Steen

Composition du conseil de laboratoire

JeanMarc Geib, directeur Collège des chercheurs et enseignantschercheurs Bernard Carré, Max Dauchet, JeanLuc Dekeyser, JeanPaul Delahaye, Philippe Devienne, Philippe Durif, Rémi Gilleron, Sylvain Karpf, JeanFrançois Méhaut, Nour Eddine Oussous, Bernard Toursel. Collège des ingénieurs techniciens administratifs Gilles Carin, Annie Kaczmarek.

R APPORT SCIENTIFIQUE DU LIFL

Collège des doctorants Yves Denneulin, Luc Wibaux, Bruno Beaufils.

5

6

L ABORATOIRE D 'I NFORMATIQUE F ONDAMENTALE DE L ILLE

Table des matières

Présentation du laboratoire et de ses projets .......................................................................1

Axe 1 : ParDis page 9 Équipe West ....................................................................................................................11 Dataparallélisme et irrégularité ...................................................................................13 Environnement d'aide à la programmation scientifique data parallèle ............................17 Équipe MAP ....................................................................................................................21 Krylov : Méthodes de Krylov hybrides parallèles pour réseaux hétérogènes .................23 Équipe Goal.....................................................................................................................27 Support d'exécution multithreadé.................................................................................29 Parallélisme adaptatif ...................................................................................................32 Équipe Paloma .................................................................................................................35 Réseaux d’interconnexion............................................................................................37 Fragmentation et parallélisme adaptatifs.......................................................................40

Axe 2 : Cim page 45 Équipe Goal.....................................................................................................................47 Conception d'environnements pour la coopération .......................................................49 Représentation par objets.............................................................................................52 Équipe Graphix ................................................................................................................55 Amélioration du rendu projectif ...................................................................................57 Radiosité parallèle .......................................................................................................59 Simulateurs médicaux ..................................................................................................61 Interfaces 3D...............................................................................................................63 Équipe RD2P...................................................................................................................67 Carte à microprocesseur ..............................................................................................69 Carte à microprocesseur et mobilité .............................................................................71

Axe 3 : Calc page 75 Équipe Méthéol................................................................................................................77 Compilation logique ....................................................................................................79 Agents coopératifs.......................................................................................................81 Révision de la connaissance .........................................................................................84 Analyse de programmes logiques .................................................................................87 Équipe Lac.......................................................................................................................91 Contraintes ensemblistes..............................................................................................94

R APPORT SCIENTIFIQUE DU LIFL

Automates et réécriture ...............................................................................................96 Équipe Caabaal ................................................................................................................97 Compression et génomes .............................................................................................99 Apprentissage............................................................................................................102 Systèmes et problèmes complexes..............................................................................105 Équipe AL .....................................................................................................................107 Semicommutations ...................................................................................................108 Codage......................................................................................................................111 Équipe CalFor................................................................................................................115 Séries formelles, algèbres de Lie et groupes de Lie.....................................................117 Algèbre différentielle .................................................................................................119 Interface calcul formel, calcul numérique appliqué à l'automatique .............................121

Pôles associés CRIL 125 LABOGP.......................................................................................................................127 LIL ............................................................................................................................131 Annexes Listes permanents, doctorants, personnel technique ........................................................135 Thèses ...........................................................................................................................140 Résumés des thèses et habilitations.................................................................................144

Liste classée des publications p. 169 Équipe AL....................................................................................................................170 Équipe CAABAAL ......................................................................................................172 Équipe CALFOR..........................................................................................................174 Équipe GOAL ..............................................................................................................176 Équipe GRAPHIX........................................................................................................180 Équipe LAC .................................................................................................................184 Équipe MAP ................................................................................................................187 Équipe METHEOL ......................................................................................................188 Équipe PALOMA.........................................................................................................192 Équipe RD2P ...............................................................................................................194 Équipe WEST ..............................................................................................................195 Pôles associés CRIL 197 LIL ...........................................................................................................................198 LABOGP ......................................................................................................................200

7

8

L ABORATOIRE D 'I NFORMATIQUE F ONDAMENTALE DE L ILLE

Présentation du laboratoire et de ses projets

LeLaboratoire d'Informatique Fondamentale de Lille (LIFL) est situé sur le campus de l'Université des Sciences et Technologies de Lille (université de Lille I), à Villeneuve d'Ascq, près de Lille. Ce laboratoire, créé en 1983, est une unité associée au CNRS (URA 369). L'association en cours a débuté en janvier 1995, et le présent rapport est un rapport à trois ans correspondant à la fin de l’association actuelle consécutive à la demande de création d’une Unité Mixte de Recherche dans le cadre de la contractualisation de l’université pour la période 19982001.

Le LIFL peut être caractérisé par les repères suivants :

 trois axes scientifiques forts : parallélisme, informatique théorique, systèmes informatiques pour la coopération et l'image ;  110 personnes avec un équipement performant, un environnement riche en formations et collaborations, mais installées dans des locaux bien trop exigus ;  une production scientifique importante, de nombreux partenariats ;  une politique de contrats active et guidée par les objectifs ;  et pour finir un dynamisme et une bonne ambiance favorisant les initiatives et projets.

Une structuration en 3 axes scientifiques

A la suite de la dernière "réassociation", et avec la volonté de stabiliser son organisation, le LIFL a adopté une structure en 3 axes, reflet de son histoire et de ses développements :

 d'une part, issu de la fusion de deux équipes de recherche associées (ERA Architectures et Systèmes,Jeune Équipe Informatique Théorique), le laboratoire conserve cette double dominance disciplinaire que l'on retrouve dans l'axePardiset Distribution) et (Parallélisme dans l'axeCalc(Calcul Formel, Algorithmes, Langages et Complexité) ;

 d'autre part, l'ouverture vers de nouvelles thématiques (comme les cartes à micro processeurs, l'infographie appliquée, le travail coopératif, etc.) et une approche pluridisciplinaire ont donné naissance à des opérations qui se retrouvent maintenant, pour la plupart, dans l'axeCim (Coopérations, Images et Mobilités). Cet axe, récent, montre encore une grande diversité, mais la volonté de ses équipes de s'associer, et une participation commune au programmeGanymède du Contrat de Plan État/Region sur la communication avancée sont les éléments fédérateurs nécessaires à cet axe.

Chacun des trois axes est structuré en équipes (4 pourPardis, 5 pourCalcet 3 pourCim) , et ce rapport présente les différentes opérations de recherche menées par ces équipes. L'accent est mis plus sur les problèmes scientifiques précis abordés au LIFL que sur la structure d'équipe. Cette forme de document a pour but de mieux présenter les actions du laboratoire, et

1

2

L ABORATOIRE D 'I NFORMATIQUE F ONDAMENTALE DE L ILLE

d'en démontrer sa vivacité. Chaque opération fait l'objet d'un recto/verso précisant les chercheurs impliqués, les résultats, perspectives et collaborations associés à cette opération. Les publications majeures de l'opération sont indiquées (5 au maximum). On se referera à la partie "annexes" du document pour trouver la liste exhaustive et triée des productions scientifiques du laboratoire. Les trois axes sont respectivement présentés pages 9, 45 et 75.

Perspectives

La stabilisation de la structure en 3 axes permet de dégager des perspectives scientifiques clairement identifiées pour le laboratoire.

Avec l’axe Pardis, le LIFL s’est clairement inscrit dans l’évolution de la recherche française en parallélisme: de l’académisme à la réutilisation des résultats pour le calcul hautes performances. Le succès de la plateforme PM2, bien accueillie et réutilisée par de nombreux projets français et américains, est au centre d’une synergie au LIFL sur la mise en oeuvre d’une chaîne complète pour les applications parallèles (de leurs supports sur différentes architectures, des étapes de compilations et d’outillage, jusqu’à l’algorithmique pour le calcul scientifique). Cette dynamique devrait déboucher sur une forte identité unique de l’informatique lilloise du parallélisme. Le LIFL est déjà reconnu comme un des centres français sur ce thème. Une autre orientation que nous développons est l’utilisation à grande échelle de réseaux hétérogènes pour le calcul distribué (“ métacomputing ”), en particulier pour les gros problèmes comme ceux d’optimisation combinatoire. Nous avons déjà des résultats (inscrits par exemple dans la QAPLib internationale). Ce thème doit être ici développé. Ces actions sont au centre des nouvelles propositions d’actions concertées nationales (Ex GDRPRC, voir le projet iHPerf’98 présenté par Bougé, Geib, Plateau au Ministère, CNRS, et INRIA, projet tourné vers la valorisation), et des programmes cadres en émergence (Télécoms, Modélisation et Simulation). Un projet de PPF Simulation et Parallélisme a aussi été déposé pour le prochain contrat d’établissement.

L’axe CALC est très reconnu nationalement et internationalement comme un pôle fort en informatique théorique. Ses orientations se caractérisent par une volonté d’allier ses approches formelles à des ouvertures vers de nouveaux champs de recherche. On peut citer ici le génome, l’automatique ou l’apprentissage par une approche fondée sur la complexité de Kolmogorov. On peut citer aussi l’équipe Méthéol et ses travaux sur le dilemme itéré des prisonniers, le multiagents et la révision des connaisssances, ou encore les travaux de Sophie Tison et de Philippe Devienne sur les contraintes ensemblistes. Ces orientations montrent la grande vivacité de cet axe, elles donnent lieu à de nombreuses collaborations et implications dans des programmes dépassant de loin le cadre du laboratoire. Elles donnent lieu aussi à des collaborations nouvelles  et qu'il faut développer  plus appliquées (contrats ou thèses) avec par exemple Dassault, le CNES, la DGA, ou encore la socièté Maple pour laquelle le laboratoire est en charge d’une bibliothèque de traitement des équations différentielles.

L’axe CIM place ses perspectives dans deux grandes orientations: les services répartis à grande échelle (incluant ici, au delà des aspects répartition, des problématiques de sécurité et de mobilité) et l’infographie appliquée aux interfaces hommemachine 3D et aux simulateurs médicaux. Ce sont des thèmes qui s’articulent parfaitement dans les nouvelles orientations de l’informatique actuelle sur l’utilisation de la synthèse d’images et des réseaux mondiaux. Les