Abstract FR:

Lors de la compilation de programmes sequentiels sur machine parallele, il est important de degager le maximum de parallelisme. Ceci peut etre fait en ordonnancant les calculs de facon a obtenir un ordonnancement a la fois rapide et respectant les contraintes de precedence. Dans cette these, nous nous interessons au cas ou le domaine de calcul est un polyedre convexe semi-infini ou borne, lorsque les dependances sont uniformes. Nous etudions la complexite de determination de l'ordonnancement optimal, et nous montrons que le probleme est np-difficile, et ce meme dans des cas tres simples. Puis nous etudions les performances d'ordonnancements affines et nous montrons qu'ils sont asymptotiquement optimaux. Nous regardons enfin des cas ou le nombre de processeurs est limite. Nous etudions le cas des processeurs differencies, et nous montrons qu'il est possible d'obtenir un ordonnancement de debit optimal lorsque le parallelisme des calculs n'est pas borne