Calcul parallèle et en-ligne de fonctions arithmétiques.

  • By: Sylvanus Kla
  • Number: PhD1993-01
  • Date: January 1, 1993
  • Availability: Not available by FTP. Out of print.

Evaluation de fonctions dans les systèmes redondants d'écriture de nombres.

  • By: Jean-Claude Bajard
  • Number: PhD1993-02
  • Date: January 1, 1993
  • Availability: Not available by FTP.

Contribution a l'etude semantique des langages a parallelisme de donnees; application a la compilation.

  • By: Jean-Luc Levaire
  • Number: PhD1993-03
  • Date: May 18, 1993
  • Abstract:

    Nous etudions la semantique operationnelle des langages parallelisme de donnees, et plus particulierement les structures de controle parallele. Nous definissons un petit langage pour exprimer ces structures, et en proposons deux semantiques operationnelles. Comme ces semantiques peuvent etre vues comme des techniques de compilation, nous pouvons ainsi valider les methodes employees dans les compilateurs existants. Nous etudions particulierement ici les compilateurs C*, MPL et POMPC. Une deuxieme approche pour prouver la correction des techniques de compilation est l'equivalence de programmes. Nous l'appliquons au cas particulier de l'optimisation du switch propose par le compilateur POMPC. Enfin, en implementant ce petit langage sous l'atelier semantique Centaur, nous montrons qu'il possible de construire des environnements de programmation pour le parallelisme de donnees.
  • Keywords:

    C*, Centaur, Compilation, Data Parallelisme, Langages, MPL, POMPC, Semantique Operationnelle, Structures de Controle, Validation.
  • Availability: Electronic copy only.
  • Format: Compressed PostScript
  • Get it

Algorithmes d'amincissement d'images sur machines parallèles.

  • By: Stephane Ubeda
  • Number: PhD1993-04
  • Date: February 5, 1993
  • Availability: Not available by FTP.

De la micro-optimisation a l'algorithmique parallele.

  • By: Henri-Pierre Charles
  • Number: PhD1993-05
  • Date: May 18, 1993
  • Abstract:

    Cette these traite d'optimisation et de parallelisation de programmes. Pour l'optimisation, les microprocesseurs cible sont de type superscalaire (comme le i860). Pour la parallelisation, la classe de machines visee correspond aux calculateurs a memoire distribuee. Les deux approches convergent pour les etudes algorithmiques menees autour de l'hypercube iPSC860 d'INTEL. Les techniques de pipeline sont au coeur des deux approches. La premiere partie de la these comprend trois chapitres. Le premier est consacre a une description des processeurs superscalaires comme le i860 (caracteristiques architecturales, logiciel de base, comparaison de compilateurs). Le deuxieme chapitre offre une revue synthetique des quelques techniques d'optimisation de code (la plus celebre etant l'algorithme d'Aiken/Nikolau pour les boucles). Le troisieme chapitre presente une technique de depliage de boucles greffee sur le compilateur Gcc comme une phase supplementaire d'optimisation, avec analyse des resultats obtenus sur les boucles de Livermore. La deuxieme partie de la these traite d'algorithmique parallele. La conception d'une interface de programmation permettant la portabilite, tout en preservant l'efficacite, de la librairie parallele de traitement d'images medicales volumiques sur machines a memoire distribuee en cours de developpement au LIP, fait l'objet du premier chapitre. L'interface, appelee PPCM, est de niveau suffisamment eleve pour permettre au programmeur de s'abstraire des contraintes specifiques de chaque machine, mais reste suffisamment pointue quant aux primitives de communication et de redistribution dynamique inclues, pour garantir la bonne efficacite des parallelisations obtenues. Le deuxieme chapitre est consacre a la parallelisation, utilisant PPCM, d'un algorithme de reconstruction d'images 3D. Plusieurs implementations de cet algorithme, extrêmement gourmand en temps de calcul, sont analysees et comparees sur diverses machines. Le troisieme chapitre traite d'un probleme d'enchaînement de calculs reguliers sur hypercube. Le probleme pose a l'origine etait de calculer une suite de FFT en temps reel. L'approche maître/esclave classique est comparee a plusieurs techniques algorithmiques specifiques de distribution/collection sur hypercube. Enfin, le dernier chapitre est l'occasion d'une convergence entre techniques d'optimisation et techniques de parallelisation, puisqu'il s'agit, a la demande des partenaires du contrat europeen NANA2, de montrer que les machines hypercube type Intel IPSC860 peuvent rivaliser avec des machines specialisees en matiere de traitement d'images. L'algorithme choisi est celui du tampon de profondeur (ou Z-buffer).
  • Keywords:

    Optimisation de Programmes, Parallelisation de Programmes, Microprocesseurs Super-Scalaires, Depliage de Boucles, Imagerie Medicale Volumique, Calculateurs a Memoire Distribuee, Reconstruction 3D, Tampon de Profondeur, Distribution/collection sur Hypercube.
  • Availability: Electronic copy only.
  • Format: Compressed PostScript
  • Get it

Construction modulaire d'automates cellulaires.

  • By: Bruno Martin
  • Number: PhD1993-06
  • Date: February 23, 1993
  • Availability: Not available by FTP. Out of print.

