Partitioning Automata, Cellular Automata, Simulation and Reversibility.

  • By: Jerome-Olivier Durand-Lose
  • Number: RR1995-01
  • Date: January, 1995
  • Abstract:

    Partitioning automata (PA) are defined. Various properties are proved and universality is showed. This class of automata is linked to Turing machines and cellular automata (CA).A simple partitioning automaton, reversible and universal is described. It is shown that there are reversible PA and CA that are able to simulate any reversible PA or CA for both finite and infinite configurations.
  • Abstract (in french):

    La classe des automates à partitions (PA) est tout d'abord définie. Divers propriétés les concernant sont démontrées. L'universalité des PA est prouvée en montrant qu'ils peuvent simuler n'importe quelle machine de Turing. Cette classe est ensuite comparée à celle des automates cellulaires (CA). Un exemple simple de PA universel et réversible est décrit. Dans la partie 7, il est montré qu'il existe des PA et des CA reversibles capables de simuler n'importe quel PA ou CA reversible pour des configurations finies ou non.
  • Keywords:

    Partitioning Automata, Universality, Reversibility, Simulation and Cellular Automata.
  • Keywords (in french):

    Automates à partitions, universalité, simulation et automates cellulaires.
  • Availability: Electronic copy only.
  • Citation: A short version of this paper was published in proceedings latin'95, LNCS 911, Springer-Verlag, pp 230-244, 1995.
  • Size: 2+23p
  • Format: Compressed PostScript
  • Get it

Worst Case Bounds for Shortest Path Interval Routing.

  • By: Cyril Gavoille , Eric Guevremont
  • Number: RR1995-02
  • Date: April 5, 1995
  • Abstract:

    Consider shortest path interval routing, a popular memory-balanced method for solving the routing problem on arbitrary networks. Given a network G, let IRS(G) denote the maximum number of intervals necessary to encode groups of destinations on an edge, minimized over all shortest path interval routing schemes on G. In this paper, we establish tight worst case bounds on IRS(G). More precisely for any n, we construct a network G of n nodes with IRS(G) in Theta(n), thereby improving on the best known lower bound of Omega(n / log n). We also establish a worst case bound on bounded degree networks: for any Delta >= 3 and any n, we construct a network G' of n nodes and maximum degree Delta with IRS(G') in Omega(n/(log n)^2).
  • Abstract (in french):

    Nous considérons le problème du routage par intervalles de plus courts chemins, une méthode populaire et distribuée résolvant le problème du routage sur les réseaux arbritraires. Etant donné un réseau G, nous posons Irs (G) le nombre maximum d'intervalles nécessaires pour coder les groupes de destinations sur une arête, minimisé sur tous les routages par intervalles de plus courts chemins sur G. Dans cet article, nous établissons des bornes très étroite sur le pire cas pour Irs (G). Plus précisément, pour tout n, nous construisons un réseau G de n noeuds avec Irs(n) in Theta(n), améliorant par conséquent, la meilleure borne inférieure connue Omega(n/logn). Nous établissons également un pire cas pour les réseaux de degré borné : pour tout Delta >= 3 et tout n, nous construisons un réseau G\Delta de n noeuds et de degré maximum Delta avec Irs-G\Delta) in Omega(n/(log n)2).
  • Keywords:

    Communication on Parallel and Distributed Networks, Compact Routing Tables, Interval Routing, Shortest Path Routing.
  • Keywords (in french):

    Communication sur réseaux parallèles et distribués, tables de routages compactes, routage par intervalles, routages de plus courts chemins.
  • Availability: Paper copy available.
  • Citation: Not published yet.
  • Size: 2+23p
  • Format: Compressed PostScript
  • Get it

Modular Range Reduction: A New Algorithm for Fast and Accurate Computation of the Elementary Functions.

  • By: Marc Daumas , Christophe Mazenc , Xavier Merrheim , Jean-Michel Muller
  • Number: RR1995-03
  • Date: February 7, 1995
  • Abstract:

    A New range reduction algorithm, called Modular Range Reduction (MRR), briefly introduced by the authors in a previous publication, is deeply analyzed. It is used to reduce the arguments to exponential and trigonometric function algorithms to be within the small range for which the algorithms are valid. MRR reduces the arguments quickly and accurately. A fast hardwired implementation of MRR operates in time O(log n), where n is the number of bits of the binary input value. For example, with MRR it becomes possible to compute the sine and cosine of a very large number accurately. We propose two possible architectures implementing this algorithm.
  • Abstract (in french):

    Un nouvel algorithme de réduction d'argument, appelé réduction d'argument modulaire (MRR), présenté brièvement par les auteurs du présent rapport dans une publication antérieure, est analysé en détail. Il permet de ramener les arguments des fonctions trigonométriques et de l'exponentielle aux petits domaines dans lesquels les algorithmes usuels sont valides. MRR effectue cette opération rapidement et avec précision. Une implantation matérielle rapide de MRR effectue la réduction d'argument en temps O(log(n)), où n est le nombre de bits de la variable à réduire. Par exemple, en employant MRR, il devient possible de calculer le sinus ou le cosinus d'un très grand nombre très précisément. On propose deux architectures implantant cet algorithme.
  • Keywords:

    Computer Arithmetic, Elementary Functions, Range Reduction.
  • Keywords (in french):

    Arithmétique des ordinateurs, fonctions élémentaires, réduction d'argument.
  • Availability: Electronic copy only.
  • Citation: Published in JUCS Vol 1 numero 3, 1995, Springer Verlag.
  • Size: 2+17p
  • Format: Compressed PostScript
  • Get it

Semi-Logarithmic Number Systems.

  • By: Jean-Michel Muller , Alexandre Scherbyna , Arnaud Tisserand
  • Number: RR1995-04
  • Date: February 15, 1995
  • Abstract:

    We present a new class of number systems, called Semi-Logarithmic Number systems, that constitute a family of various compromises between floating-point and logarithmic number systems. We propose arithmetic algorithms for the Semi-Logarithmic Number Systems, and we compare these number systems to the classical floating-point or logarithmic number systems.
  • Abstract (in french):

    Nous présentons une nouvelle famille de systèmes de représentation des nombres réels en machine. Ces systèmes, appelés systèmes semi-logarithmiques, constituent une classe de compromis entre le système virgule flottante et le système logarithmique. Nous proposons des algorithmes permettant d'effectuer les opérations arithmétiques sur les systèmes semi-logarithmiques, et nous comparons ces systèmes aux systèmes usuels de représentation des réels.
  • Keywords:

    Number Systems, Floating-Point Arithmetic, Logarithmic Number Systems.
  • Keywords (in french):

    Arithmétique des ordinateurs, systèmes de numération, virgule flottante, systèmes logarithmiques.
  • Availability: Electronic copy only.
  • Citation: To appear in 12th IEEE Symposium on computer arithmetic Bath, Angleterre, 1995, IEEE Computer Society Press. Extending version published in IEEE Transactions on Computers, Vol. 47 No 2, February 1998.
  • Size: 2+12p
  • Format: Compressed PostScript
  • Get it

Memory Requirement for Universal Routing Schemes.

  • By: Pierre Fraigniaud , Cyril Gavoille
  • Number: RR1995-05
  • Date: March 13, 1995
  • Abstract:

    In this paper, we deal with the compact routing problem, that is implementing routing schemes that use a minimum memory size on each router. In [20], Peleg and Upfal showed that there is no hope to do that with less than a total Omega(n^{1+1/(2s+4)}) memory bits for any stretch factor s >= 1. We improve this bound for stretch factors s < 2 by proving that any near-shortest path routing scheme uses a total of Omega(n^2) memory bits.
  • Abstract (in french):

    Dans cet article, nous abordons le problème du routage compact, qui est l'implémentation des stratégies de routages utilisant une taille mémoire minimum pour chaque routeur. Dans [20], Peleg et Upfal on montré qu'il n'y a aucun espoir de la réaliser avec moins de Omega(n^{1+1/(2s+4)}) bits mémoire au total pour tout facteur d'étirement s >= 1. Nous améliorons cette borne pour les facteurs d'étirement s < 2 en prouvant que toute stratégie de routage des presques plus courts chemins utilise un total de Omega(n^2) bits mémoire.
  • Keywords:

    Communication on Parallel and Distributed Networks, Compact Routing Tables, Near-Shortest Path Routing.
  • Keywords (in french):

    Communication sur réseaux parallèles et distribués, tables de routages compactes, routages de plus courts chemins.
  • Availability: Paper copy available.
  • Citation: To appear in proceedings of 14th ACM PODC, 20-23 August 1995, Ottawa.
  • Size: 2+13p
  • Format: Compressed PostScript
  • Get it

Algorithmes de division pour microprocesseurs: illustration a l'aide du ``Bug'' du Pentium.

  • By: Jean-Michel Muller
  • Number: RR1995-06
  • Date: March 14, 1995
  • Abstract:

    This paper briefly presents the division algorithms that are the most frequently inplemented on microprocessors, especially the algorithm used by Intel's Pentium. The FDIV flaw of the Pentium is analysed, in order to help the users to estimate, depending on their applications, what are the potential risks.
  • Abstract (in french):

    Dans cet article, on présente rapidement les algorithmes de division les plus employés sur les microprocesseurs actuels, et tout particulièrement l'algorithme utilisé par le Pentium d'Intel. On analyse en détail le problème qui a causé l'imprécision de la division du Pentium (qui a fait couler il y a quelques mois beaucoup de ``salive électronique''), afin de permettre à l'utilisateur potentiel d'estimer, en fonction de ses applications, quels sont les problèmes qu'il peut encourir.
  • Keywords:

    Division, Floating-Point Arithmetic.
  • Keywords (in french):

    Division, arithmétique virgule flottante.
  • Availability: Paper copy available.
  • Citation: Published in Technique et Science Informatiques (TSI), Vol. 14 No 8. October 1995.
  • Size: 2+17p
  • Format: Compressed PostScript
  • Get it

