Abstract FR:

La these est une contribution aux logiciels d'exploitation de systemes multiprocesseurs, sans memoire partagee, et formes de processus cooperants. Elle traite de deux questions: a) un schema de cooperation d'interpretes prolog, pour lequel la repartition de charge est guidee par celle des connaissances (procedures) prolog. Ce schema permet de conserver la plupart des possibilites semantiques de haut niveau de prolog. Le parallelisme est de granularite moyenne, et combine une forme de parallelisme et et une forme de parallelisme ou. La forme et a ete implemente sur architecture a transputers. B) une methode heuristique de placement de taches/procedures, permettant egalement la configuration d'un reseau de transputers. La methode est basee sur le partitionnement de graphe; elle s'applique au graphe des communications des interpreteurs prolog, mais plus generalement au probleme de partitionnement de graphe; aucune contrainte n'est indispensable concernant le nombre ou les cardinalites des parties du graphe. Le principe est celui de bipartitions recursives, sur la base d'une forme diagonale de la matrice d'adjacence du graphe. Cette forme est obtenue par un algorithme de type reseau d'automates; des perturbations par groupes de transformations sont appliquees a ses points fixes. Plusieurs resultats sont relates, la complexite de calcul est estimee. Certaines preuves, des elements concernant les fondements theoriques, sont fournis