Extraction de surfaces en imagerie médicale : approches parallèles.

  • By: Jean-Marc Nicod
  • Number: PhD1997-01
  • Date: January 1997
  • Abstract:

    The context of the works presented in this PhD thesis is at the intersection of two main axes, namely parallel computing and geometric modelization for medical imaging. More precisely, it deals about the parallelization of surfaces extraction algorithms in 3D medical images. This work is included into a research activity of the parallel image processing team of our laboratory. Our project is to implement a chain of medical image processing, from the acquisition of a 3D medical image to its visualization onto the screen. Our studies focus mainly on two surfaces extraction techniques, called the Marching-Cubes and the Dividing-Cubes algorithms. For these two approaches, we have proposed a geometric modelization so as to analyze the complexity of the extracted surfaces. We show how this modelization allows to evaluate precisely the execution time of these algorithms. In a second step, we use this evaluation to reallocate the data among the processors so as to balance the workload. Because of very strong locality constraints associated to the computation of a surface, we use data-driven load balancing techniques leading to an optimal use of the parallel computer. Our data allocation strategies allow to exploit the spatial coherence associated to the computations. But we can also take the temporal coherence into account so as to optimize the production of an animation. In the case of a regular variation of the iso-surface threshold as well as in the case of small camera movements, we show the advantages of this strategy : the data used by a processor to compute an image are almost the same as those that are used by the same processor to compute the following image. We propose a communication primitive which exploits this property. Some experimentations made on the Cray T3D parallel computer demonstrate the efficiency of our approaches. Interactive response times are reported for surface extraction in real-life medical datasets.
  • Abstract (in french):

    Le contexte du travail présenté dans cette thèse se situe à l'intersection entre le parallélisme et la modélisation géométrique pour l'imagerie médicale. Il s'agit plus précisément de la parallélisation d'algorithmes d'extraction de surfaces, à partir de données volumiques médicales. Ce travail s'insère dans un projet du groupe d'imagerie parallèle du LIP, visant à la mise en oeuvre sur des machines parallèles à mémoire distribuée de toute une chaîne de traitements d'imagerie médicale. Nous nous focalisons sur deux algorithmes d'extraction de surfaces, l'algorithme des Marching-Cubes et celui des Dividing-Cubes. Pour ces deux approches, nous avons mené à bien des études de modélisation géométrique permettant d'analyser la complexité des surfaces extraites. Nous montrons comment ces modèles de complexité permettent d'obtenir une évaluation la plus précise possible du temps d'exécution de ces algorithmes. Dans un deuxième temps, nous utilisons cette évaluation pour remettre en cause l'allocation initiale des données afin d'obtenir une parallélisation équilibrée. En raison des très fortes contraintes de localité associées à nos calculs, nous utilisons des stratégies d'équilibrage dirigées par les données, qui nous permettent d'exploiter au mieux la puissance des machines parallèles. Notre stratégie d'allocation des données permet de prendre en compte la cohérence spatiale associée à nos calculs. Mais nous pouvons également prendre en compte la cohérence temporelle pour optimiser l'allocation des données lors de la production d'une animation. Aussi bien pour la variation régulière du seuil d'une iso-surface que pour le changement des paramètres de visualisation, nous démontrons les bénéfices d'une telle stratégie : les données utilisées par un processeur lors de la production d'une image sont peu différentes celles qui sont utilisées par le même processeur lors du calcul de l'image suivante. Nous proposons une primitive de communication qui exploite cette propriété. Des expérimentations sur une machine T3D de Cray, démontrent l'efficacité de notre approche et permettent d'envisager d'effectuer ces traitements de manière interactive.
  • Keywords:

    Parallel Algorithm, Medical Imaging, Load Balancing, Discrete Geometry, Rectilinear Partitioning, Marching-Cubes, Dividing-Cubes.
  • Keywords (in french):

    Algorithmique parallèle, Imagerie médicale, équilibrage de charge, Géométrie discrète, Partitionnement rectilinéaire, Marching-cubes, Dividing-cubes.
  • Availability: Paper copy available.
  • Size: 138p
  • Format: Compressed PostScript
  • Get it

Mémoire Distribuée-Partagée sur Systèmes Parallèles et Distribués.

  • By: Laurent Lefevre
  • Number: PhD1997-02
  • Date: January 1997
  • Availability: Paper copy available.
  • Size: p
  • Format: Compressed PostScript
  • Get it

