N d'ordre Année

Aurélie Hurault

Description

Niveau: Supérieur, Doctorat, Bac+8

• mémoire

N? d'ordre : 2415 Année 2006 THÈSE présentée pour obtenir le titre de DOCTEUR DE L'INSTITUT NATIONAL POLYTECHNIQUE DE TOULOUSE École doctorale : Informatique et Télécommunications Spécialité : Informatique Courtage sémantique de services de calcul Aurélie HURAULT Soutenue publiquement le 4 décembre 2006 devant un jury composé de : MME. Thérèse HARDIN Professeur, Université Pierre et Marie Curie - LIP6 Présidente de Jury M. Michel DAYDÉ Professeur, INPT-IRIT Directeur de thèse MM. Michel BIDOIT Directeur de recherche CNRS, LSV Rapporteurs Thierry PRIOL Directeur de recherche INRIA, IRISA MM. Frédéric DESPREZ Directeur de recherche INRIA, LIP Examinateur Marc PANTEL Maître de conférences, INPT-IRIT Co-encadrant

• équipe des enseignants du département d'informatique et de mathématiques ap- pliquées


• inpt-irit directeur de thèse


• années passées

Sujets

• Mémoire
• Desprez
• Institut national polytechnique de Toulouse
• Hurault
• Toulouse
• Ayache
• Hardin

Informations

• Publié par: profil-feym-2012
• Nombre de lectures: 49
• Langue: Français
• Poids de l'ouvrage: 1 Mo

Extrait

