Algorithmique parallèle du texte : du modèle systolique au modèle CGM

We have all the intuition that a work can be completed in much less time if it is distributed between several people or on several machines. This concept names the parallelism which can be defined as the state of what develops in the same direction or at the same time. It is naturally that this concept of parallelism was applied to computers. So it was possible to answer to the needs for power necessary to the realization of greedy projects in computing times and in memory size. Parallelism combined with efficient algorithmic makes it possible to save time in order to answer important needs as well as possible. It breaks with the traditional approach which consists in gaining speed by carrying out each operation more quickly, approach limited by the laws of physics. Thus, the concept of parallelism largely contributed to the multiplication of data-processing models.We will be interested in systolic model and coarse grained parallel model baptized (Coarse Grained Multicomputers). CGM was proposed by F. Dehne and al. and it has properties which make it very interesting from a practical point of view. It is adapted perfectly to the modelling of existing architectures for which the number of processors can be several thousands and the size of the data can reach several billion bytes. An algorithm developed for this model consists of local computations using, if possible, optimal sequential algorithms and communication rounds of which the number must be independent of the size of the data to treat. Thus, CGM is very interesting from an economic point of view. Indeed, this model is independent of real architectures and makes it possible to re-use efficient sequential algorithms, which makes it very portable. In this thesis we are interested in parallel string matching algorithms problems. These problems can improve data compression or be used in bio-data processing. Thus, we propose CGM solutions for the problems of research of the longest increasing subsequence, longest common subsequence to two words, longest repeated suffix ending in each character of a word and repetitions. For that, we started from existing systolic solutions which we adapted to CGM. The goal of this work is in fact double. On the one hand, we propose for the first time CGM solutions to these four problems. In addition, we show how systolic solutions can be derived in CGM algorithms. Indeed, many problems were studied on systolic architectures, i.e. dedicated machines, no reusable for other problems. CGM makes it possible to work with inexpensive and reusable machines. Moreover, the experience gained during this work enables us to have a good idea of systolic solutions adaptable to CGM. This could make it possible to consolidate the existing bridge between fine grained models and coarse grained models. We finish this thesis by a discussion on load balancing of the solutions suggested and on the predictivity of the adaptation of other systolic solutions to CGM.Nous avons tous l'intuition qu'un travail peut être réalisé en beaucoup moins de temps s'il est réparti entre plusieurs personnes ou sur plusieurs machines. Cette notion se nomme le parallélisme qui peut se définir comme l'état de ce qui se développe dans la même direction ou en même temps. C'est naturellement que la notion de parallélisme a été appliquée aux ordinateurs. De ce fait, il a été possible de répondre aux besoins de puissance nécessaire à la réalisation de projets gourmands en temps de calculs et en taille mémoire. Le parallélisme combiné à une algorithmique performante permet de gagner du temps afin de répondre au mieux à d'importants besoins. Il rompt avec l'approche classique qui consiste à gagner de la vitesse en effectuant plus rapidement chaque opération, approche bornée par les lois de la physique. La notion de parallélisme a donc grandement contribué à la multiplication des modèles informatiques. Nous nous intéresserons au modèle systolique et au modèle parallèle à gros grains baptisé (Coarse Grained Multicomputers). Le modèle CGM a été proposé par F. Dehne et al. et il possède des propriétés qui le rendent très intéressant d'un point de vue pratique. Il est parfaitement adapté à la modélisation des architectures existantes pour lesquelles le nombre de processeurs peut être de plusieurs milliers et la taille des données peut atteindre plusieurs milliards d'octets. Un algorithme développé pour ce modèle est constitué de calculs locaux utilisant, si possible, des algorithmes séquentiels optimaux et de rondes de communication dont le nombre doit être indépendant de la taille des données à traiter. Le modèle CGM est donc très intéressant d'un point de vue économique. En effet, ce modèle est indépendant des architectures réelles et permet de réutiliser des algorithmes séquentiels efficaces, ce qui le rend très portable. Dans cette thèse nous nous intéressons à des problèmes d'algorithmique du texte. Ces problèmes peuvent améliorer la compression de données ou bien être utilisés en bio-informatique. Ainsi, nous proposons des solutions CGM aux problèmes de recherche de la plus longue sous-suite croissante, de la plus longue sous-suite commune à deux mots, du plus long suffixe répété en chaque caractère d'un mot et de répétitions. Pour cela, nous sommes partis de solutions systoliques existantes que nous avons adaptées au modèle CGM. Le but de ce travail est en fait double. D'une part, nous proposons pour la première fois des solutions CGM à ces quatre problèmes. D'autre part, nous montrons comment des solutions systoliques peuvent être dérivées en algorithmes CGM. En effet, de nombreux problèmes ont été étudiés sur des architectures systoliques, c'est à dire des machines dédiées, non réutilisables pour d'autres problèmes. Le modèle CGM quant à lui permet de travailler avec des machines peu coûteuses et réutilisables à souhaits. De plus, l'expérience acquise au cours de ces travaux nous permet d'avoir une bonne idée des solutions systoliques adaptables au modèle CGM. Ceci pourrait permettre de consolider le pont existant entre modèles à grains fins et modèles à gros grains. Nous finissons cette thèse par une discussion sur l'équilibrage de charge des solutions proposées et sur la prédictivité de l'adaptation d'autres solutions systoliques au modèle CGM