Cercles discrets sur automates cellulaires.

  • By: Laure Tougne
  • Number: PhD1997-03
  • Date: Janvier 1997
  • Abstract:

    In this thesis, we study the following problem : how can we construct in real time ``discrete circles'' with the help of cellular automata ? In the literature, there exists various definitions of discrete circles. Their study allows us in a first time to put in a prominent the fact that, in the first octant, a discrete circle is composed of vertical segments the extremities of which belong to beams of parabolas. Then we observe that constructing these beams with cellular automata allow us to engender simultaneously discrete circles. In a first part, we interest us to a new digitization which is near Pitteway's one, which consists in considering a family of discrete parabolas obtained using ``the floor'' of a family of real parabolas. We first explain the evolution of some automata that construct parts of this beam from others parts, which depend themselves on the possibility of constructing the first ones. Then, we study the construction of a unique cellular automaton that engenders the beams of discrete parabolas. The justification of all these constructions needs a complicated recurrence reasoning. Finally we describe the automaton that constructs the ``floor circles''. Then, we generalize the previous construction to other families of discrete circles. The first one which is considerated is the family of ``ceil circles''. Here we explain how we can obtain the beam of ``ceil parabolas'' from the beam of ``floor parabolas''. Moreover, we use a technic which is purely linked up to the cellular automata (the grouping cells) and we show the possibility of constructing by cellular automata all the ``reasonable discrete circles''. We complete this result studying the recognition of discrete circles with the help of cellular automata.
  • Abstract (in french):

    Dans cette thèse, nous étudions le problème suivant : comment engendrer en temps réel des "cercles discrets" par automates cellulaires ? Il existe, dans la littérature, plusieurs définitions de cercles discrets. Leur étude nous permet tout d'abord de mettre en évidence le fait que, dans le premier octant, un cercle discret est composé de segments verticaux dont les extrémités appartiennent à des faisceaux de paraboles discrètes. Nous observons alors que construire ces faisceaux par automate cellulaire permet d'engendrer simultanément une famille de cercles discrets. Dans un premier temps, nous nous intéressons à une nouvelle discrétisation très proche de celle de Pitteway , qui consiste à considérer une famille de paraboles discrètes obtenue par ``passage au plancher'' d'une famille de paraboles réelles. Nous mettons tout d'abord en évidence des automates cellulaires construisant des parties de ce faisceau à partir d'autres parties, dépendant elles-mêmes de la possibilité de construire les premières. Ensuite, nous montrons la construction d'un automate unique engendrant ce faisceau des paraboles discrètes. La justification de ces constructions nécessite une récurrence compliquée. Nous décrivons alors l'automate qui construit les ``cercles plancher''. Ensuite, nous généralisons la construction précédente à d'autres familles de cercles discrets. La première considérée est celle des ``cercles plafond''. Dans ce cadre, nous montrons comment passer du faisceau de ``paraboles plancher'' au faisceau des ``paraboles plafond''. Par ailleurs, grâce à une technique purement liée aux automates cellulaires (le groupage de cellules), nous montrons la possibilité de construire par automates cellulaires tous les ``cercles discrets raisonnables''. Nous complétons ce résultat en étudiant la reconnaissance de cercles discrets par automates cellulaires.
  • Keywords:

    Cellular Automata, Discrete Circles, Discrete Parabolas, Real Time.
  • Keywords (in french):

    Automates cellulaires, Cercles discrets, Paraboles discrètes, Temps réel.
  • Availability: Paper copy available.
  • Size: 140p
  • Format: Compressed PostScript
  • Get it

Contribution à l'étude des réseaux d'ondelettes.

  • By: Richard Baron
  • Number: PhD1997-04
  • Date: Février 1997
  • Abstract:

    Contribution to the study of wavelet networks Neural networks constitute a tool for function approximation and for classification task. The wavelet network model establishes a link between neural methods and wavelet decomposition theory, coming from signal processing. Our work deals with this model, treating different problems, and making links with other techniques. We first give a brief presentation of decomposition in wavelet functions, and address the case of multidimensional wavelet functions. Aiming at an application to neural networks, we consider properties of {\it frames}, families of functions authorizing some redundancy in decomposition. We then describe the architecture of neural networks using these properties. Then, we present a useful family of wavelet functions, due to the practical choice of functions which it authorizes. We then address the problem of the application of the wavelet network model to function approximation. We examine the universal approximation property, which shows that the wavelet model may approximate any function. The model is then compared with other, on a theoretical point of vue. Experimental results of comparison of models are given, for problem of function approximations in small dimension. Finally, we present a tool, based on parallel computation on clusters of workstations or on dedicated parallel machine, allowing the fine tuning of parameters used in wavelet networks. The wavelet network model is also applied to classification tasks. We first present the peculiarities of the wavelet network architecture, with simple problems, in small dimension. Results are then given for the classical Breiman's waveform problem. This allows to compare the classification performances of the wavelet model, in relation to others works. We address the problem of input data dimension, which raises specific problems in the case of wavelet networks. An initialization algorithm is thus proposed. We give results from a comparative study of three classifier models (multilayered perceptron, Monoplan and wavelet), used to learn sonar signal classification. We investigate in this case the question of hard to classify examples, and propose some measure for detecting them. We conclude on the studying of the efficiency of this measure. Then, results concerning an application to data of olfactive perception task are given. Finally, a link is drawn between wavelet networks and regularization techniques. We define regularization terms adapted to wavelet model architecture, and give experimental results showing their interest. Then, the theoretical link between the wavelet network model and regularization networks is examined. Convergence considerations allow us to conjecture that wavelet networks are not regularization networks.
  • Abstract (in french):

    Les réseaux de neurones artificiels constituent des outils pour l'approximation de fonctions et pour la classification. Le modèle des réseaux d'ondelettes établit un lien entre les méthodes neuronales et la théorie de la décomposition en ondelettes, issue des techniques de traitement du signal. Notre travail porte sur ce modèle, en l'appliquant à différents problèmes, et en le reliant à d'autres techniques. Nous donnons tout d'abord quelques rappels concernant la décomposition en fonctions ondelettes, et abordons le cas des fonctions ondelettes vectorielles. Dans la perspective d'une application aux réseaux de neurones, nous nous intéressons aux propriétés des structures obliques, familles de fonctions autorisant une redondance dans la décomposition. Nous précisons alors l'architecture de réseaux de neurones utilisant les propriétés de ces familles. Nous présentons une famille de fonctions ondelettes utile, par le choix pratique des fonctions qu'elle autorise. Nous traitons ensuite le problème de l'application du modèle réseau d'ondelettes à l'approximation de fonctions. Nous évoquons la propriété d'approximation universelle, qui montre que le modèle ondelette peut réaliser l'approximation de n'importe quelle fonction. Nous comparons ensuite ce modèle aux autres modèles neuronaux sur le plan théorique. Nous montrons des résultats expérimentaux de comparaison de ces modèles, sur des problèmes d'approximation de fonctions en petite dimension. Enfin, nous présentons un outil, utilisant le calcul parallèle sur réseaux de stations de travail ou machine spécifique, afin de régler de manière fine les paramètres intervenant dans les réseaux d'ondelettes. Nous appliquons également le modèle réseau d'ondelettes à des problèmes de classification. Nous commençons par montrer les particularités de l'architecture de réseaux d'ondelettes, sur des problèmes simples, en petite dimension. Nous donnons ensuite des résultats obtenus sur le problème classique des formes d'ondes de Breiman. Cela nous permet de situer le modèle ondelette, en terme de performances en classification, par rapport à des travaux antérieurs. Nous abordons la question de la dimension des données d'entrée, qui pose des problèmes pratiques dans le cas des réseaux d'ondelettes, et proposons un algorithme d'initialisation ad'hoc. Nous donnons les résultats d'une étude comparative de trois modèles de classifieurs (multicouches, Monoplan et ondelette), pour l'apprentissage de la classification de signaux sonar. Nous étudions sur cet exemple la question des exemples difficiles à classer, et proposons une mesure visant à détecter ces exemples. Nous concluons quant à l'efficacité de la mesure proposée. Enfin des résultats concernant une application à des données d'un problème de perception olfactive sont évoqués. En dernier lieu, nous établissons un lien entre les réseaux d'ondelettes et les techniques de régularisation. Nous définissons des termes de régularisation adaptés à l'architecture du modèle ondelette, et donnons des résultats expérimentaux montrant l'inter\^et de ces termes. Enfin, nous examinons le lien théorique entre le modèle des réseaux d'ondelettes et celui des réseaux de régularisation. Des considérations de convergence nous amènent à conjecturer que les réseaux d'ondelettes ne constituent pas des réseaux de régularisation.
  • Keywords:

    Neural Networks, Wavelet Networks, Function Approximation, Classification, Regularization.
  • Keywords (in french):

    Réseaux de Neurones, Réseaux d'ondelettes, Approximation de Fonctions, Classification, Régularisation.
  • Availability: Paper copy available.
  • Size: 140p
  • Format: Compressed PostScript
  • Get it

