Abstract FR:

L'implantation optimisee d'algorithmes reactifs sur des architectures paralleles, est un probleme complexe que nous nous proposons de resoudre par la methodologie adequation algorithme architecture. Elle permet de construire rapidement, a partir de la specification d'un algorithme et d'une architecture, le programme optimise de chaque processeur. Chaque programme est constitue d'une partie applicative qui correspond a l'algorithme et d'une partie executif. Cet executif ne peut etre construit sans un modele precis de l'architecture, de l'algorithme et de leur mise en adequation (implantation optimisee). Nous proposons un nouveau modele d'architecture suffisamment generique pour modeliser le plus grand nombre possible d'architectures, et bien adapte a l'optimisation et la generation automatique d'executifs. Une machine est modelisee par un graphe oriente ou les sommets correspondent a ses sequenceurs de calculs et de communications, ses bus, ses memoires. L'algorithme est modelise par un hypergraphe oriente ou les sommets sont des operations de calcul et les arcs les dependances de donnees entre ces operations. Par transformation de ces deux graphes nous construisons l'ensemble des graphes d'implantation. Chacun d'eux decrit la distribution et l'ordonnancement des calculs et des communications. Nous choisissons parmi ces implantations, a l'aide d'une heuristique d'optimisation, celle qui possede la plus courte duree d'execution et minimise les memoires. Ensuite, nous formalisons les transformations du graphe d'implantation optimise en un executif distribue optimise, reposant sur un macro-code intermediaire pour supporter le plus d'architectures possibles. Cet executif est taille sur mesure pour l'application afin de minimiser son surcout et garantir l'ordonnancement precis des calculs et des communications. Enfin, nous presentons le developpement du logiciel syndex supportant la methodologie presentee, ainsi que son utilisation dans deux applications concretes.