Techniques de parallelisation automatique de nids de boucles.

  • By: Alain Darte
  • Number: PhD1993-07
  • Date: April 1993
  • Abstract:

    Dans la plupart des programmes scientifiques de calcul numerique, une grande fraction du temps d'execution total est passee dans le calcul d'un petit nombre d'instructions internes a des nids de boucles (c'est-a-dire des boucles imbriquees). La qualite d'un compilateur pour machines paralleles dedie a de tels programmes passe par une parfaite comprehension du parallelisme implicite figurant dans les nids de boucles. L'objet de cette these est de montrer comment on peut utiliser la structure reguliere et repetitive des boucles pour developper des techniques de parallelisation automatique. Dans un premier temps, une description approfondie de la repartition des calculs dans les reseaux systoliques est presentee permettant de mettre en evidence l'importance de la regularite issue de l'emploi de fonction d'ordonnancement et d'allocation lineaires. Puis, une etude exhaustive des fonctions d'ordonnancement de graphes cycliques est proposee, offrant une classification des differentes classes d'ordonnancements affines et des algorithmes de recherche d'ordonnancements optimaux. Enfin, ces resultats sont appliques premierement pour une reecriture de boucles permettant l'extraction de boucles explicitement paralleles et deuxiemement pour une generation de code de type SPMD pour des architectures de type grilles distribuees.
  • Keywords:

    Systolic Arrays, Synthesis Methodologies, Automatic Parallelization, Nested Loops, Linear Programming.
  • Availability: Electronic copy only.
  • Size: 129p
  • Comment: This report is written in French.
  • Format: Compressed PostScript
  • Get it

Puissance de calcul des reseaux de neurones artificiels.

  • By: Pascal Koiran
  • Number: PhD1993-08
  • Date: June 17, 1993
  • Abstract:

    Depuis quelques annees on s'est beaucoup interesse a la resolution de problemes d'<> avec des reseaux de neurones artificiels (par exemple en reconnaissance de formes, robotique, prediction de series temporelles, optimisation...). La plupart de ces travaux sont de nature empirique, et ne comportent que peu ou pas du tout d'analyse mathematique rigoureuse. Cette these se situe dans une perspective tout-a-fait differente : il s'agit d'etudier les relations entre les reseaux de neurones et les modeles de calculs classiques ou moins classiques de l'informatique theorique (automates finis, machines de Turing, circuits booleens, machines de Turing reelles de Blum, Shub et Smale). Les principaux resultats sont les suivants : - Simulation d'une machine de Turing universelle par des reseaux recurrents. - Etude generale de la puissance de calcul des systemes dynamiques definis par des iterations de fonctions, notamment en petites dimensions. - Etude de modeles de calculs sur les nombres reels, avec application aux reseaux recurrents et acycliques. On montre que la classe des fonctions (discretes) calculables en temps polynomial est P/poly.
  • Keywords:

    Neural Networks, Complexity, Models of Computation, Computations Over the Real Numbers.
  • Availability: Electronic copy only.
  • Size: 81p
  • Format: Compressed PostScript
  • Get it

Parallel algorithms and architectures based on digit-serial arithmetic computation.

  • By: Hong-Jin Yeh
  • Number: PhD1993-09
  • Date: July 22, 1993
  • Abstract:

    In scientific computing, the parallelization of numerical algorithms is closely related to its implementation to parallel architectures. The discussion begins with a computational model, called "on-line arithmetic", in which all digits of the result can be generated digit-serially, starting from the most significant digits. This model enables us to combine strength of "parallel processing" with strength of "digit-level pipelining". The on-line operators for basic floating-point arithmetic operations are investigated for their efficient implementation. And then, the research is focused on two main themes: the "application-specified architecture design" from arithmetic operators, and in the opposite direction, the "scheduling of arithmetic expressions" over a network of on-line operators. The former is explored by a new approche for evaluating polynomials and inverses of polynomials, varying the transmission of digits either in serial or in parallel. For the latter, a heuristic method is proposed to take into account the characteristics of on-line arithmetic.
  • Keywords:

    Fine Grain Parallelisme, On-line Arithmetic, Evaluation of Polynomials and Inverses of Polynomials, Pipeline, Parallel Processing, Scheduling of Arithmetic Expressions, Reconfigurable Network.
  • Availability: Electronic copy only.
  • Size: 121p
  • Format: Compressed PostScript
  • Get it

Systemes de representation des nombres et arithmetiques sur machines paralleles.

  • By: Christophe Mazenc
  • Number: PhD1993-10
  • Date: December 17, 1993
  • Availability: Paper copy available. Not available by FTP.

Contribution a l'algorithme parallele des structures de donnees et des structures discretes : machine dictionnaire et algorithmes pour les graphes.

  • By: Michel Gastaldo
  • Number: PhD1993-11
  • Date: December 17, 1993
  • Availability: Paper copy available. Not available by FTP.

Mise en oeuvre et application de la reconfiguration quasi-dynamique sur SuperNode.

  • By: Christophe Bonello
  • Number: PhD1993-12
  • Date: December 7, 1993
  • Availability: Not available by FTP. Out of print.

Evaluation du modele de programmation parallele a phases reconfigurables : cas du gradient conjugue et de l'operation de Sommes Partielles.

  • By: Luis Trejo
  • Number: PhD1993-13
  • Date: December 17, 1993
  • Abstract:

    The synchronous phase programming model proposed by Snyder and some time later reconsidered by Adamo, is based on the idea that most useful algorithms can be be decomposed into series of elementary data movements. As a consequence, these algorithms can be implemented as series of phases, so that each phase can be efficiently executed on the processor graph best suited to the need of the performed data movement. We present in this work some experimental results using this model under a high level parallel programming environment called C\_NET. First, we present an implementation of the conjugate gradient method as a phase reconfigurable algorithm; next we present some algorithms to solve the parallel prefix problem and we give some of its applications. Finally, we give some directions towards an asynchronous phase programming model. In that effect, we consider the OCP model (Optical Communication Parallel): the parallel prefix and multiprefix operations are presented, as well as an implementation of a radix sort, which illustrates the use of the parallel primitives. These algorithms are shown to be efficiently implemented on such a model.
  • Availability: Electronic copy only.
  • Size: 163p
  • Format: Compressed PostScript
  • Get it