Traitement parallèle de requêtes relationnelles : Modélisation, optimisation et stratégies d'ordonnancement.

  • By: Harald Kosch
  • Number: PhD1997-05
  • Date: June 1997
  • Abstract:

    This dissertation introduces a novel methodology for optimizing complex, relational queries for parallel execution in a multi-query database (typical for decision support queries on a data warehouse). The contributions of this methodology are fourfold. First, a new representation model for parallel query processing, the DPL graphs, have been developed. In comparison with related models DPL graphs take processing strategies explicitly into account, not yet considered (i.e. operator orderings without reference to the data stream and bucket processing). These DPL graphs provide the framework for our optimizer, which is able to access sub-search spaces not yet considered (serialized bushy trees). Second, the different optimization functionalities have been separated into different modules~: the transformation manager in charge of finding the best join ordering with randomized search strategies; the resource allocation module which determines the resource allocation of each operator, and the match optimizer which evaluates the best implementation strategy of each operator. Third, a global optimization strategy has been developed, which combines the works of these modules in order to determine the optimal execution scenario. Fourth, an original methodology for the control of complex relational query processing in shared nothing systems has been implemented. In comparison to previous approaches, this formalism offers a complete methodology for detecting and correcting critical estimation errors ; it can be extended to adapt the query processing to changing workload during the execution of the query. Experiments on the Intel iPSC860 and Paragon show the pertinence of this approach. Based on the presented concepts, an optimizer prototype (called ModParOpt) was entirely implemented. In order to study the efficiency of the whole query optimization methodology 432 different queries have been run up to 200 times on a database scheme with 100 relations. A rigorous analysis of the cost distributions is performed. The results demonstrate that the resource allocation, combined with parallized randomized search algorithms are very cost-effective methods, which achieve high quality execution scenarios.
  • Abstract (in french):

    Dans cette thèse nous introduisons une méthodolgie d'optimisation de requêtes complexes (typique pour des applications d'aide à la décision) dans une base de données multi-requêtes sur une machine parallèlle multi-tâche. Cette méthodologie s'articule sur quatre idées-forces. Premièrement, l'introduction d'une nouvelle modélisation du traitement parallèles de requêtes (appelé DPL graphes), plus proche des situations d'exécution réelles que les travaux précédents. Les DPL graph permettent à notre optimisateur de rechercher des sous-espaces pas encore considerées dans ce contexte (serialized bushy trees). Deuxièmement, la structuration de l'optimisation de requêtes en trois modules via un découplage entre optimisation inter-opération et optimisation intra-opération. Une stratégie randomisée analyse, en parallèle, l'espace des parallélisations possibles et détermine le degré du parallélisme inter-opération. Un deuxième module effectue l'allocation de ressources et calcule le degré du parallélisme intra-opération. Celui-ci est basé sur une heuristique qui prend en considération le volume de travail à effectuer ainsi que la charge des machines. Un dernier module détermine la meilleure méthode d'implémentation ainsi que les méthodes d'accès aux données. Troisièmement, le développement d'une stratégie globale d'optimisation fondée sur l'analyse de l'espace de toutes les parallélisations possibles qui gère l'exécution coopérative de ce trois modules d'optimisation. Finalement, l'introduction d'une nouvelle méthodologie de contrôle du traitement des requêtes dans un système shared nothing systems. Comparé aux travaux précédents, notre formalism offre une méthodologie complete pour détecter et corriger des erreurs d'estimation de l'optimisateur statique pendant l'exécution. Des tests de performances sur des machines parallèles (Intel iPSC860 et Paragon) ont montré l'efficacité et cette méthodologie. Un prototype d'optimiseur de requêtes (appelé ModParOpt), s'appuyant sur l'ensemble des concepts développés ci-dessus, a été entièrement implémenté. Un protocole de validation très complet (schéma de bases de données intégrant 100 relations avec 432 requêtes aux caractéristiques très variées) a été défini et mis en oeuvre pour vérifier la pertinence des méthodologies et techniques proposées. Une vaste étude de l'espace de parallélisation a été menée qui montre l'efficacité du modèle proposé.
  • Keywords:

    Relational Parallel Database, Query Optimization, Serialized Bushy Trees, Query Processing, Load Balancing.
  • Keywords (in french):

    Bases de Données Relationnelles Parallèles, Optimisation de Requêtes, Serialized Bushy Trees, Traitement Parallèle de Requêtes, Equilibrage de Charge
  • Availability: Paper copy available.
  • Size: 208p
  • Format: Compressed PostScript
  • Get it

