Leader Election by d Dimensional Cellular Automata.

  • By: Codrin Nichitiu , Eric Remila
  • Number: RR1999-01
  • Date: January 1999
  • Abstract:

    We present a cellular algorithm in O(w^2) for the leader election problem on a finite connected subset F of Z^d of diameter w, for any fixed d. The problem consists in finding an algorithm such that when setting the elements of F to a special state, and all the others to a state #, the cellular automaton iterates a finite number of steps and eventually sets only one precise element of F to a special state called leader state. We describe the algorithm in detail, prove it and its complexity, and discuss the possible extensions on more general Cayley graphs.
  • Abstract (in french):

    Nous présentons un algorithme cellulaire en O(w^2) pour le problème d'élection d'un général sur un sous-ensemble fini connexe F\subset\Z^d de diamètre w, pour n'importe quel d fixé. Le problème consiste à trouver un algorithme tel que lorsqu'on met les éléments de F dans un état spécial et tous les autres dans un état #, l'automate cellulaire itère un nombre fini de pas, et met un seul élément de F dans un état spécial nommé état général. Nous décrivons l'algorithme en détail, démontrons sa correction et sa complexité et discutons des extensions possibles à des graphes de Cayley plus généraux.
  • Keywords:

    Graph Automata, Leader Election, Finite State Automata, d-dimensional Integer Grid, Cellular Automata.
  • Keywords (in french):

    Graphes d'Automates, Eléction d'un Général, Automate Fini, Grille Entière de Dimension d, Automates Cellulaires.
  • Availability: Electronic copy only.
  • Citation: Not published yet.
  • Size: 2+10p
  • Format: Compressed PostScript
  • Get it

SOPHIE: a Tool for Collecting PHiPAC Metrics Of C Code.

  • By: Emmanuel Cagniot , Thomas Peugeot , Gil Utard , Michel Cosnard
  • Number: RR1999-02
  • Date: January 1999
  • Abstract:

    In designing efficient software for High Performance Real Time embedded signal processing applications, several performance issues must be addressed prior and during implementation. We present a tool that helps engineers predict and analyze the performance of their C programs. Modern processors can achieve high performance on processing kernels but this requires extensive machine specific hand tuning. However, there is a recent methodology, PHiPAC, whereby near peak performance on a variety of systems can be achieved automatically for such routines. In this paper, we propose a set of platform-independent and platform-dependent metrics of distance between the coding style of a routine and the PHiPAC guidelines. Next, we present a software prototype, SOPHIE (Simulator of PHIpac machinE), that collects these metrics during the execution of the routine. We report results on the utilization of our measurement tool at Matra Systemes \& Information on a real world image processing application which show that the profiler is useful in determining performance bottlenecks.
  • Abstract (in french):

    Les processeurs modernes peuvent atteindre des performances élevées sur des noyaux d'algèbre linéaire mais cela requiert un travail manuel coûteux. Cependant, il existe une méthodologie récente, PHiPAC, pour laquelle une performance proche de la performance crête peut être atteinte automatiquement pour ces fonctions. Dans ce papier, nous proposons un ensemble de métriques indépendantes et dépendantes de la plate-forme qui mesurent la distance entre le style de codage d'une routine et les directives de PHiPAC. Nous présentons ensuite un logiciel prototype, SOPHIE (Simulator of PHIpac machinE), qui collecte ces métriques durant l'exécution d'une routine. Nous rapportons des résultats de notre instrument de mesure à Matra Systèmes et Information sur une application réelle du traitement de l'image temps réel. Nous montrons que cet outil d'analyse permet de déterminer les goulots d'étranglements lors de l'exécution d'un code.
  • Keywords:

    PHiPAC, ATLAS, SOPHIE, Simulation, Performance Optimization, Performance Counters, PerfAPI, PCL.
  • Keywords (in french):

    PHiPAC, ATLAS, SOPHIE, Simulation, Optimisation des Performance, Compteurs de Performance, PerfAPI, PCL.
  • Availability: Electronic copy only.
  • Citation: This paper was accepted and presented the workshop on Performance Characterisation and Benchmarking of Vision Systems. International Conference on Vision Systems (ICVS' 99).
  • Size: 1+12p
  • Format: Compressed PostScript
  • Get it

Division of Floating Point Expansions.

  • By: Marc Daumas , Claire Finot
  • Number: RR1999-03
  • Date: January 1999
  • Abstract:

    The floating point unit becomes a more and more efficient part of modern computers. This led us to work on multiple precision arithmetic on floating point numbers already presented as expansions. We propose here a modified algorithm for the division of expansions to obtain a complete arithmetic library that is our first step towards natural adaptivity of numerical softwares. In this work, we isolate a set of properties and one lemma on floating point numbers. They are used to prove the correct behavior of both division algorithms. In the case of an exact division, the algorithm must halt after a finite number of steps. We exclude the case of an algorithm approaching the quotient but always failing to find it exactly. To benchmark our routine, we have implemented fast and exact routines for the determinant of a small matrix (size 3 to 10) as often used in computational geometry. We compare three different algorithms with two multiple precision packages on two different IEEE machines.
  • Abstract (in french):

    L'unité flottante devient de plus en plus performante dans les processeurs actuels. Ceci nous conduit à travailler sur l'arithmétique en précision multiple sur les nombres flottants. Cette technique a déjà été présentée sous le nom d'expansions. Nous proposons ici une modification de l'algorithme de division d'expansions et nous completons ainsi notre bibliothèque d'opérations arithmétiques sur les expansions. Ces algorithmes représentent une première étape naturelle vers une bibliothèque de calcul adaptatif. Dans ce travail, nous isolons un ensemble de propriétés et un lemme sur les nombres flottants. Ils sont utilisés pour prouver le bon comportement des algorithmes de division. Dans le cas d'une division exacte, l'algorithme s'arrete après un nombre fini d'étapes. Nous excluons le cas où l'algorithme s'approche du résultat exact sans jamais l'atteindre. Pour tester notre algorithme, nous avons implémenté le calcul exact de déterminants de petites matrices (de taille 3 à 10). Ce calcul est souvent utile en géometrie algorithmique. Nous comparons trois algorithmes différents sur deux bibliothèques de calcul précision multiple et sur deux machines normalisées IEEE.
  • Keywords:

    Exact Arithmetic, Multiple Precision, Expansion, Division, Computational Geometry.
  • Keywords (in french):

    Arithmétique Exacte, Précision Multiple, Expansion, Division, Géometrie Algorithmique.
  • Availability: Electronic copy only.
  • Citation: Published in the Journal of Universal Computer Science, vol. 5, no. 6, pp. 323-338, 1999. Paper copy available from the INRIA RR 3771.
  • Size: 2+13p
  • Format: Compressed PostScript
  • Get it

The Complexity of local dimensions for constructible sets.

  • By: Pascal Koiran
  • Number: RR1999-04
  • Date: January 1999
  • Abstract:

    We show that deciding whether an algebraic variety has an irreducible component of codimension at least d is an \np_{\c}-complete problem for every fixed d (and is in the Arthur-Merlin class if we assume a bit model of computation). However, when d is not fixed but is instead part of the input, we show that the problem is not likely to be in \np_{\c} or in \conp_{\c}. These results are generalized to arbitrary constructible sets. We also study the complexity of a few other related problems. This report updates LIP report 98-10.
  • Abstract (in french):

    On montre que décider si une variété algébrique a une composante irréductible de codimension au moins d est un problème \np_{\c}-complet pour toute constante d (et est dans la classe Arthur-Merlin si on travaille avec un modèle de calcul booléen). Par contre, si d n'est pas fixé mais est au contraire un entier arbitraire donné en entrée, on montre que ce problème n'est probablement pas dans \np_{\c} ni dans \conp_{\c}. Ces résultats sont étendus aux ensembles constructibles. On étudie également la complexité de quelques problèmes connexes. Ce rapport est une mise à jour du rapport LIP 98-10.
  • Keywords:

    Irreducible Components, Dimension, NP-Completeness, Blum-Shub-Smale Model.
  • Keywords (in french):

    Composantes Irréductibles, Dimension, NP-Complétude, Modèle de Blum-Shub-Smale.
  • Availability: electronic copy only.
  • Citation: Not published yet.
  • Size: 2+13p
  • Format: Compressed PostScript
  • Get it

Deciding stability and mortality of piecewise affine dynamical systems.

  • By: Vincent Blondel , Olivier Bournez , Pascal Koiran , Christos H. Papadimitriou , John N. Tsitsiklis
  • Number: RR1999-05
  • Date: January 1999
  • Abstract:

    We show that several global properties (attractivity, global asymptotic stability and mortality) of discrete time dynamical systems defined by iteration of piecewise-affine maps are undecidable. Such results had been known only for local properties (e.g., point-to-point reachability). These three properties are undecidable in dimension at least two, but turn out to be decidable in one dimension for continuous maps.
  • Abstract (in french):

    Nous montrons que plusieurs propriétés globales (attractivité, stabilité asymptotique globale et mortalité) sont indécidables pour des sytèmes dynamiques à temps discret définis par itération de fonctions affines par morceaux. De tels résultats n'étaient connus auparavant que pour des propriétés locales (comme par exemple l'atteignabilité point à point). Les trois propriétés ci-dessus sont indécidables en dimension au moins égale à deux, mais se trouvent être décidables en dimension un pour des fonctions continues.
  • Keywords:

    Dynamical Systems, Piecewise Affine Systems, Piecewise Linear Systems, Hybrid Systems, Mortality, Stability, Decidability.
  • Keywords (in french):

    Sytèmes Dynamiques, Systèmes Affines par Morceaux, Systèmes Linéaires par Morceaux, Systèmes Hybrides, Mortalité, Décidabilité, Stabilité.
  • Availability: Electronic copy only.
  • Citation: Not published yet.
  • Size: 2+11p
  • Format: Compressed PostScript
  • Get it

Multiplication by an Integer Constant.

  • By: Vincent Lefevre
  • Number: RR1999-06
  • Date: January 1999
  • Abstract:

    We present an algorithm allowing to perform integer multiplications by constants. This algorithm is compared to existing algorithms. Such algorithms are useful, as they occur in several problems, such as the Toom-Cook-like algorithms to multiply large multiple-precision integers, the approximate computation of consecutive values of a polynomial, and the generation of integer multiplications by compilers.
  • Abstract (in french):

    Nous présentons un algorithme permettant de faire des multiplications entières par des constantes. Cet algorithme est comparé à d'autres algorithmes existants. De tels algorithmes sont utiles, car ils interviennent dans plusieurs problèmes, comme les algorithmes du style Toom-Cook pour multiplier des entiers à grande précision, le calcul approché de valeurs consécutives d'un polynôme et la génération de multiplications entières par les compilateurs.
  • Keywords:

    Multiplication, Addition Chains.
  • Keywords (in french):

    Multiplication, Chaînes d'Additions.
  • Availability: Electronic copy only.
  • Citation: Not published yet.
  • Size: 2+5p
  • Format: Compressed PostScript
  • Get it

