Abstract FR:

Cette these propose une methodologie pour l'analyse et la conception des algorithmes paralleles. On illustre d'abord la methodologie couramment utilisee en prenant comme exemple un probleme de simulation multi-etages de reseaux de neurones dans une architecture a passage de message. Une telle approche demande une connaissance profonde de l'application traitee et une experience importante en algorithmique parallele. Une autre alternative consiste a transformer un programme sequentiel preexistant en un programme parallele equivalent. Meme si l'application ne peut pas etre totalement traduite de maniere automatique, l'objectif est de faciliter la tache du programmeur en traduisant certaines parties du code. Les reseaux de petri sont le formalisme adopte dans cette these avec les objectifs suivants. Le premier est d'etudier les proprietes structurelles des reseaux de petri qui offrent des bases mathematiques solides venant de l'algebre lineaire et de la theorie des graphes. Le deuxieme objectif est de modeliser des algorithmes a l'aide de reseaux de petri. On etablit que le modele peut etre base sur une analyse directe du probleme ou bien sur un algorithme sequentiel qui le resout. On essaie de montrer l'equivalence entre une modelisation par graphes de dependances de donnees et par reseaux de petri lorsque les antidependances et les dependances de sortie ont ete supprimees. Le troisieme objectif est l'ordonnancer des taches non preemptives avec contraintes de precedence par des graphes d'evenements sur un nombre non limite, et eventuellement optimal, de processeurs identiques. Le quatrieme objectif est la detection des communications globales a realiser. Si de tels schemas de communication peuvent etre identifies, alors les appels aux procedures de communication peuvent etre effectues sans avoir a se preoccuper de l'architecture de la machine cible.