Abstract FR:

Avec l'emergence de machines paralleles possedant un grand nombre de processeurs la moindre parcelle de parallelisme doit etre extraite par les compilateurs paralleliseurs. Or les paralleliseurs bases sur les conditions de bernstein generent du code sequentiel pour les calculs de recurrences. Comme certaines de ces recurrences peuvent etre calculees de facon efficace sur les machines paralleles, il faut prevoir une phase de detection de recurrences. Nous presentons une nouvelle methode de detection de recurrences basee sur les systemes d'equations. La methode est precise car elle sait traiter les recurrences calculees dans des tableaux multi-dimensionnels. La phase de reconnaissance de forme est reduite a sa plus simple expression grace a une forte normalisation du systeme a l'aide de substitutions a la gauss. Les recurrences detectees sont mises sous une forme condensee ecrite a l'aide d'un operateur adapte: l'operateur scan. Il est montre que le systeme contenant des recurrences explicites peut etre ordonnance en utilisant les methodes classiques d'ordonnancement en parallelisation automatique. L'ordonnancement est calcule pour une machine virtuelle possedant un nombre illimite de processeurs et des unites arithmetiques et logiques avec un nombre illimite d'entrees. Il est explique comment cet ordonnancement peut etre adapte a une machine reelle. Pour chaque recurrence deux types de code parallele peuvent etre generes. Il est difficile de dire lequel des deux codes est le plus efficace, cependant une heuristique de choix est donnee. Le calcul de l'heuristique et la generation du code peuvent etre automatises a l'aide d'outils classiques. Une etude de cas sur un processeur vectoriel d'un cray y-mp a ete menee