Codifying guarded definitions with recursive schemes.

  • By: Eduardo Gimenez
  • Number: RR1995-07
  • Date: February 1995
  • Abstract:

    We formalize an extension of the Calculus of Constructions with inductive and coinductive types which allows a more direct description of recursive definitions. The approach we follow is close to the one proposed by Thierry Coquand for Martin-L\"of's type theory in his paper ``Infinite Objects in Type Theory''. Recursive objects can be defined by fixed-point definitions as in functional programming languages, and a syntactical checking of these definitions avoids the introduction of non-normalizable terms. We show that the conditions for accepting a recursive definition proposed in the mentioned paper are not sufficient for the Calculus of Constructions, and we modify them. As a way of justifying our conditions, we develop a general method to codify a fix point definition satisfying them using well-known recursive schemes, like primitive recursion and co-recursion. We also propose different reduction rules from the ones used in [5] in order to obtain a decidable conversion relation for the system.
  • Abstract (in french):

    On formalise une extension du calcul des constructions avec des types inductifs et co-inductifs qui permet une description plus directe des définitions récursives. L'approximation suivie est proche de celle proposée pour la théorie des types de Marti-Lof dans son article ``Infinite Objects in Type Theory''. Les objets récursifs peuvent être définis par points fixes comme dans les langages de programmation fonctionnels, une vérification syntaxique de ces définitions évitant l'introduction des termes qui non normalisables. On montre que la condition proposé dans l'article mentionné n'est pas suffisante pour le calcul des constructions, et on propose une modification de celle-ci. On développe une méthode pour coder des définitions par point fixe satisfaisant la condition syntaxique en termes de principes de récursion bien connus, comme la récursion primitive et la co-récursion. On propose aussi des règles de réduction différentes de celles utilisées dans [5] pour obtenir la décidabilité du typage.
  • Keywords:

    Thype Theory, Co-Inductive Types, Co-Recursion.
  • Keywords (in french):

    Théorie des types, types co-inductifs, co-récursion.
  • Availability: Paper copy available.
  • Citation: A shorter version of this paper will be published in the Proceedings of the 1994 Meeting of the BRA project Types for Proofs and Programs (LNCS Series).
  • Size: 2+20p
  • Format: Compressed PostScript
  • Get it

Proofs by annotations for a simple data-parallel language.

  • By: Luc Bouge , David Cachera
  • Number: RR1995-08
  • Date: March 1995
  • Abstract:

    We present a proof outline generation system for a simple data-parallel kernel language called L. We show that proof outlines are equivalent to the sound and complete Hoare logic defined for L in previous papers. Proof outlines for L are very similar to those for usual scalar-like languages. In particular, they can be mechanically generated backwards from the final post-assertion of the program. They appear thus as a valuable basis to implement a validation assistance tool for data-parallel programming.
  • Abstract (in french):

    Nous présentons un système pour la génération de schémas de preuve par annotations proof outlines pour un petit noyau de langage à parallélisme de données appelé L. Nous montrons que les schémas de preuve par annotations sont équivalents à la logique de Hoare pour le langage L définie dans les articles précédents. La manipulation des annotations des programmes L est très semblable à celle des langages scalaires habituels de type Pascal. En particulier, les annotations peuvent être générées automatiquement à partir de la post-condition du programme. Cette méthode constitue donc une base formelle intéressante pour l'implémentation d'outils d'aide à la programmation data-parallèle.
  • Keywords:

    Concurrent Programming, Specifying and Verifying and Reasoning about Programs, Semantics of Programming Languages, Data-Parallel Languages, Proof System, Hoare Logic, Weakest Preconditions.
  • Keywords (in french):

    Programmation parallèle, spécification et validation de programmes, sémantique des langages de programmation, langages data-parallèles, système de preuve, logique de hoare, plus faibles préconditions.
  • Availability: Paper copy available.
  • Citation: Not published yet.
  • Size: 2+19p
  • Format: Compressed PostScript
  • Get it

A Characterization of One-to-One Modular Mappings.

  • By: Alain Darte , Michele Dion , Yves Robert
  • Number: RR1995-09
  • Date: April 1995
  • Abstract:

    In this paper, we deal with modular mappings as introduced by Lee and Fortes, and we build upon their results. Our main contribution is a characterization of one-to-one modular mappings that is valid even when the source domain and the target domain of the transformation have the same size but not the same shape. This characterization is constructive, and a procedure to test the injectivity of a given transformation is presented.
  • Abstract (in french):

    Nous étudions dans ce rapport les placements modulaires tels qu'ils ont été introduits par Lee et Fortes, et nous développons les résultats qu'ils ont obtenus. Notre apport principal consiste en une caractérisation des placements modulaires bijectifs qui reste valide même lorsque les domaines source et cible de la transformation contiennent le même nombre de points mais n'ont pas la même forme. La caractérisation est constructive et nous présentons une procédure qui permet de tester l'injectivité d'une transformation.
  • Keywords:

    Automatic Parallelization, Loop Nests, Time-Space Transformation, Modular Mapping, Injectivity, Characterization.
  • Keywords (in french):

    Parallélisation automatique, nids de boucles, transformation temps-espace, placement modulaire, injectivité, caractérisation.
  • Availability: Electronic copy only.
  • Citation: Not published yet.
  • Size: 2+13p
  • Format: Compressed PostScript
  • Get it

Priming an artificial neural classifier.

  • By: Didier Puzenat
  • Number: RR1995-10
  • Date: April, 1995
  • Abstract:

    Repetition priming capacity enables biological systems to manage easily with recently met situations. Priming an artificial neural network is of great interest in some modeling tasks. The network is an incremental neural classifier. This system creates units when it is not able to recognize a pattern correctly. Repetition priming is introduce through a priming function, by reinforcing the recognition of recently seen categories. Characteristics of this function are discussed in order to find the more suitable shape. Experiments are performed on handwritten recognition application. Methods described enable to detect easily priming with low computation (computation of a simple linear regression). More computation enables to measure the phenomenon (difference between the slope of the regression lines, with and without priming).
  • Abstract (in french):

    L'amorçage de répétition permet aux systèmes biologiques de réagir plus facilement face à une situation déjà rencontrée. Amorcer un réseau de neurones artificiels est particulièrement interessant pour des travaux de modélisation. Le réseau est un classifieur neuronal incrémental. Ce système crée des cellules lorsqu'il n'est pas capable de reconnaître correctement une "forme". L'amorçage de répétition est introduit par l'intermédiaire d'une "fonction d'amorçage" , en aidant la reconnaissance des formes dont la catégorie a été rencontrée récemment. Les caractéristiques de cette fonction sont analysées afin d'en trouver la forme la plus adaptée. Des expériences sont faites sur une application de reconnaissance de caractères manuscrits. Les méthodes décrites permettent de détecter facilement l'amorçage, avec peu de calculs (simple régression linéaire). Des calculs plus lourds permettent de mesurer le phénomène (différence entre la pente des droites de régression, avec et sans amorçage).
  • Keywords:

    Connectionism, Incremental Classifier, Priming, Perceptive Memory.
  • Keywords (in french):

    Connexionnisme, classifieur incrémental, amorçage, mémoire perceptive.
  • Availability: Electronic copy only.
  • Citation: Published in proceedings IWANN'95 International Workshop on Artificial Neural Networks Torremolinos (Malaga) Spain - June, 1995.
  • Size: 2+9p
  • Format: Compressed PostScript
  • Get it

