Abstract FR:

Cette these traite de la parallelisation d'algorithmes de graphe sur des machines multiprocesseurs sans memoire partagee. Les algorithmes de graphe sont utilises dans les systemes d'exploitation repartis pour fournir des operateurs lies au reseau. Nous proposons l'approche inverse, c'est a dire la construction, a partir des graphes a traiter, de machines-reseau qui soient capables de resoudre de facon efficace les algorithmes de graphe. Nous definissons un principe de resolution d'algorithmes de graphe, que nous avons appele principe de flux diffusant, extension de techniques algorithmiques reparties presentees dans le memoire. Il s'agit d'un principe de simulation qui prend la topologie du graphe comme element structurel dans l'execution de l'algorithme, ce qui entraine la parallelisation immediate et optimale du probleme. Selon ce principe, nous avons developpe plusieurs algorithmes dont la reconnaissance des graphes series-paralleles et le flot maximal dans un graphe. Nous proposons ensuite une implantation sur machine a transputers d'un logiciel appele apf dont les objectifs sont le developpement des algorithmes de graphe selon le principe de flux mais egalement de tout type d'algorithme en reseau, la facilitation de la mise au point de ces algorithmes et une plateforme d'execution permettant l'analyse des performances. Ce logiciel offre de grandes opportunites d'integration dans des machines-reseau plus vastes