Recoders for partial compression and rounding.

  • By: Marc Daumas , David W. Matula
  • Number: RR1997-01
  • Date: January 1997
  • Abstract:

    The purpose of this paper is to treat digit set conversions and digit recodings in terms of primitive recoding operations that have elementary implementations.The partial compressions and roundings are each associated with borrow-save or carry-save recodings implementable in one level of logic. Iterative utilization of recoding have application for : i) reducing the range of truncated lower order digits of a redundant binary operand to intervals less than a 2 ulp range (-1, 1) approaching 1 ulp, ii) truncating strings of leading insignificant digits in a redundant binary operand, iii) realizing Booth recoding for radices 2k, k >= 2, by realizing the symmetric minimal redundant digit set for 2k for all k bit substring of a redundant binary operand.
  • Abstract (in french):

    Le but de ce travail est de traiter les conversions entre systèmes d'écriture des nombres, et les conversions entre systèmes d'écriture des chiffres en termes d'opérations primitives de recodage qui possèdent une implantation élémentaire. La compression partielle et l'arrondi partiel associés avec les systèmes de notation redondante borrow-save ou carry-save sont alors implantés en un seul niveau de cellules logiques. En utilisant plusieurs fois ces cellules de recodage, nous obtenons les applications suivantes: i) on peut réduire le domaine de troncature des chiffres de poids faible d'un nombre redondant à un intervalle plus petit que l'intervalle usuel ]-1, 1[, jusqu'à approcher un intervalle de largeur 1 ulp ; ii) on peut supprimer les chiffres non significatifs de tête d'un nombre redondant sans modifier sa valeur ; iii) le codage de Booth en base 2k, k >= 2, est réalisé en utilisant l'ensemble de chiffres minimal symétrique redondant pour 2k à partir d'un nombre redondant quelconque.
  • Keywords:

    Computer Arithmetic, Floating Point Notation, Redundant Notation, Number Conversion.
  • Keywords (in french):

    Arithmétique des ordinateurs, Notation à virgule flottante, Notation redondante, Conversion.
  • Availability: Paper copy available.
  • Citation: Not published yet.
  • Size: 2+16p
  • Format: Compressed PostScript
  • Get it

Self-applicable partial evaluation for pi-calculus.

  • By: Marc Gengler , Matthieu Martel
  • Number: RR1997-02
  • Date: February 1997
  • Abstract:

    In this paper we are interested in self-applicable partial evaluation for pi-calculus, a language that models concurrent behavior of parallel systems. We use the usual three-step methodology : First, write a meta-interpreter for the language; Second, introduce an abstract analysis which determines which operations (communications) can be executed at compile-time; Finally exhibite the self-applicable partial evaluator and prove its correctness with respect to well-annotated pi-terms. This approach is compatible with Futamura's projections. Proofs of correctness are based on the notion of weak reduction equivalence.
  • Abstract (in french):

    L'évaluation partielle est une technique permettant de calculer à la compilation les parties statiques d'un programme. Nous nous intéressons ici à l'évaluation partielle du pi-calcul, un language qui modélise le comportement des systèmes concurrents et parallèles. Nous utilisons la méthodologie classique composée de trois étapes. La première consiste à écrire un méta-évaluateur pour le langage. Nous présentons ensuite une analyse abstraite visant à déterminer quelles opérations (ici des communications) peuvent être exécutées au moment de la compilation. Enfin nous proposons un évaluateur partiel auto-applicable et prouvons sa correction. Notre approche permet de conserver les projections de Futamura. Les preuves de correction utilisent la notion d'équivalence faible sous réduction.
  • Keywords:

    Partial Evaluation, Parallelism, Pi-Calculus, Meta-Interpretation, Binding-Time Analysis.
  • Keywords (in french):

    Evaluation partielle, Parallélisme, Pi-calcul, Méta-interprétation, Analyse abstraite.
  • Availability: Electronic copy only.
  • Citation: To appear in PEPM'97: ACM-SIGPLAN Workshop on Partial Evaluation and Semantics Based Program Manipulation, Amsterdam, 12-13 June 1997.
  • Size: 2+13p
  • Format: Compressed PostScript
  • Get it

Building and scheduling coarse grain task graphs.

  • By: Michel Cosnard , Emmanuel Jeannot
  • Number: RR1997-03
  • Date: February 1997
  • Abstract:

    It has been shown recently that it is possible to efficiently schedule direct acyclic task graphs. A tool like Pyrros [14] is able to generate a parallel program, if the user specifies precedence constraints between the tasks. This approach has two major drawbacks: it is hard for the user to perform a good analysis of the source code and scheduling a DAG is costly in terms of memory and time. In [3], a new model of parallel computation, the parameterized task graph is introduced. The Parameterized Task Graph (PTG) is a compact, problem size independent representation of some frequently used direct acyclic task graphs. In [4, 10], techniques and a tool (PlusPyr), are designed to generate such a representation from an annotated sequential program. In this report, we review the PTG and associated techniques, we give a general framework and an algorithm to dynamically schedule the parameterized graph and generate the associated code.
  • Abstract (in french):

    On a montré récemment qu'il est possible d'ordonnancer efficacement un graphe de tâches acyclique. Un outil comme Pyrros [14] est capable de générer un programme parallèle si l'utilisateur spécifie les contraintes de précédence entre les tâches. Cette approche a deux défauts majeurs : il est difficile pour l'utilisateur de faire une bonne analyse du code source et ordonnancer un graphe acyclique est coûteux en termes de temps et de mémoire. Dans [3], un nouveau modèle de calcul parallèle, le graphe de tâches paramétré a été introduit. Le GTP est une représentation compacte, indépendante de la taille du problème, de quelques graphes de tâches acycliques orientés fréquemment utilisés. Dans [4, 10], des techniques et un outil (PlusPyr) sont construit pour générer une telle représentation à partir d'un programme séquentiel annoté. Dans ce rapport, nous revoyons le GTP et les techniques associés, nous donnons une structure générale et un algorithme pour ordonnancer dynamiquement le graphe paramétré et générer le code associé.
  • Keywords:

    Automatic Parallelization, Task Graph, Affine Dependences, Static Scheduling, Dynamic Allocation.
  • Keywords (in french):

    Parallélisation automatique, Graphe de tâches, Dépendances affines, Ordonnancement statique, Allocation dynamique.
  • Availability: Electronic copy only.
  • Size: 2+19p
  • Format: Compressed PostScript
  • Get it

Finite Automata Theory in Coq A constructive proof of Kleene's theorem.

  • By: Jean-Christophe Filliatre
  • Number: RR1997-04
  • Date: February 1997
  • Abstract:

    We describe here a development in the system Coq of a piece of Finite Automata Theory. The main result is the Kleene's theorem, expressing that regular expressions and finite automata define the same languages. From a constructive proof of this result, we automatically obtain a functional program that compiles any regular expression into a finite automata, which constitutes the main part of the implementation of grep-like programs. This functional program is obtained by the automatic method of extraction which removes the logical parts of the proof to keep only its informative contents. Starting with an idea of what we would have written in ML, we write the specification and do the proofs in such a way that we obtain the expected program, which is therefore efficient.
  • Abstract (in french):

    Nous décrivons dans cet article un développement dans le système Coq d'une partie de la Théorie des Automates Finis. Le principal résultat est le théorème de Kleene, qui établit que les expressions rationnelles et les automates finis définissent la même classe de langages. A partir d'une preuve constructive de ce résultat, on obtient automatiquement un programme fonctionnel qui compile une expression rationnelle en un automate fini, ce qui constitue la partie critique de l'implémentation des programmes du style grep. Ce programme fonctionnel est obtenu par la méthode automatique d'extraction qui supprime les parties logiques de la preuve pour ne conserver que son contenu informatif. Avec en tête l'idée du programme ML que l'on aurait écrit directement, on écrit la spécification et on mène les preuves de manière à obtenir le programme voulu, qui est par conséquent efficace.
  • Keywords:

    Automata Theory, Proof-checkers, Calculus of Constructions, Specification, Extraction, Program Validation.
  • Keywords (in french):

    Théorie des automates, Preuves formelles, Calcul des constructions, Spécification, Extraction, Validation de programmes.
  • Availability: Paper copy available.
  • Size: 2+19p
  • Format: Compressed PostScript
  • Get it

Etude des cercles discrets via les automates cellulaires.

  • By: Laure Tougne
  • Number: RR1997-05
  • Date: March 1997
  • Abstract:

    In this report, we first introduce the discrete circles and define more precisely some of them. Afterwards, we study them with the help of cellular automata. So, we show that if we consider that a discrete circle is a succession of horizontal, vertical and diagonal segments which lean on a beam of parabolas, we can describe it by local properties and so, construct it by cellular automata. A part of this report is dedicated to the digitization of beams of parabolas. Afterwards we succesively examine the arithmetical circles and the Pitteway's circles. Finally in the last part, which is more general, we study the intersection between a given real circle and the grid.
  • Abstract (in french):

    Dans ce rapport, après avoir introduit les cercles discrets et défini plus précisément certains d'entre eux, nous les étudions à l'aide des automates cellulaires. Ainsi, nous montrons que si on considère un cercle discret comme étant une succession des segments horizontaux, verticaux et diagonaux s'appuyant sur un faisceau de paraboles alors, nous pouvons le décrire à l'aide de propriétés locales et donc le construire par automate cellulaire. Une partie de ce rapport est consacrée à la discrétisation des faisceaux de paraboles. Nous étudions ensuite, successivement les cercles de Pitteway et cercles arithmétiques. Enfin la dernière partie, plus générale, étudie les intersections entre un cercle réel donné et la grille.
  • Keywords:

    Discrete Circles, Digitization, Discrete Parabolas, Construction, Two-dimensional Cellular Automata.
  • Keywords (in french):

    Cercles discrets, Discrétisation, Paraboles discrètes, Construction, Automates cellulaires 2D.
  • Availability: Paper copy available.
  • Citation: A short version has been accepted to DGCI'96.
  • Size: 2+33p
  • Format: Compressed PostScript
  • Get it

Genetic detumbling a satellite.

  • By: Dimitri C. Dracopoulos
  • Number: RR1997-06
  • Date: March 1997
  • Abstract:

    The genetic programming approach is applied to a highly nonlinear control problem, the attitude control problem. A rigid body satellite is detumbled and controlled by using the control law derived by GP. It is shown that the discovered control regime is stable.
  • Abstract (in french):

    L'approche de la programmation génétique est appliquée à un problème de contrôle qui est fortement non linéaire : le problème du contrôle de la position. Les tendances à la rotation d'un satellite à corps rigide sont stoppées et controlées grâce à une loi de contrôle dérivée de la programmation génétique. On montre que le régime de contrôle ainsi découvert est stable.
  • Keywords:

    Genetic Programming, Control, Satellite.
  • Keywords (in french):

    Programmation génétique, Contrôle, Satellite.
  • Availability: Paper copy available.
  • Citation: Preprint of Genetic Programming 1997 Conference, Stanford, USA accepted paper.
  • Size: 2+7p
  • Format: Compressed PostScript
  • Get it