A formalization of Static Analyses in System F.

  • By: Frederic Prost
  • Number: RR1999-07
  • Date: January 1999
  • Abstract:

    We propose a variant of Girard's System F. The aim of this new system is to provide a common framework for various type based analyses. We modify $F$ by the introduction of two different universes from which types may be built. Following C. Paulin, those two universes may be seen as $Prop$ and $Spec$. The originality of our system lies on two points: 1) We define an inclusion relation between the two universes, from which we derive a subtyping relation on types. 2) We introduce a notion of {\em universe variable}, and develop a polymorphism \`a la ML on universes. We show that this system has the standard properties (conflence, SN, etc.) and how it can be used to formalize various program analyses like binding time and dead code. We relate our work to previous analyses in terms of expressiveness (often only simply typed calculi are considered) and power (more information can be inferred).
  • Abstract (in french):

    Dans ce papier,nous proposons un cadre théorique générique pour l'analyse statique de programmes fonctionnels. Le but poursuivi est l'étude des relations entre typage et analyse statique de programmes. Nous présentons une variante du système $F$ de Girard. Nous montrons que ce système satisfait les propriétés standards et utilisons ensuite ce système pour formaliser différentes analyses statiques de la littérature, et même de les dépasser à la fois en expressivité (souvent ne sont considérés que des calculs simplements typés) et en puissance (plus d'informations peuvent être déterminées sur un programme donné).
  • Keywords:

    Type Theory, Pruning, Static Analysis, Polymorphism, Subtyping.
  • Keywords (in french):

    Théorie des Types, Analyse Statique, Polymorphisme, Sous-Typage.
  • Availability: Electronic copy only.
  • Citation: Not published yet.
  • Size: 2+25p
  • Format: Compressed PostScript
  • Get it

An efficient and transparent thread migration scheme in the PM2 runtime system.

  • By: Gabriel Antoniu , Luc Bouge , Raymond Namyst
  • Number: RR1999-08
  • Date: January 1999
  • Abstract:

    This paper describes a new iso-address approach to the dynamic allocation of data in a multithreaded runtime systemwith thread migration capability. The system guarantees that the migrated threads and their associated static data are relocated exactly at the same virtual address on the destination nodes, so that no post-migration processing is needed to keep pointers valid. In the experiments reported, a thread can be migrated in less than 75 us.
  • Abstract (in french):

    Nous décrivons une nouvelle technique d'allocation dynamique de mémoire (approche que nous appellons iso-adresse) concue et implémentée dans l'environnement multithread PM2, qui propose la migration de processus légers. Le système garantit que les threads et leurs données associées sont relogés exactement à la même adresse sur le noeud destinataire. Ainsi, aucun traitement post-migration n'est nécessaire pour préserver la validité des pointeurs. Dans les expériences présentées, un thread peut être migré en moins de 75 us.
  • Keywords:

    Thread Migration, Iso-Address Allocation, PM2, Multithreading.
  • Keywords (in french):

    Thread, Processus Léger, Migration, Allocation Iso-Adresse, PM2, Multithreading.
  • Availability: Electronic copy only.
  • Citation: Proc. 3rd Workshop on Runtime Systems for Parallel Programming (RTSPP
  • Size: 2+15p
  • Format: Compressed PostScript
  • Get it

A Prefetching Strategy for Multimedia On-Demand Servers.

  • By: Ahmed Mostefaoui , Lionel Brunie
  • Number: RR1999-09
  • Date: January 1999
  • Abstract:

    In a multimedia system, I/O have a dramatic impact on the performance. Therefore, reducing I/O has become a key issue. The latter has been mostly addressed by using buffering techniques. In this paper, we propose a new prefetching approach to handle this problem. The proposed technique take advantage of the target application structures to trigger an optimized prefetching operations. Simulation results show the effectiveness of the proposed method under various system configurations and request scenarios.
  • Abstract (in french):

    Dans un système multimédia, les E/S ont un impact important sur les performances. Par conséquent, la réduction des E/S est devenue un challenge majeur. Ce dernier a été largement étudié dans la littérature à travers la proposition de techniques de gestion de la mémoire. Dans ce rapport, nous proposons une nouvelle technique, basée sur l'utilisation de la structuration des données, pour anticiper le chargement des données vidéos. Les résultats de simulation montrent clairement la pertinence de l'approche proposée.
  • Keywords:

    Video Server, Multimedia Database, TV Archive.
  • Keywords (in french):

    Serveur Video, Bases de Données Multimédias, Archive TV.
  • Availability: Electronic copy only.
  • Citation: Submitted to International Database Engineering and Applications Symposium IDEAS'99.
  • Size: 2+16p
  • Format: Compressed PostScript
  • Get it

Efficient Communications in Multithreaded Runtime Systems.

  • By: Luc Bougé, Jean-François Méhaut, Raymond Namyst
  • Number: RR1999-10
  • Date: February 1999
  • Abstract:

    Most of existing multithreaded environments have an implementation built on top of standard communication interfaces such as MPI which ensures a high level of portability. However, such interfaces do not meet the efficiency needs of RPC-like communications which are extensively used in multithreaded environments. We propose a new portable and efficient communication interface for RPC-based multithreaded environments, called Madeleine. We describe its programming interface and its implementation on top of low-level network protocols such as VIA. We also report performance results that demonstrate the efficiency of our approach.
  • Abstract (in french):

    Bon nombre d'environnements multithreads possèdent une implantation s'appuyant des bibliothèques de communication standard telles MPI, ce qui leur confère un haut degré de portabilité. Cependant, ces interfaces ne répondent pas aux exigences d'efficacité des communications de type RPC qui sont intensivement utilisées dans les environnements multithreads. Nous proposons une nouvelle interface de communication efficace et portable, nommée Madeleine, pour repondre à ces besoins. Nous décrivons son interface de programmation ainsi que son implantation au-dessus de protocoles de communication de bas-niveau tels que VIA. Nous rapportons également plusieurs résultats expérimentaux qui démontrent l'efficacité de notre approche.
  • Keywords:

    Multithreading, Remote Procedure Call, High Speed Networks, VIA.
  • Keywords (in french):

    Multithreading, Appel de Procedure à Distance, Reseaux Haut Débit, VIA.
  • Availability: Electronic copy only.
  • Citation: Proc. 3rd Workshop on Runtime Systems for Parallel Programming (RTSPP
  • Size: 2+14p
  • Format: Compressed PostScript
  • Get it

Customizable thread scheduling directed by prioritiess.

  • By: Yves Denneulin, Jean-François Méhaut, Raymond Namyst
  • Number: RR1999-11
  • Date: February 1999
  • Abstract:

    We present in this paper the scheduling policy of the Marcel library and propose a new definition of priorities as a relative execution speed for threads. We explore the extension of priorities to a distributed architecture and propose a load-balancing policy based on priorities. Finally, we illustrate the use of priorities for the design of parallel applications and system tools such as load-balancing daemons or communication daemons.
  • Abstract (in french):

    Nous présentons dans ce papier l'ordonnancement des processus légers de la librairie Marcel et nous définissons la priorité d'un thread comme étant sa vitesse relative d'exécution. Cette définition est étendue au contexte des architectures parallèles et distribuées et nous proposons une régulation de charge basée sur le respect des priorités. Nous illustrons dans la dernière section de ce papier l'utilisation des priorités pour certaines classes de programmes parallèles et de composants systèmes tels que des démons assurant la régulation de la charge ou la scrutation des communications.
  • Keywords:

    Scheduling, Priorities, Multithreaded Environment, Combinatorial Optimization Applications.
  • Keywords (in french):

    Ordonnacement, Priorités, Environnements de Programmation Multithread, Applications d'Optimisation Combinatoire.
  • Availability: Electronic copy only.
  • Citation: Proc. Workshop on Multithreaded Exection and Compilation
  • Size: 2+9p
  • Format: Compressed PostScript
  • Get it

The Price of Routing in FPGAs.

  • By: Florent de Dinechin
  • Number: RR1999-12
  • Date: February 1999
  • Abstract:

    This paper studies an architectural issue concerning field programmable gate arrays (FPGAs). The observation of mainstream FPGA architectures leads to the following remark: in these circuits, the proportion of silicon devoted to reconfigurable routing is increasing, reducing the proportion of silicon available for computation resources. A quantitative analysis shows that this trend, if pursued, will lead to a widening gap between FPGA performance and VLSI performance. Some prospective solutions to this problem are discussed.
  • Abstract (in french):

    Cet article étudie une question d'architecture qui concerne les réseaux de cellules logiques reconfigurables (ou FPGAs pour field programmable gate arrays). Il remarque, dans ces circuits, une tendance générale à l'augmentation du pourcentage de silicium qui est consacré au routage au détriment du silicium consacré aux ressources de calcul. Une analyse quantitative montre que cette tendance conduira à un écart de performance croissant entre FPGA et circuit intégré VLSI dédié, pour une même application. Après ce constat, des solutions à ce problème sont évoquées et discutées.
  • Keywords:

    FPGA, Routing Resources, Complexity.
  • Keywords (in french):

    FPGA, Routage, Complexité.
  • Availability: Electronic copy only.
  • Citation: Not published yet.
  • Size: 2+10p
  • Format: Compressed PostScript

Choix d'un service de communication pour un serveur vidéo tolérant aux pannes : étude du service GM.

  • By: Alice Bonhomme , Loïc Prylli
  • Number: RR1999-13
  • Date: February 1999
  • Abstract:

    In the context of a video server project, we look at fault tolerant communication services. As the Myrinet network has been selected for this project, we focus on the GM system, which has the appropriate properties, especially in terms of error recovery. After looking what requirements a server video put on the communication system, we propose an error recovery strategy for the Myrinet network and we show how one can implement it with the GM system.
  • Abstract (in french):

    Dans le cadre d'un projet de serveur vidéo, nous nous intéressons aux services de communication tolérants aux pannes. Le réseau Myrinet ayant été retenu pour ce projet, nous nous focalisons sur le système GM qui a les bonnes propriétés, notamment en terme de reprise sur erreur. Après une étude des besoins imposés par un serveur vidéo sur le service de communication (détection de panne réseau, rajout ou réinitialisation de machine, etc), nous proposons une stratégie de détection d'erreur pour le réseau Myrinet, et montrons comment le système GM permet de l'implémenter.
  • Keywords:

    Video Server, Fault Tolerance, Myrinet Network, GM.
  • Keywords (in french):

    Serveur Vidéo, Tolérance aux Pannes, Réseau Myrinet, GM.
  • Availability: Electronic copy only.
  • Citation: Not published yet.
  • Size: 2+12
  • Format: Compressed postscript
  • Get it

Orthogonal Polyhedra: Representation and Computation.

  • By: Olivier Bournez , Oded Maler , Amir Pnueli
  • Number: RR1999-14
  • Date: February 1999
  • Abstract:

    In this paper we investigate orthogonal polyhedra, i.e. polyhedra which are finite unions of full-dimensional hyper-rectangles. We define representation schemes for these polyhedra based on their vertices, and show that these compact representation schemes are canonical for all (convex and non-convex) polyhedra in any dimension. We then develop efficient algorithms for membership, face-detection and Boolean operations for these representations.
  • Abstract (in french):

    Dans ce papier nous étudions la représentation des polyèdres orthogonaux, c'est à dire des unions finies d'hyperrectangles. Nous définissons plusieurs représentations pour ces polyèdres basées sur leurs sommets, et nous prouvons que ces représentations compactes sont canoniques pour tous les polyèdres convexes et non-convexes en dimension quelconque. Nous développons ensuite des algorithmes efficaces pour le problème de l'appartenance, de la détection des faces et des opérations booléennes pour ces représentations.
  • Keywords:

    Orthogonal Polyhedra, Representations.
  • Keywords (in french):

    Polyèdres Orthogonaux, Représentations.
  • Availability: Electronic copy only.
  • Citation: Accepted for publication in "Hybrid Systems: Computation and Control", HSCC'99.
  • Size: 2+14p
  • Format: Compressed PostScript
  • Get it

A constructive solution to the juggling problem in systolic array synthesis.

  • By: Alain Darte , Robert Schreiber , B. Ramakrishna Rau , Frederic Vivien
  • Number: RR1999-15
  • Date: February 1999
  • Abstract:

    We describe a new, practical, constructive method for solving the well-known conflict-free scheduling problem for the locally sequential, globally parallel (LSGP) case of systolic array synthesis. Earlier attempts to solve this problem provided a solution with an important practical disadvantage, which we discuss. Here, we provide a closed form solution that enables the enumeration of all valid schedules. The second part of the paper discusses another practical issue: reducing the cost of hardware whose function is to control the flow of data, enable or disable functional units, and generate memory addresses. We present a new technique for controlling the complexity of these housekeeping functions in a systolic array. Both of these techniques have been incorporated into a software system for the automatic synthesis of hardware accelerators developed by HP Labs.
  • Abstract (in french):

    Nous présentons une méthode constructive permettant de résoudre le problème bien connu de l'ordonnancement sans conflits du partitionnement localement séquentiel, globalement séquentiel (LSGP) de la synthèse de réseaux systoliques. Les techniques proposées antérieurement conduisent à des solutions comportant quelques inconvénients pratiques majeurs que nous discutons. Ici, nous donnons une expression analytique des solutions qui nous permet d'énumérer tous les ordonnancements valides. La seconde partie du rapport discute d'un autre aspect pratique: comment réduire le coût du matériel dont le rôle est de contrôler le flot des données, d'activer ou de désactiver les unités fonctionnelles et de générer les adresses mémoire. Nous montrons comment maîtriser la complexité de ces calculs de maintenance du circuit. Ces deux techniques ont été intégrées dans un logiciel de synthèse automatique d'accélérateurs matériels, développé dans les laboratoires de Hewlett-Packard.
  • Keywords:

    Hardware Accelerators, Systolic Arrays, Automatic Synthesis, LSGP Partitioning.
  • Keywords (in french):

    Acclérateurs Matériels, Réseaux Systoliques, Synthèse Automatique, Partitionnement LSGP.
  • Availability: Electronic copy only.
  • Citation: Not published yet.
  • Size: 2+22p
  • Format: Compressed PostScript
  • Get it

Bounded Polymorphism for Extensible Objects.

  • By: Luigi Liquori
  • Number: RR1999-16
  • Date: March 1999
  • Abstract:

    In the ECOOP'97 conference, the author of the present paper investigated a conservative extension, called ACone, of the first-order Object Calculus ACo of Abadi and Cardelli, supporting method extension in presence of object subsumption. In this paper, we extend that work with explicit variance annotations and selftypes. The resulting calculus, called AC, is a proper extension of ACone. Moreover it is proved to be type sound.
  • Abstract (in french):

    A la conférence ECOOP'97, l'auteur du rapport a présenté une extension, appelée ACone, du calcul du premier ordre de Abadi et Cardelli ; ce calcul supporte la "method extension" et l'"objet subsumption". Cet article est la continuation de l'article de ECOOP : on ajoute des "explicit variance annotations" et des "selftypes". Le calcul obtenu est une extension propre et "sound" de ACone.
  • Keywords:

    Type Systems, Design and Semantics of Object-Oriented Languages.
  • Keywords (in french):

    Langages Basés sur les Objets, Sémantique Opérationnelle, Système de Types.
  • Availability: Electronic copy only.
  • Citation: A smaller version will appear in Proc of Types-99.
  • Size: 2+22p
  • Format: Compressed PostScript
  • Get it

A Proposal for a Heterogeneous Cluster ScaLAPACK (Dense Linear Solvers).

  • By: Vincent Boudet , Fabrice Rastello , Yves Robert
  • Number: RR1999-17
  • Date: March 1999
  • Abstract:

    This paper discusses some algorithmic issues when computing with a heterogeneous network of workstations (the typical poor man's parallel computer). How is it possible to efficiently implement numerical linear algebra kernels like those included in the ScaLAPACK library ? Dealing with processors of different speeds requires to use more involved strategies than purely static block-cyclic data distributions. Dynamic data distribution is a first possibility but may prove impractical and not scalable due to communication and control overhead. Static data distributions tuned to balance execution times constitute another possibility but may prove inefficient due to variations in the processor speeds (e.g. because of different workloads during the computation). There is a challenge in determining a trade-off between the data distribution parameters and the process spawning and possible migration (redistribution) policies. We introduce a semi-static distribution strategy that can be refined on the fly, and we show that it is well-suited to parallelizing several kernels of the ScaLAPACK library such as LU or QR decomposition.
  • Abstract (in french):

    Dans ce rapport, nous nous interessons a des problèmes algorithmiques liés à l'exécution de programmes sur un réseau de stations hétérogène (La machine parallèle du programmeur pauvre). Comment implémenter les algorithmes de calcul linéaire, de manière efficace, tout comme ceux inclus dans la librairie ScaLAPACK? Si dans le cadre d'un réseau de machines hétéerogènes, une distribution cyclique purement statique des données est souvent optimale, elle n'est pas du tout adaptée à cette nouvelle configuration. Une distribution dynamique ne constitue pas non plus la solution à notre problème, à cause du surcoup de communications lié à la présence d'un maître ou à la présence incessante de redistributions. Un solution purement statique reste limitée à de courtes exécutions durant lesquelles la charge des processeurs ne varie pas. Nous proposons donc un algorithme semi-statique, quasi optimal dans le cas ou la aharge des processeurs ne varie pas, et permettant toutefois des redistributions au vol de temps en temps le cas échéant. Ainsi, nous montrons par des tests effectués sur 2 plateformes différentes que cette approche constitue probablement une solution bien adaptée à la parallélisation de plusieurs noyaux de la librairie ScaLAPACK, comme par exemple la décomposition LU ou QR.
  • Keywords:

    Heterogeneous Networks, Distributed-Memory, Different-Speed Processors, Communication-Computation Overlap, Scheduling, Mapping, Numerical Libraries.
  • Keywords (in french):

    Plateforme Hétérogène, Mémoire Distribuée, Processeurs de Vitesse Différente, Ordonnancement, Recouvrement Calcul/Communications, Distribution, Librairies de Calcul Numérique.
  • Availability: Electronic copy only.
  • Citation: Not published yet.
  • Size: 2+16p
  • Format: Compressed PostScript
  • Get it

A Construction of Distributed Reference Counting.

  • By: Luc Moreau , Jean Duprat
  • Number: RR1999-18
  • Date: March 1999
  • Abstract:

    Distributed reference counting is a general purpose technique, which may be used, e.g., to detect termination of distributed programs or to implement distributed garbage collection. We present a distributed reference counting algorithm and a mechanical proof of correctness carried out using the proof assistant Coq. The algorithm is formalised by an abstract machine, and its correctness has two different facets. The safety property ensures that if there exists a reference to a resource, then its reference counter will be strictly positive. Liveness guarantees that if all references to a resource are deleted, its reference counter will eventually become null.
  • Abstract (in french):

    Le décompte des références distribuées est une technique d'usage très général, qui peut être utilisée, par exemple, pour détecter la terminaison de programmes distribués ou pour implanter un ramasse miettes distribué. Nous décrivons un algorithme de décompte de références distribuées et une preuve mécanique de sa correction qui utilise l'assistant de preuve Coq. L'algorithme est basée sur une machine abstraite, et la correction se fait en deux étapes. La propriété de sureté qui garantit que, s'il existe une référence à une ressource, alors le compteur de référence est strictement positif. La propriété de vivacité garantit que si toutes les références à une ressource ont été effacées, alors, en fin de compte, le compteur s'annulera.
  • Keywords:

    Distributed Programs, Reference Counting, Computer Aided Proofs.
  • Keywords (in french):

    Programmes Distribués, Décompte de références, Preuves Assistées par Ordinateur.
  • Availability: Electronic copy only.
  • Citation: Not published yet (submitted to Acta Informatica).
  • Size: 2+30p
  • Format: Compressed PostScript
  • Get it

Algorithmic Issues for (Distributed) Heterogeneous Computing Platforms. Extended Abstract.

  • By: Vincent Boudet , Fabrice Rastello , Yves Robert
  • Number: RR1999-19
  • Date: March 1999
  • Abstract:

    Future computing platforms will be distributed and heterogeneous. Such platforms range from heterogeneous networks of workstations (NOWs) to collections of NOWs and parallel servers scattered throughout the world and linked through high-speed networks. Implementing tightly-coupled algorithms on such platforms raises several challenging issues. New data distribution and load balancing strategies are required to squeeze the most out of heterogeneous platforms. In this paper, we first summarize previous results obtained for heterogeneous NOWs, dealing with the implementation of standard numerical kernels such as finite-difference stencils or dense linear solvers. Next we target distributed collections of heterogeneous NOWs, and we discuss data allocation strategies for dense linear solvers on top of such platforms. These results indicate that a major algorithmic and software effort is needed to come up with efficient numerical libraries on the computational grid.
  • Abstract (in french):

    Sans aucun doute, les machines parallèles du futur seront des machines distribuées et hétérogènes. Cela va du simple réseau hétérogène de stations de travail (NOW), à l'interconnexion de tels réseaux et de machines parallèles répartis dans le monde entier et reliées par des réseaux rapides. Dans ce rapport, tout d'abord, nous résumons les résultats précédemment obtenus, relatifs au calcul linéaire ou aux problèmes de différences finies, sur un simple NOW hétérogène. Ensuite, nous traitons du problème de l'allocation des données en algèbre linéaire dans le cas d'un réseau plus large, composé de sous réseaux, etc... Ces résultats montrent la nécessité d'un effort conséquent dans cette direction avant de pouvoir, à terme, mettre en place une librairie d'algèbre linéaire efficace sur le réseau mondial des stations de travail.
  • Keywords:

    Meta-Computing, Heterogeneous Networks, Computational Grid, Distributed-Memory, Different-Speed Processors, Scheduling, Mapping, Finite-Difference Stencils, Numerical Libraries.
  • Keywords (in french):

    Meta-Computing, Computational Grid, Plateforme Hétérogène, Mémoire Distribuée, Processeurs de Vitesses Différentes, Ordonnancement, Distribution, Librairies de Calcul Numérique, Méthodes de Différences Finies.
  • Availability: Electronic copy only.
  • Citation: Not published yet.
  • Size: 2+9p
  • Format: Compressed PostScript
  • Get it

On the mortality problem for matrices of low dimensions.

  • By: Olivier Bournez , Michael Branicky
  • Number: RR1999-20
  • Date: March 1999
  • Abstract:

    In this paper, we discuss the existence of an algorithm to decide if a given set of 2 \times 2 matrices is mortal: a set F=\{A_1,\dots,A_m\} of 2 \times 2 matrices is said to be \motnouv{mortal} if there exist an integer k \ge 1 and some integers i_1,i_2,\dots,i_k \in \{1, \ldots, m\} with A_{i_1} A_{i_2} \cdots A_{i_k}=0. We survey this problem and propose some new extensions: we prove the problem to be BSS-undecidable for real matrices and Turing-decidable for two rational matrices. We relate the problem for rational matrices to the entry equivalence problem, to the zero in the left upper corner problem and to the reachability problem for piecewise affine functions. Finally, we state some NP-completeness results.
  • Abstract (in french):

    Dans ce papier, nous discutons l'existence d'un algorithme pour décider si un ensemble donné de matrices 2 \times 2 est mortel: un ensemble F=\{A_1,\dots,A_m\} de matrices 2 \times 2 est dit \motnouv{mortel} s'il existe un entier k \ge 1 et des entiers i_1,i_2,\dots,i_k \in \{1, \ldots, m\} avec A_{i_1} A_{i_2} \cdots A_{i_k}=0. Nous présentons une synthèse des résultats connus sur ce problème et présentons quelques extensions: nous prouvons que le problème est BSS-indécidable pour les matrices réelles et Turing-décidable pour les matrices rationnelles. Nous relions le problème au problème de l'égalité des coefficients, au problème du zéro dans un coin et au problème de l'atteignabilité pour les fonctions affines par morceaux. Enfin, nous établissons des résultats de NP-complétude.
  • Keywords:

    Mortality, Matrices, Decidability.
  • Keywords (in french):

    Mortalité, Matrices, Décidabilité.
  • Availability: Electronic copy only.
  • Citation: Not published yet.
  • Size: 2+13p
  • Format: Compressed PostScript
  • Get it

Lower bounds are not easier over the reals: inside PH.

  • By: Herve Fournier , Pascal Koiran
  • Number: RR1999-21
  • Date: March 1999
  • Abstract:

    We prove that all NP problems over the reals with addition and order can be solved in polynomial time with the help of a boolean NP oracle. As a consequence, the ``P = NP?'' question over the reals with addition and order is equivalent to the classical question. For the reals with addition and equality only, the situation is quite different since P is known to be different from NP. Nevertheless, we prove similar transfer theorems for the polynomial hierarchy.
  • Abstract (in french):

    On montre que tous les problèmes NP sur les réels avec addition et ordre peuvent êetre résolus en temps polynomial à l'aide d'un oracle NP booléen. Il en résulte que la question ``P=NP ?'' sur les réels avec addition et ordre est équivalente à la question classique. Pour les réels avec addition et égalité la situation est bien différente puisqu'il est connu que P est différent de NP. Cependant, nous démontrons des résultats de transferts similaires pour la hiérarchie polynomiale.
  • Keywords:

    Transfer Theorems, Decision Trees, Point Location, Algebraic Complexity, Blum-Shub-Smale Model.
  • Keywords (in french):

    Théorèmes de Transfert, Arbres de Decision, Localisation de Point, Complexité Algébrique, Modèle de Blum-Shub-Smale.
  • Availability: Electronic copy only.
  • Citation: Not published yet.
  • Size: 2+p
  • Format: Compressed PostScript
  • Get it

Parallel Evaluation of Relational Queries on a Network of Workstations.

  • By: Lionel Brunie , Matthieu Exbrayat , André Flory
  • Number: RR1999-22
  • Date: March 1999
  • Abstract:

    In this paper we propose an innovative approach to handle ``read-most'' data bases. This approach is based on a parallel extension, called parallel relational query evaluator, working over a network of workstations, in a coupled mode with a sequential Database Management System (DBMS). We present a detailed architecture of the parallel query evaluator and focus on the management of data during executions and transmissions, especially through macro-pipelining. We then present Enkidu, the prototype that has been build according to our concepts. We finally expose a set of measurements, conducted over Enkidu, highlighting both the specific performances of macro-pipelining and the global ones of Enkidu.
  • Abstract (in french):

    Ce document propose une approche innovante de gestion des bases de données ``majoritairement en lecture'', c'est-à-dire pour lesquelles l'accès en lecture est très nettement dominant vis-à-vis de l'accès en écriture. L'approche proposée se fonde sur l'usage d'une extension parallèle, appelée évaluateur relationnel parallèle, fonctionnant sur un réseau de stations, en couplage avec un Système de Gestion de Bases de Données (SGBD) séquentiel. Nous présentons ici l'architecture détaillée de cet évaluateur parallèle. Nous insistons particulièrement sur la gestion des données durant les transferts et les interrogations, en étudiant notamment l'utilisation du macro-pipelining. Nous introduisons ensuite notre implémentation de l'évaluateur parallèle, le prototype Enkidu. Nous présentons enfin divers tests et mesures réalisés sur le prototype Enkidu et mettant en avant, non seulement les performances globales du prototype, mais également celles plus spécifiques liées au macro-pipelining.
  • Keywords:

    Relational Database, Query Parallelism, Network of Workstations, Macro-Pipelining.
  • Keywords (in french):

    Base de Données Relationnelle, Parallélisation de Requêtes, Réseau de Stations, Macro-Pipelining.
  • Availability: Electronic copy only.
  • Citation: Not published yet.
  • Size: 2+16p
  • Format: Compressed PostScript
  • Get it

Multi-protocol communications and high speed networks.

  • By: Benoit Planquelle , Jean-Francois Mehaut , Nathalie Revol
  • Number: RR1999-23
  • Date: March 1999
  • Abstract:

    Due to heterogeneity in modern computing systems, methodological and technical problems arise for the development of parallel applications. Heterogenity occurs for instance at architecture level, when processing units use different data representation or exhibit various performances. At interconnection level, heterogeneity can be found in the programming interfaces and in the communication performances. In this paper, we focus on problems related to heterogeneity in the frame of interconnected clusters of workstations. In order to help the programmer to overcome these problems, we propose an extension of the multithreaded programming environment PM2. It facilitates the development of efficient parallel applications on such systems. The implementation of this extension is then described, the mechanisms involved are fundamental for an environment for meta-computing.
  • Abstract (in french):

    L'heterogeneite des nouvelles architectures distribuees pose de nouveaux problemes methodologiques et techniques pour le developpement d'applications paralleles. Au niveau architectural, les processeurs peuvent utiliser differents formats de representation des donnees et afficher des niveaux de performance forts differents. Dans ce papier, nous nous interesserons a interconnecter des grappes de PC par Internet. Nous proposerons une extension de l'environnement PM2 pour lui permettre de supporter efficacement des applications paralleles s'executant des infrastructures heterogenes. Nous decrirons dans ce papier les mecanismes implementes dans PM2 qui constituent une extension necessaire pour le support d'applications dans un environnement de type meta-computing.
  • Keywords:

    Clusters of Workstations, Multithreaded Runtimes, Communication Polling, Data Conversion.
  • Keywords (in french):

    Grappes de Stations, Environnements Multithreads, Scrutation des Communications, Conversion de Donnees.
  • Availability: Electronic copy only.
  • Citation: Euro-Par '99: Parallel Processing, volume 1685 of Lect. Notes
  • Size: 2+8p
  • Format: Compressed PostScript
  • Get it

An algebraic method to compute a shortest path of local flips between two tilings.

  • By: Eric Remila
  • Number: RR1999-24
  • Date: April 1999
  • Abstract:

    A flip of a tiling T is a local transformation of T using a bounded number of tiles. For different kinds of tilings (formed from two bars (a horizontal and a vertical one), from triangles and "leaning dominoes", or from "calissons"), we produce an algorithm of optimal time complexity which, given a pair (T, T') of tilings of a same figure, exhibits a length minimal sequence of flips to transform T into T'. These algorithms are based on the use of tiling groups, and of their quotients and subgroups.
  • Abstract (in french):

    Une rotation locale d'un pavage est une transformation de ce pavage ne mettant en jeu qu nombre uniformémemt borné de pavés. Pour différents types de pavages (par deux barres (l'une horizontale et l'autre verticale), par des triangles et des dominos penchés ou par des calissons) nous produisons un algorithme de complexité optimale qui, étant donnée une paire de pavages d'une même figure, exhibe une suite de rotation locales, de longueur minimale, faisant passer d'un pavage à l'autre. Ces algorithmes utilisent les groupes de pavage, et leurs quotients et sous-groupes.
  • Keywords:

    Tiling, Riling Group.
  • Keywords (in french):

    Pavage, Groupe de Pavage.
  • Availability: Electronic copy only.
  • Citation: Submitted to FOCS 99.
  • Size: 2+13p
  • Format: Compressed PostScript
  • Get it

The lattice structure of the set of domino tilings of a polygon.

  • By: Eric Remila
  • Number: RR1999-25
  • Date: April 1999
  • Abstract:

    Fix a polygon P with vertical and horizontal sides. We first recall how each tiling of P with dominoes (i. e. rectangles 2 \times 1) can be encoded by a height function. Such an encoding induces a lattice structure on the set T_P of the tilings of P. We give some applications of this structure, and we especially describe the order of meet irreducible elements of T_P.
  • Abstract (in french):

    Fixons un polygone P, dont les côtés sont parallèles aux axes. Nous commençons par rappeler commennt tout pavage de P par des dominos (i. e. rectangles 2 \times 1) peut être codé au moyen d'une fonction de hauteur. Un tel codage induit une structure de treillis distributif sur l'ensemble T_P des pavages de P. Après avoir donné deux applications de cette structure, nous étudions en détail la structure de l'ordre restreint aux éléments irréductibles de T_P.
  • Keywords:

    Tiling, Height Function, Distributive Lattice.
  • Keywords (in french):

    Pavage, Fontion de Hauteur, Treillis Distributif.
  • Availability: Electronic copy only.
  • Citation: Submitted to ORDAL'99.
  • Size: 2+12p
  • Format: Compressed PostScript
  • Get it

Loop Alignment for Memory Accesses Optimization.

  • By: Antoine Fraboulet , Guillaume Huard , Anne Mignotte
  • Number: RR1999-26
  • Date: April 1999
  • Abstract:

    Portable or embedded systems allow more and more complex applications like multimedia today. These applications and submicronic technologies have made the power consumption criterium crucial. We propose new techniques thanks to which we can optimize the behavioral description of an integrated system before the hardware/software partitioning (Codesign). These transformations are performed on ``for'' loops that constitute the main parts of the multimedia code which handle the arrays. We present in this paper two new (polynomial) techniques for minimizing memory accesses in loop nests by data temporal locality optimization.
  • Abstract (in french):

    Les systèmes portables ou embarqués supportent des applications toujours plus complexes comme aujourd'hui le multimédia. Ces applications et les technologies submicroniques ont rendu le critère de la consommation incontournable. Nous proposons de nouvelles techniques permettant d'optimiser la description comportementale d'un système intégré avant le partitionnement matériel-logiciel (Codesign). Ces transformations sont effectuées sur les boucles ``for'' qui sont les principales parties du code multimédia manipulant les tableaux. Nous présentons dans ce rapport deux nouvelles techniques (polynomiales) pour minimiser les accès à la mémoire dans les nids de boucles par optimisation de la localité temporelle des données.
  • Keywords:

    Memory Optimization, Code Transformation, Codesign, Loop Alignment (Folding).
  • Keywords (in french):

    Optimisation Mémoire, Transformation de Code, Conception Conjointe (Codesign), Alignement de Boucles.
  • Availability: Electronic copy only.
  • Citation: Not published yet.
  • Size: 2+13p
  • Format: Compressed PostScript
  • Get it

Using VIA to build distributed, multithreaded runtime systems: a case study.

  • By: Luc Bouge , Jean-Francois Mehaut , Raymond Namyst , Loic Prylli
  • Number: RR1999-27
  • Date: May 1999
  • Abstract:

    The Virtual Interface Architecture (VIA) has been recently introduced as a portable interface for high speed communication on high performance local networks. We show that VIA cannot be directly used as a building block for distributed, multithreaded runtime systems, and that an additional medium-level layer is needed to fill the gap with the applications. This layer should be carefully design so as to preserve the definite qualities of VIA, and yet hide its low-level aspect to the user. As a case study, we present an implementation of our Madeleine API for high performance networking on top of VIA, and we evaluate the potential benefits of this approach through some preliminary experiments.
  • Abstract (in french):

    La bibliothèque de communication VIA (Virtual Interface Architecture) a été présentée récemment comme une interface portable pour les communications hautes performances sur les réseaux locaux. Nous expliquons pourquoi la bibliothèque VIA ne peut être utilisée directement pour la construction d'exécutifs à base de processus légers (multithreading) pour les applications distribuées en pratique. Un niveau intermédiaire d'interface est nécessaire à cause de la grande différence de niveaux d'abstraction entre les fonctions VIA et les besoins des applications. Cette interface intermédiaire devrait être conçue de manière à préserver les qualités indéniables de VIA, mais elle devrait aussi masquer ses aspects de plus bas niveau. À titre d'exemple, nous décrivons une implantation au-dessus de VIA de notre bibliothèque de communication Madeleine, spécialement conçue pour l'utilisation de réseaux locaux hautes performances. Nous discutons l'intérêt potentiel d'une telle appriche à partir de quelques résultats expérimentaux préliminaires.
  • Keywords:

    VIA, High Performance Networking, Distributed Multithreading, Madeleine, PM2, Fast Ethernet.
  • Keywords (in french):

    VIA, Réseau Haut Débit, Communication Haute Performance, Calcul Distribué, Processus Léger, Madeleine, PM2, Fast Ethernet.
  • Availability: Electronic copy only.
  • Citation: Proc. 2000 ACM Symposium on Applied Computing (SAC 2000), Villa Olmo,
  • Size: 2+14p
  • Format: Compressed PostScript
  • Get it

Efficient Load-balancing and Communication Overlap in Parallel Shear-Warp Algorithm on a Cluster of PCs.

  • By: Frederique Chaussumier , Frédéric Desprez , Michel Loi
  • Number: RR1999-28
  • Date: May 1999
  • Abstract:

    In the medical field, volume rendering provides good quality 3D visualizations but is still not enough interactive for a day-to-day practice. The most efficient sequential algorithm is the shear-warp algorithm. It renders up to 10 images per second for a small dataset. The goal of this report is to present an efficient parallel implementation of the shear-warp algorithm for a distributed memory architecture, a cluster of PCs connected with a high speed network. This highly irregular algorithm led us to implement a dynamic load balancing algorithm. Furthermore, to reduce the overhead due to data redistribution, we overlap communications with computations using MPI's asynchronous communications. Using a good load-balancing and communication overlap, our implementation generates real-time 3D medical images with a good quality and a high resolution.
  • Abstract (in french):

    Dans le domaine médical, le rendu volumique offre des visualisations 3D de bonne qualité mais il n'est pas suffisement intéractif pour une utilisation quotidienne. L'algorithme séquentiel le plus efficace est l'algorithme du Shear-Warp. Il peut rendre jusqu'à 10 images par seconde pour un petit jeu de données. Le but de ce rapport est de présenter une implémentation parallèle efficace de l'algorithme du Shear-Warp pour une architecture à mémoire distribuée, un cluster de PC connectés avec un réseau rapide. Cet algorithme très irrégulier nous a conduit à implémenter un algorithme d'équilibrage des charges dynamique. De plus, afin de réduire le surcoût des redistributions, nous recouvrons les communications avec les calculs en utilisant les communications asynchrones de MPI. Avec l'équilibrage des charges dynamique et le recouvrement des communications, notre implémentation génère des images médicales 3D en temps réel avec une bonne qualité et une haute résolution.
  • Keywords:

    Volume Rendering, Shear Warp Algorithm, Dynamic Load-Balancing, Communication Overlap.
  • Keywords (in french):

    Rendu Volumique, Algorithme du Shear-Warp, Equilibrage des Charges.
  • Availability: Electronic copy only.
  • Citation: Not published yet.
  • Size: 2+20p
  • Format: Compressed PostScript
  • Get it

Loop shifting for loop compaction.

  • By: Alain Darte , Guillaume Huard
  • Number: RR1999-29
  • Date: May 1999
  • Abstract:

    The idea of decomposed software pipelining is to decouple the software pipelining problem into a cyclic scheduling problem without resource constraints and an acyclic scheduling problem with resource constraints. In terms of loop transformation and code motion, the technique can be formulated as a combination of loop shifting and loop compaction. Loop shifting amounts to move statements between iterations thereby changing some loop independent dependences into loop carried dependences and vice versa. Then, loop compaction schedules the body of the loop considering only loop independent dependences, but taking into account the details of the target architecture. In this paper, we show how loop shifting can be optimized so as to minimize both the length of the critical path and the number of dependences for loop compaction. Both problems (and the combination) are polynomially solvable with fast graph algorithms, the first one by using an algorithm due to Leiserson and Saxe, the second one bya variant of a minimum-cost flow algorithm.
  • Abstract (in french):

    L'idée du pipeline logiciel décomposé est de découpler le problème en un problème d'ordonnancement cyclique sans contraintes de ressource et un problème d'ordonnancement acyclique avec contraintes de ressources. En termes de transformations de boucles et de déplacement de code, cette technique peut être formulée comme une combinaison de décalage et de compaction de boucle. Le décalage de boucle déplace les instructions entre différentes itérations ce qui change certaines dépendances internes en dépendances portées par la boucle et vice-versa. Puis, la compaction de boucle ordonnance le corps de la boucle en ne respectant que les dépendances internes mais en prenant en compte les contraintes architecturales. Dans ce rapport, nous montrons comment le décalage de boucle peut être optimisé afin de minimiser à la fois la longueur du chemin critique et le nombre de contraintes pour la compaction. Les deux problèmes (et leur combinaison) sont solubles en temps polynômial par des algorithmes de graphes, le premier par un algorithme dû à Leiserson and Saxe, le second par une variante d'algorithme de flot à coût minimum.
  • Keywords:

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

    Pipeline Logiciel, Resynchronisation de Circuit, Ordonnancement de Liste, Ordonnancement Cyclique.
  • Availability: Electronic copy only.
  • Citation: Submitted to LCPC'99.
  • Size: 2+24p
  • Format: Compressed PostScript
  • Get it

Addressed Term Rewriting Systems.

  • By: Frederic Lang , Daniel Dougherty , Pierre Lescanne , Kristoffer Rose
  • Number: RR1999-30
  • Date: June 1999
  • Abstract:

    We propose Addressed Term Rewriting Systems (ATRS) as a solution to the still-standing problem of finding a simple yet formally useful framework that can account for computation with sharing, cycles, and side effects. ATRS are characterised by the combination of three features: they work with terms where structural induction is useful, they use a minimal ``back-pointer'' representation of cyclic data, and they ensure a bounded complexity of rewrite steps by eliminating implicit pointer redirection. In the paper we develop this and show how it is a very useful compromise between less abstract term graph rewriting and the more abstract equational rewriting.
  • Abstract (in french):

    Nous proposons les Systèmes de Réécriture de Termes à Adresses (ATRS) comme solution au problème de définition d'un cadre simple et formel qui permet de rendre compte de calculs mettant en oeuvre du partage, des cycles, et des effets de bord. Les ATRS sont caractérisés par la combinaison de trois aspects : ils sont basés sur une représentation des graphes par des termes, où l'induction structurelle est utile, ils mettent en oeuvre une représentation minimale des structures de données cyclique par ``pointeur arriére'', et ils assurent une complexité bornée des pas de réécriture en éliminant les redirections de pointeurs implicites. Dans cet article, nous développons ceci, et nous montrons qu'il s'agit d'un compromis très utile entre la réécriture de graphes, moins abstraite, et la réécriture équationnelle, plus abstraite.
  • Keywords:

    Rewriting, Addresses, Mutation, Sharing, Cycles.
  • Keywords (in french):

    Réécriture, Adresses, Mutation, Partage, Cycles.
  • Availability: Electronic copy only.
  • Citation: Not published yet.
  • Size: 2+34p
  • Format: Compressed PostScript
  • Get it

Data Allocation Strategies for Dense Linear Algebra Kernels on Heterogeneous Two-dimensional Grids.

  • By: Vincent Boudet , Antoine Petitet , Fabrice Rastello , Yves Robert
  • Number: RR1999-31
  • Date: June 1999
  • Abstract:

    We study the implementation of dense linear algebra computations, such as matrix multiplication and linear system solvers, on two-dimensional (2D) grids of heterogeneous processors. For these operations, 2D-grids are the key to scalability and efficiency. The uniform block-cyclic data distribution scheme commonly used for homogeneous collections of processors limits the performance of these operations on heterogeneous grids to the speed of the slowest processor. We present and study more sophisticated data allocation strategies that balance the load on heterogeneous 2D-grids with respect to the performance of the processors. The practical usefulness of these strategies is fully demonstrated by experimental data for a heterogeneous network of workstations.
  • Abstract (in french):

    Dans ce rapport, nous étudions l'implémentation de programmes d'algèbre linéaire, tels que la multiplication de matrices ou la résolution de systèmes linéaires, sur une grille hétérogène bidimensionnelle de processeurs. Pour ces problèmes, seule une grille 2D assure la scalabilité des algorithmes utilisés. La distribution classique ``bloc-cyclique'' utilisée communément dans le cas d'une grille homogène de processeurs, réduit la performance sur une grille hétérogène à la vitesse du processeur le plus lent. L'intérêt pratique de notre étude est grandement justifié par des experiences effectuées sur un réseau local de machines hétérogènes.
  • Keywords:

    Heterogeneous Network, Heterogeneous Grid, Different-Speed Processors, Load-Balancing, Data Distribution, Data Allocation, Numerical Libraries.
  • Keywords (in french):

    Plateforme Hétérogène, Grille Hétérogène, Processeurs de Vitesses Différentes, Distribution des Données, Equilibrage de Charges, Librairies de Calcul.
  • Availability: Electronic copy only.
  • Citation: Not published yet.
  • Size: 2+24 pages
  • Format: Compressed PostScript
  • Get it

Pebble Automata. Figures families recognition and universality.

  • By: Marianne Delorme , Jacques Mazoyer
  • Number: RR1999-32
  • Date: July 1999
  • Abstract:

    In this paper, we consider the pebble automata introduced by Blum and Hewitt, but now moving through the unbounded plane Z^{2}. We are interested in their ability to recognize families of dotted figures. Contrary to the bounded case studied by Blum and Hewitt, the hierarchy collapses: there are families recognized with 0, 1, 2 and 3 pebbles, but each family recognized with more than three pebbles is recognized with exactly 3 ones. This result is connected to the existence of an intrinsically universal 3-pebble-automaton. We formally define the underlying universality notion, and prove that there exists some 3-pebble automaton intrinsically universal, but no such automaton with only 2 pebbles.
  • Abstract (in french):

    Dans cet article, nous considérons les automates à galets introduits par Blum et Hewitt, mais comme pouvant, maintenant, se déplacer dans le plan Z^{2} tout entier. Nous nous intéressons à leur capacité de reconnaissance de familles de figures pointées. Contrairement au cas borné étudié par Blum et Hewitt, la hiérarchie s'éffondre : il existe des familles reconnues avec 0, 1, 2 et 3 galets, mais toute famille reconnue avec plus de 3 galets l'est avec exactement 3 galets. Ce résultat est directement relié à l'existence d'un automate à 3 galets intrinsèquement universel. Nous définissons formellement la notion d'universalité sous-jacente, et nous prouvons qu'il existe un automate intrinsèquement universel à 3 galets mais aucun à 2 galets.
  • Keywords:

    Figure Recognition, Pebble Automata, Universality.
  • Keywords (in french):

    Reconnaissance de Figures, Automates à Galets, Universalité.
  • Availability: Electronic copy only.
  • Citation: Submitted to Informaticae Fundamentae.
  • Size: 2+71p
  • Format: Compressed PostScript
  • Get it

On the sensitivity of additive cellular automata in Besicovitch topologies.

  • By: Enrico Formenti
  • Number: RR1999-33
  • Date: July 1999
  • Abstract:

    We prove that additive cellular automata in the Besicovitch topology are sensitive to initial conditions if and only if the Hausdorff dimension D_H of their Willson limit set is strictly bigger than 1.
  • Abstract (in french):

    Nous montrons que les automates cellulaires additifs sur une topologie de Besicovitch sont sensible aux conditions initiales si et seulement si la dimension de Hausdorff D_H de l'ensemble limite de Willson est strictement plus grande que 1.
  • Keywords:

    Cellular Automata, Hausdorff Dimension, Besicovitch Topology.
  • Keywords (in french):

    Automates Cellulaires, Dimension de Hausdorff, Topologie de Besicovitch.
  • Availability: Electronic copy only.
  • Citation: Submitted to Fundamenta informaticae.
  • Size: 2+12p
  • Format: Compressed PostScript
  • Get it

A group interpretation of particles generated by one dimensional cellular automaton, 54 Wolfram's rule.

  • By: Bruno Martin
  • Number: RR1999-34
  • Date: August 1999
  • Abstract:

    One dimensional cellular automata are known to be able to present complex behaviors. In some cases, their evolution may be understood as movings, collisions, creations of particles. In the case of the special Wolfram 54 rule, N. Boccara has previously pointed out basic particles. In this paper, we introduce a group which allows to formally study interactions between these particles. Coming back on the complexity of the rule 54, using a new algebraic classification due to I. Rapaport, we give sense to, and prove, the fact that the rule 54 is not simple.
  • Abstract (in french):

    Les automates cellulaires sont connus pour présenter des comportements complexes. Dans certains cas, il est possible de faire une analogie entre l'évolution de la règle des l'interaction de particules. Dans le cas de la règle 54 de Wolfram, N. Boccara a précédemment mis en évidence les particules élémentaires permettant une telle interprétation. Dans ce papier, nous introduisons un groupe qui permet d'étudier formellement les interactions entre ces particules. Ces résultats nous donnent un nouvel éclairage sur la complexité de la règle 54, en particulier, en utilisant la nouvelle classification algébrique d'I.~Rapaport, nous montrons que d'un certain point de vu, la règle 54 n'est pas simple.
  • Keywords:

    Cellular Automaton, Particle, Tiling.
  • Keywords (in french):

    Automate Cellulaire, Particule, Pavage.
  • Availability: Electronic copy only.
  • Citation: Not published yet.
  • Size: 2+24p
  • Format: Compressed PostScript
  • Get it

A Geometrical Hierarchy on Graphs via Cellular Automata.

  • By: Bruno Martin
  • Number: RR1999-35
  • Date: August 1999
  • Abstract:

    Historically, cellular automata were defined on the lattices \IZ n, but the definition can be extended to bounded degree graphs. Given a notion of simulation between cellular automata defined on different structures (namely graphs of automata), we can deduce an order on graphs. In this paper, we link this order to graph properties and explicit the order for most of the common graphs.
  • Abstract (in french):

    Les automates cellulaires sont connus pour présenter des comportements complexes. Dans certains cas, il est possible de faire une analogie entre l'évolution de la règle des l'interaction de particules. Dans le cas de la règle 54 de Wolfram, N. Boccara a précédemment mis en évidence les particules élémentaires permettant une telle interprétation. Dans ce papier, nous introduisons un groupe qui permet d'étudier formellement les interactions entre ces particules. Ces résultats nous donnent un nouvel éclairage sur la complexité de la règle 54, en particulier, en utilisant la nouvelle classification algébrique d'I. Rapaport, nous montrons que d'un certain point de vu, la règle 54 n'est pas simple.
  • Keywords:

    Cellular Automaton, Graph of Automata, Simulation, Cayley Graphs, Graph Growth, Hyperbolic Space, Hierarchy.
  • Keywords (in french):

    Automate Cellulaire, Graphe d'Automates, Simulation, Graphes de Cayley, Croissance de Graphes, Espace Hyperbolique, Hierarchie.
  • Availability: Electronic copy only.
  • Citation: Submitted to a special issue of Fundamenta Informaticae.
  • Size: 2+25p
  • Format: Compressed PostScript
  • Get it

Algorithms and Tools for (Distributed) Heterogeneous Computing: A Prospective Report.

  • By: Jean-Francois Mehaut , Yves Robert
  • Number: RR1999-36
  • Date: August 1999
  • Abstract:

    We discuss algorithms and tools to help program and use metacomputing resources in the forthcoming years. Metacomputing with highly distributed heterogeneous environments stands to become a major, if not dominant, method to implement all kinds of parallel applications. In this report, we survey some general aspects of metacomputing (hardware, system and administration issues, as well as the application field). Next we identify some algorithmic issues and software challenges that must be solved to efficiently program and/or transparently use such platforms: - Data decomposition techniques for cluster computing, - Granularity issues for metacomputing, - Scheduling and load-balancing methods, - Programming models. We illustrate each of these issues and challenges by the analysis of several case studies: Cluster ScaLAPACK, AppLeS, Globus, Legion, Albatross and Netsolve. We conclude this report by stating some final remarks and recommendations.
  • Abstract (in french):

    Le calcul distribué à hautes performances, encore appellé ``metacomputing'', constitue aujourd'hui une des approches les plus prometteuses pour implémenter des applications parallèles. Ce rapport présente une synthèse des outils facilitant la programmation et l'utilisation des ressources du métacomputing, et discute les nouvelles techniques algorithmiques à mettre en oeuvre pour utiliser efficacement de telles plateformes. Dans la première partie, nous introduisons les principes généraux du métacomputing (infrastructures matérielles, systèmes et environnements, administration ainsi que le champ applicatif). Nous détaillons ensuite quelques uns des nouveaux problèmes algorithmiques et les challenges logiciels pour pouvoir programmer efficacement et/ou utiliser de manière transparente ces nouvelles infrastructures: - Techniques d'allocation de données pour le calcul sur les grappes, - Problèmes de granularité pour le métacomputing, - Méthodes pour ordonnancer et réguler la charge de calcul, - Modèles de programmation. Nous illustrons cette étude par l'analyse de plusieurs projets: Cluster ScaLAPACK, AppLeS, Globus, Legion, Albatross et Netsolve. Nous concluons ce rapport avec un certain nombre de recommandations sur les directions à suivre dans ce nouveau domaine de recherche.
  • Keywords:

    Meta-Computing, Heterogeneous Networks, Computational Grid, Distributed Environments.
  • Keywords (in french):

    ``Meta-Computing'', Réseaux Hétérogenes, Grille de Calcul, Environnements Distribues.
  • Availability: Electronic copy only.
  • Citation: Not published yet.
  • Size: 2+45p
  • Comment: This research report is directly issued from the prospective report written by Yves Robert for the "ERCIM Prospective Report on ICST Research in Europe", an initiative of ERCIM
  • Format: Compressed PostScript
  • Get it

On strong normalisation of explicit substitution calculi.

  • By: Frederic Lang , Pierre Lescanne
  • Number: RR1999-37
  • Date: August 1999
  • Abstract:

    In this paper, we present an attempt to build a calculus of explicit substitution expected to be confluent on open terms, to preserve strong normalisation and to simulate one step `b-reduction. We show why our attempt failed and we explain how we found a counter-example to the strong normalisation or termination of the substitution calculus. As a consequence, we provide also a counter-example to the strong normalisation of another calculus, namely~`t (the substitution calculus of `l`t) of Riòs, for which the problem was open.
  • Abstract (in french):

    Dans cet article, nous rendons compte d'une tentative pour construire un calcul de substitutions explicite sensé être confluent sur les termes ouverts, préserver la forte normalisation et simuler la `b-r\'eduction en une seule étape. Nous montrons pourquoi notre tentative a échoué et nous expliquons comment nous avons trouvé un contrexemple à la terminaison du calcul de substitutions. Comme conséquence nous exhibons un contrexemple à la forte normalisation d'un autre calcul à savoir le calcul `t (le calcul de substitution de `l`t) de Riòs, pour lequel le problème était ouvert.
  • Keywords:

    Explicit Substitution, Strong Normalisation, Confluence, Termination, Lambda Calculus.
  • Keywords (in french):

    Substitution Explicite, Normalisation Forte, Confluence, Terminaison ,Lambda Calcul.
  • Availability: Electronic copy only.
  • Citation: Not published yet.
  • Size: 2+11p
  • Format: Compressed PostScript
  • Get it

Tiling with bars under tomographic constraints.

  • By: Christoph Durr , Eric Goles , Ivan Rapaport , Eric Remila
  • Number: RR1999-38
  • Date: September 1999
  • Abstract:

    We wish to tile a rectangle or a torus with only vertical and horizontal bars of a given length, such that the number of bars in every column and row equals given numbers. We present results for particular instances and for a more general problem, while leaving open the initial problem.
  • Abstract (in french):

    Nous nous proposons de paver un rectangle ou un tore au moyen de barres horizontales et verticales de longueur donnée, de façon que le nombre de barres dans chaque colonne et chaque ligne soit égal à un nombre donné. Nous présentons des résultats pour des instances particulières et pour un problème plus général, mais nous laissons le problème original ouvert.
  • Keywords:

    Tiling, Tomography, Reconstruction.
  • Keywords (in french):

    Pavage, Tomographie, Reconstruction.
  • Availability: Electronic copy only.
  • Citation: Submitted to Theoretical Computer Science.
  • Size: 2+11p
  • Format: Compressed PostScript
  • Get it

Treewidth and minimum fill-in: grouping the minimal separators.

  • By: Vincent Bouchitte , Ioan Todinca
  • Number: RR1999-39
  • Date: September 1999
  • Abstract:

    We use the notion of potential maximal clique to characterize the maximal cliques appearing in minimal triangulations of a graph. We show that if these objects can be listed in polynomial time for a class of graphs, the treewidth and the minimum fill-in are polynomially tractable for these graphs. We prove that for all classes of graphs for which polynomial algorithms computing the treewidth and the minimum fill-in exist, we can list their potential maximal cliques in polynomial time. Our approach unifies these algorithms. Finally we show how to compute in polynomial time the potential maximal cliques of weakly triangulated graphs, for which the treewidth and the minimum fill-in problems were open.
  • Abstract (in french):

    Nous utilisons la notion de clique maximale potentielle pour caractériser les cliques maximales qui apparaissent dans les triangulations minimales d'un graphe. Nous montrons que si ces objets peuvent être énumérés en temps polynomial pour une classe de graphes, la largeur arborescente et la complétion minimale de ces graphes se calculent aussi en temps polynomial. Nous prouvons que pour toutes les classes de graphes pour lesquels il existe des algorithmes polynomiaux calculant la largeur arborescente et la complétion minimale, nous pouvons générer toutes les cliques maximales potentielles en temps polynomial. Notre approche unifie ainsi ces algorithmes. Enfin, nous montrons comment calculer en temps polynomial les cliques maximales potentielles pour les graphes faiblement triangulés, pour lesquels les problèmes de la largeur arborescente et de la complétion minimale étaient ouverts.
  • Keywords:

    Graph Algorithms, Treewidth, Minimum Fill-In, Weakly Triangulated Graphs.
  • Keywords (in french):

    Algorithmique des Graphes, Largeur Arborescente, Complétion Minimale, Graphes Faiblement Triangulés.
  • Availability: Electronic copy only.
  • Citation: Submitted to SIAM Journal on Computing.
  • Size: 2+20p
  • Format: Compressed PostScript
  • Get it

Listing all potential maximal cliques of a graph.

  • By: Vincent Bouchitte , Ioan Todinca
  • Number: RR1999-40
  • Date: September 1999
  • Abstract:

    A potential maximal clique of a graph is a vertex set that induces a maximal clique in some minimal triangulation of that graph. It is known that if these objects can be listed in polynomial time for a class of graphs, the treewidth and the minimum fill-in are polynomially tractable for these graphs. We show here that the potential maximal cliques of a graph can be generated in polynomial time in the number of minimal separators of the graph. Thus, the treewidth and the minimum fill-in are polynomially tractable for all graphs with polynomial number of minimal separators.
  • Abstract (in french):

    Une clique maximale potentielle d'un graphe est un ensemble de sommets qui induit une clique maximale dans au moins une triangulation minimale de ce graphe. Il a été prouvé que si ces objets peuvent être énumérés en temps polynomial pour une classe de graphes, la largeur arborescente et la complétion minimale sont calculables en temps polynomial pour ces graphes. Nous montrons ici que les cliques maximales potentielles d'un graphe peuvent être générées en temps polynomial par rapport au nombre de ses séparateurs minimaux. En conséquence, la largeur arborescente et la complétion minimale sont calculables en temps polynomial pour tous les graphes ayant un nombre polynomial de séparateurs minimaux.
  • Keywords:

    Treewidth, Minimum Fill-In, Minimal Separators, Potential Maximal Cliques.
  • Keywords (in french):

    Largeur Arborescente, Complétion Minimale, Séparateurs Minimaux, Cliques Maximales Potentielles.
  • Availability: Electronic copy only.
  • Citation: Not published yet.
  • Size: 2+13p
  • Format: Compressed PostScript
  • Get it

Improving Goldschmidt Division, Square Root and Square Root Reciprocal.

  • By: Milos Ercegovac , Laurent Imbert , David Matula , Jean-Michel Muller , Guoheng Wei
  • Number: RR1999-41
  • Date: September 1999
  • Abstract:

    The aim of this paper is to accelerate division, square root and square root reciprocal computations, when Goldschmidt method is used on a pipelined multiplier. This is done by replacing the last iteration by the addition of a correcting term that can be looked up during the early iterations. We describe several variants of the Goldschmidt algorithm assuming 4-cycle pipelined multiplier and discuss obtained number of cycles and error achieved. Extensions to other than 4-cycle multipliers are given.
  • Abstract (in french):

    Le but de cet article est l'accélération de la division, et du calcul de racines carrées et d'inverses de racines carrées lorsque la méthode de Goldschmidt est utilisée sur un multiplieur pipe-line. Nous faisons ceci en remplaçant la dernière itération par l'addition d'un terme de correction qui peut être déduit d'une lecture de table effectuée lors des premières itérations. Nous décrivons plusieurs variantes de l'algorithme obtenu en supposant un multiplieur à 4 étages de pipe-line, et donnons pour chaque variante l'erreur obtenue et le nombre de cycles de calcul. Des extensions de ce travail à des multiplieurs dont le nombre d'étages est différent sont présentées.
  • Keywords:

    Division, Square Root, Square Root Reciprocal, Convergence Division, Computer Arithmetic, Goldschmidt Iteration.
  • Keywords (in french):

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

Vers des primitives propres en arithmétique des ordinateurs.

  • By: Jean-Michel Muller
  • Number: RR1999-42
  • Date: September 1999
  • Abstract:

    The IEEE-754 floating-point standard gives a specification of the four basic arithmetic operations. The elementary functions should be standardized as well within a few years. In this paper, we present the various advantages of a completely specified arithmetic system.
  • Abstract (in french):

    La norme IEEE-754 consacrée à l'arithmétique virgule flottante spécifie le comportement des quatre opérations arithmétiques. Une spécification des fonctions élémentaires devrait voir le jour dans les années à venir. On s'intéresse dans cet article aux avantages que l'on peut tirer d'un système dont le ``primitives numériques'' sont complètement spécifiées.
  • Keywords:

    Computer Arithmetic, Floating-Point Arithmetic, Software Reliability.
  • Keywords (in french):

    Arithmétique des Ordinateurs, Virgule Flottante, Fiabilité des Logiciels.
  • Availability: Electronic copy only.
  • Citation: To appear in Technique et Science Informatiques.
  • Size: 2+5p
  • Format: Compressed PostScript
  • Get it

Radix-10 BKM Algorithm for Computing Transcendentals on Pocket Computers.

  • By: Laurent Imbert , Jean-Michel Muller , Fabien Rico
  • Number: RR1999-43
  • Date: September 1999
  • Abstract:

    We present a radix-10 variant of the BKM algorithm. It is a shift-and-add, CORDIC-like algorithm that allows fast computation of complex exponentials and logarithms. This radix-10 version is suitable for implementation in a pocket computer.
  • Abstract (in french):

    Nous proposons une variante de l'algorithme BKM adaptée au calcul en base 10. C'est un algorithme à additions et décalages, qui permet d'évaluer rapidement des exponentielles et logarithmes complexes. Cette version adaptée à la base 10 est destinée à l'implantation sur des calculatrices de poche.
  • Keywords:

    Elementary Functions, CORDIC Algorithms, Computer Arithmetic, Radix-10 Arithmetic.
  • Keywords (in french):

    Fonctions Elémentaires, Algorithmes CORDIC, Arithmétique des Ordinateurs, Arithmétique Base 10.
  • Availability: Electronic copy only.
  • Citation: Not published yet.
  • Size: 2+9p
  • Format: Compressed PostScript
  • Get it

Graph Automata Recognition.

  • By: Christophe Papazian , Eric Remila
  • Number: RR1999-44
  • Date: September 1999
  • Abstract:

    Graph automata were first introduced by P.Rosensthiel. A.Wu and A.Rosenfeld shown later how a graph automata can study its own structure, by building a system of signals that explore the underlying graph, giving in this way algorithms in linear time allowing to know if the graph is a grid. Then, E.Remila extended this result to other geometrical structures. We show here a very general method that allow to recognize all finite subsets of the grid $Z^2$, by puting orientation on edges, then by computing coordinates for each vertex. Depending on the class of graphs we want to recognize, we could finally do different processing on the border of the detected geometrical structure.
  • Abstract (in french):

    Les graphes d'automates ont été introduits par P. Rosensthiel. A. Wu et A. Rosenfeld ont ensuite montré comment un graphe d'automates peut étudier sa propre structure, en construisant un système de signaux qui explorent le graphe sous-jacent, donnant ainsi un algorithme en temps linéaire permettant à un graphe d'automates de savoir si son graphe est un rectangle. Nous proposons ici une méthode très générale qui permet de reconnaître toute sous-partie de $Z^2$, en plaçant des orientations sur les arêtes du graphe, puis en calculant des coordonnées pour chaque sommet du graphe. Selon la classe de graphe que l'on souhaite reconnaître, on peut alors effectuer des traitements différents de reconnaissance sur les bords de la structure géométrique détectée.
  • Keywords:

    Finite Automata, Algorithms and Data Structures.
  • Keywords (in french):

    Automates Finis, Algorithmes et Structures de Données.
  • Availability: Electronic copy only.
  • Citation: Submitted to STACS.
  • Size: 2+12p
  • Format: Compressed PostScript
  • Get it

Using preemptive thread migration to load-balance data-parallel applications.

  • By: Gabriel Antoniu , Christian Perez
  • Number: RR1999-45
  • Date: September 1999
  • Abstract:

    Generic load balancing policies for irregular parallel applications may be efficiently implemented by integrating preemptive thread migration into the runtime support. In this context, a delicate issue is to manage pointer validity in a migration-safe way. This paper discusses how our iso-address migration approach to this problem could provide the runtime of the Adaptor HPF compiler with generic support for dynamic load balancing. We report some encouraging results obtained by testing our system on a HPF flame simulation code, which is one of the motivating applications of HPF 2.0.
  • Abstract (in french):

    L'intégration de la migration préemptive des processus légers dans le support d'exécution des applications irregulières peut s'avérer un moyen efficace d'implantation de politiques génériques d'équilibrage de charge pour ces applications. Dans ce contexte, un problème délicat est la gestion de la validité des pointeurs en présence de la migration. Dans ce rapport nous montrons comment nous avons l'équilibrage dynamique de charge peut être intégré dans le compilateur HPF Adaptor grâce à une approche iso-addresse de la migration préemptive de processus légers. Nous présentons quelques résultats encourageants obtenus en testant notre système sur un code de simulation de combustion, l'une des applications motivantes d'HPF 2.0.
  • Keywords:

    Load Balancing, Data-Parallel, Thread Migration, Iso-Address Allocation, PM2, Multithreading.
  • Keywords (in french):

    Équilibrage de Charge, Parallélisme de Données, Thread, Processus Léger, Migration, Allocation Iso-Qdresse, PM2, Multithreading.
  • Availability: Electronic copy only.
  • Citation: Euro-Par '99: Parallel Processing, volume 1685 of Lect. Notes
  • Size: 2+12p
  • Format: Compressed PostScript
  • Get it

Using Simulation to Evaluate Scheduling Heuristics for a Class of Applications in Grid Environments.

  • By: Francine Berman , Henri Casanova , Dimitrii Zagarodnov , Arnaud Legrand
  • Number: RR1999-46
  • Date: September 1999
  • Abstract:

    Fast networks have made it possible to aggregate distributed CPU, memory, and storage resources into Grids that can deliver considerable performance. However, achieving performance on such systems requires good performance prediction which is usually difficult due to their dynamic and heterogeneous nature. This is especially true for parallel applications whose performance is highly dependent upon the efficient coordination of their constituent components (e.g. computation and data). The goal of the AppLeS project is to develop application-level scheduling agents that provide mechanisms for automatically scheduling individual applications on production heterogeneous systems. AppLeS agents utilize the Network Weather Service (NWS) to monitor and forecast the varying performance of resources potentially usable by their applications. Each AppLeS uses static and dynamic application and system information to select viable resource configurations and evaluate their potential performance. The AppLeS then interacts with the appropriate resource management system to implement the application's network transfers and computational tasks. The next generation of AppLeS agents aims at providing templates that can be used for scheduling classes of structurally similar applications. In this document we introduce a template for scheduling Parameter Sweep applications (application consisting of {\em large} number of independent tasks, with possible input data sharing). We have designed a general scheduling algorithm that can adapt to Grid environments and use a variety of strategies and heuristics to assign tasks and data to resources. In order to evaluate and compare those heuristics we have built a simulator as part of the template. The simulator makes it possible to rapidly conduct large numbers of experiments in a variety of environments. Our starting point was to use widely accepted heuristics that have been proposed in the litterature and venture improvements given our Grid and application model. This document presents the implementation of our simulator and explains how it will be used to obtain new research results in the field of Grid scheduling.
  • Abstract (in french):

    Les réseaux haut débit ont permis de connecter des capacités de calcul et de stockage distribuées en des grilles susceptibles de fournir des puissances de calcul considérables. Cependant, l'utilisation efficace de tels systèmes recquiert de bonnes prédictions des performances des différentes ressources, ce qui est généralement difficile en raison de l'hétérogénéité et du caractère dynamique de ces environnements. Ce constat est tout particulièrement vrai dans le cas d'applications parallèles dont l'efficacité dépend de la bonne coordination de ses différents composants. L'objectif du projet AppLeS est de développer des agents chargés de l'ordonnancement dans des environnement de calculs distribués hétérogènes et spécialisés pour chaque application. Les agents AppLeS utilisent le Network Weather Service (NWS) pour contrôler et prédire les performances des ressources disponibles pour les applications cibles ainsi que leur variations. Chaque agent utilise des informations statiques et dynamiques sur les applications dont il est responsable et sur l'environnement auquel il a accès pour effectuer ses choix. Il peut alors utiliser les systèmes chargés de la gestion de l'environnement pour l'alllocation des fichiers et des calculs aux différentes ressources. La prochaine génération d'agents AppLeS devrait être des modèles, des agents ``types'', dédiés à des classes d'applications structurellement équivalentes. Dans ce document, nous introduisons un modèle d'agent dédié à l'ordonnancement des applications de type Parameter-Sweep (des applications constituées d'un grand nombre de tâches de calcul indépendantes pouvant partager des fichiers d'entrée). Nous avons conçu un algorithme d'ordonnancement général capable de tenir compte des modifications de structure ou de performances de l'environnement et d'utiliser un certain nombre d'heuristiques pour l'allocation des données et des calculs aux différentes ressources. Nous avons développé un simulateur avec lequel l'agent peut interagir pour pouvoir évaluer et comparer ces heuristiques. Ce simulateur nous a permit de réaliser rapidement un grand nombre d'expériences dans un environnement paramétrable à volonté. Notre point de départ à été l'utilisation d'heuristiques tirées de la littérature et de les adapter à notre type d'application. Ce document présente la mise en oeuvre du simulateur et explique comment il va être utilisé pour obtenir de nouveaux résultats concernant l'ordonnancement dans des environnements instables de type grille.
  • Keywords:

    Scheduling, Meta-Computing, Grid-Computing, Grid, Parameter-Sweep Template, Sufferage, File-Sharing.
  • Keywords (in french):

    Ordonnancement, Méta-Computing, Calcul Distribué, Grilles, Applications Indépendantes, Partage de Fichiers.
  • Availability: Electronic copy only.
  • Citation: Not published yet.
  • Size: 2+40p
  • Format: Compressed PostScript
  • Get it

The presence of a zero in an integer linear recurrent sequence is NP-hard to decide.

  • By: Vincent Blondel , Natacha Portier
  • Number: RR1999-47
  • Date: September 1999
  • Abstract:

    We show that the problem of determining if a given integer linear recurrent sequence has a zero is NP-hard. It is not known whether this problem is decidable or not. With a similar argument we show that the problem of determining if a given directed graph has paths of all positive lengths between two given nodes is co-NP-hard, and that the problem of finding the minimal realization dimension of a one-letter max-plus rational series is NP-hard. This last result answers a folklore question raised in the control literature on discrete event systems.
  • Abstract (in french):

    Nous montrons que savoir si une suite récurrente linéaire d'entiers a un zéro est un problème NP-dur. Sa décidabilité reste une question ouverte. En utilisant des raisonnements similaires, nous montrons que décider si entre deux sommets d'un graphe orienté il existe des chemins de longueur quelconque est co-NP-dur et que le problème de la réalisation minimale d'une série rationnelle sur une lettre dans le demi-anneau max-plus est NP-dur. Ce dernier problème était une question ouverte classique en automatique des systèmes à événements discrets.
  • Keywords:

    Linear Recurrent Sequence, NP-Hard, Max-Plus, Rational Series, Graph, Minimal Realization.
  • Keywords (in french):

    Suite Récurrente Linéaire, NP-Dur, Max-Plus, Série Rationnelle, Graphe, Réalisation Minimale.
  • Availability: Electronic copy only.
  • Citation: Vincent Blondel et Natacha Portier, The presence of a zero in an integer linear recurrent sequence is NP-hard to decide, Rapport de recherche 1999-47.
  • Size: 2+7p
  • Format: Compressed PostScript
  • Get it

La théorie des cofinalités possibles et ses applications.

  • By: Grégory Lafitte
  • Number: RR1999-48
  • Date: September 1999
  • Abstract:

    Cardinal arithmetic, which has given birth to set theory,seemed to be until lately either simple (addition and multiplication ofinfinite cardinals are simple), or quite elastic (by forcing methods, it seemed possible to show the consistency with set theory of any reasonablebehaviour of cardinal exponentiation). Saharon Shelah has developped a rich theory with surprising applications in cardinal arithmetic, changing completely those beliefs. We present a state of the art of this theory anda certain number of its applications.
  • Abstract (in french):

    L'arithmétique des cardinaux, qui est à l'origine de lathéorie des ensembles, semblait jusqu'il y a quelques années, soit simple (l'addition et la multiplication de cardinaux infinis sont simples), soit élastique (par le biais de forcing, on pensait pouvoir montrer laconsistence avec la théorie des ensembles de tout comportement raisonnablede l'exponentiation de cardinaux). Saharon Shelah a développé une théorie ayant des applications surprenantes pour l'arithmétique des cardinaux, changeant complètement cette vision des choses. Nous présentonsun état de l'art de cette théorie et un certain nombre d'applications decelle-ci.
  • Keywords:

    Cardinal Arithmetic, Cofinality, Large Cardinals.
  • Keywords (in french):

    Arithmétique des Cardinaux, Cofinalité, Grands Cardinaux.
  • Availability: Electronic copy only.
  • Citation: Not published yet.
  • Size: 2+19p
  • Format: Compressed PostScript
  • Get it

The Data Broadcast Problem with Preemption.

  • By: Nicolas Schabanel
  • Number: RR1999-49
  • Date: September 1999
  • Abstract:

    The data-broadcast problem consists in finding an infinite schedule to broadcast a given set of messages so as to minimize the average response time to clients requesting messages, and the cost of the broadcast. This is an efficient means of disseminating data to clients, designed for environments, such as satellites, cable~TV, mobile phones, where there is a much larger capacity from the information source to the clients than in the reverse direction. Previous work concentrated on scheduling indivisible messages. Here, we studied a generalization of the model where the messages can be preempted. We show that this problem is NP-hard, even in the simple setting where the broadcast costs are zero, and give some practical 2-approximation algorithms for broadcasting messages. We also show that preemption can improve the quality of the broadcast by an arbitrary factor.
  • Abstract (in french):

    La diffusion de données est une réponse apportée au problème de la surcharge des réseaux et serveurs d'information (de type info-trafic, info-bourse, info-sport), où le nombre de clients est très élevés et la plus part d'entre eux demande majoritairement le même petit nombre de messages; et plus généralement adaptées aux réseaux asymétriques où la bande passante des serveurs vers les clients est bien plus grande que des clients vers les serveurs (les réseaux satellites, téléphones mobiles/base,...). L'idée est de réserver des canaux (typiquement hertzien) pour la diffusion de ce petit nombre de messages qui seront diffusés indépendamment des requêtes effectives: un client intéressé par un de ces messages, se connecte sur ces canaux et attend que le message demandé soit diffusé. Le problème de la diffusion de données [Data broadcast problem] consiste à trouver un ordonnancement qui diffuse les messages, en minimisant l'attente moyenne des utilisateurs (défini par un profil-utilisateur: les probabilités de demande pour chaque message), et le coût de la diffusion des messages. Alors que les travaux précédents étudient l'ordonnancement de messages indivisibles, nous étudions ici une généralisation du modèle au cas où la diffusion des messages peut être interrompue. Nous démontrons que le problème est NP-dur, même quand les coûts de diffusion sont nuls, et proposons un algorithme qui génère un algorithme de coût inférieur au double de l'optimal. Nous montrons aussi que l'ajout de préemption permet d'améliorer d'un facteur arbitraire la qualité d'un ordonnancement de messages de temps de transmission non-uniforme.
  • Keywords:

    Data Broadcast, Broadcast Disk, Push Technology, Preemption, Approximation Algorithm, Wireless Networks.
  • Keywords (in french):

    Diffusion de Données, Broadcast Disk, Push Technology, Préemption, Algorithme d'Approximation, Réseaux Sans Fil.
  • Availability: Electronic copy only.
  • Citation: Not published yet.
  • Size: 3+21p
  • Format: Compressed PostScript
  • Get it

Towards Portable Hierarchical Placement for FPGAs.

  • By: Florent de Dinechin , Wayne Luk , Steve McKeever
  • Number: RR1999-50
  • Date: October 1999
  • Abstract:

    Field Programmable Gate Arrays (FPGAs) are usually programmed using languages and methods inherited from the domain of VLSI synthesis. These methods, however, have not always been adapted to the new possibilities opened by FPGAs, nor to the new constraints they impose on a design. This paper addresses in particular the issue of laying out the various components of an architecture on an FPGA. The problem is to embed placement information in FPGA-oriented hardware description languages, in a way that is both expressive enough to be useful, and abstract enough to be portable from one FPGA architecture to the other. A generic placement framework is defined to address this problem, and two prototype implementations of this framework are presented, for Xilinx 6200 and Xilinx 4000 devices, on the example of a bit-serial complex multiplier.
  • Abstract (in french):

    Les réseaux de cellules reconfigurables (FPGAs) sont programmés au moyen de langages et de méthodes héritées de la syntheèse VLSI, mais ces méthodes ne sont pas toujours adaptées aux nouvelles possibilités offertes par les FPGAs, ni aux nouvelles contraintes qu'ils imposent. Cet article s'intéresse en particulier aux questions de placement des différents composants d'un circuit dans le FPGA. Le problème est l'expression de contraintes de placement dans les langages de description de matériel pour ces architectures, et ce d'une manière suffisamment expressive pour être utile, mais suffisamment abstraites pour être portable d'une architecture à l'autre. Un cadre formel est défini pour répondre à cette attente, et deux prototypes d'implémentation de ce cadre sont présentées sur les architectures très différentes des circuits Xilinx 4000 et 6200, avec l'exemple d'un multiplieur bit-série complexe.
  • Keywords:

    FPGA, Placement, Layout, Hardware Description Language.
  • Keywords (in french):

    FPGA, Placement, Langage de Description de Matériel.
  • Availability: Electronic copy only.
  • Citation: Not published yet.
  • Size: 2+11p
  • Format: Compressed PostScript
  • Get it

On functions which are limits of domino tilings.

  • By: Eric Remila
  • Number: RR1999-51
  • Date: November 1999
  • Abstract:

    In this paper, we study domino tilings of polygons. We are especially interested in what happens when the domino prototiles become smaller and smaller. This study is done using tiling height functions, which are a numerical way to encode tilings. The main result of this paper is an analytic characterization of functions which are limits of height functions when the size of dominoes converges to 0. It is obtained from lattice properties of sets of tilings induced by height functions.
  • Abstract (in french):

    Nous étudions ici les pavages de polygones par des dominos. Nous nous intéressons en particulier à ce qui ce passe quand ces dominos deviennent de plus en plus petits. Cette étude est faite au moyen des fonctions de hauteur des pavages, qui permettent de coder les pavages de manière numérique. Le résultat principal de ce papier est une caractérisation analytique des fonctions qui se trouvent être des limites des fonctions de hauteur, quand la taille des dominos tend vers 0. Il est obtenu à partir des propriétés de treillis des ensembles de pavages, induites par les fonctions de hauteur.
  • Keywords:

    Tiling, Height Function.
  • Keywords (in french):

    Pavage, Fonction de Hauteur.
  • Availability: Electronic copy only.
  • Citation: Not published yet.
  • Size: 2+13p
  • Format: Compressed PostScript
  • Get it

Cache Web : un état de l'art des techniques et prototypes.

  • By: Jean-Christophe Mignot
  • Number: RR1999-52
  • Date: November 1999
  • Abstract:

    This paper presents a survey of the state-of-the-art techniques and prototypes for Web caches. The basic principles are presented, the most important hardwares and softwares approaches are described.
  • Abstract (in french):

    Ce document présente un état de l'art des prototypes et techniques des caches WEB actuelles. Les principaux matériels et logiciels disponibles sur le marché sont présentés. Les principales approches dédiées aux machines parallèles sont décrites.
  • Keywords:

    Web Caches, Distributed Systems.
  • Keywords (in french):

    Caches Web, Systèmes Distribués.
  • Availability: Electronic copy only.
  • Citation: Not published yet.
  • Size: 2+23p
  • Format: Compressed PostScript
  • Get it

Workshop "Compilation et Parallélisation Automatique".

  • By: C. Mongenet , S. Rajopadhye , Y. Robert , F. Vivien
  • Number: RR1999-53
  • Date: November 1999
  • Abstract:

    This report gathers the abstracts of the paper presented at the workshop "Parallelisation techniques" which to place in Saint Nabor, France on October 18-20 1999.
  • Abstract (in french):

    Ce rapport rassemble les résumés des contributions présentées au Worshop "Compilation et Parallélisation Automatique" qui a eu lieu a Saint Nabor, France du 18 au 20 octrobre 1999.
  • Keywords:

    Worshop "Parallelisation Techniques".
  • Keywords (in french):

    Worshop "Compilation et Parallélisation Automatique".
  • Availability: Electronic copy only.
  • Citation: Not published yet.
  • Size: 2+38p
  • Format: Compressed PostScript
  • Get it

A generic object-calculus based on Addressed Term Rewriting Systems.

  • By: Daniel Dougherty , Frédéric Lang , Pierre Lescanne , Luigi Liquori , Kristoffer Rose
  • Number: RR1999-54
  • Date: December 1999
  • Abstract:

    In a previous paper we have outlined a framework (or a generic object-calculus) called \Obja, for modeling \textit{object calculi}. In this one, we would like to describe the foundations of \Obja{}. This framework is essentially a detailed formal operational semantics of object based languages, in the style of the Lambda Calculus of Objects. As a formalism for specification \Obja{} is arranged in \textit{modules}, permitting a natural classification of many object-based calculi according to their features, including their reduction-strategies. In particular there are modules for calculi of non mutable objects (\ie, \emph{functional object calculi}) and for calculi of mutable objects (\ie, \emph{imperative object calculi}). As a computational formalism \Obja{} is based on rewriting rules. Classical first-order term rewriting systems are not appropriate since we want to reflect aspects of implementation practice such as sharing, cycles in data structures and mutation. Therefore we define the notion of \textit{addressed terms}, and develop the corresponding notion of \textit{addressed term rewriting systems}.
  • Abstract (in french):

    Dans un article précédent, nous avions présenté un cadre de travail (ou si l'on préfère un calcul générique) appelé \Obja, pour modéliser des calculs d'objets, tandis que dans ce rapport, nous voudrions décrire les bases formelles d'\Obja. Ce cadre est essentiellement une sémantique opérationnelle formelle et détaillée des langages d'objets. En temps que formalisme de spécification, \Obja{} est disposé en modules, qui permettent une classification naturelle des divers calculs à objets par rapport à leurs caractéristiques, y compris leurs stratégies de réduction. En particulier, \Obja{} contient des modules qui décrivent les calculs à objets non mutables (c-à-d les \emph{calculs à objets fonctionnels}) et des modules qui décrivent les calculs à objets mutables (c-à-d les \emph{calculs à objets impératifs}). En temps que formalisme de calculs, \Obja{} est fondé sur des règles de réécriture, mais les systèmes de réécriture classiques du premier ordre sont inappropriés, car nous souhaitons refléter des aspects relevant de la pratique des implanteurs tels que le partage, les cycles dans les structures de données et la mutation. Pour cela, nous définissons la notion de terme avec adresses et développons la notion correspondante de système de réécriture avec adresses.
  • Keywords:

    Object-Calculus, Graph Rewriting, Operational Semantics, Sharing, Mutation.
  • Keywords (in french):

    Calcul d'Objets, Réécriture de Graphes, Sémantique Opérationnelle, Partage, Mutation.
  • Availability: Electronic copy only.
  • Citation: Not published yet.
  • Size: 2+32p
  • Format: Compressed PostScript
  • Get it

Madeleine: An Efficient and Portable Communication Interface for RPC-based Multithreaded Environments.

  • By: Luc Bouge , Jean-Francois Mehaut , Raymond Namyst
  • Number: RR1999-55
  • Date: December 1999
  • Abstract:

    We introduce Madeleine, a communication interface specifically designed to support distributed, multithreaded applications in both a portable and efficient way. Thanks to its new API, Madeleine can implement RPC operations without any extra copy with respect to the underlying protocol. Madeleine can thus achieve very good performance on a variety of protocols (MPI, TCP, BIP, VIA, etc.) and networks (Fast-Ethernet, Myrinet, SCI, etc.). Madeleine serves as a building block for the multithread programming environment PM2. We provide detailed experimental results for each representative implementation and discuss a number of possible improvements.
  • Abstract (in french):

    Nous présentons Madeleine, une interface de communication spécifiquement conçue pour supporter les applications multithreads distribuées de manière à la fois portable et efficace. Grâce à sa nouvelle interface de programmation (API), Madeleine peut implémenter efficacement les appels de procédures à distrances (RPC) sans copie supplémentaire par rapport au protocole sous-jacent. Madeleine peut ainsi réaliser des performances excellentes sur un large spectre de protocoles (MPI, TCP, BIP, VIA, etc.) et de réseaux (Fast-Ethernet, Myrinet, SCI, etc.). Madeleine est l'un des blocs de base de l'environnement de programmation multithread PM2. Nous présentons des résulats expérimentaux détaillés pour chaque implémentation représentative et nous discutons des améliorations possibles.
  • Keywords:

    High-Performance Computing, Cluster Computing, Multithreading, Communication Interface, Zero-Copy Protocol, Remote Procedure Call, Remote DMA.
  • Keywords (in french):

    Calcul Haute Performance, Grappes, Multithreadingm Interface de Communication, Protocole Zéro-Copie, RPC, Accès Mémoire Distant.
  • Availability: Electronic copy only.
  • Citation: Submitted for publication.
  • Size: 2+27p
  • Format: Compressed PostScript
  • Get it

Serveurs vidéo: concepts de base et prototypes.

  • By: Alice Bonhomme , Ahmed Mostefaoui
  • Number: RR1999-56
  • Date: December 1999
  • Abstract:

    This report presents a survey of techniques used in the conception of a video server. It also includes a survey of prototypes developped in this area. Based on a fonctionnal model of video server, the different components of a video server are described : the storage system, the memory management, the client interface, the ressources management, etc. The main techniques that implement these components are explained.
  • Abstract (in french):

    Ce document présente un état de l'art des techniques utilisées dans la conception de serveurs vidéo ainsi qu'un panorama des différents prototypes développés dans ce domaine. A partir d'un modéle fonctionnel de serveur vidéo, les différents composants d'un serveur vidéo sont décrits~: le système de stockage, la gestion mémoire, l'interface avec le client, la gestion des ressources, etc. Les principales techniques implémentant ces composants sont expliquées.
  • Keywords:

    Video Server, Survey, Prototypes.
  • Keywords (in french):

    Serveur Vidéo, Etat de l'Art, Prototypes.
  • Availability: Electronic copy only.
  • Citation: Not published yet.
  • Size: 2+40p
  • Format: Compressed postscript
  • Get it