Athapascan-1 : distributed interpretation of parallel programs based on data flow analysis

Athapascan-1 : interprétation distribuée du flot de données d'un programme parallèle

François Galilée (1)

1 ID-IMAG - Informatique et Distribution

The topic of this thesis is the modelisation by a data-flow graph of any execution of a parallel application. This graph, that links tasks and data, is dynamically built. This construction is independant from the effective tasks' scheduling. This independance enables the definition of a data access semantic and the control of memory consumption. We study in the first part the distributed algorithms enabling the construction and the management of this kind of graph. The central point of this management is the detection of the end of access of tasks on shared data. We propose a reactive algorithm performing this detection efficiently. The implementation of this algorithm is the kernel of the distributed implementation of the Athapascan-1 interface for parallel programming. The semantic of data access in this programming interface is lexicographic and its definition is based on the data-flow graph of the application. We show in a second part that the knowledge of the data-flow of an application enables a theoretical bound of the time and space of any execution. We propose, implement in Athapascan-1 and evaluate two distributed sheduling algorithms that limit the memory space used by any parallel execution. These experiments validate the theoretical results claimed by the two policies.

Cette thèse est centrée sur la modélisation de l'exécution d'une application parallèle par un graphe de flot de données. Ce graphe, qui relie les tâches aux données partagées, est construit de manière dynamique. Cette construction, indépendante de l'ordonnancement des tâches effectué, permet de définir la sémantique des accès aux données et de controler la consommation mémoire de toute exécution. Nous étudions dans une première partie les algorithmes permettant la construction et la gestion d'un tel graphe de flot de données dans un environnement distribué. Un point crucial de ces algorithmes est la détection de terminaison des accès des tâches sur les données partagées. Nous proposons un algorithme réactif réalisant cette détection. L'implantation de cet algorithme est au centre de l'implantation distribuée de l'interface de programmation parallèle Athapascan-1. Cette interface permet la description du parallélisme d'une application par création de tâches asynchrones. La sémantique (de type lexicographique) de cette interface est également définie à partir du graphe de flot de données. Nous montrons dans une deuxième partie que la connaissance du flot de données d'une application permet de controler de manière théorique la durée et, surtout, la consommation mémoire de toute exécution. Ce controle est effectué à partir d'un ordonnancement séquentiel implicite des tâches. Nous proposons, implantons dans Athapascan-1 et évaluons deux algorithmes d'ordonnancement distribués permettant de limiter le volume de mémoire requis par toute exécution. Ces expérimentations permettent de valider les résultats théoriques obtenus.

Mots clés: parallel language; data-flow graph; distributed termination detection; online scheduling; cost model for time and space

Mots clés: Langage parallèle; graphe de flot de données; terminaison distribuée; ordonnancement à la volée; modèle de coût en temps et en mémoire.; modèle de coût en temps et en mémoire

Domaines: Réseaux et télécommunications [cs.NI]

François Galilée. Athapascan-1 : interprétation distribuée du flot de données d'un programme parallèle. Réseaux et télécommunications [cs.NI]. Institut National Polytechnique de Grenoble - INPG, 1999. Français. ⟨NNT : ⟩. ⟨tel-00004832⟩