An extended comparison of slotted and unslotted deflection routing.

  • By: Thierry Chich , Pierre Fraigniaud
  • Number: RR1997-07
  • Date: March 1997
  • Abstract:

    In this paper, we have experimentally compared synchronized versus asynchronized all-optical deflection networks. The originality of our approach is first that we have included a model of bursty traffic : it is simulated by a bi-Poissonian emission. Second, we have compared four routing modes : synchronous mode, partially synchronous mode, and asynchronous modes with fixed and bounded size packets. All modes were considered under the same emission protocols. More precisely, we have run the several experiments with a careful attention to the several time scalings related to these different modes. Our experiments mainly show that the natural decrease of the performances of the asynchronous mode, compared to the synchronous mode, can be balanced in a significant way by the use of a sophisticated routing algorithm. Moreover, we have also shown that asynchronous routing is not very sensitive to bursty traffic. These results, and the fact that asynchronous networks are easier to design, and cheaper to build than synchronous networks, show the practical interest of asynchronous deflection routing.
  • Abstract (in french):

    Nous avons expérimentalement comparé l'effet du synchronisme ou de l'asynchronisme pour le routage par déflexion dans des réseaux tout-optiques. L'originalité de notre approche est d'avoir intégré un modèle de trafic sporadique, sous la forme d'émissions bipoissonniennes. Elle est aussi dans le fait que nous avons comparé quatre modes de routage : mode synchrone, mode partiellement synchrone, et modes asynchrones avec messages de taille fixe ou de taille bornée. Tous ces modes ont été examinés à partir du même protocole d'émission. Plus précisément, nous avons veillé attentivement au respect des différentes échelles de temps que nous avons dû considérer. Nos expérimentations montrent essentiellement que la dégénerescence naturelle des performances du mode asynchrone comparées à celles du mode synchrone peut être contrebalancée par un mode de routage asynchrone plus astucieux. De plus, nous montrons que les réseaux asynchrones sont moins sensibles aux trafics sporadiques. Ces résultats, accentués par le fait que les réseaux asynchrones sont plus simples et moins chers à construire, montrent l'intérêt pratique des réseaux à déflexion asynchrone.
  • Keywords:

    All-optical Networks, Deflection Routing.
  • Keywords (in french):

    Réseaux transparents, Routage par déflexion.
  • Availability: Paper copy available.
  • Citation: Not published yet.
  • Size: 2+17p
  • Format: Compressed PostScript
  • Get it

Some bounds on the computational power of Piecewise Constant Derivative systems.

  • By: Olivier Bournez
  • Number: RR1997-08
  • Date: April 1997
  • Abstract:

    We study the computational power of Piecewise Constant Derivative (PCD) systems. PCD systems are dynamical systems defined by a piecewise constant differential equation and can be considered as computational machines working on a continuous space with a continuous time. We show that the computation time of these machines can be measured either as a discrete value, called discrete time, or either as a continuous value, called continuous time. We relate the two notions of time for general PCD systems. We prove that general PCD systems are equivalent to Turing machines and linear machines in finite discrete time. We prove that the languages recognized by purely rational PCD systems in dimension d in finite continuous time are precisely the languages of the d-2th level of the arithmetical hierarchy. Hence the reachability problem of purely rational PCD systems of dimension d in finite continuous time is Sigma d-2-complete.
  • Abstract (in french):

    Nous étudions la puissance de calcul des systèmes à dérivée constante par morceaux (PCD systems). Les systèmes PCD sont des systèmes dynamiques définis par une équation différentielle constante par morceaux. Ils peuvent être vus comme des modèles de calcul évoluant sur espace continu avec un temps continu. Nous montrons que le temps de calcul sur ces machines peut être mesuré soit par une valeur discrète ``le temps discret'', soit par une valeur réelle ``le temps continu''. Nous relions ces deux notions de temps. Nous prouvons que les systèmes PCD sont équivalent aux machines de Turing et aux machines linéaires en temps discret fini. Nous prouvons que les langages reconnus par les systèmes PCD purement rationnels en dimension d en temps continu fini coincident avec les langages du d-2ieme niveau de la hiérarchie arithmétique. Ainsi le problème de l'atteignabilité pour les systèmes PCD purement rationnels de dimension d est Sigma d-2 complet.
  • Keywords:

    Real Computability, Continuous Time Computations, Dynamical Systems, Arithmetical Hierarchy.
  • Keywords (in french):

    Calculabilité réelle, Calculs en temps continu, Systèmes dynamiques, Hiérarchie arithmétique.
  • Availability: Paper copy available.
  • Citation: A preliminary version can be found in the proceedings of ICALP'97.
  • Size: 2+30p
  • Format: Compressed PostScript
  • Get it

ML type inference for Dead Code Analysis.

  • By: Frederic Prost
  • Number: RR1997-09
  • Date: May 1997
  • Abstract:

    We propose to adapt ML type inference algorithm to find and erase dead-code in simply typed lambda-terms. We prove the correctness of our optimization : the optimized program is observationnaly equivalent to the original one. This paper also sheds new lights on links between typing and static analyses, in the particular case of dead code analysis. Indeed, the same algorithm can be used both for typing and dead-code analysis. Moreover, it appears new to the author that ML type inference can be used to represent links as encountered in data flow analyses.
  • Abstract (in french):

    Nous proposons d'adapter l'algorithme d'inférence de type de ML pour trouver et effacer le code mort de lambda-termes simplement typés. Nous prouvons la correction de notre optimisation : le programme optimisé est observationnellement équivalent à l'original. Ce papier éclaire d'une manière nouvelle les liens entre le typage et l'analyse statique, dans le cas particulier de l'analyse de code mort. En effet, le même algorithme peut être utilisé à la fois pour le typage et l'analyse de code mort. De plus, il apparaît nouveau à l'auteur que l'inférence de type à la ML soit utilisée pour représenter les liens rencontrés dans les analyses de types flots de données.
  • Keywords:

    ML Type Inference, Dead-Code Analysis, Polymorphism, Extraction.
  • Keywords (in french):

    Inférence de Type à la ML, Analyse de code mort, Polymorphisme, Extraction.
  • Availability: Paper copy not available.
  • Size: 2+14p
  • Format: Compressed PostScript
  • Get it

Detecting and Removing Dead Code using Rank 2 Intersection.

  • By: Frederic Prost
  • Number: RR1997-10
  • Date: May 1997
  • Abstract:

    In this paper we extend, by allowing rank 2 intersection types, the type assignment system for the detection and elimination of dead code in typed functional programs presented by Coppo et al Giannini and the first author in the Static Analysis Symposium'96.The main application of this method is the optimization of programs extracted from proofs in logical frameworks, but it could be used as well in the elimination of dead code determined by program specialization. This system rely on annotated types which allow to exploit the type structure of the language for the investigation of program properties. The detection of dead code is obtained via annotated type inference, which can be performed in a complete way, by reducing it to the solution of a system of inequalities between annotation variables. Even though the language considered in the paper is the simply typed lambda-calculus with cartesian product, if-then-else, fixpoint, and arithmetic constants we can generalize our approach to polymorphic languages like Miranda, Haskell, and CAML.
  • Abstract (in french):

    Dans ce papier nous étendons, en permettant des types d'intersections de rang 2, un système d'inférence de types pour la détection et l'élimination du code mort dans les programmes fonctionnels typés présenté par Coppo et al Giannini dans le Static Analysis Symposium'96. La principale application de cette méthode est l'optimisation de programmes extraits de preuves, mais il peut aussi bien être utilisé pour l'élimination du code mort produit par la spécialisation de programmes. Ce système repose sur des types annotés qui permettent d'exploiter la structure des types du langage pour trouver des propriétés sur un programme. La détection du code mort est obtenue via un système d'inférence de types. L'inférence peut être réalisée en réduisant le problème à la solution d'un système d'inégalités entre les variables d'annotations. Bien que le langage considéré soit le lambda-calcul simplement typé étendu par le produit cartésien, le if-then-else, le point fixe et des constantes arithmétiques, nous pouvons généraliser notre approche aux langages polymorphes tels que Miranda, Haskell et CAML.
  • Keywords:

    Intersection Types, Dead-Code Analysis, Annotated Types.
  • Keywords (in french):

    Types intersection, Analyse de code mort, Types annotés.
  • Availability: Paper copy available.
  • Citation: Not published yet.
  • Size: 2+23p
  • Format: Compressed PostScript
  • Get it

PPCM : une mise à jour.

  • By: Fabien Feschet , Jean-Marc Pierson , Remy Sanlaville
  • Number: RR1997-11
  • Date: May 1997
  • Abstract:

    We present in this report the advances in PPCM, a Parallel Portable Communication Module. This environment, built as a friendly and portable way of programming MIMD machines has been developed in three main fields : the notion of group of processors has been added, a new data redistribution scheme ParList which allows overlapping of partitions and finally a distributed graphic interface to the parallel machine, PpcmX. We present here the implementation of these three new paradigm of programmation in our environment.
  • Abstract (in french):

    Nous présentons dans ce rapport un travail concernant les avancées dans l'implémentation de nouvelles fonctionnalités à PPCM, notre module de communication parallèle et portable. Cet environnement, conçu pour aider à la programmation portable des machines MIMD a été développé ces derniers temps dans 3 directions principales : une notion de groupe de processeurs, une nouvelle primitive de redistribution de données ParList qui permet le recouvrement des partitions, et enfin une interface graphique distribuée à la machine parallèle, PpcmX. Nous présentons ici l'implémentation de ces trois nouveaux paradigmes de programmation dans notre environnement.
  • Keywords:

    Parallel Portable, Groups, Load Balancing, Distributed Graphical System.
  • Keywords (in french):

    Parallèle Portable, Groupes, Equilibrage, Système Graphique Distribué.
  • Availability: Paper copy available.
  • Size: 2+34p
  • Format: Compressed PostScript
  • Get it

Asynchronous Sub-Logarithmic Adders.

  • By: Jean-Michel Muller , Arnaud Tisserand , Jean-Marc Vincent
  • Number: RR1997-12
  • Date: May 1997
  • Abstract:

    Fast arithmetic operators have always been an important topic in computer design. There are two kinds of arithmetic operators : fixed-time and variable-time ones. While fixed-time arithmetic operators have been widely studied, variable-time operators seem to be more and more interesting for low-power design and very high performance computing. Self-timed arithmetic operators are able to deliver their result in an average computation time less than the worst case time. We present an architecture, which is a variant of the carry select adder, for the addition of n-bit numbers with a O(sqrt(log_2 n)) average computation time.
  • Abstract (in french):

    La conception d'opérateurs arithmétiques rapides est un enjeu important dans la réalisation d'un ordinateur. Il existe deux types d'opérateurs arithmétiques : ceux à délai fixe et ceux à délai variable. Tandis que les opérateurs à délai fixe ont été beaucoup étudiés dans le passé, les opérateurs à délai variable semblent très prometteurs pour les réalisations basse consommation et pour le calcul haute performance. Les opérateurs auto-séquencés délivrent leur résultat dans un temps moyen beaucoup plus petit que le temps dans le pire cas. Nous présentons ici une nouvelle architecture, basée sur l'additionneur à sélection de la retenue, pour laquelle le temps moyen d'une addition de deux nombres de n chiffres est en O(sqrt(log n)).
  • Keywords:

    Computer Arithmetic, Asynchronous Operators, Addition.
  • Keywords (in french):

    Arithmétique des ordinateurs, opérateurs asynchrones, addition.
  • Availability: Paper copy available.
  • Citation: Published in IEEE Pacific Rim Conference on Communication, Computers and Signal Processing (PACRIM97), Victoria, Canada, August 1997.
  • Size: 2+9p
  • Format: Compressed PostScript
  • Get it

