Régulation dynamique de charge dans les systèmes logiques parallèles
Institution:
Grenoble INPGDisciplines:
Directors:
Abstract EN:
The development of appropriate load balancing techniques constitutes one of the most important challenges to be dealt with, in order to exploit efficiently parallel architectures. The implementation of an efficient parallel logic system also needs the development of appropriate scheduling rules. This thesis is dedicated to the study of the mechanisms and parallel evaluation strategies in order to build the PLoSys parallel programming environment. The PLoSys computational model exploits implicit or-parallelism of a "pure" Prolog programs following a multisequential approach on a scalable distributed memory architecture. In this class of systems, the parallelisation is driven by the load balancing function according to the available processing elements. In order to identify an appropriate load balancing function, we built an evaluation platform based on a modelling technique. Our approach consists in modelling the Prolog program execution by a directed acyclic graph. The task graph execution emulates the program evaluation on a given target architecture. We analyze the main implementation problems of an efficient load balancing function for the PLoSys system among an evaluation environment. This environement is currently implemented on the MegaNode machine whose processing elements are Transputers. The main analysis results of the different scheduling strategies are presented and evaluated
Abstract FR:
L'un des enjeux les plus importants à l'heure actuelle pour l'utilisation efficace d'une architecture parallèle est le développement de techniques de régulation de charge appropriées. La mise en oeuvre d'un système logique parallèle efficace se heurte également à cette même exigence. Cette thèse est consacrée à l'étude des mécanismes et stratégies d'évaluation parallèles pour la conception et la réalisation de l'environnement de programmation Prolog parallèle PLoSys. PLoSys se place dans la catégorie des systèmes logiques adoptant un modèle d'exécution multi-séquentiel. Ce modèle exploite automatiquement le parallélisme OU inhérent à la sémantique des programmes Prolog "pur" sur des architectures sans mémoire commune. Dans cette classe de systèmes, la parallélisation est guidée dynamiquement par la stratégie de régulation adoptée en fonction des ressources de calcul disponibles. Afin d'élaborer une fonction de régulation de charge appropriée, nous avons choisi l'utilisation d'une technique de modélisation dans le but d'émuler le comportement réel du système sur une architecture parallèle existante. Notre approche repose sur la représentation de l'exécution d'un programme PROLOG par un graphe de tâches acyclique. L'exécution de ce graphe de tâches permet l'émulation de l'évaluation du programme PROLOG sur l'architecture ciblée. Nous analysons les principaux problèmes liés à la conception d'une fonction de régulation de charge efficace, pour le système PLoSys, à travers un environnement d'évaluation implanté sur un réseau de Transputers : le MegaNode. Les principaux résultats d'analyse des différentes stratégies de régulation de charge sont présentés et évalués