Apports de l'analyse bayésienne aux méthodes d'apprentissage des perceptrons multi-couches.

  • By: Domenico Perrotta
  • Number: PhD1997-06
  • Date: April 1997
  • Availability: Not available by FTP.
  • Size: p
  • Format: Compressed PostScript
  • Get it

Adequation Arithmetique Architecture problemes et etudes de cas.

  • By: Arnaud Tisserand
  • Number: PhD1997-07
  • Date: September 1997
  • Abstract:

    Nowadays, computers offer more and more arithmetic functions wired in hardware. Last generations of processors integrate fast hardware operators to evaluate divisions, square roots, sines, cosines, logarithms... Many references in computer arithmetic stress on the fact that changing number representation and/or using specific algorithms make it possible to build very efficient hardware operators. The goal in this thesis is to investigate and illustrate the fundmental links between computer arithmetic and computer architecture through four real problems. Self-Timed Circuits evaluate the arithmetic functions with variable input-dependent computation time. We have developped low complexity asynchronous adders, including a space efficient adder with average computation time of O(sqrt(log(n))). With On-Line Arithmetic, numbers flow serially, one digit each clock cycle, most significant digit first. All the functions can be implemented with on-line arithmetic whereas common serial arithmetic, least significant digit first, is restricted to addition and multiplication. I described in VHDL a set of on-line operators much smaller that require less I/O pads than their parallel counterpart. To attain Exact Rounding of the Elementary Functions one has to estimate the appropriate internal precision required for each function (sine, cosine...). We detail here a method which allow reasonnably fast exact rounding of the elementary functions. The Semi-Logarithmic Number System is an hybrid notation that allows fast average computation in problems even in the presence of a high number of multiplications and divisions compared to the number of additions and subtractions.
  • Abstract (in french):

    Les machines actuelles offrent de plus en plus de fonctionnalités arithmétiques au niveau matériel. Les générations actuelles de processeurs proposent des opérateurs matériels rapides pour le calcul des divisions, des racines carrées, des sinus, des cosinus, des logarithmes... La littérature du domaine montre qu'en changeant notre façon de représenter les nombres et/ou en utilisant des algorithmes spécifiques de calcul, il est possible de réaliser des opérateurs matériels particulièrement efficaces. Le but de cette thèse est d'étudier et d'illustrer les liens profonds existants entre l'arithmétique et l'architecture des ordinateurs à travers quatre problèmes. Les Opérateurs Arithmétiques Asynchrones permettent de calculer les fonctions arithmétiques (addition, multiplication, division) avec un délai variable. En particulier, nous avons développé un additionneur asynchrone dont le temps moyen de calcul est O(sqrt(log(n))). L'Arithmétique En-Ligne permet de réaliser des architectures où les nombres circulent en série, chiffre par chiffre, les poids forts en tête. L'intérêt de cette arithmétique est de pouvoir calculer toutes les fonctions (en arithmétique série poids faibles en tête, il n'est pas possible de calculer les divisions et les maximums) et d'obtenir des opérateurs de petite taille avec un nombre d'entrées/sorties plus faible que leur équivalents parallèles. L'Arrondi Exact des Fonctions Elémentaires consiste à déterminer la précision intermédiaire permettant de toujours pouvoir arrondir ``exactement'' les résultats du calcul des fonctions élémentaires (sinus, cosinus, exponentielle...). Nous proposons dans cette thèse une méthode qui permet d'arrondi exactement les fonctions élémentaires assez rapidement. Le Système Semi-Logarithmique de Représentation des Nombres est un système permettant d'effectuer rapidement les calculs de problèmes dont le nombre de multiplications/divisions est grand devant le nombre d'additions/soustractions.
  • Keywords:

    Computer Arithmetic, Computer Architecture, Exact Rounding, Logarithmic Number System, On-Ligne Computation, Asynchronous Circuits
  • Keywords (in french):

    Arithmétique des Ordinateurs, Architecture des Ordinateurs, Arrondi Exact, Système Logarithmique, Calcul en-ligne, Circuits Asynchrones
  • Availability: Paper copy available.
  • Size: 161p
  • Format: Compressed PostScript
  • Get it