Concurrent rebalancing of AVL trees: a fine-grained approach.

  • By: Luc Bouge , Joaquim Gabarro , Xavier Messeguer, Nicolas Schabanel
  • Number: RR1997-13
  • Date: May 1997
  • Abstract:

    We address the concurrent rebalancing of almost balanced binary search trees (AVL trees). Such a rebalancing may for instance be necessary after successive insertions and deletions of keys. We show that this problem can be studied through the self-reorganization of distributed systems of nodes controlled by local evolution rules in the line of the approach of Dijkstra and Scholten. This yields a much simpler algorithm that the ones previously known. As a by-product, 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 search trees?.
  • Abstract (in french):

    Ce rapport présente un algorithme concurrent pour la gestion dynamique d'un arbre binaire de recherche équilibré (Arbre AVL). Une série d'insertions et de suppressions de clés dans un tel arbre peut lui donner une forme arbitraire. Nous montrons dans ce papier que le rééquilibrage de la structure peut être vu comme une auto-réorganisation d'un système distribué formé par les noeuds, dirigée par quelques règles d'évolutions locales. Cette approche mène à un algorithme bien plus simple que les solutions précédentes connues. De plus, ce résultat permet de répondre à la question posée par H.T. Kung et P.L.Lehman : ``Peut-on effectuer les rotations dans un ordre quelconque pour rééquilibrer un arbre arbitraire ?''. La réponse est : ``Oui''.
  • Keywords:

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

    Algorithmes concurrents, Arbres de recherche, Arbre AVL, Insertions et suppressions concurrentes, Rotations concurrentes généralisées, Preuves de terminaison distribuée.
  • Availability: Electronic copy only.
  • Citation: A shorter version has been accepted to Euro-Par'97.
  • Size: 2+17p
  • Format: Compressed PostScript
  • Get it

Achilles and the Tortoise climbing up the hyper-arithmetical hierarchy.

  • By: Olivier Bournez
  • Number: RR1997-14
  • Date: May 1997
  • Abstract:

    We study the computational power of rational Piecewise Constant Derivative (PCD) systems. PCD systems are dynamical systems defined by a piecewise constant differential equation and can be considered as computational machines working on a continuous space with a continuous time. We prove that the languages recognized by rational PCD systems in dimension d=2k+3 (respectively: d=2k+4), k >= 0, in finite continuous time are precisely the languages of the omega ^k th (resp. omega ^k +1 th) level of the hyper-arithmetical hierarchy. Hence the reachability problem for rational PCD systems of dimension d=2k+3 (resp. d=2k+4), k >0 , is hyper-arithmetical and is Sigma_{omega ^k}-complete (resp. Sigma_{omega ^k +1}-complete).
  • Abstract (in french):

    Nous étudions la puissance de calcul des systèmes à dérivée constante par morceaux (systèmes PCD) à coefficients rationnels. Les systèmes PCD sont des systèmes dynamiques définis par une équation différentielle constante par morceaux. Ils peuvent être vus comme des modèles de calcul évoluant sur espace continu avec un temps continu. Nous prouvons que les langages reconnus par des systèmes PCD rationnels en dimension d=2k+3 (respectivement: d=2k+4), k >= 0, en temps continu fini sont précisément les langages du omega ^k ieme (resp. omega ^k+1 ieme) niveau de la hiérarchie hyper-arithmétique. Ainsi le problème de l'atteignabilité des systèmes PCD de dimension d=2k+3 (resp. d=2k+4), k >0 , est hyper-arithmétique et est Sigma_{omega ^k}-complet (resp. Sigma_{omega ^k+1}-complet).
  • Keywords:

    Real Computability, Continuous Time Computations, Dynamical Systems, Hyper-Arithmetical Hierarchy.
  • Keywords (in french):

    Calculabilité réelle, Calculs en temps continu, Hiérarchie hyper-arithmétique, Systèmes dynamiques.
  • Availability: Paper copy available.
  • Citation: Not published yet.
  • Size: 2+49p
  • Format: Compressed PostScript
  • Get it

Tiling with limited resources.

  • By: Pierre-Yves Calland , Jack Dongarra , Yves Robert
  • Number: RR1997-15
  • Date: May 1997
  • Abstract:

    In the framework of perfect loop nests with uniform dependences, tiling has been extensively studied as a source-to-source program transformation. Little work has been devoted to the mapping and scheduling of the tiles on to physical processors. We present several new results in the context of limited computational resources, and assuming communication-computation overlap. In particular, under some reasonable assumptions, we derive the optimal mapping and scheduling of tiles to physical processors.
  • Abstract (in french):

    Dans le cadre de l'étude des nids de boucles parfaits à dépendances uniformes, le partitionnement a été largement étudié en tant que technique de réécriture du programme source. Peu de travaux ont été consacrés à l'allocation et à l'ordonnancement des tuiles sur les processeurs physiques. Nous présentons plusieurs résultats dans le contexte de ressources de calcul limitées, et de recouvrement calculs-communications. En particulier, sous un certain nombre d'hypothèses raisonnables, nous calculons l'allocation et l'ordonnancement optimaux des tuiles sur les processeurs physiques.
  • Keywords:

    Tiling, Communication-Computation Overlap, Mapping, Limited Resources.
  • Keywords (in french):

    Partitionnement, Recouvrement calculs-communications, Allocation, Ressources limitées.
  • Availability: Paper copy available.
  • Citation: To appear in Application Specific Array Processors ASAP'97 Proceedings.
  • Size: 2+19p
  • Format: Compressed PostScript
  • Get it

A logical framework to prove properties of Alpha programs (revised version).

  • By: Luc Bouge , David Cachera
  • Number: RR1997-16
  • Date: May 1997
  • Abstract:

    We present an assertional approach to prove properties of Alpha programs. Alpha is a functional language based on affine recurrence equations. We first present two kinds of operational semantics for Alpha together with some equivalence and confluence properties of these semantics. We then present an attempt to provide Alpha with an external logical framework. We therefore define a proof method based on invariants. We focus on a particular class of invariants, namely canonical invariants, that are a logical expression of the program's semantics. We finally show that this framework is well-suited to prove partial properties, equivalence properties between Alpha programs and properties that we cannot express within the Alpha language.
  • Abstract (in french):

    Nous présentons une méthode de preuve par assertions pour les programmes Alpha. Alpha est un langage fonctionnel d'équations récurrentes affines. Nous présentons tout d'abord deux types de sémantiques opérationnelles pour Alpha, ainsi que des propriétés d'équivalence et de confluence de ces sémantiques. Nous munissons ensuite Alpha d'un cadre logique externe au langage. Nous définissons pour cela une méthode de preuve fondée sur l'utilisation d'invariants. Nous insistons sur une classe particulière d'invariants, les invariants canoniques. Nous montrons finalement que ce cadre permet de prouver des propriétés partielles, des équivalences de programmes et surtout des propriétés non exprimables en Alpha.
  • Keywords:

    Concurrent programming, Recurrence Equations, Specifying and Verifying and Reasoning About Programs, Semantics of Programming Languages, Data-Parallel Languages, Proof Methodology, Invariants.
  • Keywords (in french):

    Programmation parallèle, Equations récurrentes, Spécification et Validation de programmes, Sémantique des langages de programmation, Langages data-parallèles, Méthode de preuve, Invariants.
  • Availability: Electronic copy only.
  • Citation: Published in ASAP'97 Conference proceedings, Zurich, Switzerland, 1997.
  • Size: 2+16p
  • Format: Compressed PostScript
  • Get it

Loop parallelization algorithms : from parallelism extraction to code generation.

  • By: Pierre Boulet , Alain Darte , Georges-Andre Silber , Frederic Vivien
  • Number: RR1997-17
  • Date: June 1997
  • Abstract:

    In this paper, we survey loop parallelization algorithms, analyzing the dependence representations they use, the loop transformations they generate, the code generation schemes they require, and their ability to incorporate various optimizing criteria such as maximal parallelism detection, detection of permutable loops , minimization of synchronizations, easiness of code generation, etc. We complete the discussion by presenting new results related to code generation and loop fusion for a particular class of multi-dimensional schedules, called shifted linear schedules. We demonstrate that algorithms based on such schedules, while generally considered as too complex, can indeed lead to simple codes.
  • Abstract (in french):

    Dans ce rapport, nous présentons divers algorithmes de parallélisation, en prenant en compte la représentation des dépendances qu'ils utilisent, les transformations de boucle qu'ils génèrent, les techniques de génération de code dont ils ont besoin, et enfin, leur capacité à incorporer divers critères d'optimisation tels que la détection du parallélisme maximal, la détection de boucles permutables, la minimisation des synchronisations, la simplicité de la génération de code, etc... Nous complétons notre discussion par la présentation de nouveaux résultats liés à la génération de code et à la fusion de boucles pour une classe particulière d'ordonnancements multi-dimensionnels appelés ordonnancements linéaires décalés. Nous montrons que des algorithmes qui se fondent sur de tels ordonnancements, souvent considérés comme trop complexes, peuvent néanmoins générer des codes simples.
  • Keywords:

    Automatic Parallelization, Nested Loops, Parallelization Algorithms, Loop Fusion, Synchronizations, Code Generation.
  • Keywords (in french):

    Parallélisation automatique, Boucles imbriquées, Algorithmes de parallélisation, Fusion de boucles, Synchronisations, Génération de code.
  • Availability: Paper copy available.
  • Citation: Not published yet.
  • Size: 2+30p
  • Format: Compressed PostScript
  • Get it