A comparison of nested loops parallelization algorithms.

  • By: Alain Darte , Frederic Vivien
  • Number: RR1995-11
  • Date: May 24, 1995
  • Abstract:

    In this paper, we compare three nested loops parallelization algorithms (Allen and Kennedy's algorithm, Wolf and Lam's algorithm and Darte and Vivien's algorithm) that use different representations of distance vectors as input. We identify the concepts that make them similar or different. We study the optimality of each with respect to the dependence analysis it uses. We propose well-chosen examples that illustrate the power and limitations of the three algorithms. This study permits to identify which algorithm is the most suitable for a given representation of dependences.
  • Abstract (in french):

    Dans ce rapport, nous comparons trois algorithmes de parallélisation automatique de boucles imbriquées (les algorithmes de Kennedy et Allen, de Wolf et Lam et de Darte et Vivien) qui utilisent des représentations différentes des vecteurs de distance. Nous identifions les concepts qui leur sont communs et ceux qui les différencient. Nous étudions l'optimalité de chacun des algorithmes par rapport à l'analyse de dépendance qu'il utilise. Nous illustrons sa puissance et ses limitations par des exemples bien choisis. Cette étude permet finalement d'identifier quel algorithme est le mieux adapté à une analyse de dépendance donnée.
  • Keywords:

    Automatic Parallelization, Dependence Analysis, Linear Programming.
  • Keywords (in french):

    Parallélisation automatique, analyse de dépendances, programmation linéaire.
  • Availability: Electronic copy only.
  • Citation: Not published yet.
  • Size: 2+18p
  • Format: Compressed PostScript
  • Get it

Distributed simulation of parallel computers.

  • By: Loic Prylli
  • Number: RR1995-12
  • Date: May 1995
  • Abstract:

    Our work deals with simulation of distributed memory parallel computers. The tool we realized allows to take an application written for say an Intel Paragon and run it on a workstations cluster by just recompiling the code. The hardware of the target machine is simulated so that the behavior of your application on the workstations is identical to a native run on the simulated computer (except for total execution time!). We present here this tool as well as a mathematical analysis of the conditions required about the simulation host, the simulated host and the application to be able to distribute efficiently the simulation.
  • Abstract (in french):

    Nous nous intéressons ici à la simulation distribuée d'ordinateurs eux-mêmes parallèles. Nous avons réalisé un outil permettant d'exécuter une application développée pour une machine parallèle (par exemple le Paragon d'Intel) sur un réseau de stations de travail par le simple biais d'une recompilation. Les composantes matérielles de la machine cible sont simulées, de sorte que le comportement de l'application est identique à celui obtenu par une exécution native sur la machine simulée (hormis le temps total d'exécution!). Nous présentons ici cet outil ainsi qu'une analyse mathématique des conditions sur la machine simulante, l'application et la machine simulée qui permettent de distribuer efficacement la simulation.
  • Keywords:

    Simulation, Parallel Computers, Performance Analysis.
  • Keywords (in french):

    Simulation distribuée, ordinateurs parallèles, analyse de performances.
  • Availability: Paper copy available.
  • Citation: Not published yet.
  • Size: 2+26p
  • Format: Compressed PostScript
  • Get it

Self-Simulation for the Passive Optical Star Model.

  • By: Pascal Berthome , Thibault Duboux , Torben Hagerup , Ilan Newman , Assaf Schuster
  • Number: RR1995-13
  • Date: June 15, 1995
  • Abstract:

    Optical technology offers simple interconnection schemes with straightforward layouts that support complex logical interconnection patterns. The Passive Optical Star (POS) is often suggested as a platform for implementing the optical network: logically it offers an all-to-all broadcast capability. We investigate the use of POS optical technology as the communication medium for parallel computing. In particular, a feature of parallel models which is extremely important for the simplicity of algorithm design and program portability is the scalability property or self-simulation capability. It states that when a computation achieves a certain speedup on a large machine with many processors, then it achieves a similar speedup on any smaller machine (relative to the number of processors). We show that the POS is indeed scalable, namely, we present a randomized algorithm for an n-processor POS that does not assume global knowledge and that simulates a kn-processor POS with a slowdown of O(k +log* n). We also analyze direct algorithms, namely, algorithms that send messages directly from sender to receiver, for this case we prove that Theta(k^2) is the exact complexity.
  • Abstract (in french):

    La technologie optique permet la conception de réseaux d'interconnexions simples qui supportent des phases complexes de communications. L'étoile passive optique (POS) est souvent proposée comme plateforme d'implantation de réseau optique : elle offre la possibilité de faire un échange total logique. Nous montrons que le POS est extensible. En particulier, nous présentons un algorithme probabiliste pour un POS à n processeurs avec un coût O(k+log*n). Nous analysons aussi des algorithmes directs, c'est-à-dire des algorithmes qui transmettent les messages directement des émetteurs vers les récepteurs. Pour ce cas, nous prouvons que la complexité exacte est Theta(k2).
  • Keywords:

    Optical Networks, Brent Principle, Communication Simulation.
  • Keywords (in french):

    Réseaux optiques, principe de Brent, simulation de communications.
  • Availability: Electronic copy only.
  • Citation: Published in proceedings European Symposium on Algorithms'95, 1995, LNCS Series.
  • Size: 2+20p
  • Format: Compressed PostScript
  • Get it

Biased random walks, lyapunov functions, and stochastic analysis of best fit bin packing.

  • By: Claire Kenyon , Yuval Rabani , Alistair Sinclair
  • Number: RR1995-14
  • Date: September 1995
  • Abstract:

    We study of the average case performance of the Best Fit algorithm for on-line bin packing under the distribution in which the item sizes are uniformly distributed in the discrete range{1/k,2/k,...,j/k}. Our main result is that, in the case j=k-2, the expected waste for an infinite stream of items remains bounded. This settles an open problem posedrecently by Coffman et al. It is also the first result which involves a detailed analysis of the infinite multi-dimensional Markov chain underlying the algorithm.
  • Abstract (in french):

    Nous étudions l'algorithme "Meilleur choix" pour le problème de la mise en boîtes en-ligne lorsque les données sont tirées de façon aléatoire uniforme dans l'ensemble {1/k, 2/k, ..., j/k}. Notre résultat principal est que, dans le cas j = k - 2, l'espace moyen perdu reste asymptotiquement borné. Ceci résoud un problème de Coffman et al. , et utilise une analyse détaillée de la chaîne de Markov infinie multi-dimensionnelle sous-jacente à l'algorithme.
  • Keywords:

    Best Fit, Bin-Packing, On-line Algorithms, Average-Case Analysis, Markov Chains.
  • Keywords (in french):

    Mise en boîtes, algorithmes en-ligne, analyse en moyenne, chaînes de Markov.
  • Availability: Paper copy available.
  • Citation: Not published yet.
  • Size: 2+19p
  • Format: Compressed PostScript
  • Get it

Approximation algorithms for information dissemination problems.

  • By: Pierre Fraigniaud , Sandrine Vial
  • Number: RR1995-15
  • Date: September 1995
  • Abstract:

    Broadcasting and gossiping are known to be NP-hard problems. This paper deals with approximation algorithms for such problems. We consider both round-complexity and step-complexity in the telephone model. After an overview of previously derived approximation algorithms, we present new strategies for broadcasting and gossiping in any graphs. Broadcasting strategies are based on the construction of edge-disjoint spanning trees. Gossiping strategies are based on on-line computation of matchings along with the gossiping process. Our approximation algorithms for broadcasting offer almost optimal complexity when the number of messages to be broadcasted is large. We show that our best approximation algorithm for gossiping performs optimally in many cases. We also show experimentally that it can perform faster than the best known handmade algorithms in some particular cases.
  • Abstract (in french):

    La diffusion et l'échange total sont des problèmes NP-durs. Cet article traite d'algorithmes d'approximation pour ces problèmes. Nous considérons à la fois la complexité en temps et en taille de messages dans le modèle ``téléphone''. Après un bref aperçu des algorithmes d'approximation existants, nous présentons de nouvelles stratégies pour la diffusion et l'échange total dans un graphe quelconque. Les stratégies pour la diffusion sont basées sur la construction d'arbres de recouvrement arêtes-disjoints. Celles pour l'échange total sont basées sur le calcul de couplages tout au long du processus d'échange total. Nos algorithmes d'approximation pour la diffusion ont une complexité presque optimale lorsque le nombre de messages diffusés est grand. Nous montrons que notre meilleur algorithme d'approximation pour l'échange total s'exécute optimalement dans de nombreux cas. Nous montrons, expérimentalement, que cet algorithme peut dans certains cas, produire des algorithmes d'échange total plus rapides que les meilleurs algorithmes connus.
  • Keywords:

    Broadcasting, Gossiping, Approximation Algorithms.
  • Keywords (in french):

    Diffusion, échange total, algorithmes d'approximation.
  • Availability: Paper copy available.
  • Citation: Not published yet.
  • Size: 2+23p
  • Format: Compressed PostScript
  • Get it

Circuits as streams in COQ: verification of a sequential multiplier.

  • By: Christine Paulin-Mohring
  • Number: RR1995-16
  • Date: September 1995
  • Abstract:

    This paper presents the proof of correctness of a multiplier circuit formalized in the calculus of inductive constructions. It uses a representation of the circuit as a function from the stream of inputs to the stream of outputs. We analyze the computational aspect of the impredicative encoding of coinductive types and show how it can be used to represent synchronous circuits. We identify general proof principles that can be used to justify the correctness of such a circuit. The example and the principles have been formalized in the Coq proof assistant.This paper presents the proof of correctness of a multiplier circuit formalized in the Calculus of Inductive Constructions. It uses a representation of the circuit as a function from the stream of inputs to the stream of outputs. We analyze the computational aspect of the impredicative encoding of coinductive types and show how it can be used to represent synchronous circuits. We identify general proof principles that can be used to justify the correctness of such a circuit. The example and the principles have been formalized in the Coq proof assistant.
  • Abstract (in french):

    Cet article présente la preuve formalisée dans le calcul des constructions inductives de la correction d'un circuit réalisant la multiplication sur les entiers. Le circuit est représenté par une fonction transformant la suite infinie d'entrées en une suite infinie de sorties. Nous analysons l'aspect calculatoire de la représentation imprédicative des définitions co-inductives et montrons comment cette représentation peut servir à coder un circuit synchrone. Nous identifions des principes de preuve généraux pour justifier de tels circuits. Les exemples et les principes ont été formalisés dans l'assistant à la démonstration Coq.
  • Keywords:

    Specification, Hardware Verification, Co-Inductive Definitions.
  • Keywords (in french):

    Spécification, vérification de matériel, définition co-inductives.
  • Availability: Paper copy available.
  • Citation: Not published yet.
  • Size: 2+15p
  • Format: Compressed PostScript
  • Get it

The influence on synthesis of modern computer arithmetic.

  • By: Anne Mignotte , Jean-Michel Muller , Olivier Peyran
  • Number: RR1995-17
  • Date: September 12, 1995
  • Abstract:

    Taking into account the various possibilities offered by computer arithmetic during high-level synthesis may help to design much powerfull architectures. The arithmetic operators (mainly in floating point arithmetic) may be carefully tuned up to exactly fit the time and accuracy requirements. This, of course, may have an influence on the synthesis process. In this paper, we mainly address two topics: first of all the problem of numerical error control; and then the possible use of redundant number systems -- which allow some nice features such as carry free addition or digit-serial, most significant digit first arithmetic operations. We then propose some potential applications and we discuss the new synthesis problems they involve.
  • Abstract (in french):

    La prise en compte des diverses possibilités offertes par l'arithmétique des ordinateurs permet la conception d'architectures plus puissantes. Les opérateurs arithmétiques doivent être convenablement modifiés afin de s'adapter correctement aux exigences de temps et de précision. Ceci a bien sûr une influence sur le processus de synthèse. Dans cet article, nous nous intéressons principalement à deux sujets : tout d'abord le problème du contrôle d'erreur ; ensuite la possibilité de l'utilisation de systèmes redondants d'écriture des nombres - qui possèdent des propriétés interessantes comme l'addition sans propagation de retenue ou les opérations série avec poids forts en tête. Finalement nous proposons de possibles applications et discutons des nouveaux problèmes de synthèse qu'elles impliquent.
  • Keywords:

    Arithmetic, Redundant Number Systems, Floating Point Number, High Level Synthesis.
  • Keywords (in french):

    Arithmétique, système redondant d'ecriture des nombres, nombres en virgule flottante, synthèse de haut niveau.
  • Availability: Paper copy available.
  • Citation: Published in ``Logic and architecture synthesis : state of the art and novel approaches'', Chapman and Hall, 1995.
  • Size: 2+11p
  • Format: Compressed PostScript
  • Get it

Retiming DAGs.

  • By: Pierre-Yves Calland , Anne Mignotte , Olivier Peyran , Yves Robert , Frederic Vivien
  • Number: RR1995-18
  • Date: September 1995
  • Abstract:

    The increasing complexity of digital circuitry makes global design optimization no longer possible: a designer will only consider the critical parts of his circuit. This paper discusses timing optimization problems when these critical parts can be represented by Direct Acyclic Graphs (DAGs). We deal with different (though related) clock period problems, under various external constraints. The main algorithm concerns the determination of the optimal clock period of a given circuit. We propose an efficient solution, based on the retiming technique, which improves current results in the literature. We give three different formulations depending on which combinational gates delay model is used: same delay for every gate, different delays or non-uniform delays.
  • Abstract (in french):

    La complexité grandissante des circuits numériques rend désormais impossible toute optimisation globale d'un circuit: les concepteurs ne considèrent plus que les parties critiques de leur circuit. Cet article traite des problèmes d'optimisation temporelle lorsque ces parties critiques peuvent être représentées par des graphes acycliques orientés. Nous considérons différents problèmes concernant les contraintes sur la période d'horloge, qui interviennent lors de la conception d'un circuit, et qui découlent de la détermination de la période optimale du circuit. Nous proposons un algorithme de faible complexité, basé sur la technique de resynchronisation, pour résoudre ce problème essentiel, et nous donnons trois formulations différentes, dépendant du modèle de délai utilisé pour les portes combinatoires : meme délai pour toutes les portes, délais différents ou délais non-uniformes.
  • Keywords:

    Direct Acyclic Graph, Clock Period, Optimization, Retiming, Delay Model, Registers.
  • Keywords (in french):

    Graphe acyclique orienté, période d'horloge, optimisation, modèle de délai, registres.
  • Availability: Paper copy available.
  • Citation: Not published yet.
  • Size: 2+20p
  • Format: Compressed PostScript
  • Get it

Best-fit bin-packing with random order.

  • By: Claire Kenyon
  • Number: RR1995-19
  • Date: September 1995
  • Abstract:

    Best-fit is the best known algorithm for on-line bin-packing, in the sense that no algorithm is known to behave better both in the worst case (when Best-fit has performance ratio 1.7) and in the average uniform case, with items drawn uniformly in the interval [ 0, 1]. In practical applications, Best-fit appears to perform within a few percent of optimal. In this paper, we study the expected performance ratio, taking the worst-case multiset of items L$, and assuming that the elements of L are inserted in random order, with all permutations equally likely. We show a lower bound of 1.07... and an upper bound of 1.5 on the random order performance ratio of Best-fit. The upper bound contrasts with the result that in the worst case, any (deterministic or randomized) on-line bin-packing algorithm has performance ratio at least 1.54....
  • Abstract (in french):

    L'algorithme de meilleur choix est le meilleur pour la mise en boîte en-ligne, en ce sens qu'on ne connaît pas d'algorithme qui lui est supérieur à la fois dans le pire cas et dans le cas moyen uniforme. En pratique, Meilleur choix semble être à quelques pour cent de l'optimum. Dans cet article, nous étudions la performance relative moyenne par rapport à l'optimum, considérant le pire cas de valeurs de données mais supposant que leur ordre d'arrivée est aléatoire. Nous montrons une borne inférieure de 107 % et une borne supérieure de 150 % à la performance de Meilleur choix avec cette définition.
  • Keywords:

    Best Fit, Bin-Packing, On-line Algorithms, Approximation Ratio, Markov Chains.
  • Keywords (in french):

    Mise en boîtes, algorithmes en-ligne, rapport de performance, chaîne de Markov.
  • Availability: Electronic copy only.
  • Citation: Not published yet.
  • Size: 2+12p
  • Format: Compressed PostScript
  • Get it

Error-resilient DNA computation.

  • By: Richard M. Karp , Claire Kenyon , Orli Waarts
  • Number: RR1995-20
  • Date: September 1995
  • Abstract:

    The DNA model of computation, with test tubes of DNA molecules encoding bit sequences, is based on three primitives, extract-a-bit, merge-two-tubes and detect-emptiness. Perfect operations can test the satisfiability of any boolean formula in linear time. However, in reality the extract operation is faulty. We determine the minimum number of faulty extract operations required to simulate a single highly reliable extract operation, and derive a method for converting any algorithm based on error-free operations to an error-resilient one.
  • Abstract (in french):

    Le modèle de calcul basé sur les molécules d'ADN codant des suites de bits utilise trois primitives, extraction d'un bit, fusion de deux éprouvettes et détection d'éprouvette vide. Avec des opérations fiables, on peut tester la satisfiabilité d'une formule booléenne quelconque en temps linéaire. Mais en réalité, l'opération d'extractions est peu fiable. Nous déterminons le nombre minimum d'extractions non fiables et de fusions permettant de simuler une extraction très fiable, puis donnons une réduction qui, d'un algorithme basé sur des primitives parfaitement fiables, déduit un algorithme lorsque l'opération extraction est non fiable.
  • Keywords:

    Reliability, Errors, DNA Computations, Lower Bounds, Algorithms.
  • Keywords (in french):

    Fiabilité, calculs avec l'ADN, bornes inférieures, algorithmes.
  • Availability: Electronic copy only.
  • Citation: Not published yet.
  • Size: 2+23p
  • Format: Compressed PostScript
  • Get it

Dynamic load balancing in a parallel particle simulation.

  • By: Jean-Marc Pierson , Serge Miguet
  • Number: RR1995-21
  • Date: September 1995
  • Abstract:

    This paper presents the parallel implementation of a dynamic system of particles on a distributed memory architecture. The implementation simulates the temporal evolution and behavior of a general system of particles. Long range interactions with the environment as well as short range interactions between particles are fairly handled. Distribution of the particles is a spaced-based partition, and the allocation of the particles on a linear network of processors is dynamic. An important study on the compromise between the cost of an unbalanced world and those of load balancing has been developed for a simple case, while an heuristic is proposed for general cases. Some results on MIMD architectures and on a network of workstations are finally presented.
  • Abstract (in french):

    Nous présentons dans ce rapport un travail concernant l'implémentation parallèle d'un système dynamique de particules sur machine à mémoire distribuée. Le logiciel permet de simuler le comportement temporel d'un ensemble de particules, où les interactions entre les particules et l'environnement sont prises en compte, ainsi que les interactions à courte distance entre particules. Afin de pouvoir traiter efficacement ces interactions, nous proposons une distribution spatiale des particules, où chaque processeur prend en charge une région de l'espace. La répartition des particules évolue constamment au cours du temps. Nous sommes donc contraints à rééquilibrer fréquemment la charge de travail, par une redistribution dynamique des données. Cette redistribution est effectuée de manière très efficace sur un réseau linéaire de processeurs. Nous montrons comment optimiser notre politique d'équilibrage des charges, en cherchant un compromis entre une charge déséquilibrée et un rééquilibrage trop fréquent. Une étude exacte sur un cas simple et une heuristique dans le cas général sont proposées pour cette application. Divers résultats sur machines MIMD ainsi que sur réseau de station de travail sont présentés et analysés.
  • Keywords:

    Parallel Particle Simulation, Load Balancing.
  • Keywords (in french):

    Simulation de particules, équilibrage de charges.
  • Availability: Electronic copy only.
  • Citation: To appear in proceedings of HPCS'95.
  • Size: 2+13p
  • Format: Compressed PostScript
  • Get it

On the complexity of deadlock detection in families of planar nets.

  • By: Bruno Durand , Anne-Cecile Fabret
  • Number: RR1995-22
  • Date: September 1995
  • Abstract:

    We are interested in some properties of massively parallel computers that we model by finite automata connected together as a 2-dimensional grid. We wonder whether it is possible to anticipate a possible appearance of a deadlock in such nets. Thus, we look for efficient algorithms to predict whether deadlocks can appear in grids of bounded size. From the point of view of worst-case complexity, we prove that this problem is NP-complete whereas it is quadratic for linear structures. The method we use is a reduction from a tiling problem. We also prove that this problem, associated with a natural probability distribution on its instances, is RNP-complete (Random NP-complete) in the theory proposed by Levin and Gurevich. Very few randomized problems are known to be RNP-complete. Under classical complexity hypotheses, this result proves that there does not exist any algorithm that solves this problem efficiently on average case. We present others extentions of our results for different planar underlying communication graphs, and we present a Sigma_2-complete problem for networks with inputs.
  • Abstract (in french):

    Nous nous intéressons à des propriétés des ordinateurs massivement parallèles que nous modélisons par des automates finis connectés suivant une grille 2D. Nous nous demandons s'il est possible de prévoir l'apparition d'interblocage dans le réseau. Nous cherchons donc des algorithmes efficaces pour résoudre ce problème dans des grilles de taille finie. Du point de vue de la complexité dans le pire des cas, nous prouvons que ce problème est NP-complet alors qu'il est quadratique sur des réseaux en forme de ligne. Nous utilisons une réduction depuis un problème de pavabilité. Nous prouvons aussi que lorsque l'on munit l'ensemble des entrées d'une distribution de probabilité naturelle, ce problème est RNP-complet (Random NP-complet) dans la théorie proposée par Levin et Gurevich. Très peu de problèmes ont été prouvés RNP-complets. Sous des hypothèses classiques de complexité, ce résultat prouve qu'aucun algorithme ne résoud ce problème efficacement en moyenne. Nous présentons aussi d'autres extensions de notre résultat à différentes structures de communication sous-jacentes, et présentons un problème Sigma_2-complet lorsque le réseau a des entrées.
  • Keywords:

    Computational Complexity, Theory of Parallel and Distributed Computation, Automata Graphs, Tilings, Deadlock.
  • Keywords (in french):

    Complexité, pavages, algorithmique parrallèle, graphes d'automates, pavages, interblocage.
  • Availability: Paper copy available.
  • Citation: To appear in Theoretical Computer Science.
  • Size: 2+12p
  • Format: Compressed PostScript
  • Get it

A mathematical model for feed-forward neural networks : theoretical description and parallel applications.

  • By: Cedric Gegout , Bernard Girau , Fabrice Rossi
  • Number: RR1995-23
  • Date: September 1995
  • Abstract:

    We present a general model for differentiable feed-forward neural networks. Its general mathematical description includes the standard multi-layer perceptron as well as its common derivatives. These standard structures assume a strong relationship between the network links and the neuron weights. Our generalization takes advantage of the suppression of this assumption. Since our model is especially well-adapted to gradient-based learning algorithms, we present a direct and a backward algorithm that can be used to differentiate the output of the network. Theoretical computation times are estimated for both algorithms. We describe a direct application of this model: a parallelization method that uses the expression of our general backward differentiation to overlap the communication times.
  • Abstract (in french):

    Nous présentons un modèle général de réseaux de neurones différentiables non récurrents. Ce modèle inclut l'architecture standard du perceptron multicouche, aussi bien que ses dérivés classiques. Cette architecture standard se base sur une relation forte entre la notion de connexion du réseau et celle de poids des neurones. Notre généralisation tire profit de la suppression de cette relation. Le modèle présenté étant plus particulièrement adapté aux algorithmes d'apprentissage à base de gradient, nous présentons un algorithme direct ainsi qu'un algorithme rétropropagé pour le calcul de la différentielle de la sortie du réseau de neurones. Les temps de calcul des deux algorithmes sont estimés théoriquement. Enfin, nous présentons une des principales applications de ce modèle, basée sur l'algorithme généralisé de rétropropagation : une méthode de parallélisation qui se base sur une connaissance fine des calculs requis par cet algorithme afin d'introduire un recouvrement des communications par les calculs.
  • Keywords:

    Feed-forward Neural Networks, Backpropagation, Parallel Implementation, Network-partitioning.
  • Keywords (in french):

    Réseaux de neurones non récurrents, rétropropagation, implémentation parallèle, partition de réseau.
  • Availability: Paper copy available.
  • Citation: Not published yet.
  • Size: 2+12p
  • Format: Compressed PostScript
  • Get it

A load-balanced parallel implementation of the Marching-Cubes algorithm.

  • By: Serge Miguet , Jean-Marc Nicod
  • Number: RR1995-24
  • Date: October 1995
  • Abstract:

    This report presents a load-balanced parallelization of the well known Marching-Cubes algorithm, that aims at constructing an iso-surface in a 3D image. Our main contributions lie in the non-redundant computations of our parallel implementation, and in the dynamic distribution of the data for load-balancing purposes. We first derive a modelization for the computation time as a function of the generated surface complexity. The workload associated to each slice of the input data is evaluated by counting the number of vertices that will be generated on that slice. The slices are then locally redistributed to ensure a balanced workload. Furthermore, counting the number of vertices allows us to foresee (and thus allocated) the memory size needed for the data structures and to assign to each vertex a unique global reference. Experiments done on an Intel Paragon machine are given both for synthetic and medical images. They show the usefulness of our dynamic data redistribution scheme.
  • Abstract (in french):

    Ce rapport présente une parallélisation équilibrée de l'algorithme d'extraction de surface bien connu des Marching-Cubes. Notre contribution intervient au niveau de la non-redondance des calculs de notre implémentation parallèle et au niveau de la répartition dynamique de la charge de travail. Une modélisation montre comment le temps de calcul est fonction de la complexité de la surface. A chaque coupe de données est associée une charge de travail proportionnelle au nombre de sommets calculés par cette coupe. Une redistribution des données assure ensuite un calcul équilibré. Le dénombrement des sommets qui seront produits dans la triangulation nous permet de plus, de prévoir le volume de la structure de données produite par l'algorithme et également de référencer chaque sommet de la triangulation de manière unique. Des expériences ont été menées sur la machine Paragon d'Intel sur des images artificielles et des images médicales. Elles montrent l'opportunité de notre schéma de redistribution dynamique des données.
  • Keywords:

    Marching-Cubes, Dynamic Load Balancing, Parallel Computing, Medical Imaging, Surface Extraction.
  • Keywords (in french):

    Marching-Cubes, équilibrage dynamique de la charge, calcul parallèle, imagerie médicale, extraction de surface.
  • Availability: Electronic copy only.
  • Citation: To appear in IWPIA'95, ENSLyon, 1995.
  • Size: 2+15p
  • Format: Compressed PostScript
  • Get it

An optimized and load-balanced portable parallel Zbuffer.

  • By: Henri-Pierre Charles , Laurent Lefevre , Serge Miguet
  • Number: RR1995-25
  • Date: October 1995
  • Abstract:

    This paper describes the parallel implementation of the Zbuffer algorithm on different distributed memory machines. In computer graphics domain, the Zbuffer is one of the most popular and fastest technique that can be used to generate a surfacic representation of a scene consisting of objects in a 3-dimensional world. To improve this method we develop a parallel algorithm which uses an hypercube topology, load-balancing techniques and portable global communications phases.
  • Abstract (in french):

    Nous présentons dans ce rapport une implémentation parallèle d'un algorithme de synthèse d'image : le Zbuffer. Cette implémentation a été portée sur différents types de machines parallèles à mémoire distribuée. En synthèse d'image, le Zbuffer est l'une des plus populaires et rapides techniques pour générer une représentation surfacique d'une scène constituée de facettes dans un monde en trois dimensions. Pour améliorer cette technique, nous présentons un algorithme parallèle qui tire pleinement profit d'une topologie en hypercube et de méthodes d'équilibrage de charges. Cette implémentation est basée sur des phases de communications globales générales qui assurent la portabilité du Zbuffer sur différentes plateformes de développement.
  • Keywords:

    Parallelism, Load-balancing Methods, Synthesis.
  • Keywords (in french):

    Parallélisme, équilibrage de charge, synthèse d'image.
  • Availability: Electronic copy only.
  • Citation: Published in the proceedings of IS&T/SPIE Symposium on electronic imaging: Science and technology, San Jose, 1995.
  • Size: 2+9p
  • Format: Compressed PostScript
  • Get it

How to optimize residual communications ?

  • By: Michele Dion , Cyril Randriamaro , Yves Robert
  • Number: RR1995-27
  • Date: October 1995
  • Abstract:

    Minimizing communications when mapping affine loop nests onto distributed memory parallel computers has already drawn a lot of attention. This paper focuses on the next step : as it is generally impossible to obtain a communication-free (or local) mapping, how to optimize the residual communications? We explain how to take advantage of macro-communications such as broadcasts, scatters, gathers or reductions or how to decompose general affine communications into simpler ones that can be performed more efficiently. We finally give a two-step heuristic that summarizes our approach : first minimize the number of nonlocal communications, then optimize residual affine communications using macro-communications or decompositions.
  • Abstract (in french):

    Minimiser les communications lors du placement d'un nid de boucles affine sur une machine parallèle à mémoire distribuée a déjà été l'objet de beaucoup d'attention. Dans ce rapport, nous nous intéressons à l'étape suivante : puisqu'il est en général impossible d'obtenir un placement sans communication, comment optimiser les communications résiduelles ? Nous expliquons comment tirer avantage de macro-communications (diffusions, distributions, rassemblements ou réductions) ou comment décomposer des communications affines en communications plus simples et plus efficaces. Nous donnons finalement une heuristique en 2 étapes qui résume notre approche : d'abord minimiser le nombre de communications non locales , puis optimiser les communications résiduelles en utilisant des macro-communications ou des décompositions.
  • Keywords:

    Mapping, Affine Loop Nests, Distributed Memory Parallel Computers, Minimizing Communications, Macro-communications.
  • Keywords (in french):

    Placement, nids de boucles affines, machines parallèles à mémoire distribuée, minimisation des communications, macro-communications.
  • Availability: Paper copy available.
  • Citation: Not published yet.
  • Size: 2+26p
  • Format: Compressed PostScript
  • Get it

Pavages du plan : indecidabilite et periodicite.

  • By: Cyril Allauzen , Bruno Durand
  • Number: RR1995-28
  • Date: September 1995
  • Abstract:

    We study some decision problems concerning the tiling of the plane with Wang tiles. We present a proof for the undecidability of the tiling problem for the whole plane, and also for the periodic tiling. In these poofs, an aperiodic tile set is constructed. We are interested in the second part in the link between the cardinality of possible tilings of the plane with a given tile set and the existence of a periodic tiling. We are also interested in the property of quasiperiodicity and prove that all tile sets that tile the plane, may tile the plane quasiperiodically.
  • Abstract (in french):

    Nous nous intéressons à des problèmes de décidabilité des pavages du plan par des tules de Wang. Nous étudions le problème du pavage du plan avec une tuile imposée à l'origine et nous montrons que ce problème est indécidable. Ensuite, nous donnons une preuve de l'indécidabilité du pavage du plan ; la démonstration de ce résultat nous permet d'exhiber un jeu de tuiles apériodique. Enfin, nous montrons l'indécidabilité du pavage périodique du plan. Nous étudions dans la suite des problèmes liés à la périodicité. Dans les constructions précédentes, nous avons vu qu'il existe au moins un jeu de tuiles apériodique. Ceci nous amène à nous intéresser au lien entre la cardinalité de l'ensemble des pavages possibles pour un certain jeu de tuiles et la périodicité d'un des pavages donné par ce jeu. Finalement, nous nous intéressons à la généralisation de la notion de périodicité qu'est la quasipériodicité et nous prouvons que tout ensemble de tuiles pavant le plan permet de le paver quasipériodiquement.
  • Keywords:

    Undecidability, Tilings, Periodicity, Quasiperiodicity.
  • Keywords (in french):

    Indécidabilité, pavages, périodicité, quasipériodicité.
  • Availability: Paper copy available.
  • Citation: Not published yet.
  • Size: 2+28p
  • Format: Compressed PostScript
  • Get it

Two completeness results about a proof system for a simple data-parallel language (full version).

  • By: David Cachera
  • Number: RR1995-29
  • Date: October 1995
  • Abstract:

    We consider a proof system a la Hoare for a simple data-parallel language. This proof system manipulates two-part assertions, where the predicate on current values of program variables is distinct from the specification of the current extent of parallelism. We know from a previous result that this proof system is complete for loop-free programs. This result was obtained by means of a method acting upon the proof system, at a semantic level. We show that it is possible to get the same result by another method, acting this time at a syntactic level, directly on the program's syntax. We finally show that these two methods are equivalent.
  • Abstract (in french):

    Nous considérons un langage data-parallèle simple, muni d'un système de preuve à la Hoare. Les assertions manipulées par ce système de preuve sont décomposées en deux parties, l'une étant un prédicat sur les variables du programme, l'autre une expression booléenne décrivant le contexte d'activité. Nous savons d'après un résultat antérieur que ce système de preuve est complet pour les programmes sans boucles. Ce résultat a été obtenu par une méthode sémantique, intervenant au niveau du système de preuve. Nous montrons qu'il est possible d'utiliser une méthode syntaxique, qui intervient cette fois au niveau du programme. Nous montrons également que ces deux méthodes sont équivalentes.
  • Keywords:

    Concurrent Programming, Specifying and Verifying and Reasoning About Programs, Semantics of Programming Languages, Data-Parallel Languages, Proof System, Hoare Logic, Weakest Preconditions.
  • Keywords (in french):

    Programmation parallèle, spécification et validation de programmes, sémantique des langages de programmation, langages data-parallèles, système de preuve, logique de Hoare, plus faibles préconditions.
  • Availability: Paper copy available.
  • Citation: Extended abstract in proceedings RenPar'7 : septiemes rencontres francophones du parallelisme, Mons, Belgium, 1995.
  • Size: 2+14p
  • Format: Compressed PostScript
  • Get it

On the computational power and super-turing capabilities of dynamical systems.

  • By: Olivier Bournez , Michel Cosnard
  • Number: RR1995-30
  • Date: October 1995
  • Abstract:

    We explore the simulation and computational capabilities of dynamical systems. We first introduce and compare several notions of simulation between discrete systems. We give a general framework that allows dynamical systems to be considered as computational machines. We introduce a new discrete model of computation : the analog automaton model. We determine the computational power of this model and prove that it does have super-turing capabilities. We then prove that many very simple dynamical systems from literature are actually able to simulate analog automata. From this result we deduce that many dynamical systems have intrinsically super-turing capabilities.
  • Abstract (in french):

    Nous étudions la puissance de calcul et de simulation des systèmes dynamiques. Dans un premier temps, nous introduisons et comparons plusieurs notions de simulation entre systèmes discrets. Nous donnons un cadre général permettant de considérer les systèmes dynamiques comme des modèles de calcul. Nous définissons un nouveau modèle de calcul : le modèle des automates analogiques. Nous déterminons la puissance de calcul de ce modèle et prouvons qu'il possède des capacités super-Turing. Nous prouvons alors que des systèmes dynamiques très simples tirés de la littérature sont en fait capable de simuler les automates analogiques. De ces résultats, nous en déduisons que beaucoup des sytèmes dynamiques ont intrinsèquement des capacités super-Turing.
  • Keywords:

    Super-Turing Capabilities, Dynamical Systems, Complexity Theory, Real Machines.
  • Keywords (in french):

    Capacités super-Turing, systèmes dynamiques, théorie de la complexité, machines réelles.
  • Availability: Electronic copy only.
  • Citation: Not published yet.
  • Size: 2+38p
  • Format: Compressed PostScript
  • Get it

Is it possible to discriminate odors with common words ?

  • By: Regina Eberhardt , Helene Paugam-Moisy , Didier Puzenat , Jean-Pierre Royet
  • Number: RR1995-31
  • Date: November 1995
  • Abstract:

    Several experiments have been performed in order to study the cognitive processes which are involved in odor recognition. The current report summarizes experimental protocol and analyzes collected data. The goal is to try to recognize odors from descriptors which are selected by subjects from a list. Different groups have to choose in several descriptor lists, some with profound descriptors and some with a few surface descriptors. Profound descriptors are supposed to involved more cognition than surface descriptors. Subjects also have to name the odors. Recorded data are first analyzed, and then learned by an incremental neural classifier. The problem is hard to be learned. It seems very difficult to discriminate the different odors from the sets of descriptors. A variant of the learning algorithm, less sensitive to difficult examples, is proposed. The pertinence of surface descriptors is discussed.
  • Abstract (in french):

    Des expériences ont été réalisées pour étudier les processus cognitifs impliqués dans la reconnaissance des odeurs. Ce rapport résume le protocole expérimental et étudie les données collectées. Le but est d'essayer de discriminer des odeurs à partir de descripteurs qui sont choisis par les sujets dans une liste. Plusieurs groupes travaillent avec différentes listes de descripteurs, ces descripteurs pouvant être de surface ou profonds. Les descripteurs profonds sont supposés être imliqués dans des traitememts plus cognitifs que les descripteurs de surface. Les sujets doivent également nommer les odeurs. Les données recueillies sont d'abord analysées, puis apprises par un classifieur neuronal incrémental. Le problème est difficile à apprendre. Il semble très délicat de discriminer les odeurs à partir des jeux de descripteurs. Une variante de l'algorithme d'apprentissage, moins sensible aux exemples difficiles, est proposée. La pertinence des descripteurs de surface est discutée.
  • Keywords:

    Olfaction, Recognition, Neural Networks, Classification.
  • Keywords (in french):

    Olfaction, reconnaissance, réseaux neuronaux, classification.
  • Availability: Paper copy available.
  • Citation: Not published yet.
  • Size: 2+16p
  • Format: Compressed PostScript
  • Get it

A communication-oriented approach to parallel relational query optimization and processing.

  • By: Lionel Brunie , Harald Kosch
  • Number: RR1995-32
  • Date: November 1995
  • Abstract:

    This report presents a compile-time optimization methodology for complex relational query processing on a multiprocessor machine. A new scheduling algorithm is proposed to allocate the resources of the machine. Furthermore the management of intra-processors communication and load balancing is explicitly introduced into the parallelization strategy. A new control mechanism is presented in order to supervise the run-time execution, and if necessary, to trigger a two-phases elastic data redistribution. Additional optimization is obtained by overlapping the communications and the computations whenever it is possible.
  • Abstract (in french):

    Dans ce rapport nous introduisons une méthodologie d'optimisation statique des requêtes relationnelles complexes sur une machine multi-processeurs. Un nouvel algorithme d'ordonnancement est proposé pour allouer les ressources de la machine. De plus la gestion de communication entre les processeurs et l'équilibrage de charge sont explicitement introduits dans la stratégie de parallélisation. Un nouveau mécanisme de contrôle est introduit afin de tracer le traitement des requêtes et, si nécessaire, d'appeler un algorithme de redistribution élastique en deux phases. Des tests de performances sur des machines parallèles (avec un réseau d'interconnection de type hypercube ou grille) ont montré l'efficacité et la robustesse de notre approche.
  • Keywords:

    Parallel Databases, Parallel Query Optimization, Parallel Query Processing, Load Balancing.
  • Keywords (in french):

    Bases de données parallèles, optimisation de requête pour l'exécution parallèle, traitement parallèle de requêtes, équilibrage de charge.
  • Availability: Paper copy available.
  • Citation: Published in proceedings of the BIWIT Conference, San Sebastian, Spain, 1995, IEEE Computer Society Press, pages 50-59. Published in Books of abstracts, ParCo Conference 95, Gent, Belgium, 1995, page 75.
  • Size: 2+28p
  • Format: Compressed PostScript
  • Get it

Towards exact rounding of the elementary functions.

  • By: Jean-Michel Muller , Arnaud Tisserand
  • Number: RR1995-33
  • Date: November 1995
  • Abstract:

    Always getting exactly rounded results when implementing the elementary functions in floating-point arithmetic has been an open problem for many years. After a brief recall of previous results in that domain, we show that that problem can be solved, and we discuss the time required to always provide exactly rounded results.
  • Abstract (in french):

    Etre capable de toujours arrondir exactement les fonctions élémentaires est un problème ouvert depuis plusieurs années. Après un bref survol des résultats antérieurs, nous montrons que ce problème peut être résolu, et nous donnons une estimation du temps requis pour toujours fournir des arrondis exacts.
  • Keywords:

    Floating-point Arithmetic, Roundings.
  • Keywords (in french):

    Arithmétique virgule flottante, arrondis.
  • Availability: Paper copy available.
  • Citation: Published in Scientific Computing and Validated Numerics, Alefeld, Frommer and Lang Eds, Akademie verlag, Berlin, 1996.
  • Size: 2+12p
  • Format: Compressed PostScript
  • Get it

FPGA implementation of polynomial evaluation algorithms.

  • By: Milos Ercegovac , Jean-Michel Muller , Arnaud Tisserand
  • Number: RR1995-34
  • Date: November 1995
  • Abstract:

    The most-significant-digit-first function evaluation method (E-method) allows efficient evaluation of polynomials and certain rational functions on custom hardware. The time required for the computation is of the order of m carry-free addition operations, m being the number of digits in the result. We discuss a digit-parallel and a digit-serial implementation of this method on a DecPeRLe-1 board, made up with Xilinx FPGAs. After a presentation of the E-method, we give a description of the architecture of the Dec-PeRLe-1 board, present our designs and analyze their performances.
  • Abstract (in french):

    La méthode d'évaluation ``chiffre de poids fort en tête'' (E-méthode) permet l'évaluation rapide de polynômes et de certaines fonctions rationnelles par matériel. Le temps requis pour le calcul est de l'ordre du temps nécessité par m additions sans propagation de retenue, où m est le nombre de chiffres du résultat. On propose une implantation parallèle et une implantation série de cette méthode, sur une carte DEC-PeRLe1, constituée de circuits FPGA Xilinx. Après une description de la E-méthode, nous donnons une description de l'architecture de la carte Dec-PeRLe1, nous présentons nos implantations et analysons leurs performances.
  • Keywords:

    On-line Arithmetic, FPGA, Polynomial Evaluation.
  • Keywords (in french):

    Arithmétique en-ligne, FPGA, évaluation de polynômes.
  • Availability: Paper copy available.
  • Citation: Published in SPIE Photonics East'95 Conference proceedings, Philadelphia, USA, 1995.
  • Size: 2+14p
  • Format: Compressed PostScript
  • Get it

Pyramides d'images couleur.

  • By: Didier Calle , Annick Montanvert , Stephane Ubeda
  • Number: RR1995-35
  • Date: November 1995
  • Abstract:

    For the last fifteen years, pyramidal representations of images have been used in image processing. However, the works have mainly dealt with pyramids of grey-level images. In this paper, we are interested in the development of color image pyramids. Our purpose is to exploite the power of color information to process images when using pyramids (e.g. segmentation) as well as to exploite pyramidal representations for color image processing (e.g. restoration). In application, we design a new algorithm for compression and progressive transmission, and a quantization method, for color images.
  • Abstract (in french):

    Depuis une quinzaine d'années, les représentations pyramidales d'images ont particulièrement été étudiées et utilisées en traitement d'images. Cependant, l'essentiel des travaux a porté sur les pyramides d'images en niveaux de gris. Dans cet article, nous nous intéressons à la construction de pyramides d'images dans l'espace des couleurs. L'objectif est aussi bien d'exploiter la richesse de l'information couleur pour des traitements basés sur les pyramides d'images (ex. segmentation) que d'exploiter la représentation pyramidale pour des traitements d'images couleur (ex. restauration). En application, nous développons un nouvel algorithme de compression et de transmission progressive, ainsi qu'une méthode de quantification, pour les images couleur.
  • Keywords:

    Image Processing, Pyramid, Color Model, Compression, Quantization.
  • Keywords (in french):

    Traitement d'images, pyramide, couleur, compression, quantification.
  • Availability: Electronic copy only.
  • Citation: Published in 5th DGCI : Discrete Geometry Computer Imagery, Clermont-Ferrand, France, 1995, pages 17-26, ISBN 2-87663-040-0.
  • Size: 2+16p
  • Format: Compressed PostScript
  • Get it

Pyramides d'images residuelle par expansion inductive.

  • By: Didier Calle , Annick Montanvert
  • Number: RR1995-36
  • Date: November 1995
  • Abstract:

    We define a new pyramidal model derived from Laplacian pyramid which is frequently used in computer vision. As Laplacian pyramid, the aim of our model is to provide a representation which decorrelates the image pixels, by noncausal prediction, at multiple resolutions. But instead of using a prediction by interpolation, we use an inductive prediction technique in order to minimize residual errors. The result is a better decorrelation. The residual layers have lower entropy and variance than Laplacian layers. A natural application is image compression.
  • Abstract (in french):

    Nous présentons un nouveau modèle pyramidal s'inspirant de la pyramide laplacienne, fréquemment utilisée en vision artificielle. Comme pour celle-ci, l'objectif du modèle proposé est de fournir une représentation où les pixels de l'image sont décorrélés, suivant une technique de prédiction non causale, à divers niveaux de résolutions. Mais au lieu de procéder par interpolation, notre modèle prédictif procède par induction afin de minimiser l'erreur de prédiction. Le résultat est une meilleure décorrélation. Les couches résiduelles construites ont une entropie et une variance plus faibles que celles des couches laplaciennes. Une application naturelle est la compression d'images.
  • Keywords:

    Image Processing, Multiresolution, Pyramid, Correlation, Induction, Compression.
  • Keywords (in french):

    Traitement d'images, multirésolution, pyramide, corrélation, induction, compression.
  • Availability: Electronic copy only.
  • Citation: To appear in Dixieme Congres RFIA : Reconnaissance des Formes et Intelligence Artificielle, Rennes, France, 16-18 janvier 1996.
  • Size: 2+16p
  • Format: Compressed PostScript
  • Get it

Volumic segmentation using hierarchical representation and triangulated surface.

  • By: Jacques-Olivier Lachaud, Annick Montanvert
  • Number: RR1995-37
  • Date: October 1995
  • Abstract:

    This research report presents a new algorithm for segmenting three-dimensional images. It is based on a dynamic triangulated surface and on a pyramidal representation. The triangulated surface, which follows a physical modelization and which can as well modify its geometry as its topology, segments images into their components by altering its shape according to internal and external constraints. In order to speed up the whole process, an algorithm of pyramid building with any reduction factor allows us to transform the image into a set of images with progressive resolutions. This organization into a hierarchy, combined with a model that can adapt its mesh refinement to the resolution of the workspace, authorizes a fast estimation of the general forms included in the image. After that, the model searches for finer and finer details while relying successively on the different levels of the pyramid.
  • Abstract (in french):

    Ce rapport de recherche présente un nouvel algorithme de segmentation d'images tridimensionnelles par utilisation de pyramides et de triangulation de surface dynamique. La triangulation, dotée d'une modélisation physique et capable de changer sa topologie, va, en se déformant suivant certaines contraintes, segmenter l'image en ses constituants. Afin d'accélérer le processus, un algorithme de construction de pyramide de facteur de réduction quelconque permet de transformer l'image en un ensemble d'images de résolution progressive. Cette hiérarchisation, couplée à un modèle capable d'adapter la précision de sa maille à la résolution de son espace de travail, permet d'estimer très rapidement les formes générales contenues dans une image. Une fois ceci fait, le modèle recherche les détails de plus en plus petits en s'appuyant successivement sur les différents niveaux de la pyramide.
  • Keywords:

    Three-dimensional Segmentation, Deformable Model, Three-dimensional Pyramid, Complex Topology, Triangulated Surface, Multi-scale.
  • Keywords (in french):

    Segmentation tridimensionnelle, modèle déformable, triangulation de surface, topologie variable, multi-résolution, pyramide tridimensionnelle.
  • Availability: Paper copy available.
  • Citation: French version published in proceedings of the 4th Conference on Discrete Geometry for Computer Imagery, Grenoble, France, 1994 and of the 10th Conference on Reconnaissance de Formes et Intelligence Artificielle, Rennes, France, 1996. Submitted to the 4th European Conference on Computer Vision, Cambridge, England, 1996 (english version).
  • Size: 2+29p
  • Format: Compressed PostScript
  • Get it

Co-inductive types in Coq : an experiment with the alternating bit protocol.

  • By: Eduardo Gimenez
  • Number: RR1995-38
  • Date: June 1995
  • Abstract:

    We describe an experience concerning the implementation and use of co-inductive types in the proof editor Coq. Co-inductive types are recursive types which, opposite to inductive ones, may be inhabited by infinite objects. In order to illustrate their use in Coq, we describe an axiomatisation of a calculus of broadcasting systems where recursive processes are represented using infinite objects. This calculus is used for developing a verification proof of the alternating bit protocol.
  • Abstract (in french):

    Dans cet article nous décrivons une expérience concernant l'implantation et l'utilisation de types co-inductifs dans l'environnement de preuves Coq. Les types co-inductifs sont des types recursifs qui, à la différence des types inductifs, peuvent etre habités par des objets infinis. Pour illustrer leur utilisation dans Coq nous décrivons comment axiomatiser un calcul de processus qui communiquent par diffusion, où les processus qui ne terminent pas sont représentés à l'aide des objets infinis. Ce calcul est utilisé pour développer une preuve de vérification du protocole du bit alterné.
  • Keywords:

    Program Verification, Type Theory, Co-Inductive Types, Communicating Processes.
  • Keywords (in french):

    Vérification de programmes, théorie des types, types co-inductifs, processus communicants.
  • Availability: Paper copy available.
  • Citation: Submitted to the 1995 Workshop on Types for Proof and Programs.
  • Size: 2+19p
  • Format: Compressed PostScript
  • Get it

Block cyclic array redistribution.

  • By: Loic Prylli , Bernard Tourancheau
  • Number: RR1995-39
  • Date: October 1995
  • Abstract:

    Implementing linear algebra kernels on distributed memory parallel computers raises the problem of data distribution of matrices and vectors among the processors. Block-cyclic distribution seems to suit well for most algorithms. But one has to choose a good compromise for the size of the blocks (to achieve a good efficiency and a good load balancing). This choice heavily depends on each operation, so it is essential to be able to go from one distribution to another very quickly. We present here the algorithms we implemented in the SCALAPACK library. A complexity study is then made that proves the efficiency of our solution. Timing results on a network of SUN workstations and the Cray T3D using PVM corroborates the results.
  • Abstract (in french):

    L'implantation de noyaux d'algèbre linéaire sur les machines parallèles à mémoire distribuée pose le problème du choix de la distribution des données pour les matrices et les vecteurs sur les différents processeurs. Une distribution bloc-cyclique semble convenir pour la plupart des algorithmes, mais un compromis est nécessaire dans le choix de la taille des blocs (pour avoir à la fois des calculs efficaces et une bonne répartition de charge). Le choix optimal est différent pour chaque algorithme, et il est donc essentiel de pouvoir passer d'une distribution à l'autre très rapidement. Nous présentons ici les algorithmes de redistribution que nous avons implantés dans la bibliothèque SCALAPACK. Une étude de complexité vient ensuite prouver l'efficacité des solutions choisies. Les performances obtenues sur réseaux de stations et Cray T3D en utilisant PVM corroborent nos résultats.
  • Keywords:

    Linear Algebra, Data Redistribution, HPF, Block Scattered, Block-cyclic.
  • Keywords (in french):

    Algèbre linéaire, redistribution de données, hpf, bloc-cyclique.
  • Availability: Electronic copy only.
  • Citation: Not published yet.
  • Size: 2+12p
  • Format: Compressed PostScript
  • Get it

The bouclettes loop parallelizer.

  • By: Pierre Boulet
  • Number: RR1995-40
  • Date: November 1995
  • Abstract:

    Bouclettes is a source to source loop nest parallelizer. It takes as input Fortran uniform, perfectly nested loops and gives as output an HPF (High Performance Fortran) program with data distribution and parallel ($HPF! INDEPENDENT) loops. This paper presents the tool and the underlying parallelization methodology.
  • Abstract (in french):

    Bouclettes est un paralléliseur source à source de nids de boucles. Il prend en entrée des boucles Fortran uniformes et parfaitement imbriquées et retourne en sortie un programme HPF (High Performance Fortran) avec une distribution des données et des boucles parallèles ($HPF! INDEPENDENT). Ce papier présente l'outil et les méthodes employées.
  • Keywords:

    Automatic Parallelization, Loop Nest, HPF, Compiler.
  • Keywords (in french):

    Parallélisation automatique, nid de boucles, hpf, compilation.
  • Availability: Paper copy available.
  • Citation: Not published yet.
  • Size: 2+13p
  • Format: Compressed PostScript
  • Get it

Distributed simulation of parallel computers.

  • By: Loic Prylli , Bernard Tourancheau
  • Number: RR1995-41
  • Date: December 1995
  • Abstract:

    We propose a method for emulating the behavior of your favorite MIMD computer on a network of workstations, so that programs written for the MIMD target can run on the distributed emulated version with just a recompilation. This is achieved by executing the computational parts as in the native run, with the message passing being simulated. The hardware of the target machine is simulated so that the behavior of the application is identical to a native run on the simulated computer with virtual timings and trace files. Moreover, our complexity analysis sets up the conditions required to achieve a good speedup as a function of the number of simulation hosts, the network latency and the granularity of the application.
  • Abstract (in french):

    Cet article présente nos travaux sur la simulation distribuée, dirigée par les événements, d'ordinateurs parallèles à mémoire distribuée. Nous décrivons nos algorithmes de simulation distribuée et l'analyse théorique des conditions nécessaires pour obtenir une bonne accélération de la simulation. Notre implémentation d'un tel simulateur permet, à partir d'une application écrite pour un ordinateur MIMD, une exécution sur un ensemble de stations de travail avec seulement une recompilation du code. La machine cible est simulée au niveau matériel de manière à ce que le comportement de l'application soit le même que sur l'ordinateur simulé avec le maintient de temps d'exécution virtuels et la construction des fichiers de traces correspondants. Les résultats obtenus corroborent notre étude de complexité et suggèrent le nombre de processeurs de la machine simulante, la granularité de l'application parallèle qui permettront d'obtenir une bonne efficacité de la simulation parallèle.
  • Keywords:

    Distributed Simulation, Parallel Computers, Performance Analysis, Non-intrusive Monitoring.
  • Keywords (in french):

    Simulation distribuée, ordinateurs parallèles, analyse de performances, monitoring non-intrusif.
  • Availability: Not available by FTP. Out of print.
  • Citation: Not published yet.
  • Size: 2+15p
  • Format: Compressed PostScript
  • Get it

A new guaranteed heuristic for the software pipelining problem.

  • By: Pierre-Yves Calland , Alain Darte , Yves Robert
  • Number: RR1995-42
  • Date: November 1995
  • Abstract:

    We present yet another heuristic for the software pipelining problem. We believe this heuristic to be of interest because it brings a new insight to the software pipelining problem by establishing its deep link with the circuit retiming problem. Also, in the single resource class case, our new heuristic is guaranteed, with a better bound than that of Gasperoni and Schwiegelshohn's heuristic. Finally, we point out that, in its simplest form, our algorithm has a lower complexity.
  • Abstract (in french):

    Nous présentons une nouvelle heuristique pour le problème du pipeline logiciel. Nous montrons, par cette nouvelle approche, l'existence d'un lien étroit entre le problème du pipeline logiciel et le problème de resynchronisation des circuits. De plus, nous montrons que dans le cas de ressources identiques, notre heuristique est garantie (avec une borne de garantie meilleure que celle obtenue pour l'heuristique de Gasperoni et Schwiegelshohn) et, dans sa forme non optimisée, une complexité moindre.
  • Keywords:

    Software Pipelining, Circuit Retiming, Guaranteed Heuristic, List Scheduling, Cyclic Scheduling.
  • Keywords (in french):

    Pipeline logiciel, resynchronisation de circuits, heuristiques garanties, ordonnancement de liste, ordonnancement cyclique.
  • Availability: Electronic copy only.
  • Citation: Not published yet.
  • Size: 2+24p
  • Format: Compressed PostScript
  • Get it

Code generation in bouclettes.

  • By: Pierre Boulet , Michele Dion
  • Number: RR1995-43
  • Date: November 1995
  • Abstract:

    Bouclettes is a source to source loop nest parallelizer. It takes as input Fortran uniform, perfectly nested loops and gives as output a HPF (High Performance Fortran) program with data distribution and parallel ($HPF! INDEPENDENT) loops. This paper explains how the HPF program is built from some scheduling and allocation functions automatically generated by Bouclettes.
  • Abstract (in french):

    Bouclettes est un paralléliseur source à source de nids de boucles. Il prend en entrée des boucles Fortran uniformes et parfaitement imbriquées et retourne en sortie un programme HPF (High Performance Fortran) avec une distribution des données et des boucles parallèles ($HPF! INDEPENDENT). Ce papier explique comment le programme HPF est construit à partir des fonctions d'ordonnancement et d'allocation générées automatiquement par Bouclettes.
  • Keywords:

    Automatic Parallelization, Loop Nest, HPF, Compiler, Code Generation.
  • Keywords (in french):

    Parallélisation Automatique, Nid De Boucles, HPF, Compilation, Génération De Code.
  • Availability: Paper copy available.
  • Citation: Not published yet.
  • Size: 2+21p
  • Format: Compressed PostScript
  • Get it

Evaluation of automatic parallelization strategies for HPF compilers.

  • By: Pierre Boulet , Thomas Brandes
  • Number: RR1995-44
  • Date: November 1995
  • Abstract:

    In the data parallel programming style the user usually specifies the data parallelism explicitly so that the compiler can generate efficient code without enhanced analysis techniques. In some situations it is not possible to specify the parallelism explicitly or this might be not very convenient. This is especially true for loop nests with data dependences between the data of distributed dimensions. In the case of uniform loop nests there are scheduling, mapping and partitioning techniques available. Some different strategies have been considered and evaluated with existing High Performance Fortran compilation systems. This paper gives some experimental results about the performance and the benefits of the different techniques and optimizations. The results are intended to direct the future development of data parallel compilers.
  • Abstract (in french):

    Dans le style de programmation data-parallèle, l'utilisateur spécifie habituellement le data-parallélisme explicitement de façon à permettre au compilateur de générer du code efficace sans techniques d'analyse avancées. Dans certaines situations, il n'est pas possible de spécifier le parallélisme explicitement ou ce n'est pas très pratique. C'est particulièrement vrai dans le cas des nids de boucles avec des dépendances entre les données des dimensions réparties. Dans le cas des nids de boucles uniformes, des techniques d'ordonnancement, d'allocation et de partitionnement sont disponibles. Des stratégies différentes ont été considérées et évaluées avec des systèmes de compilation d'High Performance Fortran existants. Ce rapport donne des résultats expérimentaux de performance et quantifie les bénéfices apportés par les différentes techniques et optimisations. Ces résultats ont pour but d'orienter le développement futur des compilateurs data-parallèles.
  • Keywords:

    Data Parallelism, High Performance Fortran, Loop Nests, Automatic Parallelization, Compilation, Optimization.
  • Keywords (in french):

    Data-parallélisme, high performance fortran, nids de boucles parallélisation automatique, compilation, optimisation.
  • Availability: Paper copy available.
  • Citation: Not published yet.
  • Size: 2+13p
  • Format: Compressed PostScript
  • Get it

Concurrent AVL revisited : self-balancing distributed search trees.

  • By: Luc Bouge , Joaquim Gabarro , Xavier Messeguer
  • Number: RR1995-45
  • Date: December 1995
  • Abstract:

    We address the concurrent insertion and deletion of keys in binary almost balanced search trees (AVL trees). We show that this problem can be studied through the self-reorganization of distributed systems of processes controlled by local evolution rules in the line of the approach of Dijkstra and Scholten. This yields a simple and abstract presentation of the insertion and deletion mechanisms. In particular, we show that our approach encapsulates a number of previous attempts described in the literature. They can in fact be seen as ad hoc specializations of the nondeterministic evolution rules. This solves in a very general setting an old question raised by H.T. Kung and P.L. Lehman: where should rotations take place to rebalance arbitrary trees ?
  • Abstract (in french):

    Nous considérons le problème de l'insertion et de l'élimination de clés dans les arbres binaires équilibrés de recherche (arbres AVL). Nous montrons que ce problème peut être abordé par l'étude de l'auto-organisation de systèmes répartis de processus dont l'évolution est exclusivement spécifiée par des règles locales d'évolution, dans l'esprit de l'approche de Dijkstra et Scholten. Ceci conduit à une présentation simple et abstraite des mécanismes d'insertion et d'élimination. En particulier, nous montrons que cette approche recouvre un certain nombre de propositions antérieures décrites dans la littérature. Ces propositions peuvent en fait être obtenues par des spécialisations des règles d'évolution non déterministes. Cette étude résout ainsi une question posée il y a 15 ans par H.T. Kung et P.L. Lehmann : où les rotations doivent-elles être appliquées pour rééquilibrer un arbre binaire arbitraire ?
  • Keywords:

    Distributed Algorithms, Search Trees, AVL Algorithm, Concurrent Generalized Rotations, Safety and Liveness Proofs.
  • Keywords (in french):

    Algorithmes répartis, arbres de recherche, algorithme AVL, rotations concurrentes généralisées, preuves de sûreté et de vivacité.
  • Availability: Paper copy available.
  • Citation: Extended abstract version submitted to the International Colloquium on Automata, Languages and Programming (ICALP'96), Padeborn, Germany, July 1996.
  • Size: 2+27p
  • Format: Compressed PostScript
  • Get it

Memory requirement for routing in distributed networks.

  • By: Cyril Gavoille , Stephane Perennes
  • Number: RR1995-46
  • Date: December 1995
  • Abstract:

    In this paper, we deal with the compact routing problem on distributed networks, that is implementing routing schemes that use a minimum memory size on each node. We prove that for every shortest path routing scheme, for any constant e, 0 < e < 1, and for every integer d such that 3 <= d <= en, there exists a n-node network of maximum degree d that locally requires at least Theta(n logd) bits of memory on Theta(n) nodes. This optimal lower bound means that whatever the routing scheme (interval routing, boolean routing, prefix routing, ...), there exists a network on which one can not do better than routing tables. Moreover, we prove that, for the well-known interval routing scheme, there exists a n-node network of bounded degree d, for every d >= 3, that requires Theta(n) intervals on Theta(n) links to code any shortest path routing function. This tight lower bound shows that, for networks of bounded degree, the interval routing scheme can be worst than the routing tables in term of size.
  • Abstract (in french):

    Dans cette étude nous nous intéressons au routage compact dans les réseaux distribués, c'est-à-dire à l'implémentation de fonctions de routage par des plus courts chemins dont le codage est minimal sur chaque routeur. Nous construisons des graphes de taille n et de degré borné par d tel que 3 <= d <= en pour une constante fixée e quelconque, 0 < e < 1, telle que la capacité mémoire nécessaire afin de router soit, sur une fraction constante des routeurs, d'au moins Theta(n log{d}) bits. Ceci signifie que sur ces réseaux, quelque soit le mode de routage (par intervalles, booléen, par préfixes, ...), certains routeurs devront mémoriser quasiment la table de routage in extenso. Enfin, ces graphes sont utilisés pour montrer qu'il existe des réseaux de degré borné par 3 où le routage par intervalles utilise Theta(n) intervalles sur Theta(n) arcs, ce qui nécessite plus de mémoire que les tables de routage.
  • Keywords:

    Communication On Parallel and Distributed Networks, Compact Routing Tables, Interval Routing, Shortest Path Routing.
  • Keywords (in french):

    Communication sur réseaux parallèles et distribués, tables de routages compactes, routage par intervalles, routages de plus courts chemins.
  • Availability: Paper copy available.
  • Citation: Published in the proceedings of PODC '96 - Best Student Paper Award.
  • Size: 2+23p
  • Format: Compressed PostScript
  • Get it

Marking techniques for extraction.

  • By: Frederic Prost
  • Number: RR1995-47
  • Date: December 1995
  • Abstract:

    Constructive logic can be used to consider program specifications as logical formulas. The advantage of this approach is to generate programs which are certified with respect to some given specifications. The programs created in such a way are not efficient because they may contain large parts with no computational meaning. The elimination of these parts is an important issue. Many attempts to solve this problem have been already done. We call this extracting procedure. In this work we present a new way to understand the extraction problem. This is the marking technique. This new point of view enables us, thanks to a high abstraction level, to unify what was previously done on the subject. It enables also to extend to higher-order languages some pruning techniques developed by Berardi and Boerio, which were only used in first and second order language.
  • Abstract (in french):

    La logique constructive peut être utilisée pour produire des programmes en les considérant comme des formules de la logique. L'avantage d'une telle méthodologie est de produire des programmes dont on est sûr qu'ils vérifient certaines spécifications. Les programmes générés par ces méthodes sont en général peu efficaces car ils comportent de larges parts qui ne servent pas au calcul final. Pour les repérer et les effacer, de nombreuses techniques ont déjà été développées. On parle de technique d'extraction. Dans ce travail nous donnons une nouvelle manière d'approcher ce problème. Il s'agit du marquage. Ce nouvel angle de vision permet, grâce à un niveau d'abstraction élevé, d'unifier les connaissances relatives à l'extraction. Il permet aussi l'extension aux ordres supérieurs des techniques de taillage exploitées par Berardi et Boerio, qui n'étaient valables qu'aux premier et au second ordre.
  • Keywords:

    Program Verification, Type Theory, Logic, Program Proof, Extraction, Marking.
  • Keywords (in french):

    Vérification de programmes, théorie des types, logique, preuves de programmes, extraction, marquage.
  • Availability: Paper copy available.
  • Citation: Not published yet.
  • Size: 2+35p
  • Format: Compressed PostScript
  • Get it

CAPNX, un environnement NX, PVM et MPI multi-utilisateurs sur MCS Capitan.

  • By: Loic Prylli
  • Number: RR1995-48
  • Date: December 1995
  • Abstract:

    We present here the use, the implementation and the performances, of the usual message-passing libraries NX, PVM and MPI on the Capitan machine. In particular, the implementation of a multi-user environment is described.
  • Abstract (in french):

    Nous présentons ici, l'utilisation, l'implémentation et les performances des bibliothèques classiques de communication par échanges de messages NX, PVM et MPI sur la machine Capitan. En particulier l'implémentation de l'environnement multi-utilisateurs est décrite.
  • Keywords:

    Parallel Computer, Capitan, CAPCASE, PVM, MPI.
  • Keywords (in french):

    Ordinateur parallèle, Capitan, CAPCASE, PVM, MPI.
  • Availability: Paper copy available.
  • Citation: Not published yet.
  • Size: 2+17p
  • Format: Compressed PostScript
  • Get it