Parallélisme et Modularité des Modèles Connexionnistes.

  • By: Didier Puzenat
  • Number: PhD1997-08
  • Date: October 1997
  • Abstract:

    Connectionism solves problems by simulating neural networks. Using an artificial neural network means heavy computation and justifies the use of the most powerful parallel computers: MIMD machines with distributed memory. This thesis focuses particularly on the parallelization of an incremental neural classifier. Such a connectionist model discriminates a data set into categories, adding cells if needed. A first parallelization distributes the input space of the neural network between processors. The parallelized classifier follows exactly the sequential behavior; the higher the dimension of the input space, the higher the maximum possible speedup. Several modular parallelizations are proposed by parallelizing the learning strategy rather than the topology. Parallel and sequential behaviors are different but recognition performances are preserved. Specializing modules on categories enables to reach optimal speedups. The efficiency of this modular approach leads to the development of an asynchronous version suitable for a network of workstations. This new version makes the classifier independent of the target machine by using a virtual computer. Connectionism is also suitable to modelize and understand life within cognitive science researches. The classifier has been used to simulate a repetition priming phenomenon well known by psychologist. Further more, experiences accumulated over the classifier made it suitable to analyze the result of olfactory experimentation done with human subjects. This works validate a neuro-psychologist hypothesis about the perceptive olfactory system. The classification task by itself is a hard to learn problem and enables to test an improved version of the classifier. At least, the perspective of the modelization of human memorization process is presented, based on some incremental neural classifiers and an associative memory. This new system, highly modular, opens a wide application field.
  • Abstract (in french):

    Le connexionnisme permet de résoudre des problèmes en simulant des réseaux de neurones. La mise en oeuvre d'un réseau de neurones artificiels impose de lourds calculs et motive l'utilisation des machines les plus puissantes: les ordinateurs MIMD à mémoire distribuée. Cette thèse s'intéresse plus particulièrement à la parallélisation d'un classifieur incrémental. Ce modèle connexionniste discrimine un ensemble de données en classes, des cellules sont ajoutées en fonction des besoins. Une première parallélisation distribue l'espace d'entrée du réseau entre les processeurs. Le classifieur parallélisé suit parfaitement le comportement séquentiel. L'accélération maximale est d'autant plus grande que la dimension de l'espace d'entrée est élevée. Plusieurs parallélisations, dites modulaires, sont également proposées en parallélisant non plus le réseau mais l'apprentissage. Le comportement parallèle du modèle diffère du comportement séquentiel mais les performances en classification sont maintenues. Une spécialisation des modules permet d'atteindre une accélération optimale. Le développement d'une version asynchrone rend tout le travail réalisé indépendant de la machine cible en utilisant une machine virtuelle. Au-delà d'une utilisation en ingénierie, le connexionnisme permet de modéliser et de comprendre le vivant dans le cadre des sciences cognitives. Le classifieur est notamment mis à contribution pour simuler un phénomène d'amorçage de répétition. Par ailleurs, l'expérience accumulée sur le classifieur est mise à profit pour analyser les résultats d'experiences olfactives. Ce travail permet de valider une hypothèse faite par les neuropsychologues sur le système perceptif olfactif. La thèse s'achève sur la perspective de modéliser les processus de mémorisation humains en associant des classifieurs incrémentaux à une mémoire associative. Ce nouveau système, hautement modulaire, ouvre un champ d'application très large.
  • Keywords:

    Connectionism, Artificial Neural Networks, Parallel Computers, Incremental Classifier, Cognitive Science, Repetition Priming, Olfactory System.
  • Keywords (in french):

    Connexionnisme, Réseau de Neurones Artificiels, Parallélisme, Classifieur Incrémental, Sciences Cognitives, Amorçage de Répétition, Système Olfactif.
  • Availability: Electronic copy only.
  • Size: 108p
  • Format: Compressed PostScript
  • Get it