An Algorithm that Computes a Lower Bound on the Distance Between a Segment and $Z^2$.

  • By: Vincent Lefevre
  • Number: RR1997-18
  • Date: June 1997
  • Abstract:

    We give a fast algorithm for computing a lower bound on the distance between a straight line and the points of a regular grid. This algorithm is used to find worst cases when trying to round the elementary functions correctly in floating-point arithmetic, which consists in returning the machine number that is the closest (there are other rounding modes) to the exact result.
  • Abstract (in french):

    Nous donnons un algorithme rapide permettant de calculer une minoration de la distance entre un segment de droite et les points d'une grille régulière. Cet algorithme est utilisé pour trouver les pires cas lorsque l'on arrondit exactement les fonctions élémentaires en arithmétique à virgule flottante, ce qui consiste à renvoyer le nombre machine le plus proche (il existe d'autres modes d'arrondi) du résultat exact.
  • Keywords:

    Elementary Functions, Floating-Point Arithmetic, Rounding.
  • Keywords (in french):

    Fonctions élémentaires, Arithmétique virgule-flottante, Arrondi.
  • Availability: Paper copy available.
  • Citation: Not published yet.
  • Size: 2+9p
  • Format: Compressed PostScript
  • Get it

Deriving Proof Rules Form Continuations Semantics.

  • By: Philippe Audebaud , Elena Zucca
  • Number: RR1997-19
  • Date: June 1997
  • Abstract:

    We claim that the continuation style semantics of a programming language can provide a starting point for constructing a proof system for that language. The basic idea is to see weakest precondition as a particular instance of continuation style semantics, hence to interpret correctness assertions (e.g. Hoare triples {p}C{r}) as inequalities over continuations. This approach also shows a correspondence between labels in a program and annotations.
  • Abstract (in french):

    Nous montrons comment la sémantique par continuations peut servir de point de départ pour construire un système de preuves pour ce langage. L'idée clé est de voir la plus faible précondition comme une sémantique par continuations particulière, puis d'interpréter les assertions à la Hoare ({p}C{r}) comme des inégalités portant sur les continuations. Cette approche permet également d'établir une correspondance entre étiquettes dans un programme et annotations.
  • Keywords:

    Continuations, Hoare Semantics, Exceptions, Labels.
  • Keywords (in french):

    Continuations, Semantique a la Hoare, Exceptions, Labels.
  • Availability: Paper copy available.
  • Citation: Not published yet.
  • Size: 2+19p
  • Format: Compressed PostScript
  • Get it

On the compilation of data-parallel languages on a distributed memory multithreaded environment with thread migration.

  • By: Christian Perez , Raymond Namyst
  • Number: RR1997-20
  • Date: July 1997
  • Abstract:

    This paper focuses on the use of distributed memory multithreaded environments in data parallel programs and has two main goals. The first is to show that data parallel programs can support features like communication overlapping, load balancing without global data parallel object redistribution and the efficient use of clusters of uniprocessor and/or symmetric multiprocessors (SMPs). Our extended model introduces virtual processes. Virtual processes are implemented with mobile threads. The second goal is to determine the interactions between data parallel programs and a model of distributed memory multithreaded environments, with respect to intra-node communications and especially to thread migration. This paper also discuss this multithreaded environment with respect to the different models of threads and shows that the HPF and the C* data parallel compilation models easily integrate the proposed model.
  • Abstract (in french):

    Ce papier s'intéresse à l'utilisation des environnements multithread (processus légers) à mémoire distribuée dans les programmes data parallèles. Il vise deux objectifs principaux. Le premier est de montrer que les programmes data parallèles peuvent intégrer des caractéristiques comme le recouvrement des communications par les calculs, l'équilibrage de charge sans redistribution globale des objets data parallèles et l'exploitation efficace des groupes de machines uniprocesseurs et/ou multiprocesseurs symétriques (SMP). Notre modèle étendu introduit les processus virtuels. Les processus virtuels sont implémentés à l'aide de threads mobiles. Le second but du papier est de déterminer les interactions entre les programmes data parallèles et un modèle d'environnement multithread à mémoire distribuée vis à vis des communications intra noeud et particulièrement vis à vis de la migration de threads. Ce papier situe aussi cet environnement de thread par rapport aux autres modèles de thread et montre que les modèles de compilation data parallèles de HPF et C* s'intègrent facilement dans le modèle proposée.
  • Keywords:

    Data-Parallel Languages, Compilation, Distributed Memory Multithreaded Environment, Thread Migration.
  • Keywords (in french):

    Langages data-parallèles, Compilation, Environnement multithread à mémoire distribuée, Migration de threads.
  • Availability: Electronic copy only.
  • Citation: Not published yet.
  • Size: 2+16p
  • Format: Compressed PostScript
  • Get it

A shift-invariant metric on $S^Z$ inducing a non-trivial topology.

  • By: Gianpiero Cattaneo , Enrico Formenti , Luciano Margara , Jacques Mazoyer
  • Number: RR1997-21
  • Date: July 1997
  • Abstract:

    In this paper we discuss the meaning of sensitivity and its implications in CA behavior. A new shift-invariant metric is given. The metric topology induced by this metric is perfect but not compact. Moreover we prove that the new space is ``suitable" for the study of the dynamical behavior of CA. In this context sensitivity assumes a stronger meaning than before (usually $\SZ$ is given the product topology). Now cellular automata are sensitive if they are not only capable of ``transporting" the information but if they are also able to create new information. Finally we prove that additive CA which presents space-time diagrams with complicated structure are sensitive to initial conditions.
  • Abstract (in french):

    Dans cet article nous parlons de la signification de la sensibilité et de ses implications au comportement des AC. Une nouvelle métrique invariante par translation est donné. La topologie induite par cette métrique est parfaite mais elle n'est pas compacte. On prouve que ce nouvel espace est ``propice'' à l'étude du comportement de la dynamique des AC. Dans ce contexte, la notion de sensibilité prend une signification plus puissante. Pour être sensibles les AC ne doivent pas seulement \^etre capables de transporter de l'information mais aussi capables de créer de nouvelles informations. Finalement nous prouvons que les AC additifs avec un diagramme d'espace-temps avec une structure complique sont sensibles aux conditions initiales.
  • Keywords:

    Cellular Automata, Sensitivity to Initial Conditions, Metric Topology.
  • Keywords (in french):

    Automates cellulaires, Sensibilité aux conditions initiales, Topologie métrique.
  • Availability: Electronic copy only.
  • Citation: An early version of the paper is accepted at MFCS'97.
  • Size: 2+17p
  • Format: Compressed PostScript
  • Get it

Protocol design for high performance networking: a Myrinet experience.

  • By: Loic Prylli , Bernard Tourancheau
  • Number: RR1997-22
  • Date: July 1997
  • Abstract:

    High speed networks are now providing incredible performance. Software evolution is slow and the old protocol stacks are no longer adequate for these kind of communication speeds. When bandwidth increases, the latency should decrease as much in order to keep the system balance. With the current network technology, the main bottleneck is most often the software that is the interface between the hardware and the user. We designed and implemented new transmission protocols, targeted to parallel computing, that squeeze the most out of a high speed network (Myrinet in this paper) without wasting time in system calls or memory copies, giving all the speed to the applications. This design is presented here as well as experimental results. We achieve Gigabit/s bandwidth and less than 5us latency on a cluster of PC workstations with inexpensive network hardware. Moreover, our results compare favorably with the expensive parallel computers or ATM LANs.
  • Abstract (in french):

    Les réseaux haut-débits proposent maintenant des performances incroyables. L'évolution des logiciels est plus lente et les vieilles piles de protocoles ne sont plus adaptées. Lorsque la bande passante augmente, les latences doivent aussi diminuer pour maintenir un système équilibré. Avec les technologies actuelles de réseaux haut-débits, le goulot d'étranglement le plus courant est l'interface logicielle entre le matériel et l'utilisateur. Nous avons conçu et implémenté de nouveaux protocoles spécifiques, destinés au calcul parallèle, qui permettent d'obtenir des performances proches de celles du matériel (Myrinet dans notre étude). Ceci sans perdre de temps en appels systèmes ou recopies mémoires, laissant toutes les performances disponibles pour l'application. Nous présentons ici la conception et les résultats expérimentaux de l'implémentation réalisée. Nous atteignons un débit de 1Gbit/s avec une latence inférieure à 5$\mu$s sur une ferme de PC avec un réseau local d'un prix raisonnable. De plus, ces résultats de communication sont meilleurs que ceux des ordinateurs parallèles ou des stations reliées par un réseau ATM.
  • Keywords:

    High-speed networks, Communication Protocols, Message-passing implementations, Workstations clusters, Myrinet.
  • Keywords (in french):

    Réseaux haut-débits, Protocole de communication, Implémentation de bibliothèques de communications, Réseaux de stations, Myrinet.
  • Availability: Electronic copy only.
  • Citation: Not published yet.
  • Size: 2+10p
  • Format: Compressed PostScript
  • Get it

Automates à galets : un état de l'art.

  • By: Marianne Delorme
  • Number: RR1997-23
  • Date: August 1997
  • Abstract:

    The purpose of this paper is to give an overview on pebble automata, which can be encountered in different domains, as figures (families) recognition, complexity theory and labyrinths theory . It gives definitions, examples and some basic theorems with their proofs.
  • Abstract (in french):

    Ce rapport est un état de l'art sur les automates à galets que l'on rencontre dans divers domaines comme celui de la reconnaissance de (familles de) figures, théorie de la Complexité, mais aussi théorie des labyrinthes.
  • Keywords:

    Automata, pebbles, graphoids, labyrinths.
  • Keywords (in french):

    Automates, galets, grapho\"{\i}des, labyrinthes.
  • Availability: Electronic copy only.
  • Citation: Not published yet.
  • Size: 2+52p
  • Format: Compressed PostScript
  • Get it

Proof of Imperative Programs in Type Theory.

  • By: Jean-Christophe Filliatre
  • Number: RR1997-24
  • Date: July 1997
  • Abstract:

    Proofs of correctness of imperative programs are traditionally done in first order frameworks derived from Hoare logic~\cite{Hoare69}. On the other hand, correctness proofs of purely functional programs are almost always done in higher order logics. In particular, the realizability~\cite{Kleene52} allow to extract correct functional programs from constructive proofs of existential formulae. In this paper, we establish a relation between these two approaches and show how proofs in Hoare logic can be interpreted in type theory, yielding a translation of imperative programs into functional ones. Starting from this idea, we propose an interpretation of correctness formulae in type theory for a programming language mixing imperative and functional features. One consequence is a good and natural solution to the problems of procedures and side-effects in expressions.
  • Abstract (in french):

    Les preuves de correction de programmes impératifs sont traditionnellement faites dans des théories du premier ordre dérivées de la logique de Hoare~\cite{Hoare69}. D'un autre côté, les preuves de correction de programmes purement fonctionnels sont le plus souvent faites dans des formalismes d'ordre supérieur. En particulier, la réalisabilité~\cite{Kleene52} permet d'extraire des programmes fonctionnels corrects à partir de preuves constructives de formules existentielles. Dans ce papier, nous établissons une relation entre ces deux approches et montrons comment les preuves en logique de Hoare peuvent être interprétées en théories des types, conduisant à une traduction fonctionnelle des programmes impératifs. Partant de cette idée, nous proposons une interprétation des formules de correction en théorie des types pour un langage de programmation mélangeant des traits impératifs et fonctionnels. Une conséquence de cette interprétation est une solution simple et naturelle aux problèmes des procédures et des effets de bord dans les expressions.
  • Keywords:

    Program Validation, Hoare Logic, Realizability, Type Theory.
  • Keywords (in french):

    Validation de Programmes, Logique de Hoare, Réalisabilité, Théorie des Types.
  • Availability: Electronic copy only.
  • Citation: Not published yet.
  • Size: 2+20p
  • Format: Compressed PostScript
  • Get it

