Contribution à l'étude du placement dynamique sur machines parallèles de type MIMD

This thesis is a contribution to the study of dynamic investment process on multiprocessor machines with distributed memory . The context of our work is the simulation and evaluation of the performance of applications where the number of processes and the time of their creation depend on the current execution . We propose a new algorithm Scalable dynamic investment process approximate type with control elements and distributed information . Each node X in a parallel machine is associated with a subset of processors with whom he can share his burden equitably. This subset is called Solution Placement ( SP) of the node. Solution of initial placement of a node X is composed of the subset of nodes directly connected to node X. The investment decision of a process is made ​​at the time of its creation , it can be placed on the node on which it was created or on one of the nodes of the SP . Under the effect of certain operators ( decline , growth, merger, replacement , rotation) Solution Placement of a node changes during the execution of the application which allows distribution and load balancing nodes . To study the behavior of the Evolutionary algorithm , we used the sequential simulator SIMAD which is a tool designed to assess the dynamic load allocation algorithms on MIMD distributed memory machines . The second contribution of this thesis is the definition and integration into SIMAD a synthetic language for describing parallel applications with graphs of general communication. The paper concludes by presenting some of the results of all the experiments we conducted in order to evaluate the performance and behavior of our approach to dynamic investment process . Two types of results are presented and analyzed . First we seek the influence of certain parameters ( the maximum size of SP , updating SP , the number of processes per charge and the merging operator ) on the performance of the Evolutionary Algorithm . Then , a comparative study with other methods of dynamic placement allows to highlight the performance of our approach.Cette thèse est une contribution à l'étude du placement dynamique de processus sur des machines multiprocesseurs à mémoire distribuée. Le contexte de notre travail est celui de la simulation et de l'évaluation de l'exécution d'applications dont le nombre de processus et le moment de leur création dépendent de l'exécution en cours. Nous proposons un nouvel algorithme évolutif de placement dynamique de processus de type approximatif, avec des éléments de contrôle et d'information distribués. A chaque noeud X d'une machine parallèle est associé un sous-ensemble de processeurs avec lesquels il peut partager sa charge de manière équitable. Ce sous-ensemble est appelé la Solution de Placement (SP) du noeud. La Solution de Placement initiale d'un noeud X est composée du sous-ensemble des noeuds directement connectés au noeud X. La décision de placement d'un processus est faite au moment de sa création, il peut alors être placé sur le noeud sur lequel il a été créé ou bien sur un des noeuds de sa SP. Sous l'effet de certains opérateurs (declin, croissance, fusion, remplacement, rotation) la Solution de Placement d'un noeud évolue au cours de l'exécution de l'application ce qui permet une répartition et un équilibrage des charges des noeuds. Pour étudier le comportement de l'algorithme évolutif, nous avons utilisé le simulateur séquentiel SIMAD qui est un outil conçu pour évaluer les algorithmes d'allocation dynamique de charge sur des machines MIMD à mémoire distribuée. Le deuxième apport de cette thèse est la définition et l'intégration dans SIMAD d'un langage synthétique qui permet de décrire des applications parallèles avec des graphes de communication généraux. Le document se termine par la présentation d'une partie des résultats de l'ensemble des expériences que nous avons menées, dans le but d'évaluer les performances et le comportement de notre approche du placement dynamique de processus. Deux types de résultats sont présentés et analysés. Tout d'abord nous recherchons l'influence de certains paramètres (la taille maximale des SP, l'actualisation des SP, le nombre de processus par niveau de charge et l'opérateur de fusion) sur le comportement de l'algorithme évolutif. Ensuite, une étude comparative avec d'autres méthodes de placement dynamique permet de mettre en évidence les performances de notre approche