Abstract FR:

Nous etudions des machines paralleles construites de facon modulaire par interconnexions de petits composants de bases. Nous nous sommes interesses a deux aspects de la modularite: d'une part en travaillant sur la verification de propriete de blocage sur de telles machines et d'autre part en elaborant des algorithmes systoliques modulaires. En ce qui concerne la verification de la propriete de blocage, les reseaux modulaires sont regroupes par familles infinies. Notre demarche a consiste a determiner des familles pour lesquelles il est decidable de savoir si elles contiennent un reseau bloquant et des familles pour lesquelles ce probleme est indecidable. Nous avons a cet effet considere deux approches differentes. Dans la premiere approche, les reseaux des familles sont construits par interconnexions quelconques de copies de motifs initialement fixes. Nous montrons alors que le probleme du blocage est indecidable. Dans la deuxieme approche, la connexion des motifs lors de la construction des reseaux est controlee par un automate d'etat fini. Nous avons alors trouve des classes d'automates pour lesquelles la detection des reseaux bloquants est decidable, et d'autres classes pour lesquelles cette detection est indecidable. En ce qui concerne la construction d'algorithmes systoliques, nous avons propose une methode unificatrice pour la synthese d'algorithmes systoliques lineaires modulaires. Nous avons d'abord presente une demarche rigoureuse de mise au point d'algorithmes lineaires modulaires. Nous avons ensuite applique notre demarche a l'algorithme lineaire propose par ramakrishnan et varman portant sur le calcul de la cloture transitive d'un graphe. L'algorithme que nous avons obtenu peut resoudre aussi bien le probleme de la cloture transitive ou du plus court chemin que de la multiplication de matrices