An adaptive strategy for deflection routing in meshes.

  • By: Thierry Chich
  • Number: RR1997-25
  • Date: August 1997
  • Abstract:

    In this paper, we describe a new adaptive routing algorithm for meshed-topology deflection networks. Our algorithm is based on a local learning method which evolves in order to produce a local spatial representation of the traffic. We first prove that our algorithm is a generalization of the $Z^2$ routing. Secondly, we prove that we can set the parameters of the learning algorithm such that our adaptive policy cannot create livelock situation. Then we show experimentally the efficiency of our algorithm. First, we compare the routing policies in a grid network, under an uniform load. Second, we create local congestion in order to show that the adaptive routing scheme avoid the overloaded region. Moreover, we propose a more realistic traffic model, and show that our algorithm is valid, even in such context. At last, we show that the algorithm is also efficient in a torus network. These results show the relevance of this method.
  • Abstract (in french):

    Nous proposons un algorithme adaptatif pour les réseaux maillés à déflexion. Cet algorithme est fondé sur une méthode d'apprentissage locale qui permet d'obtenir une représentation spatiale du trafic et de gérer ainsi la répartition de la charge. Nous montrons que notre algorithme peut être vu comme une généralisation du routage $Z^2$ qui est optimal dans les réseaux maillés réguliers. Ensuite, nous montrons que notre algorithme ne peut pas créer d'inter-bloquage dynamique. Puis nous montrons expérimentalement l'efficacité de notre algorithme. D'abord, nous comparons notre politique de routage avec une politique de routage $Z^2$ dans une grille, sous une charge uniforme. Puis nous créons artificiellement des congestions locales pour montrer que notre algorithme permet d'éviter les zones surchargées. Enfin, nous proposons un modèle de trafic plus réaliste et nous montrons que, et dans la grille et dans le tore, l'algorithme permet l'amélioration des performances par un meilleur partage des ressources.
  • Keywords:

    Deflection Routing, Adaptive Strategy, All-Optical Networks.
  • Keywords (in french):

    Routage par Déflexion, Routage Adaptatif, Réseaux Tout-Optiques.
  • Availability: Electronic copy only.
  • Citation: Not published yet.
  • Size: 2+18p
  • Format: Compressed PostScript
  • Get it

Mathematical tools for loop transformations: from systems of uniform recurrence equations to the polytope model.

  • By: Alain Darte
  • Number: RR1997-26
  • Date: September 1997
  • Abstract:

    Linear programming methods, optimizations on polytopes, manipulations of integral matrices, are now commonly used in the field of automatic parallelization, for example for detecting dependences, scheduling computations, mapping data and communications, generating code for computations and communications. The aim of this paper is to give an introduction to these techniques, mainly by showing how they have been progressively used, over the last past 25 years, for studying repetitive computations: first in the context of systems of uniform recurrence equations, then in the development of basic loop transformations such as the hyperplane method or the unimodular transformations, in the ``space-time mapping'' methodology for synthesizing systolic arrays, and finally, in more recent work related to loop parallelization and HPF compilation.
  • Abstract (in french):

    Les méthodes de programmation linéaire, les optimisations sur les polytopes, les manipulations de matrices à coefficients entiers sont maintenant fréquemment utilisées dans le domaine de la parallélisation automatique, par exemple pour détecter les dépendances entre calculs, ordonnancer les calculs, placer les données et les communications ou générer le code pour les calculs et les communications. Le but de ce rapport est de donner une introduction à ces techniques, en montrant principalement comment elles ont peu à peu été utilisées pendant ces 25 dernières années pour l'étude des calculs répétitifs: tout d'abord dans le contexte des systèmes d'équations récurrentes uniformes, puis dans le développement de transformations de boucles comme la méthode de l'hyperplan ou les transformations unimodulaires, dans la méthodologie dite ``espace-temps'' de synthèse de réseaux systoliques, enfin dans des travaux plus récents liés à la parallélisation de boucles et à la compilation de High Performance Fortran (HPF).
  • Keywords:

    System of Uniform Recurrence Equations, Linear Programming, Space-Time Mapping, Systolic Arrays, Automatic Parallelization, Nested Loops, HPF Compilation.
  • Keywords (in french):

    Système d'Equations Récurrentes Uniformes, Programmation Linéaire, Réseaux Systoliques, Parallélisation Automatique, Boucles Imbriquées, Compilation de HPF.
  • Availability: Electronic copy only.
  • Citation: Will appear as a publication of the Institute for Mathematics and Applications (IMA).
  • Size: 2+37p
  • Format: Compressed PostScript
  • Get it

Experiments with a Randomized Algorithm for a Frequency Assignment Problem.

  • By: Janez Zerovnik
  • Number: RR1997-27
  • Date: September 1997
  • Abstract:

    The problems of assigning frequencies to transmitters can be naturally modelled by generalizations of graph coloring problems. We start with a randomized graph coloring algorithm of Petford and Welsh and propose a randomized algorithm for minimizing the number of constraints violated when a set of frequencies available is fixed. Experiments on instances of various types relevant to mobile communication networks are reported.
  • Abstract (in french):

    Le problème de la planification de fréquence se traduit de façon naturelle en une généralisation du problème de coloriage de graphe. En partant d'un algorithme randomizé proposé par Petford and Welsh nous l'adaptons à la minimisation des violations de contraintes induites par la planification de fréquences. Des expérimentations ont été conduites sur des exemples variés significatifs des problèmes de planification cellulaire.
  • Keywords:

    Frequency Assignment Problem, Randomized Heuristics, Cellular Telecommunications System.
  • Keywords (in french):

    Plannification de Fréquences, Heuristique Randomizé, Réseau Cellulaire de Radiocommunication.
  • Availability: Electronic copy only.
  • Citation: Not published yet.
  • Size: 2+15p
  • Format: Compressed PostScript
  • Get it

Upper bounds for the span in triangular lattice graphs: application to frequency planning for cellular network.

  • By: Stephane Ubeda , Janez Zerovnik
  • Number: RR1997-28
  • Date: September 1997
  • Abstract:

    We study a problem coming from the design of wireless cellular radiocommunication network. Frequency planning constraints are modelled in terms of graph theory. For each planning function $f$ let us call $sp(f)$ - or the {\em span} of the frequency planning $f$ - the difference between the largest and the smallest frequency used. Let the {\em Order} of the graph be $Or(G)=sp(G)+1$ and the {\em maximal local order} of the graph the maximum order of a clique of $G$, i.e. $Mlo(G) = \max_{X \ \mbox{clique of}\ G} sp(X)$. We show: $Mlo(G) \leq sp(G) \leq 8\lceil\frac{Mlo(G)}{6}\rceil$.
  • Abstract (in french):

    Ce rapport explore un problème issue de l'allocation de fréquence dans les réseaux de radiocommunication cellulaire. Le problème de planification est décrit à l'aide de la théorie des graphes. Pour une fonction donnée $f$ de plannification, on appelle le {\em span} de $f$ - ou $sp(f)$ - la différence entre la plus grande fréquence employée et la plus petite. Nous définissons aussi l'{\em ordre } du graphe comme étant $Or(G)=sp(G)+1$ et l'{\em ordre local maximum} $Mlo(G)$ comme étant l'ordre maximum d'une clique de $G$, c'est-à-dire $Mlo(G) = \max_{X \ \mbox{clique of}\ G} sp(X)$. Nous montrons le résultat suivant : $Mlo(G) \leq sp(G) \leq 8\lceil\frac{Mlo(G)}{6}\rceil$.
  • Keywords:

    Graph Coloring, Frequency Planning.
  • Keywords (in french):

    Coloriage de Graphe, Plannification de Fréquences.
  • Availability: Electronic copy only.
  • Citation: Not published yet.
  • Size: 2+15p
  • Format: Compressed PostScript
  • Get it

Kolmogorov complexity and cellular automata classification.

  • By: Jean-Christophe Dubacq , Bruno Durand , Enrico Formenti
  • Number: RR1997-29
  • Date: September 1997
  • Abstract:

    We present a new approach to cellular automata (CA for short) classification based on algorithmic complexity. We construct a parameter kappa which is based only on the transition table of CA and measures the ``randomness" of evolutions; kappa is better, in a certain sense, than any other parameter defined on rule tables. We investigate the relations between the classical approach based on topology and ours based on algorithmic randomness. We also compare our parameter with Langton's one: we prove that ours is theoretically better and also agrees with some practical evidences reported in literature. Finally we propose a protocol to approximate kappa and to make experiments on CA dynamical behavior.
  • Abstract (in french):

    Nous présentons une nouvelle approche à la classification des automates cellulaires, approche fondée sur la complexité algorithmique. Nous construisons un paramètre kappa prenant en compte la table de transitions de l'automate cellulaire considéré. Notre thèse est que ce paramètre mesure le caractère aléatoire des évolutions de l'automate cellulaire considéré. Nous prouvons qu'il est meilleur que tout autre paramètre défini sur les tables de transitions. Nous nous intéressons aux liens entre notre approche et l'analyse classique qui utilise des arguments topologiques. Nous comparons aussi notre paramètre à celui de Langton et prouvons non seulement que le notre est meilleur d'un point de vue théorique mais en plus qu'il rend mieux compte de résultats expérimentaux qu'on peut trouver dans la littérature. Finalement nous présentons un protocole d'expérimentations approchant de façon satisfaisante notre paramètre kappa.
  • Keywords:

    Kolmogorov Complexity, Topological Chaos, Cellular Automata Classification.
  • Keywords (in french):

    Complexité de Kolmogorov, Chaos Topologique, Classification du Automates Cellulaires.
  • Availability: Electronic copy only.
  • Citation: To appear in Theoretical Computer Science.
  • Size: 2+13p
  • Format: Compressed PostScript
  • Get it

Structure des Ensembles de Pavages.

  • By: Bruno Durand , Christophe Papazian
  • Number: RR1997-30
  • Date: September 1997
  • Abstract:

    In this article, we start by presenting some basic definitions, some new notions about regularity as well as a topology on the set of tilings. From there, after the study of a new structure on the tiling sets, we give some combinatorial results about the class of quasiperiodic tilings and we show two examples of set of tilings explaining the limits of the propositions given here. We finaly give some indications about 1D-periodicity in tilings.
  • Abstract (in french):

    Dans cet article, nous présentons tout d'abord quelques définitions de base sur les tuiles et les pavages, des notions nouvelles sur la régularité et une topologie intéressante sur les ensembles de pavages. Puis, après l'étude d'une nouvelle structure sur les ensembles de pavages, nous donnons des résultats de dénombrabilité sur les classes de pavages quasipériodiques, et étudions deux exemples d'ensemble de pavage afin de mieux cerner les limites des propositions présentées ici. Enfin, nous donnons quelques pistes de recherches sur la 1D-périodicité des pavages.
  • Keywords:

    Tiling, Quasiperiodicity.
  • Keywords (in french):

    Pavage, Quasipériodicité.
  • Availability: Electronic copy only.
  • Citation: Not published yet.
  • Size: 2+22p
  • Format: Compressed PostScript
  • Get it