Heuristiques pour les communications structurées dans les réseaux d'interconnexion point-à-point.

  • By: Sandrine Vial
  • Number: PhD1997-09
  • Date: October 1997
  • Abstract:

    The aim of my work is to optimize communications which have a crucial role in the growth of networks. That is why I am interested in structured communication problems. I have considered communciation protocol that are not dependent of the topology of the network. In this context, these problems are most of time NP-complete. Therefore, I am interested in heuristics. Few papers have been written in this domain. Most of them concern the broadcasting problem. I have developped heuristics for other communication problems such as gossiping, scattering or multi-scattering. I have proposed a general technique based on maximum weighted matching in graphs. When I have applied my approach to classical topologies, I obtained optimal results in many cases. I have also validated my approach in the case of a machine which is shared by many users. The subset of processors dedicated to one user is a subset of the original topology, in our case : a grid. I have compared my general technique to the best known algorithms for that class of graphs (partial grids). My approach is in general the most efficent. With the intention of dealing with communications in larger networks, I have been interested in distributed communications. In this model, each processor has a local view of the network, it only knows its neighborhood. I am interested in computing the maximum number of steps required to perform a gossip. Computing a worst-case complexity allows to guaranty the user a quality of service ensuring that, within a certain number of steps his gossiping will be finished.
  • Abstract (in french):

    Le but de mon travail est d'optimiser les communications qui jouent un rôle crucial dans le développement des réseaux. Pour cela, je me suis plus particulièrement attachée aux communications structurées. J'ai considéré des protocoles de communications non dépendants de la topologie de la machine. Les problèmes correspondants étant souvent NP-complets, je me suis intéressée à des heuristiques. Peu de travaux ont été réalisés dans ce domaine et la plupart d'entre-eux s'attachent au problème de la diffusion uniquement. Durant ma thèse, j'ai développé des heuristiques pour d'autres formes de communications, telles que l'échange total, la distribution ou la multi-distribution. J'ai proposé une technique assez générale basée sur la notion de couplage de poids maximum dans un graphe. Lorsque j'ai appliqué mon approche à des topologies classiques j'ai obtenu des résultats optimaux dans de nombreux cas. J'ai également cherché à valider mon approche dans le cas de topologie résultant du partage d'une machine entre plusieurs utilisateurs. Le sous-ensemble de processeurs à la disposition d'un utilisateur est donc un sous-ensemble de la topologie originale, dans mon cas la grille. J'ai comparé mon approche générale aux meilleurs algorithmes connus pour cette classe de graphes (sous-grilles). Mon approche s'est révélée en général la plus performante. Enfin, dans le but d'aborder les communications dans des réseaux de plus grandes tailles, je me suis intéressée à des communications <>. Dans ce cadre, chaque processeur a une vue restreinte du réseau, il ne connaît que ses voisins. Il s'agit de calculer le nombre maximum d'étapes nécessaires, dans un tel environnement, pour effectuer un échange total. Calculer un pire cas permet d'assurer à l'utilisateur une certaine qualité de service en lui garantissant qu'en un nombre fixé d'étapes son échange total sera terminé.
  • Keywords:

    Collective Communications, Approximation Algorithms.
  • Keywords (in french):

    Communications Structurées, Algorithmes d'Approximation.
  • Availability: Paper copy available.
  • Size: 114p
  • Format: Compressed PostScript
  • Get it

Prévision de séries temporelles par techniques locales d'apprentissage.

  • By: Didier Girard
  • Number: PhD1997-10
  • Date: December 1997
  • Abstract:

    This thesis is devoted to the application of local techniques to time series prediction. So far, prediction of time series has been dealt with using classical methods. Recently, non parametric statistical algorithms, such as neural networks, have started being applied for prediction. A common point of both techniques, classical and non-classical, is their two phases approach to prediction : first, to model the time series and, then to apply the estimated model to predict future values of the series. The main advantage of this approach is to turn a simple problem estimating a function at a single point into a complex one modeling a global function. Based upon this observation, we designed a technique which allows to avoid the initial modeling phase. Our work started by demonstrating through experiments the relevance of the local approach. For this purpose, we investigated the existing local regression techniques. These techniques, very promising at the theoretical level, are rarely used in practice, because they involve setting various parameters. Recent developments by Vapnik in learning theory have provided a general framework for local regression. We have used these results to derive a practical method for time series prediction through "local estimation of functions". This method was successfully applied to prediction of a benchmark time series (water consumption). It was then applied to various time series used in Atos business. Contrary to the current research trend which tries to improve prediction performances by increasing the techniques complexity, our work demonstrates that on the contrary it can be relevant to choose simplification.
  • Abstract (in french):

    Cette thèse est consacrée à l'application des techniques locales à la prévision de séries temporelles. La prévision de séries temporelles est un problème traité depuis longtemps par les méthodes statistiques classiques. Récemment des techniques statistiques non paramétriques tels que les réseaux de neurones ont été utilisées. Toutes ces techniques, classiques ou non-classiques, envisagent une approche en deux temps : modélisation de la série temporelle, utilisation du modèle estimé pour réaliser des prévisions. L'inconvénient majeur de cette approche est de transformer un problème que l'on peut qualifier de simple, l'estimation d'une fonction en un point donné, en un problème compliqué, la modélisation d'une fonction. Partant de ce constat, nous avons mis au point une technique qui permet d'éviter la phase de modélisation de la série temporelle. Cette technique est basée sur les techniques de régression locale. Les techniques de régression locale, très alléchantes au niveau théorique, sont pour des raisons pratiques peu utilisées. En nous aidant des dernières avancées de Vapnik en matière de théorie de l'apprentissage, nous avons pu dépasser ces contraintes pratiques. Ceci nous a permis de mettre au point une méthode permettant de faire de la prévision de série temporelle par estimation locale de fonctions. Cette méthode a été appliquée avec succès sur une série temporelle étalon. Elle a ensuite été appliquée à des séries temporelles de la société Atos. Contrairement à la mouvance actuelle qui cherche à améliorer les performances des outils de prévisions par la complexification des techniques utilisées, ce travail permet d'affirmer que cette voie n'est pas toujours la bonne et qu'il peut, au contraire, être pertinent de choisir la simplification.
  • Keywords:

    Neural Networks, Prediction, Learning Theory, Local Estimation.
  • Keywords (in french):

    Réseaux de Neurones, Prévision, Théorie de l'Apprentissage, Estimation Locale.
  • Availability: Paper copy available.
  • Size: 160p
  • Format: Compressed PostScript
  • Get it

