Abstract FR:

Cette thèse traite de la parallélisation dans le cadre fonctionnel et des interactions entre granularité, taux d'activité et rendement des processus. Le modèle servant de toile de fond à notre étude est MaRS (Machine à Réduction Symbolique) développé au CERT-ONERA qui se caractérise entre autres choses par des processus à coût particulièrement faible mais en nombre limité. L'objectif de cette thèse est de dériver par une critique constructive du modèle MaRS un nouveau modèle au champ d'application étendu. Pour cela une première partie est consacrée à la présentation du cadre fonctionnel et du modèle MaRS dont nous exhibons les caractéristiques les plus marquantes. La deuxième partie montre l'influence du coût d'accès aux données sur le taux de parallélisme effectif et expose l'implémentation performante sous forme combinatoire de diverses structures de données. La troisième partie traite de l'influence du taux d'activité des processus sur le taux de parallélisme effectif et étudie deux approches qui visent à augmenter le taux de parallélisme effectif en diminuant le taux d'attente des différents processus. Enfin, la quatrième partie analyse le paradigme pipe-line qui, bien qu'étant probablement le plus expressif et aisé à utiliser dont dispose le programmeur fonctionnel, s'avère un bien piètre outil de parallélisation de par la faible granularité des processus généralement engendrés. Une nouvelle approche de la synchronisation entre producteur et consommateur est proposée qui permet, tout en conservant intact l'aspect algorithmique du paradigme, de franchir ce cap de la granularité. Des exemples illustrent les différents mécanismes de synchronisation proposés et en particulier l'algorithme de recherche IDA*.