Optimal Deadlock-free Path-based Multicast Algorithms in Meshes.

  • By: Vincent Bouchitte , Johanne Cohen , Eric Fleury
  • Number: RR1997-31
  • Date: September 1997
  • Abstract:

    Multicasting is an information dissemination problem which consists, for a node of a distributed memory parallel computer, of sending the same message to an arbitrary subset of nodes. The two major criteria to be considered in multicast communication are \textsl{traffic} (number of channels used) and \textsl{latency} (time required). In this paper, we proposed new polynomial algorithms giving optimal solutions in terms of traffic or latency for a mesh network using \textsl{wormhole} routing and \textsl{path-based} facility. All the algorithms are shown to be deadlock-free. Moreover, we generalize our algorithms to arbitrary Hamiltonian graphs.
  • Abstract (in french):

    Une diffusion partielle est une opération de communication sur une machine parallèle à mémoire distribuée dans laquelle un processeur veut envoyer un même message à un sous groupe de processeurs. Les deux critères dévaluation couramment employés sont le traffic (nombre de canaux utilisés) et la latence (temps requis). Dans ce rapport, nous proposons de nouveaux algorithmes polynomiaux calculant une solution optimale soit en terme de traffic, soit en terme de latence. Nous présentons ces algorithmes dans le cas d'une grille avec comme hypothèse que le mode de routage mis en {\oe}uvre est wormhole et utilise une facilité de routage nommée path-based. Tous les algorithmes sont sans interblocage. Nous généralisons nos algorithmes à la classe des graphes hamiltoniens.
  • Keywords:

    Multicasting, Wormhole Routing, Deadlock Free, Multiprocessors, Parallel Computers.
  • Keywords (in french):

    Diffusion Partielle, Routage Wormhole, Machines Parallèles, Interblocage.
  • Availability: Electronic copy only.
  • Citation: Not published yet.
  • Size: 2+13p
  • Format: Compressed PostScript
  • Get it

Computing on Sequences of Embedded Intervals.

  • By: Marc Daumas , David Berthelot
  • Number: RR1997-32
  • Date: September 1997
  • Abstract:

    What will prevent most users to turn from standard arithmetic to interval arithmetic is the common belief that on any real-life program, interval arithmetic will return much too pessimistic bounds to their solution. Although some adequate set of refinements usually yields satisfactory results with interval arithmetic, an interval-novice would most certainly not spend the time to look into the details and learn about the mathematical peculiarities of his code. We present in this work the prototype of a software library that deals almost transparently with intervals. Directly from its model of execution, the library is able to automatically decide to refine a part or the totality of an evaluation as it is needed. We also introduce a new technique based on an extended number representation that even improves the performances of the library and reduces the interval computed after a numerical evaluation.
  • Abstract (in french):

    La plupart des utilisateurs potentiels de l'arithmétique d'intervalles n'y ont pas recours parce qu'ils croient que sur un programme de taille normale, l'arithmétique d'intervalle leur donnera un intervalle de sûreté largement trop pessimiste. Bien que certaines méthodes de raffinement donnent de bons résultats, un utilisateur inexpérimenté sur l'arithmétique d'intervalles ne voudra certainement pas mobiliser le temps nécessaire à l'apprentissage des particularités mathématiques de son code numérique en regard de l'arithmétique d'intervalles. Nous présentons dans ces travaux le prototype d'une bibliothèque logicielle qui traite les intervalles de façon quasi transparente pour l'utilisateur. Grâce au modèle de calcul implanté, il est possible de décider automatiquement et sans intervention externe de raffiner une partie ou la totalité du calcul suivant les besoins spécifiques de chaque opérateur. Nous proposons de nouveaux algorithmes sur un nouveau système de représentation des nombres pour atteindre de meilleures performances et réduir la taille de l'intervalle de sûreté donné à l'utilisateur à la fin des calculs.
  • Keywords:

    Computer Arithmetic, Interval Arithmetic, On-line Arithmetic, Redundant Notation.
  • Keywords (in french):

    Arithmétique des Ordinateurs, Arithmétique d'Intervalles, Arithmétique en-ligne, Notation Redondante.
  • Availability: Electronic copy only.
  • Citation: Published in Reliable Computing, Kluwer Academic Publishers, vol 3, no 3, august 1997, pp 219-227.
  • Size: 2+11p
  • Format: Compressed PostScript
  • Get it

Inducing an order on cellular automata by a grouping operation.

  • By: Jacques Mazoyer , Ivan Rapaport
  • Number: RR1997-33
  • Date: September 1997
  • Abstract:

    A grouped instance of a cellular automaton (CA) is another one obtained by grouping several states into blocks and by letting interact neighbor blocks. Based on this operation (and on the subautomaton notion), a preorder $\leq$ on the set of one dimensional CA is introduced. It is shown that (CA, leq) admits a global minimum and that on the bottom of (CA, leq) very natural equivalence classes are located. These classes remind us the first two well-known Wolfram ones because they capture global (or dynamical) properties as nilpotency or periodicity. Non trivial properties as the undecidability of leq and the existence of bounded infinite chains are also proved. Finally, it is shown that (CA, leq) admits no maximum. This result allows us to conclude that, in a ``grouping sense'', there is no universal CA.
  • Abstract (in french):

    Une instance groupée d'un automate cellulaire (AC) est un autre obtenu par groupage de plusieurs états en blocs et par l'interaction ``naturelle'' de ces blocs. Basé sur cette opération (et sur la notion de sous-automate), un préordre leq sur l'ensamble des AC à une dimension est introduit. Il est montré que (AC, leq) admet un minimum global et que des classes d'equivalence très naturelles se trouvent en bas de (AC, leq). On retrouve dans ces classes les deux premières bien connues de Wolfram qui capturent des proprietés globales (ou dynamiques) comme la nilpotence et la périodicité. Des proprietés non triviales comme l'indécidabilité de leq et l'existence de cha{î}nes infinies bornées sont aussi prouvées. Finalement il est montr{é} que (AC, leq) n'admet pas de maximum. Cet resultat nous permet de conclure qu'il n'existe pas de AC universel d'un point de vue ``groupage''.
  • Keywords:

    Cellular Automata, Grouping, Order, Dynamical Classification, Intrinsic Real Time Universality.
  • Keywords (in french):

    Automates Cellulaires, Groupage, Ordre, Classification Dynamique, Universalité Intrinsèque en Temps Réel.
  • Availability: Electronic copy only.
  • Citation: Not published yet.
  • Size: 2+16p
  • Format: Compressed PostScript
  • Get it

Undecidability of the global fixed point attractor problem on circular cellular automata.

  • By: Jacques Mazoyer , Ivan Rapaport
  • Number: RR1997-34
  • Date: September 1997
  • Abstract:

    A great amount of work has been devoted to the understanding of the long-time behavior of cellular automata (CA). As for any other kind of dynamical system, the long-time behavior of a CA is described by its attractors. In this context, it has been proved that it is undecidable to know whether every circular configuration of a given CA evolves to some fixed point (not unique). In this paper we prove that it remains undecidable to know whether every circular configuration of a given CA evolves to the {\em same} fixed point. Our proof is based on properties concerning NW-deterministic periodic tilings of the plane. As a corollary it is concluded the (already proved) undecidability of the periodic tiling problem (nevertheless, our approach could also be used to prove this result in a direct and very simple way).
  • Abstract (in french):

    De nombreux travaux ont été consacrés à la compréhension de l'évolution à long terme des automates cellulaires (AC). Comme pour les autres types de systèmes dynamiques, cette évolution à long terme est décrite par ses attracteurs. Dans ce contexte, il a été démontré indécidable de savoir si toute configuration périodique d'un AC donné évolue vers un point fixe (peut-{\^e}tre non unique). Dans cet article, nous prouvons l'indécidabilité de savoir si toute configuration périodique evolue vers le {\em m{\^e}me} point fixe. Notre preuve s'appuie sur les propietés des pavages NW-déterministe et périodiques du plan. Comme corollaire, nous obtenons l'indécidabilité (déjà connue) de la pavabilité périodique (cependant notre approche permet d'arriver à ce résultat de fa{\c{c}}on simple et directe).
  • Keywords:

    Cellular Automata, Periodic Tilings of the Plane.
  • Keywords (in french):

    Automates Cellulaires, Pavages Périodiques du Plan.
  • Availability: Electronic copy only.
  • Citation: Not published yet.
  • Size: 2+14p
  • Format: Compressed PostScript
  • Get it

Determining the Idle Time of a Tiling: New Results.

  • By: Frederic Desprez , Jack Dongarra , Fabrice Rastello , Yves Robert
  • Number: RR1997-35
  • Date: October 1997
  • Abstract:

    In the framework of fully permutable loops, tiling has been studied extensively as a source-to-source program transformation. We build upon recent results by H\"ogsted, Carter, and Ferrante~\cite{HogstedtCF97}, who aim at determining the cumulated idle time spent by all processors while executing the partitioned (tiled) computation domain. We propose new, much shorter proofs of all their results and extend these in several important directions. More precisely, we provide an accurate solution for all values of the {\em rise} parameter that relates the shape of the iteration space to that of the tiles, and for all possible distributions of the tiles to processors. In contrast, the authors in~\cite{HogstedtCF97} deal only with a limited number of cases and provide upper bounds rather than exact formulas.
  • Abstract (in french):

    Dans le cadre des boucle complètement permutables, le pavage a été beaucoup étudié comme une transformation source-à-source. Nous nous basons sur des travaux récents de H\"ogsted, Carter, et Ferrante~\cite{HogstedtCF97}, dont le but est de déterminer le temps d'attente cumulé passé par tous les processeurs pendant l'exécution le domaine de calcul partionné (pavé). Nous proposons des nouvelles preuves, plus courtes, de tous leurs résultats et nous les étendons dans plusieurs directions importantes. Nous donnons une solution plus précise pour toutes les valeurs du paramètre {\em rise} qui relie la forme de l'espace d'itération à celle des tuiles, et pour toutes les distributions possibles des tuiles sur les processeurs. Les auteurs dans~\cite{HogstedtCF97} ne traitent qu'un nombre limité de cas et fournissent des bornes supérieures plutôt que des formules exactes.
  • Keywords:

    Tiling, Fully Permutable Loops, Idle Time.
  • Keywords (in french):

    Pavage, Boucles Complètement Permutables, Temps d'Attente.
  • Availability: Electronic copy only.
  • Citation: Not published yet.
  • Size: 2+17p
  • Format: Compressed PostScript
  • Get it