Contributions aux techniques d'optimisation en compilation de programmes parallèles.

  • By: Pierre-Yves Calland
  • Number: PhD1997-11
  • Date: December 1997
  • Abstract:

    In most scientific programs for numerical computations, a large part of the execution time is spent in the computation of a little number of statements which are enclosed by a set of iterative loops. The parallelization of such algorithms implies a communication overhead due to communications between processors. The efficiency of a compiler targeted to parallel machines depends on the parallelism detection techniques and mapping strategies that are implemented. It is important to take resource constraints into account. My work fits in this framework and my thesis focuses on tiling, scheduling and mapping (especially for loop nests). We do take resource constraints of the target machine into account. My main contributions to this domain may be summarized as follows: the determination of the best tiling in the case of unlimited resources; the determination of the best tiling and mapping in the case of limited resources; the methodology to find the best strategy of array duplication to increase the parallelism of a program. To deeply understand parallelization problem, it is essential to develop software for automatic or semi-automatic mapping and scheduling. My contribution is also practical: indeed, I took part to the development of a semi-automatic parallelizer Partita from Simulog.
  • Abstract (in french):

    Dans la plupart des programmes scientifiques de calcul numérique, une grande fraction du temps d'exécution total est passé dans le calcul d'un petit nombre d'instructions internes à un ensemble imbriqué de boucles d'itération. Lors de la parallélisation de ces algorithmes, on ajoute un surcoût dû aux communications inter processeurs. La qualité d'un compilateur pour machine parallèle dépend de la technique de parallélisation utilisée ainsi que de la stratégie suivie pour le placement des données. Il est important de considérer ces problèmes en prenant en considération des contraintes matérielles. L'objet de ma thèse a été plus particulièrement de déterminer comment partitionner, ordonnancer et allouer les calculs et les données pour minimiser le temps d'exécution d'un programme parallèle (plus spécialement d'un nid de boucles) en prenant en considération certaines caractéristiques de la machine cible. Cette étude a fait l'objet de plusieurs travaux~: recherche du meilleur partitionnement des calculs pour une machine à ressources illimitées, recherche du meilleur partitionnement et de la meilleure allocation des calculs sur un nombre fini de processeurs, calcul du meilleur ordonnancement des tâches allouées sur un nombre fini de processeurs, recherche de la meilleure stratégie de duplication de tableaux dans le but de faire apparaître plus de parallélisme. Le développement de logiciels de parallélisation et de placement automatique ou semi-auto\-ma\-ti\-que est un support essentiel pour une bonne compréhension générale de la parallélisation de programme. J'ai consacré une partie de ma thèse au développement d'un logiciel de parallélisation semi-auto\-ma\-ti\-que~: Partita de la société Simulog.
  • Keywords:

    Automatic Parallelization, Mapping, Scheduling, Tiling, Dependences, Resource Constraints, High Performance Fortran.
  • Keywords (in french):

    Parallélisation Automatique, Allocation, Ordonnancement, Partitionnement, Dépendances, Contraintes de Ressources, High Performance Fortran.
  • Availability: Paper copy available.
  • Size: 122p
  • Format: Compressed PostScript
  • Get it

Détection de parallélisme dans les boucles imbriquées.

  • By: Frederic Vivien
  • Number: PhD1997-12
  • Date: December 1997
  • Abstract:

    Many computer users would like to be able to run on parallel computers their ``sequential'' programs (written to be run on classical computers). Thus, it became necessary to know how to transform, to ``parallelize'', the sequential programs into programs that can be run on parallel computers. This parallelization must be automatic as it is needed by plain users. Before applying any transformation to the original program, one must detect and quantify the parallelism it implicitly contains, which requires to know the program dependences. Later on, it will be necessary to reorder the computations to explicit the parallelism found. The aim of this thesis is to detect the implicit parallelism, and to search for schedules that explicit it, for particular program structures: set of nested loops. Our main goal was to understand the existing technics for parallelism detection, and to find their strong and weak points. On one hand, we have studied the main existing algorithms. On the other hand, we started from the theoretical model furnished by the systems of uniform recurrence equations and we proposed an optimal algorithm to parallelize the polyhedral reduced dependence graphs, a representation of dependences which generalizes the two classical approximation modes. We compared this new algorithm with the classical ones and we obtained a classification of the main algorithms. The problem of parallelism detection and exhibition is one of the many phases of an automatic parallelizer. Therefore, we have looked at the interactions between the problems of mapping and scheduling, and at the interactions between the problems of parallelism detection and of ``false'' dependences removal.
  • Abstract (in french):

    Nombre d'utilisateurs de l'informatique aimeraient pouvoir exécuter sur des ordinateurs parallèles leurs programmes « séquentiels » (écrits pour être exécutés sur des ordinateurs classiques). Il est donc devenu nécessaire de savoir « paralléliser » les programmes séquentiels en programmes exécutables sur machines parallèles. Cette parallélisation doit être automatique puisqu'elle s'adresse le plus souvent à de simples utilisateurs. Avant d'initier toute transformation du programme originel, il faut détecter et quantifier le parallélisme qu'il contient implicitement, ce qui requiert la connaissance des dépendances existant entre les différents calculs. Ultérieurement, il sera nécessaire de réordonner les calculs en explicitant le parallélisme découvert. Cette thèse a pour objet la détection automatique du parallélisme implicite et la recherche d'ordonnancements l'explicitant pour des structures de programmes particulières : les ensembles de boucles imbriquées. Nos travaux ont eu principalement pour but la compréhension des techniques existantes de détection de parallélisme, de leur points forts et de leurs limitations. D'un côté, nous avons étudié les principaux algorithmes préexistant à ces travaux. De l'autre, nous sommes partis du modèle théorique fourni par les systèmes d'équations récurrentes uniformes pour proposer un algorithme optimal de parallélisation des graphes de dépendance réduits polyédriques, représentation approchée des dépendances qui généralise les deux modes classiques d'approximation. Nous avons comparé ce nouvel algorithme aux algorithmes classiques et obtenu une classification des principaux algorithmes. Le problème de la détection du parallélisme et de son expression n'étant qu'une des multiples composantes de la parallélisation automatique, nous nous sommes intéressés aux interactions entre les problèmes de placement et d'ordonnancement, et entre les problèmes de détection de parallélisme et d'élimination de « fausses » dépendances.
  • Keywords:

    Automatic Parallelization, Nested Loops, Dependences, Scheduling, Mapping.
  • Keywords (in french):

    Parallélisation Automatique, Boucles Imbriquées, Dépendances, Ordonnancement, Placement.
  • Availability: Paper copy available.
  • Size: 164p
  • Format: Compressed PostScript
  • Get it

Optimisation du routage à déflexion pour les réseaux de télécommunications métropolitains.

  • By: Thierry Chich
  • Number: PhD1997-13
  • Date: December 1997
  • Abstract:

    Metropolitan Area Networks are designed in order to deserve the different ressources available in a town. Optical devices, which can support troughput of about 100~Terabit/s, seem interesting for building such a network. In this thesis, we have studied deflection routing scheme. This scheme is particulary adapted to all-optical networks. We have investigated to the synchronization requirements in deflection routing networks. Indeed, most of the time, deflection routing has been studied assuming a synchronization of the network. However, synchronization of the network needs to force packets of fixed size. Moreover the synchronization hardware for all-optical networks is expensive and induces important power losses. Furthermore, adding such hardware decreases the robustness of the network. We have shown that the global behavior of the network does not change if the network is not synchronized: congestions do not occur as it was previously claimed. Furthermore, we have shown that if, indeed, perfomances are lower in the asynchronous networks than in synchronous networks, it is essentially because of the lack of a local optimisation of the preferences of the packets. We have also proposed two different methods in order to optimize asynchronous deflection routing. The former is an adaptative method which is designed to avoid overloaded areas in the network. This method has been tested and has been shown to be efficient for asynchronous deflection routing. The latter method allows to perform local optimization of the preferences of the packets in asynchronous deflection routing. Our results show that synchronization mechanisms are not required for deflection networks.
  • Abstract (in french):

    Dans l'avenir, les réseaux métropolitains devront relier différentes ressources informatiques à l'échelle d'une ville. Dans ce cadre, la technologie optique, qui permet l'obtention d'une bande passante de l'ordre de la dizaine de térabits/s, est prometteuse. Cette thèse a pour objectif de proposer une étude d'un routage particulièrement adapté aux réseaux tout-optiques , le routage par déflexion. Nous nous sommes particulièrement intéressé à la question de la synchronisation dans les réseaux à déflexion. En effet, la très grande majorité des études faites sur le routage par déflexion suppose une synchronisation du réseau. Or, celle-ci impose que les paquets soient de tailles fixes. De plus, les synchronisateurs dans les réseaux tout-optiques sont coûteux, dissipateur de puissance, et abaisse la fiabilité du réseau. Nous avons montré que désynchroniser le réseau ne changeait pas fondamentalement son comportement, contrairement à ce qui est souvent affirmé, mais seulement son niveau de performance. Qui plus est, nous avons montré que la baisse des performances provenait moins de l'asynchronisme en tant que tel que de l'absence d'optimisation locale sur les préférences des paquets. Une telle optimisation est tout à fait naturelle dans un réseau synchrone. Nous basant sur cette première étude, nous avons proposé deux méthodes de natures très différentes pour optimiser le routage par déflexion asynchrone. La première consiste en un algorithme de routage adaptatif qui permet d'éviter les zones surchargées du réseau lorsque la topologie est une grille ou un tore. Cet algorithme a été testé sous diverses conditions, et s'est montré efficace pour la déflexion asynchrone. La deuxième méthode est un dispositif permettant d'effectuer une optimisation locale sur les préférences des paquets en mode asynchrone. Ce dispositif donne d'excellents résultats qui semblent être de nature à remettre radicalement en question la nécessité de synchroniser les réseaux à déflexion.
  • Keywords:

    Deflection Routing, All-Optical Networks, Adaptative Routing, Neural Networks, Asynchronism.
  • Keywords (in french):

    Routage à Déflexion, Réseaux Tout-Optiques, Routage Adaptatif, Réseaux Neuronaux, Asynchronisme.
  • Availability: Paper copy available.
  • Size: 115p
  • Format: Compressed PostScript
  • Get it

Synthèse d'Architectures Intégrées Utilisant des Arithmétiques Redondantes.

  • By: Olivier Peyran
  • Number: PhD1997-14
  • Date: December 1997
  • Abstract:

    .
  • Abstract (in french):

    .
  • Keywords:

    .
  • Keywords (in french):

    .
  • Availability: Paper copy available.
  • Size: 151p
  • Format: Compressed PostScript