Asynchronisme : Cadres continu et discret

In the domain of scientific computing, the main objectives consist in fastly performing a large amount of computations and treating large-size problems. In order to attain those goals, parallel computing has been developed, firstly with dedicated machines such as vector computers and shared memory ones. Then, according to the decrease of the production costs of the machines and the increase of their power, parallelism has focused on local clusters. Finally, the enhancement of the throughput in the worldwide network has allowed to envisage those last years the use of clusters of clusters, that is to say, clusters of geographically distant clusters interconnected via the Internet.That extension of the concept of parallel machine theoretically permits to gather all the machines in the world which are connected to the Internet. It presents the double advantage to increase the computation power and the memory capacity in RAM and mass storage, which allows the treatment of large-size problems.However, the programming of such meta-clusters cannot be exactly the same as the one of classical machines or even local clusters. Effectively, in that new architecture, the heterogeneity of the machines and of the communication links generates strong constraints to obtain good performances. In particular, the synchronization of the communications between the processors generally induces a major loss of performance.Thus, it is essential to propose a new kind of algorithms which allows us to use those meta-clusters as efficiently as possible. This is for all those reasons that, after having worked on synchronous parallel algorithms during my PhD Thesis, I have decided to focus my work on asynchronism, in the continuous context on the one hand, with parallel iterative algorithms, and in the discrete context on the other hand, with finite-states discrete-time systems.Asynchronism permits to efficiently solve a large number of scientific problems on meta-clusters by bringing the necessary flexibility for the adaptation to the different speeds of processors and communication links between them. However, to ensure a stable behavior and to obtain an optimal efficiency, several aspects must be studied and/or adapted according to the context of use. In the continuous case, one will especially focus on the convergence conditions of the iterative process, the detection of that convergence, the halting procedure and the load balancing. In the discrete case, one will also focus on the convergence of the system, by trying to precisely identify the initial states leading to a given fixed point, but also on the theoretical study of the asynchronous behavior and on the mixing of synchronism and asynchronism to design new systems with a given behavior.Dans le domaine du calcul scientifique, les principaux objectifs sont d'effectuer rapidement un très grand nombre de calculs ainsi que de traiter des problèmes de grande taille. Pour atteindre ces buts, le calcul parallèle a été développé, d'abord par le biais de machines spécifiques telles que les calculateurs vectoriels et les machines à mémoire partagée. Puis, avec la baisse des coûts de production des machines et l'augmentation de leur puissance, le parallélisme s'est tourné vers les grappes locales de stations de travail. Enfin, l'amélioration des débits dans le réseau mondial a permis ces dernières années d'envisager l'utilisation de grappes de grappes de machines, c'est-à-dire, des grappes de machines géographiquement distantes et reliées entre elles via l'Internet.Cette extension du concept de machine parallèle permet théoriquement de rassembler l'ensemble des machines du parc mondial qui sont reliées à l'Internet. Elle a donc le double avantage d'augmenter la puissance de calcul mais aussi la capacité de stockage en mémoire vive et en mémoire de masse, ce qui permet de traiter des problèmes de très grandes tailles.Cependant, la programmation de telles méta-grappes ne peut plus être tout à fait la même que celle des machines classiques ou même des grappes locales de machines. En effet, dans cette nouvelle architecture, l'hétérogénéité des machines utilisées et des liens de communication entre celles-ci génère des contraintes fortes pour obtenir de bonnes performances. Notamment, la synchronisation des communications entre les processeurs induit généralement une perte majeure de performance.Il est donc essentiel de proposer un nouveau type d'algorithmes qui permette d'utiliser de la manière la plus efficace possible ces méta-grappes. C'est pour ces raisons qu'après avoir travaillé sur des algorithmes parallèles synchrones lors de ma thèse, j'ai orienté mes recherches sur l'asynchronisme, dans le cadre continu d'une part, avec les algorithmes itératifs parallèles, et dans le cadre discret d'autre part, avec les systèmes dynamiques à états finis et temps discret.L'asynchronisme permet de résoudre efficacement un grand nombre de problèmes scientifiques sur des méta-grappes en apportant la souplesse nécessaire pour s'adapter aux différentes vitesses des processeurs et des liens de communication entre ceux-ci. Néanmoins, pour garantir un comportement stable et obtenir une efficacité optimale, plusieurs aspects doivent être étudiés et/ou adaptés selon le cadre d'utilisation. Dans le cadre continu, on s'intéressera notamment aux conditions de convergence du processus itératif, la détection de cette convergence, la procédure d'arrêt et l'équilibrage de charge. Dans le cadre discret, on s'intéressera également à la convergence du système, en tentant d'identifier précisément les états initiaux qui mènent à un point fixe donné, ainsi qu'à l'étude théorique du comportement asynchrone et à la combinaison du synchronisme et de l'asynchronisme pour concevoir de nouveaux systèmes ayant un comportement donné