The Real Dimension Problem is NPR-complete.

  • By: Pascal Koiran
  • Number: RR1997-36
  • Date: October 1997
  • Abstract:

    We show that computing the dimension of a semi-algebraic set of R^n is an NP-complete problem in the Blum-Shub-Smale model of computation over the reals. Since this problem is easily seen to be NPR-hard, the main ingredient of the proof is an NPR algorithm for computing the dimension.
  • Abstract (in french):

    On montre que le calcul de la dimension d'un ensemble semi-algébrique de R^n est un problème NP-complet dans le modèle de Blum-Shub-Smale de calcul sur les nombres réels. Puisqu'il est facile de voir que ce problème est NPR-dur, le principal ingrédient de la preuve est un algorithme NPR de calcul de la dimension.
  • Keywords:

    Semi-Algebraic Sets, Dimension, NP-Completeness, Blum-Shub-Smale Model.
  • Keywords (in french):

    Ensembles Semi-Algébriques, Dimension, NP-Complétude, Modèle de Blum-Shub-Smale.
  • Availability: Electronic copy only.
  • Citation: Not published yet.
  • Size: 2+12p
  • Format: Compressed PostScript
  • Get it

Elimination of parameters in the polynomial hierarchy.

  • By: Pascal Koiran
  • Number: RR1997-37
  • Date: October 1997
  • Abstract:

    Blum, Cucker, Shub and Smale have shown that the problem "P=NP ?" has the same answer in all algebraically closed fields of characteristic 0. We generalize this result to the polynomial hierarchy: if it collapses over an algebraically closed field of characteristic 0, then it must collapse at the same level over all algebraically closed fields of characteristic 0. The main ingredient of their proof was a theorem on the elimination of parameters, which we also extend to the polynomial hierarchy. Similar but somewhat weaker results hold in positive characteristic.
  • Abstract (in french):

    Blum, Cucker, Shub et Smale ont montré que la réponse au problème "P=NP ?" est la même dans tous les corps algébriquement clos de caractéristique 0. Nous généralisons ce résultat à la hiérarchie polynomiale: si elle s'effondre pour un corps algébriquement clos de caractéristique 0, alors elle s'effondre au même niveau pour tous les corps algébriquement clos de caractéristique 0. L'ingrédient principal de leur démonstration est un théorème d'élimination des paramètres, que nous étendons également à la hiérarchie polynomiale. Des résultats similaires mais un peu plus faibles s'appliquent en caractéristique positive.
  • Keywords:

    Elimination of Parameters, Polynomial Hierarchy, Blum-Shub-Smale model.
  • Keywords (in french):

    Elimination des Paramètres, Hiérarchie Polynomiale, Modèle de Blum-Shub-Smale.
  • Availability: Electronic copy only.
  • Citation: Updated version: LIP Research Report RR1998-15.
  • Size: 2+15p
  • Format: Compressed PostScript
  • Get it

