Abstract FR:

La parallelisation d'un programme sequentiel comporte plusieurs etapes: le calcul des dependances, leur representation et l'utilisation de cette representation pour l'application des transformations de programme permettant d'obtenir d'un ordonnancement parallele des instructions du programme. Le succes de la parallelisation depend de la precision du test de dependances et des representations utilises pour ces dependances. Nous presentons et comparons, dans cette these, differents algorithmes de test de dependances et differentes abstractions de ces dependances. L'algorithme du paralleliseur pips est base sur un test de faisabilite approximatif utilisant l'algorithme de fourier-motzkin. Nos experiences montrent que, dans la pratique, il est suffisamment precis pour traiter des systemes de dependances et que sa complexite protique est polynomiale. Les differentes abstractions des dependances ont des precisions differentes. Pour effectuer legalement une transformation, plusieurs abstractions sont admissibles, c'est a dire contiennent suffisamment d'information pour savoir si la transformation peut etre appliquee legalement. L'abstraction minimale est celle qui contient l'information necessaire minimale appropriee a la transformation. Nous avons identifie l'abstraction admissible minimale appropriee aux transformations de programme classiques: inversion de boucle, permutation de boucles, transformations unimodulaires, partitionnement et parallelisation. Le cone de dependance, qui est l'abstraction admissible et minimale pour l'application de toute transformation unimodulaire, contient aussi suffisamment d'information pour obtenir l'ensemble des ordonnancements lineaires valides mono- et multi-dimensionnels, identique a celui calcule a partir de l'abstraction des vecteurs de distance de dependance