◦N d’ordre : 2415 Année 2006
THÈSE
présentée pour obtenir le titre de
DOCTEUR DE L’INSTITUT NATIONAL
POLYTECHNIQUE DE TOULOUSE
École doctorale : Informatique et Télécommunications
Spécialité : Informatique
Courtage sémantique de services de calcul
Aurélie HURAULT
Soutenue publiquement le 4 décembre 2006 devant un jury composé de :
MME. Thérèse HARDIN Professeur, Université Pierre et Marie Curie - LIP6 Présidente de Jury
M. Michel DAYDÉ Professeur, INPT-IRIT Directeur de thèse
MM. Michel BIDOIT Directeur de recherche CNRS, LSV Rapporteurs
Thierry PRIOL Directeur de recherche INRIA, IRISA
MM. Frédéric DESPREZ Directeur de recherche INRIA, LIP Examinateur
Marc PANTEL Maître de conférences, INPT-IRIT Co-encadrantPour toi,
parti alors que je posais ces premiers mots sur le papier.ivRemerciements
En avant propos de ce mémoire, je tiens à remercier Messieurs Michel Bidoit et Thierry
Priol d’avoir accepté la lourde charge de rapporteur. Je remercie également Madame Thé-
rèse Hardin et Monsieur Frédéric Desprez de l’intérêt qu’ils ont porté à mon travail en
acceptant de participer à ce jury.
Je n’oublie pas Monsieur Michel Daydé qui a accepté d’être mon directeur de thèse et qui a
toujours été présent quand je le sollicitais.
J’adresse des remerciements particuliers à Monsieur Marc Pantel pour avoir encadré ce tra-
vail, pour son investissement, pour avoir répondu présent quand il le fallait et pour avoir su
gérer mes coups de stress assez fréquents et pas toujours justifiés !
Je remercie également Messieurs Alain Ayache et Patrick Sallé pour m’avoir permis de re-
joindre l’équipe des enseignants du département d’Informatique et de Mathématiques Ap-
pliquées en tant que monitrice puis en tant qu’ATER.
Je tiens également à exprimer ma reconnaissance à Pascaline, pour avoir relu ce manuscrit,
mais surtout pour son soutien tout au long de cette thèse, que ce soit en rapport avec la
recherche, l’enseignement ou plus personnel. Pour les bons moments aussi, merci.
Je remercie également Philippe Quéinnec pour le temps qu’il a accordé à la relecture d’une
partie de ce manuscrit, tous les collègues vers qui je me suis tournée un jour pour en discuter
ainsi que mes amis et collègues doctorants.
J’ai une pensée particulière pour mes collègues de bureau : Ahmed, Carlos et Pierre-Loïc
pour les heures passées en leur compagnie.
Je remercie également tous les résidents du quatrième étage et l’ensemble du personnel du
laboratoire pour leur accueil et ces années passées en leur compagnie.
Je n’oublie bien sûr pas ceux qui n’ont pas un rapport direct avec le travail de ce manuscrit,
mais sans qui je n’en serais sûrement pas là aujourd’hui.
En premier lieu, je pense à ma famille qui m’a toujours soutenue et encouragée dans mon
envie de réaliser ce projet, toujours présente à mes côtés malgré la distance, un soutien sans
faille et précieux.
Je pense également à Gwen, bientôt 15 ans d’une amitié solide qui m’a fait évoluer ; à Eléo-
nore, Sandra, Marie-Luce et Soizic, rencontrées lors de mes tous premiers jours à Toulouse
et sans qui ces années dans le sud n’auraient pas été les mêmes. Bienvenue à Mathys.
Je n’oublie pas les copines de SB pour les discussions rarement sérieuses et toujours drôles !
Merci également à mes amies de l’équitation et à mes « gros » pour ma bouffée d’air du ven-
dredi soir. Je finirai en remerciant les nouveaux arrivés dans ma vie qui ont égayé cette fin
de thèse.
vviRésumé
La recherche du ou des services de calcul scientifique disponibles sur une grille qui
répondent aux besoins d’un utilisateur, aussi appelée courtage de services, est une activité
complexe. En effet, les services disponibles sont souvent conçus pour répondre de manière
efficace à de nombreux besoins différents. Ceux-ci comportent donc en général de nombreux
paramètres et la simple signature du service ne suffit pas pour que l’utilisateur puisse le
trouver.
La solution proposée dans ces travaux consiste à utiliser une description formelle du
domaine d’application comportant l’ensemble des données et des opérateurs du domaine
ainsi que les propriétés des opérateurs. Dans le cadre de cette thèse, cette description est
effectuée sous la forme d’une spécification algébrique. Un service ou une requête sont alors
des termes de l’algèbre associée. En ce qui concerne les signatures, nous combinons le
sous-typage des sortes et la surcharge des opérateurs selon le système de type proposé par
G. Castagna pour le λ&-calcul. Le courtage consiste alors à effectuer un filtrage modulo
la théorie équationnelle associée à la spécification, entre le terme représentant le service
souhaité et les termes représentant les services disponibles.
Nous proposons et avons implanté deux algorithmes différents inspirés d’un parcours
de l’arbre de recherche des solutions contraint par une quantité d’énergie (nombre d’équa-
tions et/ou de compositions applicables). Le premier algorithme est directement dérivé des
travaux de Gallier et Snyder sur l’unification équationnelle. Nous avons montré sa correc-
tion et argumenté sa complétude (ou exhaustivité). Le second algorithme découle d’une
définition constructive de l’ensemble des services qui peuvent répondre à la requête d’un
utilisateur. L’algorithme consiste alors en un parcours particulier de l’arbre construit pour
engendrer le service requis. Nous avons également montré sa correction, et sa complétude
pour certaines formes d’équations.
Nous illustrons notre approche dans les domaines applicatifs suivants : algèbre li-
néaire et optimisation, et nous nous intéressons au traitement de la combinaison de domaines
applicatifs.
Mots clés Courtage de services, Filtrage équationnel, Spécification algébriques, Grille.
Abstract The search for a computing service available on a grid which corresponds to an
user’s needs, also called trading services, is a complex activity. Indeed available services
are often implemented to fulfill efficiently different requirements.These services offer many
parameters and their signature is often not enough for a precise description.
The object of this work consists in using a formal description of the dedicated do-
main : the data, the operators and their properties. This description is carried out as an alge-
braic specification. Services and requests are then terms of the associated algebra. For the
viiviii
signatures, we combine sub-sorting and overloading of operators by using the type system
proposed by G. Castagna for theλ&-calculus. Trading is then implemented as an equational
matching modulo the theory associated to the specification, between the term representing
the required service and the terms representing the available services.
We propose two algorithms inspired from a traversal of the solution search tree
constrained by an amount of energy. The first one is directly inspired from the work of
Gallier and Snyder on equational unification. We have proved its correctness and argued its
completeness. The second one is derived from a constructive definition of the set of ser-
vices which answer the user request. We have proved its correctness and its completeness
for some kind of equations.
We illustrate our approach with applications to linear algebra and optimization and
an interaction between these two domains.
Keywords Trading, Equational matching, Algebraic specification, GridTable des matières
1 Introduction 1
1.1 La problématique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Descriptions possibles et méthodes de comparaison associées . . . . . . . . 3
1.2.1 Les signatures et isomorphismes de types . . . . . . . . . . . . . . 4
1.2.2 Exploitation de mots-clés . . . . . . . . . . . . . . . . . . . . . . . 7
1.2.3 Web sémantique : les ontologies . . . . . . . . . . . . . . . . . . . 9
1.2.4 Les spécifications formelles en génie logiciel . . . . . . . . . . . . 10
1.2.5 Synthèse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.3 Les projets existants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.3.1 Domaines applicatifs spécifiques . . . . . . . . . . . . . . . . . . . 18
1.3.2 Les projets génériques . . . . . . . . . . . . . . . . . . . . . . . . 24
1.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2 Formalisation du problème 29
2.1 Les spécifications algébriques . . . . . . . . . . . . . . . . . . . . . . . . 30
2.1.1 Définitions . . . . . . . . . . . . .