Are lower bounds easier over the reals ?.

  • By: Pascal Koiran , Herve Fournier
  • Number: RR1997-38
  • Date: October 1997
  • Abstract:

    We show that proving lower bounds in algebraic models of computation may not be easier than in the standard Turing machine model. For instance, a superpolynomial lower bound on the size of an algebraic circuit solving the real knapsack problem (or on the running time of a real Turing machine) would imply a separation of P from PSPACE. A more general result relates parallel complexity classes in boolean and real models of computation. We also propose a few problems in algebraic complexity and topological complexity.
  • Abstract (in french):

    On montre qu'il n'est pas toujours plus facile d'obtenir des bornes inférieures dans des modèles de calcul algébriques que dans le modèle classique de la machine de Turing. Par exemple, une borne inférieure superpolynomiale sur la taille d'un circuit algébrique résolvant le problème du sac-à-dos réel (ou sur le temps de calcul d'une machine de Turing réelle) impliquerait une séparation de P et PSPACE. Un résultat plus général établit des relations entre classes de complexité parallèles dans les modèles de calcul booléens et réels. On propose aussi quelques problèmes de complexité algébriques et de complexité topologique.
  • Keywords:

    Algebraic Complexity, Decision Trees, Range Searching, Lower Bounds.
  • Keywords (in french):

    Complexité Algébrique, Arbres de Décision, Localisation de Points, Bornes Inférieures.
  • Availability: Electronic copy only.
  • Citation: Not published yet.
  • Size: 2+13p
  • Format: Compressed PostScript
  • Get it

Exploiting data structures in a High Performance Video Server for TV Archives.

  • By: Ahmed Mostefaoui , Lionel Brunie
  • Number: RR1997-39
  • Date: September 1997
  • Abstract:

    One of the key components in a multimedia interactive system is the continuous media server which is mainly dedicated to support the storage, retrieval and delivery of video streams. In this context, researchs were focused on the way to optimize the server parameters (storage space, network bandwidth, etc.) so that the real time requirements and continuity of continuous data are not violated. Hence, the features of the target application were {\em in facto} excluded from the design of the server. However, some applications, such as video repositories, have interesting features which lead to potential benefits if they are taken into account. One of these features is the data structuration resulted from the application of a modeling process. The latter segments videos into overlapped streams in order to support a content-based retrieval. In this paper, we study the problem of how to exploit data structuration to improve the server performance. The key idea behind is to promote media sharing between users requesting overlapped streams. We propose a new scheduling technique based on that feature. Our preliminary simulation results show the effectiveness of the proposed approach.
  • Abstract (in french):

    Dans un système de gestion des archives vidéos, on distingue en général deux composants principaux : le gestionnaire des meta-données et le gestionnaire des vidéos. Le premier est responsable de l'organisation et de la structuration des données de manière a faciliter la recherche des vidéos par le contenu. Le second stocke les données continues (vidéos et audios) de façon à garantir que les contraintes liées à la continuité de ces données soient resprectées. Etant donné le volume important que peut contenir un système de gestion des archives, les meta-données peuvent être très complexes et par conséquent très volumineuses. Dans cet article, on propose une technique d'ordonnancement basée sur l'exploitation des meta-données (principalement le recouvrement entre parties de vidéos) pour améliorer les performances du serveur vidéo. La technique proposée a été testée sur simulation et les résultats sont encourageant.
  • Keywords:

    Multimedia System, Video Server, Data Structuration.
  • Keywords (in french):

    Système Multimédia, Serveur Vidéo, Structuration des Données.
  • Availability: Electronic copy only.
  • Citation: Published in DMIB'97.
  • Size: 2+12p
  • Format: Compressed PostScript
  • Get it

Reducing the complexity of ILP formulations for synthesis.

  • By: Anne Mignotte , Olivier Peyran
  • Number: RR1997-40
  • Date: November 1997
  • Abstract:

    Integer Linear Programming (ILP) is commonly used in high level and system level synthesis. It is an NP-Complete problem (in general cases). There exists some tools that give an optimal solution for small ILP formulations. Nevertheless, these tools may not give solutions for complex formulations. In this paper, we present a solution to overcome the problem of complexity in ILP formulations. We propose a partitioning methodology based on a constraint graph representing all the constraints included in any ILP formulation. To direct the partitioning, the constraint graph nodes are grouped to represent Data Flow Graph (DFG) nodes. This reduced constraint graph can be used to partition any ILP formulation based on DFG. We illustrate this method on ILP formulation for scheduling. Results on ILP scheduling formulations are promising.
  • Abstract (in french):

    La programmation linéaire en nombres entiers (PLNE) est une technique classique dans la synthèse de haut niveau et la synthèse au niveau système. Il existe des outils permettant de donner le résultat optimal de formulation en PLNE de petite taille. Néanmoins, ces outils peuvent en pas parvenir à trouver cette solution pour des exemples plus complexes. Dans cet article, nous présentons une solution permettant de passer outre le problème de complexité des formulations en PLNE. Nous proposons une méthode basée sur le partitionnement d'un graphe de contrainte qui représente toutes les contraintes présentes dans une formulation en PLNE. Nous illustrons cette méthode avec une formulation du problème d'ordonnancement. Les résultats sont très encourageants.
  • Keywords:

    Redundant Arithmetics, Mixed Arithmetic, Scheduling, Integer Linear Programming, Partitioning.
  • Keywords (in french):

    Arithmetique Redondante, Arithmetique Mixte, Ordonnancement, Programmation Linéaire en Nombres Entiers, Partitionnement.
  • Availability: Electronic copy only.
  • Citation: Published in ISSS'97 proceedings, Antwerp, Belgium, 1997.
  • Size: 2+11p
  • Format: Compressed PostScript
  • Get it

Synthesis for mixed arithmetic.

  • By: Anne Mignotte , Jean-Michel Muller , Olivier Peyran
  • Number: RR1997-41
  • Date: November 1997
  • Abstract:

    This article presents a methodology to use a powerful arithmetic (redundant arithmetic) in some parts of designs in order to fasten them without a large increase in area, thanks to the use of both conventional and redundant number systems. This implies specific constraints in the scheduling process. An integer linear programming (ILP) formulation is proposed which finds an optimal solution for reasonable examples. In order to solve the problem of possibly huge ILP computational time, a general solution, based on a constraint graph partitioning, is proposed.
  • Abstract (in french):

    Cette article présente une méthode permettant l'utilisation d'une arithmétique très performante (l'arithmétique redondante) sur certaines parties d'un circuit, afin d'augmenter sa vitesse, sans trop augmenter sa surface, grâce au mélange d'arithmétiques non redondantes conventionnelles et d'arithmétiques redondantes. Cela induit des contraintes spécifiques dans le processus d'ordonnancement. Une formulation en programme linéaire en nombres entiers est proposée, afin de trouver le résultat optimal pour des exemples de taille raisonnable. Une solution, basée sur le partitionnement d'un graphe de contraintes, permet de résoudre le problème des temps de calculs trop importants.
  • Keywords:

    Arithmetic, Redundant Number Systems, Scheduling, Integer Linear Programming, Partitioning.
  • Keywords (in french):

    Arithmétique, Système Redondant d'Ecriture des Nombres, Ordonnancement, Programmation Linéaire en Nombres Entiers, Partitionnement.
  • Availability: Electronic copy only.
  • Citation: Not published yet.
  • Size: 2+24p
  • Format: Compressed PostScript
  • Get it

Scheduling using mixed arithmetic: an ILP formulation.

  • By: Anne Mignotte , Olivier Peyran
  • Number: RR1997-42
  • Date: November 1997
  • Abstract:

    DSP designer expertise shows that redundant number systems improve the delay of arithmetic operations, but lead to an increase of area. This paper proposes an arithmetic using both redundant and non redundant number systems (mixed arithmetic), providing a good speed/area tradeoff. We first study this arithmetic, both at the operator level and at the design level, and give experimental results. Then, an integer linear programming (ILP) formulation is proposed to solve a scheduling problem with mixed arithmetic operators.
  • Abstract (in french):

    L'experience des concepteurs de circuits de traitement du signal montre que les systèmes redondants de représentation des nombres permettent d'améliorer le délai des opérations arithmétiques, mais augmentent la surface. Cet article présente une arithmétique utilisant à la fois les systèmes redondants et conventionnels de représentation des nombres (arithmétique mixte), autorisant ainsi un bon compromis vitesse/surface. Nous étudions d'abord cette arithmétique, aussi bien au niveau des opérateurs qu'à celui des circuits, et donnons des résultats expérimentaux. Une formulation en programme linéaire en nombres entiers est proposée, afin de résoudre un problème le problème d'ordonnancement d'opérateurs d'arithmétique mixte.
  • Keywords:

    Redundant Arithmetics, Mixed Arithmetic, Scheduling, Integer Linear Programming.
  • Keywords (in french):

    Arithmetique Redondante, Arithmetique Mixte, Ordonnancement, Programmation Linéaire en Nombres Entiers.
  • Availability: Electronic copy only.
  • Citation: Published in EDTC'97 proceedings, Paris, France, 1997.
  • Size: 2+10p
  • Format: Compressed PostScript
  • Get it

Mixed Arithmetics: Introduction and Design Structure.

  • By: Anne Mignotte , Jean-Michel Muller , Olivier Peyran
  • Number: RR1997-43
  • Date: November 1997
  • Abstract:

    CAD tools for special purpose architecture usually use conventional radix 2 number system to represent integers. However, DSP designer expertise shows that redundant number systems improve the delay of arithmetic operations. In this paper, we come to the conclusion that arithmetic operator outputs have to be redundant whereas inputs have not. Therefore, an optimal design has to use mixed arithmetic (using both conventional and redundant number systems). Moreover, the selection of the number system for each operand is not trivial, as the inputs of operations are often the outputs of other operations. Therefore, we propose a design strategy to automatically realize this task.
  • Abstract (in french):

    Les outils de CAO d'architectures intégrées utilisent généralement un système conventionnel en base 2 pour représenter les entiers. Cependant, l'expérience des concepteurs de circuits de traitement du signal montre que l'utilisation d'arithmétiques redondantes améliorent le délai des opérateurs arithmétiques. Dans cet article, nous montrons que les sorties des opérateurs doivent être redondantes, alors que les entrées doivent être non redondantes. Ainsi, l'idéal est l'utilisation d'une arithmétique mixte (utilisant à la fois des représentations redondantes et conventionnelles des nombres). Cependant, la sélection du système de représentation de chaque opérande n'est pas évidente, puisque les entrées d'opérateurs sont souvent les sorties d'autres opérateurs. Nous proposons donc une stratégie visant à réaliser cette tâche automatiquement.
  • Keywords:

    Redundant Arithmetics, Mixed Arithmetic, High-Level Synthesis, Scheduling.
  • Keywords (in french):

    Arithmétique Redondante, Arithmétique Mixte, Synthèse de Haut Niveau, Ordonnancement.
  • Availability: Electronic copy only.
  • Citation: Published in MPCS'96 proceedings, Ischia, Italy, 1996.
  • Size: 2+14p
  • Format: Compressed PostScript
  • Get it

A Model for Using Redundant Number Systems in Special-Purpose Architectures.

  • By: Anne Mignotte , Jean-Michel Muller , Olivier Peyran
  • Number: RR1997-44
  • Date: November 1997
  • Abstract:

    Our goal is to design tools for high-level synthesis of special-purpose arithmetic circuits. After a presentation of what we call ``mixed arithmetics'' (that is, the use of different number systems on a same circuit), we propose a design strategy that could be used to automatically allocate a number system to each variable in a circuit.
  • Abstract (in french):

    Notre objectif est de concevoir des outils de synthèse de haut niveau de circuits utilisant des arithmétiques spécifiques. Après avoir présenté ce que l'on appelle ``l'arithmétique mixte'' (c'est à dire une arithmétique qui utilise différents systèmes de représentation des nombres au sein d'un même circuit), nous proposons une stratégie de conception qui permettrait, pour chaque variable à l'intérieur d'un circuit, de choisir automatiquement son système de représentation.
  • Keywords:

    Redundant Arithmetics, Mixed Arithmetic.
  • Keywords (in french):

    Arithmétique Redondante, Arithmétique Mixte.
  • Availability: Electronic copy only.
  • Citation: Published in IEEE-SMC SESA'96 proceedings, Lille, France, 1996.
  • Size: 2+11p
  • Format: Compressed PostScript
  • Get it

A polynomial time algorithm for diophantine equations in one variable.

  • By: Felipe Cucker , Pascal Koiran , Steve Smale
  • Number: RR1997-45
  • Date: November 1997
  • Abstract:

    We show that the integer roots of of a univariate polynomial with integer coefficients can be computed in polynomial time. This result holds for the classical (i.e. Turing) model of computation and a sparse representation of polynomials (i.e. coefficients and exponents are written in binary, and only nonzero monomials are represented).
  • Abstract (in french):

    On montre que les racines entières d'un polynôme en une variable à coefficients entiers peuvent être calculées en temps polynomial. Ce résultat est valable pour le modèle de calcul classique des machines de Turing et pour une représentation creuse des polynômes (coefficients et exposants sont écrits en binaire, et seuls les monômes non nul sont représentés).
  • Keywords:

    Sparse Polynomials, Diophantine Equations, Computer Algebra.
  • Keywords (in french):

    Polynômes Creux, Equations Diophantiennes, Calcul Formel.
  • Availability: Electronic copy only.
  • Citation: Not published yet.
  • Size: 2+10p
  • Format: Compressed PostScript
  • Get it

Fast Evaluation of the Same Function at Many Regularly-Spaced Points.

  • By: Milos Ercegovac , Jean-Michel Muller
  • Number: RR1997-46
  • Date: November 1997
  • Abstract:

    We present a method, called the %``conservative method'' value-preserving (VP) method for reducing the amount of work when computing the value of a function at regularly spaced points. Th VP method uses the fact that if two argument values $x$ and $y$ have $p$ common digits, then the values $f(x)$ and $f(y)$ computed with an on-line algorithm of delay $\delta$ have at least $p-\delta$ common digits. We discuss evaluation of polynomials using the VP method and compare its performance with several traditional techniques.
  • Abstract (in french):

    Nous présentons une méthode, appelée ``value-preserving method'' pour évaluer rapidement la valeur que prend une fonction $f$ en des points régulièrement espacés. Cette méthode utilise le fait que si deux nombres $x$ et $y$ ont $p$ chiffres en commun, alors les valeurs de $f(x)$ et $f(y)$ calculées par un algorithme en-ligne de délai $\delta$ auront au moins $p-\delta$ chiffres en commun. Nous discutons de l'utilisation de cette méthode pour l'évaluation de polynômes, et nous la comparons à d'autres techniques.
  • Keywords:

    On-line arithmetic, Function evaluation, Computer arithmetic.
  • Keywords (in french):

    Arithmétique ``en-ligne'', Évaluation de fonctions, Arithmétique des ordinateurs.
  • Availability: Electronic copy only.
  • Citation: To appear in 1998 SPIE Conference, July 1998, San Diego, USA.
  • Size: 2+17p
  • Format: Compressed PostScript
  • Get it

Reciprocation, Square root, Inverse Square Root, and some Elementary Functions using Small Multipliers.

  • By: Milos Ercegovac , Tomas Lang , Jean-Michel Muller , Arnaud Tisserand
  • Number: RR1997-47
  • Date: November 1997
  • Abstract:

    This paper deals with the computation of reciprocals, square roots, inverse square roots, and some elementary functions using small tables, small multipliers, and for some functions, a final ``large'' (almost full-length) multiplication. We propose a method that allows fast evaluation of these functions in double precision arithmetic. The strength of this method is that the same scheme allows the computation of all these functions. Our method is mainly interesting for designing special purpose circuits, since it does not allow a simple implementation of the four rounding modes required by the IEEE-754 standard for floating-point arithmetic.
  • Abstract (in french):

    Ce rapport traite de l'évaluation d'inverses, de racines carrées, d'inverses de racines carrées, et de quelques fonctions élémentaires en utilisant de petites tables, de petits multiplieurs, et, pour quelques fonctions, une ``grande'' (i.e., portant sur des nombres dont la taille est celle des opérandes) multiplication finale. Nous proposons une méthode qui permet l'évaluation de ces fonctions en arithmétique double précision. L'avantage de cette méthode réside dans le fait que le même schéma de calcul (et donc, en pratique, la même implantation) permet le calcul de toutes ces fonctions. Notre méthode est essentiellement intéressante pour construire des circuits dédiés à une application, car elle ne permet pas d'implanter de manière simple les quatre modes d'arrondis exigés par le standard IEEE pour l'arithmétique flottante.
  • Keywords:

    Division, Reciprocation, Square-Root, Function Evaluation, Computer Arithmetic.
  • Keywords (in french):

    Division, Inverse, Racine Carrée, Evaluation de Fonctions, Arithmétique des Ordinateurs.
  • Availability: Electronic copy only.
  • Citation: Not published yet.
  • Size: 2+22p
  • Format: Compressed PostScript
  • Get it

Verification of Arithmetic Circuits using a Functional Language and PVS.

  • By: David Cachera
  • Number: RR1997-48
  • Date: December 1997
  • Abstract:

    We present a verification technique for arithmetic circuits. Circuits are described in Haskell, a pure functional language. Using a functional language as hardware description language allows an easy and clean expression of parameterization, modularity, and definition of recursive components. From a Haskell description, we generate input to the PVS theorem prover. We make use of the higher order features of PVS to prove generic n-bit recursively defined circuits. We also generate proof strategies, in order to increase the degree of automatization. We show how our method works on the example of a decimal to binary converter.
  • Abstract (in french):

    Nous présentons une technique de vérification pour les circuits arithmétiques. Les circuits sont décrits en Haskell, un langage fonctionnel pur. L'utilisation d'un langage fonctionnel comme langage de description permet d'exprimer de façon simple et propre la paramétrisation et la modularité, et de définir des composants de façon récursive. À partir d'une description en Haskell, nous générons des entrées vers le prouveur de théorèmes PVS. Nous utilisons les possibilités de PVS pour prouver des circuits définis récursivements, manipulant leur taille de façon générique. Nous générons également des stratégies de preuve pour améliorer le degré d'automatisation. Nous montrons comment cette méthode fonctionne avec l'exemple d'un convertisseur décimal-binaire.
  • Keywords:

    Hardware Description Language, Haskell, Hardware Verification, Arithmetic Circuits, Theorem Proving, PVS.
  • Keywords (in french):

    Langage de Description de Circuits, Haskell, Verification de Circuits, Circuits Arithmétiques, Démonstration Automatique, PVS.
  • Availability: Electronic copy only.
  • Citation: Submitted to Formal Techniques for Hardware and Hardware-like Systems, FTH'98.
  • Size: 2+17p
  • Format: Compressed PostScript
  • Get it