Abstract FR:

Nous abordons deux problemes fondamentaux des systemes de gestion de bases de donnees paralleles: l'ordonnancement et le placement des taches obtenues apres parallelisation des requetes complexes. Nous commencons par modeliser au moyen d'un formalisme graphique les taches, leur granularite, les synchronisations, la circulation des donnees, les volumes traites et certaines contraintes de placement. Pour l'ordonnancement, dont le but est de minimiser le temps de reponse, nous proposons un algorithme base sur des heuristiques simples. Il utilise les dates de debut au plus tot, calculees pour un nombre infini de processeurs, ainsi que l'aptitude des taches a se deplacer dans le temps sans augmenter le temps de reponse. A cela, nous ajoutons la possibilite de modifier la granularite des taches s'il vient a manquer des processeurs pour leur execution ; c'est la l'originalite de notre methode. Nous employons egalement une heuristique pour le placement dont le role est l'equilibrage des charges. L'heuristique lpt est appliquee apres avoir rassemble les charges des processeurs. Nous en avons etudie la mise en uvre dans le cadre des systemes paralleles a memoire partagee, puis de ceux a memoire distribuee. Afin d'experimenter nos algorithmes, nous avons entrepris la realisation d'un prototype sur une machine parallele a memoire distribuee