The Game of Life: universality revisited.

  • By: Bruno Durand , Zsuzsanna Roka
  • Number: RR1998-01
  • Date: January 1998
  • Abstract:

    The Game of Life was created by J.H.~Conway. One of the main features of this game is its \emph{universality.} We prove in this paper this universality with respect to several computational models: boolean circuits, Turing machines, and two-dimensional cellular automata. These different points of view on Life's universality are chosen in order to clarify the situation and to simplify the original proof. We also present precise definitions of these 3~universality properties and explain the relations between them.
  • Abstract (in french):

    Le jeu de la Vie a été inventé par J.H.~Conway. Un des principaux interêts de ce jeu est son universalité. Nous la prouvons ici dans différents models: les circuits booléens, les machines de Turing, les automates cellulaires de dimension~2. Ces différents points de vue sont pris pour clarifier la situation et simplifier les preuves originales. Nous donnons aussi des définitions précises de ces 3~propriétés d'universalité et expliquons leurs différences.
  • Keywords:

    Game of Life, Cellular Automata, Universality.
  • Keywords (in french):

    Jeu de la Vie, Automates Cellulaires, Universalité.
  • Availability: Electronic copy only.
  • Citation: To appear in Cellular Automata theory, J. Mazoyer Ed. Kluwer.
  • Size: 2+23p
  • Format: Compressed PostScript
  • Get it

Model Theory and Computational Complexity.

  • By: Gregory Lafitte , Jacques Mazoyer
  • Number: RR1998-02
  • Date: September 1997
  • Abstract:

    Model theory has lately become a domain of interest to computer scientists. The reason is that model theory, and in particular its restriction to finite models, has led to some new results in computational complexity (e.g. NLOGSPACE=co-NLOGSPACE). In this report, firstly we present a survey of this theory and we focus on the descriptive complexity aspects and other links between computational complexity and model theory. Secondly, we extend some results of Grandjean and Lynch. We give a more precise logical characterization of complexity classes NTIME(n^d) for some d. This leads us to show applications of this result and to give openings made possible by this result.
  • Abstract (in french):

    Les informaticiens théoriques se sont récemment intéressés à la théorie des modèles. La raison est que la théorie des modèles, en particulier lorsque l'on se restreint à des modèles finis, a permis d'aboutir à de nouveaux résultats en complexité (e.g. NLOGSPACE=co-NLOGSPACE). Dans ce rapport, nous présentons premièrement une étude de cette théorie dans le but de présenter les notions de complexité descriptive et d'autres liens entre la complexité et la théorie des modèles. Deuxièmement, nous étendons des résultats de Grandjean et Lynch. Nous donnons une caractérisation logique plus précise des classes de complexité NTIME(n^d) pour un certain d. Enfin, nous montrons des implications de notre résultat et nous donnons différentes ouvertures rendues possibles grâce à ce résultat.
  • Keywords:

    Model Theory, Computational Complexity, Games on Structures.
  • Keywords (in french):

    Théorie des Modèles, Complexité de Calcul, Jeux sur des Structures.
  • Availability: Electronic copy only.
  • Citation: Not published yet.
  • Size: 2+33p
  • Format: Compressed PostScript
  • Get it

On connectedness and dimension of a Besicovitch space over SZ.

  • By: Enrico Formenti , Petr Kurka
  • Number: RR1998-03
  • Date: January 1998
  • Abstract:

    We prove that the topological space szd, proposed in is path-connected and has infinite dimension. The latter property makes of this space a more natural setting for cellular automata when they are considered as a solutions of difference equations. In fact, difference equations are defined on an infinite dimensional space. On the contrary the classical product topology on SZ is zero-dimensional. Moreover we present a transitive dynamical system on szd, whose existence was given as an open problem in. Another interesting property that we prove is that szd is not separable. This property partially explain the ``difficulty'' of finding transitive systems on such a space. We also prove that some properties of Toeplitz sequences on szd and as a byproduct we obtain a ``weak fixed point'' theorem for continuous mappings on szd. Finally we sketch an interesting connection between infinite Sturmian words and szd.
  • Abstract (in french):

    On prouve que l'espace topologique szd, proposé dans, est connexe et que sa dimension topologique est infinie. Cette dernière proprieté rend cette espace plus naturel pour l'étude des automates cellulaires, par exemple quand ils sont considerés comme solutions des équations aux différences. En effet, l'espace des équations aux différences a une dimension infinie. Alors que la topologie produit classique sur szd donne un espace de dimension zéro. De plus, nous exhibons un système dynamique topologiquement transitif sur szd; l'existence d'un tel système a été donnée comme problème ouvert dans. Une autre propriété intéressante de szd est la non-separabilité, qui explique en part ``la difficulté'' de trouver des systemes transitifs sur cet espace. On prouve aussi quelques propriétées des suites de Toeplitz sur szd. Comme corollaire, on obtient un theoreme faible de point fixe. Nous montrons aussi quelques relations entre szd et l'ensemble des mots Sturmiens infinis.
  • Keywords:

    Shift-Invariant Metrics, Topological Dimension, Discrete Time Dynamical Systems on $S^Z$.
  • Keywords (in french):

    Mêtriques Invariantes par le Shift, Dimension Topologique, Systemes Dynamiques à Temps Discrets sur $S^Z$.
  • Availability: Electronic copy only.
  • Citation: Not published yet.
  • Size: 2+12p
  • Format: Compressed PostScript
  • Get it

Compass permits leader election.

  • By: Jacques Mazoyer , Eric Remila
  • Number: RR1998-04
  • Date: January 1998
  • Abstract:

    We first prove that there exists a protocol which, given a cycle of the planar square lattice on vertices of which are placed synchronous communicating finite automata in a same initial state, breaks the symmetry to elect a unique leader. At the initialization, each automaton only knows the directions of the edges joining it to its successor and its predecessor (we say that the automaton has a compass) and knows neither the length of the cycle nor its own coordinates. The time for leader election is twice the length of the cycle. Afterwards we deduce a leader election protocol for cellular automata constructed on finite parts of the planar grid, which costs at most time 12(number of cells)+2 time units.
  • Abstract (in french):

    Nous donnons d'abord une fonction de transition qui, étant donné un cycle du réseau rectangulaire du plan euclidien sur les sommets duquels sont placés des automates finis communiquant entre eux, ces sommets se trouvant dans le même état initial, rompt la symétrie pour sélectionner un chef unique. A l'initialiation, chaque sommet ne connait que les orientations des arêtes le liant à son prédécesseur et son successeur (on dit que l'automate a une boussole), il ne connait ni la longueur du cycle, ni ses coordonnées dans le plan. Le temps nécessaire est le double de la longueur du cycle. Ensuite, nous déduisons un protocole de sélection d'un chef pour les automates cellulaires construits à partir de parties finies de la gille plane, qui nécessite au plus 12(nombre de sommets)+2 unités de temps.
  • Keywords:

    Cellular Automata, Leader Election, Symmetry Breaking.
  • Keywords (in french):

    Automates Cellulaires, Sélection d'un Chef, Rupture de Symétrie.
  • Availability: Electronic copy only.
  • Citation: Submitted to ICALP 98.
  • Size: 2+13p
  • Format: Compressed PostScript
  • Get it

Introduction à la théorie algorithmique de l'information.

  • By: Jean-Christophe Dubacq
  • Number: RR1998-05
  • Date: January 1998
  • Abstract:

    We explain the basics of the theory of the Kolmogorov complexity}, also known as algorithmic information theory, and underline the main differences between the Kolmogorov complexity and Kolmogorov prefix complexity. Then, we introduce the definition of randomness for either finite or infinite words according to P. Martin-Löf and show that it is equivalent to the notion of uncompressibility defined via Kolmogorov complexity.
  • Abstract (in french):

    Nous expliquons les bases de la théorie de la complexité de Kolmogorov ou théorie algorithmique de l'information. On analyse en particulier les différences et les ressemblances entre la complexité de Kolmogorov et sa variante dite complexité préfixe. Ensuite, nous introduisons une définition d'un mot aléatoire (finie ou infinie), celle de Martin-Löf et montrons qu'elle est équivalente à la notion d'incompressibilité définie via la complexité de Kolmogorov.
  • Keywords:

    Kolmogorov Complexity, Randomness, Codesg.
  • Keywords (in french):

    Complexité de Kolmogorov, Aléatoire, Codage.
  • Availability: Electronic copy only.
  • Citation: Not published yet.
  • Size: 2+55p
  • Format: Compressed PostScript
  • Get it

Algebraic tools for the construction of colored flows with constraints.

  • By: Marius Dorkenoo , Marie-Christine Leclerc , Eric Remila
  • Number: RR1998-06
  • Date: January 1998
  • Abstract:

    We give a linear time algorithm which, given a simply connected figure of the plane divided into cells, whose boundary is crossed by some colored inputs and outputs, produces non-intersecting directed flow lines which match inputs and outputs according to the colors, in such a way that each edge of any cell is crossed by at most one line. The main tool is the notion of height function, previously introduced for the tilings. This notion appears as the extension of the notion of potential of a flow in a planar graph.
  • Abstract (in french):

    Nous donnons un algorithme en temps lineaire qui, étant donnée une figure simplement connexe du plan divisée en cellules, dont la frontière est traversée par des arcs colorés entrant ou sortant, exhibe des lignes de flots non intersectantes reliant les entrées aux sorties avec respect des couleurs, de telle façon que n'importe quelle arête de n'importe quelle cellule soit coupée par au plus une ligne. L'outil principal est la notion de fonction de hauteur, introduite précédemment pour les pavages. Cette notion apparaît comme une généralisation de la notion de potentiel d'unn flot dans un graphe planaire.
  • Keywords:

    Flow, Finitely Presented Group, Local Transformations. Height Function.
  • Keywords (in french):

    Flots, Groupes à Présentation Finie, Transformations Locales, Fonction de Hauteur.
  • Availability: Electronic copy only.
  • Citation: Submitted to combinatorica, short version accepted at STACS'98.
  • Size: 2+13p
  • Format: Compressed PostScript
  • Get it

JNN, a Randomized Algorithm for Learning Multilayer Networks in Polynomial Time.

  • By: Andre Elisseeff , Helene Paugam-Moisy
  • Number: RR1998-07
  • Date: January 1998
  • Abstract:

    From an analytical approach of the multilayer architecture, we deduce a polynomial-time algorithm for learning from examples. We call it JNN, for ``Jacobian Neural Network''. Although this learning algorithm is a randomized algorithm, it gives a correct network with probability 1. The JNN algorithm is defined for a wide variety of multilayer networks. Starting from an exact learning algorithm, for a given database, we propose a regularization technique which improves the performance on applications. Moreover, the JNN algorithm does not require a priori statements on the network architecture. Finally, we show that a modular approach allows to learn with a reduced number of weights.
  • Abstract (in french):

    En étudiant l'architecture multicouche d'un point de vue analytique, on peut en déduire un algorithme en temps polynomial pour l'apprentissage à partir d'exemples. Nous l'appelons JNN, pour ``Jacobian Neural Network''. Bien que ce soit un algorithme randomisé, il fournit un réseau exact avec probabilité 1 et il peut être défini sur un large spectre de réseaux. A partir d'un algorithme d'apprentissage exact, pour une base donnée, nous proposons un algorithme régularisé qui améliore la preformance sur les applications. De plus, JNN ne nécessite aucune hypothèse a priori sur l'architecture du réseau. Nous montrons enfin qu'une architecture modulaire permet un apprentissage avec un nombre de poids réduit.
  • Keywords:

    Multilayer Neural Networks, Architecture, Learning Algorithms, Regularization, Polynomial Complexity.
  • Keywords (in french):

    Réseaux Neuronaux Multicouches, Architecture, Algorithmes d'apprentissage, Régularisation, Complexité polynomiale.
  • Availability: Electronic copy only.
  • Citation: Submitted to Neurocomputing.
  • Size: 2+20p
  • Format: Compressed PostScript
  • Get it

Tiling for Heterogeneous Computing Platforms.

  • By: Pierre Boulet , Jack Dongarra , Yves Robert , Frederic Vivien
  • Number: RR1998-08
  • Date: January 1998
  • Abstract:

    In the framework of fully permutable loops, tiling has been extensively studied as a source-to-source program transformation. However, little work has been devoted to the mapping and scheduling of the tiles on physical processors. Moreover, targeting heterogeneous computing platforms has, to the best of our knowledge, never been considered. In this paper we extend tiling techniques to the context of limited computational resources with different-speed processors. In particular, we present efficient scheduling and mapping strategies that are asymptotically optimal. The practical usefulness of these strategies is fully demonstrated by MPI experiments on a heterogeneous network of workstations.
  • Abstract (in french):

    Dans le cadre des boucles totalement permutables, le partitionnement a été intensivement étudié en tant que transformation de programme. Cependant, très peu de travaux ont concerné l'ordonnancement et l'allocation des tuiles sur les processeurs physiques, et aucun, à notre connaissance, n'a considéré un ensemble de processeurs hétérogène. Dans ce rapport, nous étendons les techniques de partitionnement au cadre des ressources bornées et des processeurs de vitesses diffé rentes. En particulier, nous présentons des stratégies d'ordonnancement et d'allocation asymptotiquement optimales. Nous démontrons l'intérêt pratique de ces stratégies par des expérimentations avec MPI sur un réseau hétérogène de stations de travail.
  • Keywords:

    Tiling, Communication-Computation Overlap, Mapping, Limited Resources, Different-Speed Processors, Heterogeneous Networks.
  • Keywords (in french):

    Partitionnement, Recouvrement Calculs-Communications, Allocation, Ressources Limitées, Processeurs de Vitesses Différentes, Réseau Hétérogène.
  • Availability: Electronic copy only.
  • Citation: Not published yet.
  • Size: 2+18p
  • Format: Compressed PostScript
  • Get it

Technology Transfer within the ProHPC TTN at ENS Lyon.

  • By: Christophe Barberet , Lionel Brunie , Frederic Desprez , Gilles Lebourgeois , Yves Robert , Stephane Ubeda , Karine Van Heumen
  • Number: RR1998-09
  • Date: January 1998
  • Abstract:

    This article is devoted to the description of our activities related to transferring the HPCN technology to SMEs. This work is performed in the framework of the French TTN ProHPC, which we briefly describe in the beginning of the paper. Then we move to a more technical description of our activities, which include four projects within the awareness campaign PHPC-ACRA and the participation to a "Best Practice" prototype.
  • Abstract (in french):

    Cet article a pour but de présenter nos activités autour du transfert de la technologie HPCN vers les PMEs. Ce travail est effectué à l'intérieur du TTN ProHPC francais, lequel est brièvement décrit au début de l'article. Ensuite, nous décrivons de manière plus technique nos activités, qui incluent quatre projets à l'intérieur de la campagne de promotion PHPC-ACRA et la participation à un prototype de type "Best Practice".
  • Keywords:

    TTN Pro-HPC, Applications, HPCN, SMEs.
  • Keywords (in french):

    TTN Pro-HPC, Applications, HPCN, PMEs.
  • Availability: Electronic copy only.
  • Citation: Short version to appear in HPCN'98 proceedings.
  • Size: 2+13p
  • Format: Compressed PostScript
  • Get it

The complexity of irreducible components.

  • By: Pascal Koiran
  • Number: RR1998-10
  • Date: February 1998
  • Abstract:

    We show that deciding whether an algebraic variety has an irreducible component of codimension at least d is an NP-complete problem for every fixed d in the Blum-Shub-Smale model of computation over the complex numbers (and is in the Arthur-Merlin class if we assume a bit model of computation). This is the first part of a paper which will eventually provide similar results for semi-algebraic sets.
  • 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-complet pour toute constante d dans le modèle de calcul de Blum-Shub-Smale sur les nombres complexes (et est dans la classe Arthur-Merlin si on travaille avec un modèle de calcul booléen). Ce rapport est la première partie d'un article qui présentera aussi des résultats similaires sur les ensembles semi-algébriques.
  • 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+5p
  • Format: Compressed PostScript
  • Get it

Task Ordering in Linear Tiles.

  • By: Fabrice Rastello , Santosh Pande , Amit Rao
  • Number: RR1998-11
  • Date: February 1998
  • Abstract:

    In this report we address the issue of loop tiling to minimize the completion time of the loop when executed on multicomputers. We remove the restriction of atomicity of tiles and internal parallelism within tiles is exploited by overlapping computation with communication. The effectiveness of tiling is then critically dependent on the execution order of tasks within a tile. In this paper we present a theoretical framework based on equivalence classes that provides an optimal task ordering under assumptions of constant and different permutations of tasks in individual tiles. Our framework is able to handle constant but compile-time unknown dependences by generating optimal task permutations at run-time and results in significantly lower loop completion times. Our solution is an improvement over previous approaches and is optimal for all problem instances. We also propose efficient algorithms that provide the optimal solution. The framework has been implemented as an optimization pass in the SUIF compiler and has been tested on distributed and shared memory systems using a message passing model. We show that the performance improvement over previous results is substantial.
  • Abstract (in french):

    Étant donné un nid de boucles 1-dimensionnel avec des dépendances uniformes et une distribution regulière des tâches sur une chaîne de processeurs. Nous adressons ici le problème du réordonnancement des tâches à l'intérieur même de chaque tuile afin de pipeliner les communications. En fait, nous cherchons à utiliser le parallélisme interne à chaque tuile afin de réduire la latence dans une direction critique ; ces résultats pouvant s'appliquer à des nids de boucles multidirectionnels. Les approches précedantes se tenant à chercher une permutation constante des tâches à l'intérieur de chaque tuiles, nous avons d'abord résolu se problème de manière optimale (algorithme 3) puis comparé cet algorithme à un algorithme utilisant des permutations non constantes (algorithme 4). La construction de l'algorithme 3 à nécessité la mise en oeuvre d'une formalisation mathématiques du problème suivit de preuves substentielles. C'est ce qui constitue le corps de ce rapport. Si clairement dans le cas 1-directionnel nos résultats montrent la supériorité de l'algorithme 4, certains paramètres laissent à penser que dans les dimensions supérieures, un algorithme de type 3 serait peut être plus efficace...}.
  • Keywords:

    Automatic Parallelization, Tiling, Nested Loop, Reordering, Pipelined Communications, Uniform Dependances, Equivalence Classes.
  • Keywords (in french):

    Parallélisation Automatique, Pavage, Nids de Boucle, Réordonnancement, Communications Pipelinées, Dépendances Uniformes, Classes d'Equivalence.
  • Availability: Electronic copy only.
  • Citation: Not published yet.
  • Size: 2+20p
  • Format: Compressed PostScript
  • Get it

The Table Maker's Dilemma.

  • By: Vincent Lefevre , Jean-Michel Muller , Arnaud Tisserand
  • Number: RR1998-12
  • Date: February 1998
  • Abstract:

    The Table Maker's Dilemma is the problem of always getting correctly rounded results when computing the elementary functions. After a brief presentation of this problem, we present new developments that have helped us to solve this problem for the double-precision exponential function in a small domain. These new results show that this problem can be solved, at least for the double-precision format, for the most usual functions.
  • Abstract (in french):

    Le dilemme du concepteur de tables est le problème de toujours fournir des résultats arrondis correctement lors du calcul de fonctions élémentaires. Après une brève présentation du problème, nous présentons de nouveaux résultats qui permettent de résoudre ce problème pour l'exponentielle en double précision dans un petit domaine. Ces résultats montrent que le problème peut être résolu, au moins pour le format double précision, pour la plupart des fonctions usuelles.
  • Keywords:

    Table Maker's Dilemma, Elementary.
  • Keywords (in french):

    Dilemme du Constructeur de Tables, Fonctions Elémentaires, Arrondi Correct, Arithmétique Virgule Flottante.
  • Availability: Electronic copy only.
  • Citation: Not published yet.
  • Size: 2+16p
  • Format: Compressed PostScript
  • Get it

Loop Partitioning versus Tiling for Cache-based Multiprocessors.

  • By: Fabrice Rastello , Yves Robert
  • Number: RR1998-13
  • Date: February 1998
  • Abstract:

    In this paper, an efficient algorithm to implement loop partitioning is introduced and evaluated. We improve recent results of Agarwal, Kranz and Natarajan in several directions. We give a more accurate estimation of the cumulative footprint, and we derive a much more powerful algorithm to determine the optimal tile shape. We illustrate the superiority of our algorithm on the same examples as those of Agarwal, Kranz and Natarajan to ensure the fairness of the comparisons.
  • Abstract (in french):

    Nous présentons dans ce papier une heuristique efficace permettant de faire de la distribution de boucles. Nous appuyons notre travail sur un papier récent de Agarwal, Kranz et Natarajan que nous améliorons dans de nombreuses directions. Plus précisement, nous proposons une estimation des empreintes cumulées de tuiles plus précise ; nous proposons une heuristique puissante permettant de minimiser cette empreinte cumulée ; enfin, nous montrons la superiorité de notre algorithme en l'appliquant aux exemples donnés par Agarwal, Kranz et Natarajan, afin d'assurer l' équité de notre comparaison.
  • Keywords:

    Compilation Technique, Hierarchical Memory Systems, Loop Partitioning, Tiling, Cache, Data Locality, Footprint.
  • Keywords (in french):

    Techniques de Compilation, Systèmes à Mémoire Hiérarchisée, Distribution de Boucles, Pavage, Mémoire Cache, Localité de Données, Empreintes de Tuiles.
  • Availability: Electronic copy only.
  • Citation: Not published yet.
  • Size: 2+21p
  • Format: Compressed PostScript
  • Get it

Low Memory Cost Dynamic Scheduling of Large Coarse Grain Task Graphs.

  • By: Michel Cosnard , Emmanuel Jeannot , Laurence Rougeot
  • Number: RR1998-14
  • Date: March 1998
  • Abstract:

    Scheduling large task graphs is an important issue in parallel computing since it allows the treatment of big size problems. In this report we tackle the following problem: how to schedule a task graph, when it is too large to fit into memory? Our answer features the parameterized task graph (PTG), which is a symbolic representation of the task graph. We propose a dynamic scheduling algorithm which takes the PTG as an entry and allows to generate a generic program. The performances of the method are studied as well as its limitations. We show that our algorithm finds good schedule for coarse grain task graphs, has a very low memory cost, and has a good computational complexity. When the average number of operations of each task is large enough, we prove that the scheduling overhead is negligible with respect to the makespan. The feasibility of our approach is studied on several compute-intensive kernels found in numerical scientific applications.
  • Abstract (in french):

    Ordonnancer de gros graphes de tâches est un sujet important car il permet de traiter des problèmes de grande taille. Dans ce rapport nous considérons le problème suivant : comment ordonnancer un graphe de tâche quand celui-ci est trop gros pour tenir en mémoire? Notre réponse introduit le graphe de tâche paramétré (GTP), qui est une représentation symbolique du graphe de tâches. Nous proposons un algorithme d'ordonnancement qui prend le GTP en entrée et qui permet de générer un programme générique. Nous étudions les performances de notre méthode ainsi que ses limitations. Nous montrons que notre algorithme trouve un bon ordonnancement pour les graphes de tâches à gros grain, qu'il est peu coûteux en mémoire et qu'il a une bonne complexité temporelle. Quand le nombre moyen d'opérations de chaque tâches est assez grand, nous prouvons que le surcoût de l'ordonnancement est négligeable par rapport au makespan. Nous étudions les aspects pratiques de notre approche sur plusieurs noyaux coûteux en calcul que l'on trouve dans les applications scientifiques.
  • Keywords:

    Control Parallelism, Coarse Grain Task Graph, Parameterized Task Graph, Dynamic Scheduling, Memory Optimization.
  • Keywords (in french):

    Parallélisme de Contrôle, Graphe de Tâches à Gros Grain, Graphe de Tâches Paramétré, Ordonnancement Dynamique, Optimisation Mémoire.
  • Availability: Electronic copy only.
  • Citation: Short version published in proceedings of IPPS'98.
  • Size: 2+16p
  • Format: Compressed PostScript
  • Get it

Elimination of parameters in the polynomial hierarchy.

  • By: Pascal Koiran
  • Number: RR1998-15
  • Date: March 1998
  • Abstract:

    Blum, Cucker, Shub and Smale have shown that the problem ``$\p = \np$~?'' has the same answer in all algebraically closed fields of characteristic~0. We generalize this result to the polynomial hierarchy: if it collapses over an algebraically closed field of characteristic 0, then it must collapse at the same level over all algebraically closed fields of characteristic 0. The main ingredient of their proof was a theorem on the elimination of parameters, which we also extend to the polynomial hierarchy. Similar but somewhat weaker results hold in positive characteristic. The present paper updates a report (LIP Research Report 97-37) with the same title, and in particular includes new results on interactive protocols and boolean parts.
  • Abstract (in french):

    Blum, Cucker, Shub et Smale ont montré que la réponse au problème ``$\p = \np$~?'' est la même dans tous les corps algébriquement clos de caractéristique 0. Nous généralisons ce résultat à la hiérarchie polynomiale: si elle s'effondre pour un corps algébriquement clos de caractéristique 0, alors elle s'effondre au même niveau pour tous les corps algébriquement clos de caractéristique 0. L'ingrédient principal de leur démonstration est un théorème d'élimination des paramètres, que nous étendons également à la hiérarchie polynomiale. Des résultats similaires mais un peu plus faibles s'appliquent en caractéristique positive. Cet article met à jour un rapport précédent (rapport de recherche LIP 97-37) portant le même titre, et contient notamment des résultats nouveaux sur les preuves interactives et les parties booléennes.
  • Keywords:

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

    Elimination des Paramètres, Hiérarchie Polynomiale, Modèle de Blum-Shub-Smale.
  • Availability: Electronic copy only.
  • Citation: Not published yet.
  • Size: 2+18p
  • Format: Compressed PostScript
  • Get it

Confluent Vandermonde matrices using Sylvester's structure.

  • By: Lamine Melkemi
  • Number: RR1998-16
  • Date: March 1998
  • Abstract:

    In this paper, we first show that a confluent Vandermonde matrix may be viewed as composed of some rows of a certain block Vandermonde matrix. As a result, we derive a Sylvester's structure for this class of matrices that appears as a natural generalization of the straightforward one known for usual Vandermonde matrices. Then we present some applications as an illustration of the established structure. For example, we show how confluent Vandermonde and Hankel matrices are linked with each other, and also we describe an O($n^{2}$) algorithm for solving confluent Vandermonde least squares minimizations problems.
  • Abstract (in french):

    Dans cet article, nous proposons une structure de Sylvester pour les matrices de Vandermonde confluentes qui parait comme une généralisation naturelle de celle connue dans le cas d'un système de Vandermonde simple. La démonstration de ce résultat tire profit d'une propriété intéressante disant, dans un sens que nous préciserons plus loin, qu'une telle matrice est en fait plong\'ee dans une matrice de Vandermonde par blocks. En exploitant cette structure, nous montrons ensuite, qu'il est possible d'exprimer l'inverse d'une matrice de Vandermonde confluente comme le produit de son duale et d'une matrice de Hankel. Toujours à l'aide de cette structure, nous décrivons un algorithme O($n^{2}$) permettant de résoudre les problèmes aux moindres carrés basés sur ces matrices. Enfin nous montrons comment on peut étendre les résultats établis à une classe de matrices beaucoup plus génerale.
  • Keywords:

    Confluent Vandermonde Matrix, Sylvester's Equation, Structured Matrices.
  • Keywords (in french):

    Matrice de Vandermonde Confluente, Structure de Sylvester, Matrices Structurees.
  • Availability: Electronic copy only.
  • Citation: Not published yet.
  • Size: 2+14p
  • Format: Compressed PostScript
  • Get it

More on Scheduling Block-Cyclic Array Redistribution.

  • By: Frederic Desprez , Stephane Domas , Jack Dongarra , Antoine Petitet , Cyril Randriamaro , Yves Robert
  • Number: RR1998-17
  • Date: March 1998
  • Abstract:

    This article is devoted to the run-time redistribution of one-dimensional arrays that are distributed in a block-cyclic fashion over a processor grid. In a previous paper, we have reported how to derive optimal schedules made up of successive communication-steps. In this paper we assume that successive steps may overlap. We show how to obtain an optimal scheduling for the most general case, namely, moving from a CYCLIC(r) distribution on a P-processor grid to a CYCLIC(s) distribution on a Q-processor grid, for arbitrary values of the redistribution parameters P, Q, r, and s. We use graph-theoretic algorithms, and modular algebra techniques to derive these optimal schedulings.
  • Abstract (in french):

    Nous nous intéressons à la redistribution des tableaux unidimensionnels alloués de manière bloc-cyclique sur des grilles de processeurs. Dans un article précédent, nous avons expliqués comment construire un ordonnancement optimal agencé en ``étapes'' de communication. Dans cet article, nous considérons que les étapes peuvent s'entrelacer. Nous montrons comment obtenir un ordonnancement optimal dans la majeure partie des cas, à savoir passer d'une distribution CYCLIC(r) sur une grille de P processeurs à une distribution CYCLIC(s) sur une grille de Q processeurs, pour des valeurs arbitraires des paramètres P, Q, r, et s. Pour obtenir ces ordonnancements optimaux, nous utilisons des techniques issues de la théorie de graphes, et de l'algèbre modulaire.
  • Keywords:

    Distributed Arrays, Block-Cyclic Distribution, Redistribution, Asynchronous Communications, Scheduling, HPF.
  • Keywords (in french):

    Tableaux Distribués, Distribution Bloc-Cyclique, Redistribution, Communications Asynchrones, Ordonnancement, HPF.
  • Availability: Electronic copy only.
  • Citation: Not published yet.
  • Size: 2+11p
  • Format: Compressed PostScript
  • Get it

Height-relaxed AVL rebalancing: A unified, fine-grained approach to concurrent dictionaries.

  • By: Luc Bouge , Joaquim Gabarro , Xavier Messeguer , Nicolas Schabanel
  • Number: RR1998-18
  • Date: March 1998
  • Abstract:

    We address the concurrent rebalancing of almost balanced binary search trees (AVL trees). Such a rebalancing may for instance be necessary after successive insertions and deletions of keys. We show that this problem can be studied through the self-reorganization of distributed systems of nodes controlled by local evolution rules in the line of the approach of Dijkstra and Scholten. This yields a much simpler algorithm that the ones previously known. Based on the basic rebalancing framework, we describe algorithms to manage concurrent insertion and deletion of keys. Finally, this approach is used to emulate other well known concurrent AVL algorithms. As a by-product, this solves in a very general setting an old question raised by H.T. Kung and P.L. Lehman: where should rotations take place to rebalance arbitrary search trees? This paper is the extended version of the previous research report RR1997-13
  • Abstract (in french):

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

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

    Algorithmes Concurrents, Arbres de Recherche, Arbres AVL, Insertions et Suppressions Concurrentes, Rotations Concurrentes Généralisées, Preuves de Terminaison Distribuée, Simulation.
  • Availability: Electronic copy only.
  • Citation: Not published yet.
  • Size: 2+34p
  • Format: Compressed PostScript
  • Get it

A Randomized BSP/CGM Algorithm for the Maximal Independent Set Problem.

  • By: Afonso Ferreira , Nicolas Schabanel
  • Number: RR1998-19
  • Date: March 1998
  • Abstract:

    This paper presents a randomized parallel algorithm for the Maximal Independent Set problem. Our algorithm uses a BSP-like computer with $p$ processors and requires that $\frac{n+m}{p}=\Omega(p)$ for a graph with $n$ vertices and $m$ edges. Under this scalability assumption, and after a preprocessing phase, it computes a maximal independent set after $O(\log p)$ communication rounds, with high probability, each round requiring linear computation time $O(\frac{n+m}p)$. The preprocessing phase is deterministic and important in order to ensure that degree computations can be implemented efficiently. For this, we give an optimal parallel BSP/CGM algorithm to the $p$-quantiles search problem, which runs in $O(\frac{m\log p}{p})$ time and a constant number of communication rounds, and could be of interest in its own right, as shown in the text
  • Abstract (in french):

    Nous présentons dans ce papier un algorithme randomisé parallèle pour la recherche d'un stable maximal d'un graphe shape Maximal Independent Set, MIS. Notre algorithme est écrit pour des machines parallèles de type BSP (gros grain) à $p$ processeurs, telles que $\frac{n+m}{p}=\Omega(p)$ pour un graphe à $n$ sommets et $m$ arêtes. Sous cette contrainte de granularité, il calcule un stable maximal en $O(\log p)$ rounds de communications, avec forte probabilité, chaque round nécessitant un temps de calcul de $O(\frac{n+m}p)$. L'étape initiale de placement des données, nécessaire pour un calcul efficace du degré des n\oe uds du graphe, est déterministe. Cette étape, qui pourrait s'avérer utile en soi pour d'autres algorithmes, est basée sur une recherche des $p$-quantiles, dont nous proposons une parallélisation optimale~: son temps d'exécution est $O(\frac{m\log p}{p})$ avec $O(1)$ phases de communications.
  • Keywords:

    Parallel Algorithms, Maximal Independent Set, Randomized Algorithms, Graph Algorithms, Coarse-Grained Models, BSP, CGM, $p$-quantiles search, Sorting.
  • Keywords (in french):

    Algorithmique Parallèle, Stables Maximaux, Algorithmes Randomisés, Algorithmes de Graphes, Modèles Gros-Grain, BSP, CGM, Recherche des $p$-quantiles, Tris.
  • Availability: Electronic copy only.
  • Citation: Submitted for presentation to ESA'98.
  • Size: 2+10p
  • Format: Compressed PostScript
  • Get it

Fast orthogonalization of confluent Vandermonde, confluent Chebychev Vandermonde and related matrices.

  • By: Lamine Melkemi
  • Number: RR1998-20
  • Date: March 1998
  • Abstract:

    In this paper, fast $LU$ factorization algorithms, derived from the classical updating techniques, are proposed for some structured matrices. The importance of these algorithms lies in the fact that it allows to directly obtain the $QR$ factorization of confluent Vandermonde-like and confluent Chebychev Vandermonde-like matrices.
  • Abstract (in french):

    L'objet de cet article consiste en la conception d' algorithmes d'orthogonalisation rapide des matrices de Vandermonde confluentes et matrices de Chebychev Vandermonde confluentes. De fait, il s'agit d'algorithmes $LU$ appliques a des matrices dans lesquelles les matrices sous considération sont plongées. Les résultats établis exploitent le fait que les matrices de Vandermonde confluentes, les matrices de Chebychev Vandermonde confluentes ainsi que les matrices dans lesquelles elles sont plongees sont dotees de structures de deplacement analogues a celles des matrices de Toeplitz ou des matrices de Vandermonde.
  • Keywords:

    Confluent Vandermonde Matrix, Chebychev Confluent Vandermonde Matrix, $QR$ Factorization, Cauchy-like Matrix, Updating $LU$ Factorization.
  • Keywords (in french):

    Matrice de Vandermonde Confluente, Matrice de Chebychev Vandermonde Confluente , Factorisation $QR,$ Mise à Jour de $LU$.
  • Availability: Electronic copy only.
  • Citation: Submitted for presentation to ESA'98.
  • Size: 2+17p
  • Format: Compressed PostScript
  • Get it

The Architecture of BPFS: a Basic Parallel File System Version 1.0.

  • By: Robert D. Russell
  • Number: RR1998-21
  • Date: March 1998
  • Abstract:

    BPFS is a distributed, modular parallel file system designed to be used on networks of workstations. It is specified as a set of active components, functions utilized by the components, and protocols for communication between the components. The components can be implemented in many different ways, depending on the hardware and software support systems available, the performance desired, etc. A key idea is to be able to experiment with different implementations and configurations under different operating conditions to achieve a completely general, flexible system that is also capable of delivering good performance. In particular, it should be possible to implement this system on ``commodity, off-the-shelf'' (COTS) hardware and software. However, it should also be possible to implement specialized versions of some or all components to take advantage of unique hardware or software features. BPFS is intended to support a wide range of possible applications, including real-time video on demand, medical and satellite image processing, out-of-core array manipulations, and general parallel computations that need a high performance file system. The parallel file system is intended to be ``always available'' for simultaneous use by any number of different applications. It is also capable of efficiently handling huge files containing many terabytes of data. This report describes the architecture of BPFS in terms of the set of components, their organization, the functions they utilize, and the protocol specifications for communication between them.
  • Abstract (in french):

    BPFS est un système de fichiers parallèle, modulaire et distribué, destiné à être utilisé sur les réseaux de postes de travail. Il est spécifié comme un ensemble de composants actifs, de fonctions utilisées par ces composants et de protocoles pour la communication inter-composants. Les composants peuvent être implémentés de façons diverses selon le matériel et le logiciel disponible, la performance souhaitée, etc. Une idée clé en est la possibilité d'expérimenter avec des implémentations et des configurations diverses dans des conditions d'utilisation differentes, afin de réaliser un système complètement général et flexible, qui est aussi capable de délivrer de bonnes performances. En particulier, il devrait être possible d'implémenter ce système avec du matériel et du logiciel ``commodity, off-the-shelf'' (COTS). Cependant, des versions spécialisées de certains (voire de tous) composants peuvent être implémentées afin d'exploiter les caractéristiques particulières de certains matériels ou logiciels. Le but de BPFS est de soutenir toute une gamme d'applications, y compris la vidéo en temps réel sur demande, le traitement d'images médicales ou d'images prises par satellite, les manipulations de matrices en dehors de la mémoire et les calculs parallèles généraux qui nécessitent un système de fichiers de haute performance. Le système de fichiers parallèle est conçu de façon à être ``toujours disponible'' pour l'usage simultané par un grand nombre d'applications diverses. Il est aussi capable de traiter efficacement des fichiers énormes constitués d'un grand nombre de terabytes de données. Ce rapport décrit l'architecture de BPFS en termes de l'ensemble des composants, leur organisation, les fonctions qu'ils utilisent et les spécifications de protocoles de communication.
  • Keywords:

    Parallel File Systems, Distributed File Systems, File Systems, System Architecture, Protocols.
  • Keywords (in french):

    Système de Fichiers Parallèle, Système de Fichiers Distribué, Système de Fichiers, Architecture de Système, Protocoles.
  • Availability: Electronic copy only.
  • Citation: Proc. 2nd IASTED Intl Conf. on Parallel and Distributed Computing
  • Size: 2+73p
  • Format: Compressed PostScript
  • Get it

Do most strong definitions of randomness exist?

  • By: Bruno Durand , Vladimir Kanovei , Vladimir A. Uspensky , Nikolai Vereshagin
  • Number: RR1998-22
  • Date: April 1998
  • Abstract:

    The goal of our paper is to propose a way to obtain more refined definitions of randomness than the notions known so far (e.g. Martin-Löf randomness). We show that a ``perfect'' definition of randomness based on provability does not exist. We then weaken our requirements on the definition by replacing provability by consistency and obtain a formula that defines a set of random sequences that fulfills rather strong conditions.
  • Abstract (in french):

    Nous proposons ici de raffiner les définitions classiques du caractère aléatoire des suites infinies (en particulier la très classique définition de Martin-Löf). Nous prouvons qu'il n'existe pas de définition parfaite fondée sur la notion de prouvabilité. En remplaçant la prouvabilité par la consistence, nous obtenons une définition des suites aléatoires très générale qui remplit des conditions raisonablement fortes.
  • Keywords:

    Randomness, Logics, Solovay Model.
  • Keywords (in french):

    Suites Aléatoire, Logique, Modèle de Solovay.
  • Availability: Electronic copy only.
  • Citation: Not published yet.
  • Size: 2+11p
  • Format: Compressed PostScript
  • Get it

Structures de déplacement pour les matrices p-Vandermonde confluentes et éliminations de Gauss avec pivotement partiel.

  • By: Lamine Melkemi
  • Number: RR1998-23
  • Date: May 1998
  • Abstract:

    In this paper, we show that the useful displacement structures constructed for polynomial Vandermonde matrices (see KO1 in particular) can be naturally extended to confluent polynomial Vandermonde matrices. This result was made possible by virtue of the fact (recently established by the author in M) that confluent Vandermonde matrices belong favorably to the class of structured matrices. In the context of the displacement structure theory, it is well known that once an acceptable displacement structure is established for a matrix, one may naturally expect interesting applications regarding its numerical implementation.
  • Abstract (in french):

    Dans cette note, nous construisons des structures de déplacement utiles pour les matrices p-Vandermonde confluentes, généralisant ainsi les résultats connus dans le cas des matrices p-Vandermonde KO1. L'idée principale repose sur un résultat récent établi par l'auteur M affirmant que les matrices de Vandermonde confluentes font partie, tout comme les matrices de Vandermonde, de la classe des matrices structurées.
  • Keywords:

    Confluent Vandermonde Matrix, Confluent Polynomial Vandermonde Matrix, Displacement Structure.
  • Keywords (in french):

    Matrice de Vandermonde Confluente, Matrice p-Vandermonde Confluente, Structure de Déplacement.
  • Availability: Electronic copy only.
  • Citation: Not published yet.
  • Size: 2+7p
  • Format: Compressed PostScript
  • Get it

Minimal Triangulations for Graphs with "Few" Minimal Separators.

  • By: Vincent Bouchitte , Ioan Todinca
  • Number: RR1998-24
  • Date: May 1998
  • Abstract:

    We give a characterization of minimal triangulation of graphs using the notion of ``maximal set of neighbor separators''. We prove that if all the maximal sets of neighbor separators of some graphs can be computed in polynomial time, the treewidth of those graphs can be computed in polynomial time. This notion also unifies the already known algorithms computing the treewidth of several classes of graphs.
  • Abstract (in french):

    Nous donnons une caractérisation des triangulations minimales des graphes en utilisant la notion de ``ensemble maximal de séparateurs voisins''. Nous prouvons que si tous les ensembles maximaux de séparateurs voisins d'une classe de graphes sont calculables en temps polynomial, le treewidth de ces graphes se calcule en temps polynomial. Cette notion permet d'unifier les algorithmes calculant le treewidth pour plusieures classes de graphes.
  • Keywords:

    Treewidth, Chordal Graphs, Minimal Separators, Minimal Triangulations.
  • Keywords (in french):

    Treewidth, Graphes Triangulés, Séparateurs Minimaux, Triangulations Minimales.
  • Availability: Electronic copy only.
  • Citation: To appear in proceedings of ESA'98.
  • Size: 2+13p
  • Format: Compressed PostScript
  • Get it

Static Multiprocessor Task Graph Scheduling in the Genetic Paradigm: A Comparison of Genotype Representations.

  • By: Pascal Rebreyend , F. E. Sandnes, G. M. Megson
  • Number: RR1998-25
  • Date: May 1998
  • Abstract:

    In the NP-hard multiprocessor scheduling problem a set of precedence constrained tasks are allocated onto processors in a processing order in order to minimise the makespan. Many heuristic methods for finding solutions exist, but they are all sub-optimal on general task graphs. To improve these solutions, genetic algorithms have successfully been applied to the problem and the results reported have been superior to the list-scheduling approaches. However, the application of genetic algorithms to the multiprocessor scheduling problem have predominantly followed two main paths of developments, namely the use of direct and indirect representations. In the direct chromosome representation the schedule is represented and manipulated directly by the genetic operators, and the genotype is identical to the phenotype. In the indirect representation only the decisions on how to build the schedule is encoded in the chromosome. The genetic operators affect the schedules implicitly, and the genotype is different to the phenotype. In this paper these two main approaches to genetic scheduling are compared by evaluating their respective quality of results and time of convergence.
  • Abstract (in french):

    Dans le problème NP-dur de l'ordonnancement sur machine parallèle, un ensemble de tâches avec des contraintes de précédences sont ordonnancées sur un ensemble de processeurs afin de minimiser la durée totale d'exécution. Plusieurs méthodes heuristiques existent pour trouver des solutions sous-optimales. Pour améliorer ces solutions, les algorithmes génétiques ont été utilisés avec succès et les résultats sont meilleurs que ceux obtenus avec des algorithmes de listes. Cependant, cette utilisation d'algorithmes génétiques pour le problème de l'ordonnancement sur machine parallèle s'est fait suivant deux voies principales: la représentation directe et celle indirecte. Dans le cas de la représentation directe, l'ordonnancement est représenté directement par le chromosome et manipulé aussi de manière directe par les opérateurs génétiques. Le génotype est donc identique au phénotype. Par contre, dans le cas de la représentation indirecte, le chromosome code seulement des décisions sur comment construire la solution. Les opérateurs génétiques affectent donc la solution de manière implicite, indirecte et donc le génotype est différent du phénotype. Dans ce rapport, les deux méthodes sont comparées.
  • Keywords:

    Multiprocessor Scheduling, Genetic Algorithms, Direct and Indirect Representation.
  • Keywords (in french):

    Ordonnancement de Programme Parallèle sur Machines Multiprocesseurs, Algorithmes Génétiques, Représentation Directe et Indirecte.
  • Availability: Electronic copy only.
  • Citation: Not published yet.
  • Size: 2+15p
  • 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: RR1998-26
  • Date: May 1998
  • Abstract:

    Due to their ever-growing success in the development of distributed applications, today's multithreaded environments have to be highly portable and efficient on a large variety of hardware. Most of these environments have an implementation built on top of standard communication interfaces such as PVM or MPI, which are widely available on existing architectures. Obviously, this approach ensures a high level of portability. However, we show in this paper that these communication interfaces do not meet the needs of RPC-based multithreaded environments as far as efficiency is concerned. The contribution of this paper is to propose a new portable and efficient communication interface, called MADELEINE, that is especially designed for such multithreaded environments. We report on several implementations of MADELEINE on top of various network protocols that demonstrate the efficiency of our approach.
  • Abstract (in french):

    Compte tenu de leur utilisation croissante pour le développement d'applications distribuées, les environnements multithreads actuels se doivent d'être à la fois portables et efficaces sur un vaste eventail d'architectures matérielles. L'implantation de la plupart de ces environnements s'appuie d'ailleurs sur des interfaces de communication de haut niveau telles que PVM ou MPI. Cependant, nous montrons dans cet article que ces interfaces ne conviennent pas aux environnements communiquant sur la base de RPC, en particulier en ce qui concerne l'efficacité. Cet article propose donc une nouvelle interface de communication portable et efficace, nommée MADELEINE, mieux adaptée aux besoins de ces environnements. Nous decrivons l'implantation de cette interface sur plusieurs protocoles réseaux et montrons que cette approche est très efficace.
  • Keywords:

    Distributed Multithreading, RPC-Based Communications.
  • Keywords (in french):

    Multithreading Distribué, Communications Basées sur les RPC.
  • Availability: Electronic copy only.
  • Citation: Proc. 1998 Int. Conf. Parallel Architectures and Compilation
  • Size: 2+13p
  • Format: Compressed PostScript
  • Get it

Comparison between the complexity of a function and the complexity of its graph.

  • By: Bruno Durand , Sylvain Porrot
  • Number: RR1998-27
  • Date: May 1998
  • Abstract:

    This paper investigates in terms of Kolmogorov complexity the differences between the information necessary to compute a recursive function and the information contained in its graph. Our first result is that the complexity of the initial parts of the graph of a recursive function, although bounded, has almost never a limit. The second result is that the complexity of these initial parts approximate the complexity of the function itself in most cases (and in the average) but not always.
  • Abstract (in french):

    Nous étudions en termes de complexité de Kolmogorov les différences entre l'information nécessaire au calcul d'une fonction récursive et l'information contenue dans son graphe. Nous montrons que la complexité des segments initiaux de ce graphe, bien que bornée n'a presque jamais de limite. Notre second résultat est que la complexité de ces segments initiaux approche celle de la fonction dans la plupart des cas (et en moyenne), mais pas toujours.
  • Keywords:

    Kolmogorov complexity, recursive sequences.
  • Keywords (in french):

    Complexité de Kolmogorov, suites récursives.
  • Availability: Electronic copy only.
  • Citation: To appear in proceedings of MFCS'98, LNCS, Springer Verlag, 1998.
  • Size: 2+9p
  • Format: Compressed PostScript
  • Get it

Application Interfaces to BPFS: a Basic Parallel File System.

  • By: Robert D. Russell
  • Number: RR1998-28
  • Date: June 1998
  • Abstract:

    This report describes three application program interfaces to BPFS, a distributed, modular parallel file system designed for use on clusters of workstations. These interfaces are called API0, CLI, and MPI-IO. API0 is the first of an anticipated series of low-level, experimental client interfaces to BPFS. It is an ``unconventional'' interface in many respects: it is not particularly ``UNIX-like'', it is block-oriented rather than byte oriented, it reads and writes system buffers as well as user-defined data areas, and it is asynchronous. It also provides time-regulated ``data streaming'' operations and user-level control of both server-side caching and per-file striping onto disks. Although API0 can be used directly from a user application program, it can also be used ``under'' a more conventional interface, as has been done for the next two interfaces. CLI is a ``C Library Interface'' implemented on top of API0 that exactly mimics the Standard C I/O library interface, but accesses parallel files stored by BPFS rather than sequential files stored by the host file system. The third interface is the ROMIO version of the standard MPI-IO interface which has been implemented on top of API0 to support access to BPFS files from parallel programs that use the Message Passing Interface (MPI).
  • Abstract (in french):

    Ce rapport décrit trois interfaces de programmation de BPFS, un système de fichiers distribué modulaire conçu pour des grappes de stations de travail. Ces interfaces se nomment respectivement API0, CLI et MPI-IO. API0 est la première d'une série d'interfaces d'accès à BPFS de bas niveau. Cette interface est originale à plusieurs titres : elle n'obéit pas à la philosophie classique des fichiers sous UNIX, elle opère en mode bloc et non en mode caractère, elle permet la lecture/écriture de tampons ``systèmes'' et de données utilisateurs et enfin elle est asynchrone. De plus, des opérations de flux de donnée périodique ainsi que le paramètrage des tampons du côté serveurs par les clients sont disponibles. Bien que l'interface API0 puisse être utilisée directement par n'importe quelle application, deux interfaces de niveau supérieur ont été définies pour une utilisation plus aisée. CLI est une interface s'appuyant sur API0 qui fournit les primitives standards d'entrée/sortie de la ``libc''. Ces primitives accèdent aux fichiers parallèles gérés par BPFS et non aux fichiers séquentiels UNIX traditionnels. La troisième interface est une version de l'interface ROMIO (elle même sous-ensemble de l'interface standard MPI-IO) implantée au-dessus d'API0. Cette interface permet donc aux applications développées au-dessus de MPI de s'exécuter sans modification au-dessus de BPFS.
  • Keywords:

    Parallel File Systems, Distributed File Systems, File Systems, Application Program Interfaces.
  • Keywords (in french):

    Système de Fichiers Parallèle, Systèeme de Fichiers Distribué, Système de Fichiers, Interfaces de Programmation.
  • Availability: Electronic copy only.
  • Citation: Not published yet.
  • Size: 2+50p
  • Format: Compressed PostScript
  • Get it

A Polynomial Time Incremental Learning Algorithm.

  • By: Rajesh Parekh , Codrin Nichitiu , Vasant Honavar
  • Number: RR1998-29
  • Date: June 1998
  • Abstract:

    We present an efficient incremental algorithm for learning deterministic finite state automata (DFA) from labeled examples and membership queries. This algorithm is an extension of Angluin's ID procedure to an incremental framework. The learning algorithm is intermittently provided with labeled examples and has access to a knowledgeable teacher capable of answering membership queries. The learner constructs an initial hypothesis from the given set of labeled examples and the teacher's responses to membership queries. If an additional example observed by the learner is inconsistent with the current hypothesis then the hypothesis is modified minimally to make it consistent with the new example. The update procedure ensures that the modified hypothesis is consistent with all examples observed thus far. The algorithm is guaranteed to converge to a minimum state DFA corresponding to the target when the set of examples observed by the learner includes a it live complete set. We prove the convergence of this algorithm and analyze its time and space complexities.
  • Abstract (in french):

    Nous donnons un algorithme incrémental efficace pour l'apprentissage d'automates d'états finis à partir d'exemples étiquetés et de demandes d'appartenance. Cet algorithme est une extension à un cadre incrémental de la procédure ID d'Angluin. L'algorithme d'apprentissage reçoit de manière intermittente des exemples de mots étiquetés et a accés à un "professeur" capable de répondre à des questions d'appartenance au langage-cible. L'algorithme construit une hypothèse initiale à partir du jeu d'exemples donnés et des réponses du professeur. Si un example supplémentaire trouvé par l'algorithme contredit l'hypothèse courante, alors celle-ci est modifiée de manière minimale, afin d'éliminer la contradiction. La procédure de modification assure la compatibilité de la nouvelle hypothèse avec tous les exemples précédents. L'algorithme converge vers un automate d'états finis minimal en nombre d'états reconnaissant le langage-cible quand le jeu d'exemples traités comprend un ensemble "live complete". Nous prouvons la convergence de cet algorithme et analysons ses complexités en espace et temps.
  • Keywords:

    Finite State Automata, Regular Grammar, Formal Languages, Machine Learning, Oracles, Incremental.
  • Keywords (in french):

    Automates Finis, Grammaires Rationnelles, Langages Formels, Apprentissage, Oracles, Incrémental.
  • Availability: Electronic copy only.
  • Citation: Already published as Technical Report ISU CS TR 97-03 at the Iowa State University, USA.
  • Size: 2+13p
  • Format: Compressed PostScript
  • Get it

Alignment and distribution is NOT (always) NP-hard.

  • By: Vincent Boudet , Fabrice Rastello , Yves Robert
  • Number: RR1998-30
  • Date: July 1998
  • Abstract:

    In this paper, an efficient algorithm to simultaneously implement array alignment and data/computation distribution is introduced and evaluated. We re-visit previous work of Li and Chen, and we show that their alignment step should not be conducted without preserving the potential parallelism. In other words, the optimal alignment may well sequentialize computations, whatever the distribution afterwards. We provide an efficient algorithm that handles alignment and data/computation distribution simultaneously. The good news is that several important instances of the whole alignment/distribution problem have polynomial complexity, while alignment itself is NP-complete.
  • Abstract (in french):

    Dans ce rapport, un algorithme efficace est présenté et évalué pour résoudre simultanément l'alignement des tableaux et la distribution des données et des calculs. Nous revisitons les travaux précédents de Li et Chen, et nous montrons que leur recherche d'un alignement ne doit pas être conduite sans préserver le parallélisme potentiel. En d'autres termes, l'alignement optimal peut séquentialiser les calculs quelle que soit la distribution choisie ensuite. Nous présentons un algorithme efficace qui tient compte simultanément de l'alignement et de la distribution des données et des calculs. La bonne nouvelle est que plusieurs instances du problème d'alignement/distribution ont une complexité polynomiale alors que l'alignement lui-même est NP-complet.
  • Keywords:

    Compilation Techniques, Parallel Loops, Alignment, Distribution, ``the owner computes'' Rule.
  • Keywords (in french):

    Techniques de Compilation, Boucles Parallèles, Alignement, Distribution, Règle du ``the owner computes''.
  • Availability: Electronic copy only.
  • Citation: Not published yet.
  • Size: 2+18p
  • Format: Compressed PostScript
  • Get it

Cellular automata in the Cantor, Besicovitch and Weyl spaces.

  • By: Francois Blanchard , Enrico Formenti , Petr Kurka
  • Number: RR1998-31
  • Date: July 1998
  • Abstract:

    The Besicovitch and Weyl pseudometrics on the space $A^{\ZZ}$ of biinfinite sequences measure the density of differences in either the central or arbitrary segments of given sequences. The Besicovitch and Weyl spaces are obtained from $A^{\ZZ}$ by factoring through the equivalence of zero distance. We consider cellular automata as dynamical systems on the Besicovitch and Weyl spaces and compare their topological and dynamical properties with those in the Cantor space.
  • Abstract (in french):

    Les peudo-métriques de Besicovitch et Weyl sur l'espace $A^{\ZZ}$ des suites biinfinies mesure la densité des différences dans la partie centrale ou dans une partie arbitraire d'un suite donnée. Les espaces de Besicovitch et Weyl sont obtenus en factorisant $A^{\ZZ}$ par la relation d'équivalence ``être à une distance nulle''. Nous considérons les AC comme des systèmes dynamiques sur ces espaces et nous comparons leurs propriétés topologiques et dynamiques avec celles dans l'espace de Cantor.
  • Keywords:

    Cellular Automata, Dynamical Systems.
  • Keywords (in french):

    Automates Cellulaires, Systemes Dynamiques.
  • Availability: Electronic copy only.
  • Citation: Not published yet.
  • Size: 2+14p
  • Format: Compressed PostScript
  • Get it

Definability of geometric properties in algebraically closed fields.

  • By: Pascal Koiran , Olivier Chapuis
  • Number: RR1998-32
  • Date: July 1998
  • Abstract:

    We prove that there exists no sentence F of the language of rings with an extra binary predicat I_2 satisfying the following property: for every definable set X of C^2, X is connected if and only if (C,X) satisfies F, where I_2 is interpreted by X. We conjecture that the same result holds for the closed subsets of C^2. We prove some results motivated by this conjecture.
  • Abstract (in french):

    On montre qu'il n'existe pas d'énoncé F dans le langage des anneaux muni d'un prédicat binaire supplémentaire I_2 satisfaisant la propriétée suivante: pour tout ensemble définissable X de C^2, X est connexe si et seulement si (C,X) satisfait F (I_2 est interprété par X dans l'énoncé F). Nous conjecturons que le même résultat est vrai pour les fermés de C^2. Nous démontrons également quelques résultats motivés par cette conjecture.
  • Keywords:

    Definability, Constraint Databases, Model Theory, Algebraically Closed Fields.
  • Keywords (in french):

    Définissabilité, Bases de Données Contraintes, Théorie des Modèles, Corps Algébriquement Clos.
  • Availability: Electronic copy only.
  • Citation: Not published yet.
  • Size: 2+25p
  • Format: Compressed PostScript
  • Get it

Retiming et parallélisation automatique.

  • By: Guillaume Huard
  • Number: RR1998-33
  • Date: July 1998
  • Abstract:

    In this report, we study more deeply the retiming techniques that are useful both for automatic parallelization and architecture synthesis. We recall the formalism of retiming and the main results due to Leiserson and Saxe. We propose two new optimization results: the minimization and the maximization of the number of registerless edges of a synchronous circuit. These two optimizations appear for problems such as the software pipelining and the maximization of data locality.
  • Abstract (in french):

    Nous nous proposons dans le cadre de ce rapport d'étudier plus avant les techniques de retiming utiles à la fois en synthèse d'architectures et en parallélisation automatique. Nous en présentons le formalisme et nous rappelons les principaux résultats obtenus par Leiserson et Saxe. Nous proposons deux nouveaux résultats d'optimisation sur cette technique~: la minimisation et la maximisation du nombre d'arcs sans registres d'un circuit synchrone. Ces deux problèmes apparaissent notamment dans le cadre du pipeline logiciel et de la maximisation de la localité des données.
  • Keywords:

    Automatic Parallelization, Retiming, Software Pipelining, Data Locality.
  • Keywords (in french):

    Parallélisation Automatique, Retiming, Pipeline Logiciel, Localité des Données.
  • Availability: Electronic copy only.
  • Citation: Not published yet.
  • Size: 2+36p
  • Format: Compressed PostScript
  • Get it

Computations on Cellular Automata.

  • By: Jacques Mazoyer
  • Number: RR1998-34
  • Date: July 1998
  • Abstract:

    We show simple methods in order to construct cellular automata with a defined behavior. To achieve this goal, we explain how to move local information through the networks and to set up their meeting in order to get the wished global behavior. Some well-known examples are given: Fischer's prime construction, Firing Squad Synchronization Problem and an ``ad hoc'' example of filter.
  • Abstract (in french):

    Nous montrons quelques méthodes simples de construction d'automate cellulaires avec un comportement prédéfini.Pour obtenir cela, nous expliquons comment transporter les informations locales à travers le réseau et de controler leurs rencontres de façon à avoir le comportement global souhaité. Quelques exemples bien connus sont détaillés: la construction des nombres premiers de Fischer, la Synchronisation d'une ligne de fusiliers, et un exemple ``ad hoc'' de filtre.
  • Keywords:

    Cellular Automata, Systolic Arrays, Algorithms, Synchronization.
  • Keywords (in french):

    Automates Cellulaires, Réseaux Systoliques, Algorithmes, Synchronisation.
  • Availability: Electronic copy only.
  • Citation: To be published in the book "Cellular Automata: a parallel model.", M. Delorme and J.Mazoyer Eds, Mathematics and Its Applications, Kluwer.
  • Size: 2+49p
  • Format: Compressed PostScript
  • Get it

Computations on Grids.

  • By: Jacques Mazoyer
  • Number: RR1998-35
  • Date: July 1998
  • Abstract:

    We study how the underlying graph of dependencies of one dimensional cellular automaton may be used in order to move and compose areas of computations. This allows us to define complex cellular automata, relaxing in some way the inherent synchronism of such networks.
  • Abstract (in french):

    Nous étudions comment le graphe de dépendances sous-jacent d'un automate cellulaire de dimension un peut être utilisé pour mouvoir et composer des zones de calcul dans l'espace-temps. Ceci nous permet de définir des algorithmes complexes en s'affranchissant par certains aspects du synchronisme inhérent à de tels réseaux.
  • Keywords:

    Cellular Automata, Algorithms, Dependencies Synchronous and Asynchronous Computations.
  • Keywords (in french):

    Automates Cellulaires, Algorithmes, Dependances, Calculs Synchrones et Asynchrones.
  • Availability: Electronic copy only.
  • Citation: To be published in the book "Cellular Automata: a parallel model.", M. Delorme and J.Mazoyer Eds, Mathematics and Its Applications, Kluwer.
  • Size: 2+34p
  • Format: Compressed PostScript
  • Get it

Cellular Automata as Languages Recognizers.

  • By: Jacques Mazoyer , Marianne Delorme
  • Number: RR1998-36
  • Date: July 1998
  • Abstract:

    Language recognition is a powerful tool to evaluate the computational power of devices. In case of cellular automata, a specific problematics appears in the one dimensional case where the space is bounded. A state of the art is presented. In the two dimensional case, few results are known. The main difficulty is to inject an order on a plane of cells.
  • Abstract (in french):

    Reconnaître des languages est un outil puissant pour évaluer la puissance de calcul d'un système. Dans le cas des automates celulaires une problématique spécifique apparaît dès la dimension un. Un état de l'art est présenté. En dimension deux peu de choses sont connues. La difficulté majeure est d'envoyer l'ordre naturel des mots sur un plan de cellules.
  • Keywords:

    Cellular Automata, Systolic Arrays, Languages Recognition, Complexity.
  • Keywords (in french):

    Automates Cellulaires, Réseaux Systoliques, Reconnaissance de Langages, Complexité.
  • Availability: Electronic copy only.
  • Citation: To be published in the book "Cellular Automata: a parallel model.", M. Delorme and J.Mazoyer Eds, Mathematics and Its Applications, Kluwer.
  • Size: 2+30p
  • Format: Compressed PostScript
  • Get it

An introduction to Cellular Automata.

  • By: Marianne Delorme
  • Number: RR1998-37
  • Date: July 1998
  • Abstract:

    We give basic definitions necessary to understand what are cellular automata, as well as to work with. Some efficient but sometimes problematic concepts as signal, simulation and universality, are pointed out. In particular, different notions of universality are put to light.
  • Abstract (in french):

    On donne ici les définitions essentielles pour comprendre les automates cellulaires et les utiliser. On met en évidence certaines notions très efficaces mais parfois problématiques, comme celles de signal, simulation et universalité. En particulier on presente différentes notions d'universalité.
  • Keywords:

    Cellular Automata, Universality, Signals, Simulations.
  • Keywords (in french):

    Automates Cellulaires, Universalité, Signaux, Simulations.
  • Availability: Electronic copy only.
  • Citation: To be published in the book "Cellular Automata: a parallel model.", M. Delorme and J.Mazoyer Eds, Mathematics and Its Applications, Kluwer.
  • Size: 2+53p
  • Format: Compressed PostScript
  • Get it

A Study of End-User SCSI Disk Performance with Parallel and Non-parallel Files.

  • By: Robert D. Russell
  • Number: RR1998-38
  • Date: August 1998
  • Abstract:

    This report describes a series of experiments to investigate the performance of SCSI disks as seen by the application programmer. The results show a significant performance loss, on the order of 50 %, when two or more files are simultaneously read from the same disk. Performance is also reduced when files are stored in an interleaved manner, and when small block sizes are utilized.
  • Abstract (in french):

    Ce rapport décrit une série d'expériences réalisées pour étudier les performances des disques SCSI telles que l'on peut les observer au niveau de l'interface de programmation. Les résultats indiquent une réduction significative des performances, de l'ordre de 50\%, lorsqu'au moins deux fichiers sont lus simultanément à partir du même disque. Les performances sont aussi réduites lorsque des fichiers sont stockés de façon entrelacée et lorsque des blocs de petite taille sont utilisés.
  • Keywords:

    SCSI Disk Performance, File System Performance, Parallel File System Performance.
  • Keywords (in french):

    Performances des Disques SCSI, Performances des Systèmes de Fichiers, Performances des systèmes de fichiers parallèles.
  • Availability: Electronic copy only.
  • Citation: Not published yet.
  • Size: 2+36p
  • Format: Compressed PostScript
  • Get it

Multiplications of floating point expansions.

  • By: Marc Daumas
  • Number: RR1998-39
  • Date: August 1998
  • Abstract:

    In modern computers, the floating point unit is the part of the processor delivering the highest computing power and getting all the attention from the design team. Performances of any multiple precision application will be dramatically enhanced by an adequate usage of the floating point expansions. We present in this work some new multiplication algorithms faster and more integrated than the stepwise algorithms proposed earlier. We have tested these new algorithms on an application that computes the determinant of a matrix. In the absence of overflow or underflow, the process is error free and possibly more efficient than its integer based counterpart.
  • Abstract (in french):

    Dans les ordinateurs modernes, l'unité de calcul à virgule flottante est celle qui délivre le plus de puissance et aussi celle qui retient l'attention des équipes de développement. Nous pourrons améliorer significativement les performances des applications en précision multiple en faisant un bon usage des expansions à virgule flottante. Nous présentons dans ces travaux de nouveaux algorithmes de multiplication plus rapides et mieux intégrés que les algorithmes pas à pas proposés précédement. Nous avons testé ces nouveaux algorithmes avec une application qui calcule exactement le déterminant d'une matrice. En l'absence de dépassement de capacité vers l'infiniment grand ou vers l'infiniment petit ce processus est sans erreur et potentiellement plus efficace que ses équivalents basés sur les nombres entiers.
  • Keywords:

    Floating Point, Multiple Precision, Computational Geometry.
  • Keywords (in french):

    Virgule Flottante, Précision Multiple, Géométrie Algorithmique.
  • Availability: Electronic copy only.
  • Citation: Published in the Proceedings of the 14th Symposium on Computer Arithmetic, 1999.
  • Size: 2+16p
  • Format: Compressed PostScript
  • Get it

Treewidth and Minimum Fill-in of Weakly Triangulated Graphs.

  • By: Vincent Bouchitte , Ioan Todinca
  • Number: RR1998-40
  • Date: September 1998
  • Abstract:

    We introduce the notion of "potential maximal clique" of a graph and we use it for computing the treewidth and the minimum fill-in of graphs for which the the potential maximal cliques can be listed in polynomial time. Finally we show how to compute the potential maximal cliques of weakly triangulated graphs.
  • Abstract (in french):

    Nous introduisons la notion de "clique potentielle maximale" d'un graphe et nous l'utilisons pour calculer le treewidth et le minimum fill-in des graphes pour lesquels les cliques potentielles maximales peuvent être énumerées en temps polynômial. Finalement nous montrons comment calculer les cliques potentielles maximales des graphes faiblement triangulés.
  • Keywords:

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

    Treewidth, Graphes Triangulés, Séparateurs Minimaux,
  • Availability: Electronic copy only.
  • Citation: Submitted to STACS'99.
  • Size: 2+14p
  • Format: Compressed PostScript
  • Get it

Symbolic Partitioning and Scheduling of Parameterized Task Graph.

  • By: Michel Cosnard , Emmanuel Jeannot , Tao Yang
  • Number: RR1998-41
  • Date: September 1998
  • Abstract:

    A parameterized task graph is a model of computation which is small and problem size independent (i.e. it requires the same amount of memory, whatever the size of the program parameters is). Here, we discuss a me thod that allows to statically (at compile time) schedule such a parameterized task graph. Therefore, we find an allocation algorithm which memory complexity and computational complexity are O(1). Once the symbolic allocation is computed we describe a distributed method to execute the program in a multithreaded environment and we show preliminary result on the efficiency of a parallel program built using the framework described in this paper.
  • Abstract (in french):

    Un graphe de tâches paramétré est un modèle de calcul qui est petit et indépendant de la taille des données (i.e. il requière la même quatité de mémoire quel que soit la taille des paramètres du programme). Nous présentons ici une methode qui permet d'ordonnancer statiquement (à la compilation) de tels graphes de tâches. Nous trouvons ainsi un algorithme d'allocation qui a une complexité mémoire et temporelle en $O(1)$. Nous décrivons une méthode distribuée qui, une fois cette allocation symbolique calculée, permet d'exécuter le programme dans un environnement multithreadé. Nous montrons des premiers résultats sur l'efficacité du programme parallèle construit suivant le schéma décrit dans ce papier.
  • Keywords:

    Static Scheduling, Parameterized task Graph, Thread, Control Parallelism, Control Static Program.
  • Keywords (in french):

    Ordonnancement Statique, Graphe de Tâches Paramétré, Processus Léger, Parallélisme de Contrôle, Programme à Contrôle Statique.
  • Availability: Electronic copy only.
  • Citation: Partly published in ICPADS'98.
  • Size: 2+14p
  • Format: Compressed PostScript
  • Get it

The Nestor library: a tool for implementing Fortran source to source transformations.

  • By: Georges-Andre Silber , Alain Darte
  • Number: RR1998-42
  • Date: September 1998
  • Abstract:

    We describe Nestor, a library to easily manipulate Fortran programs through a high level internal representation based on C++ classes. Nestor is a research tool that can be used to quickly implement source to source transformations. The input of the library is Fortran 77, Fortran 90, and HPF 2.0. Its current output supports the same languages plus some dialects such as Petit, OpenMP, CrayMP. Compared to SUIF 2.0 that is still announced, Nestor is less ambitious, but is light, ready to use, fully documented and is better suited for Fortran to Fortran transformations.
  • Abstract (in french):

    Dans ce rapport, nous décrivons Nestor, une bibliothèque pour manipuler facilement des programme Fortran à l'aide d'une représentation interne de haut niveau qui se fonde sur des classes C++. Nestor est un outil de recherche qui peut être utilisé pour implanter rapidement des transformation source à source. Les langages reconnus par la librairie sont Fortran 77, Fortran 90 et HPF 2.0. Les langages disponibles en sortie sont les précédents plus des dialectes de Fortran comme Petit, OpenMP, CrayMP, etc. Comparé à SUIF 2.0 qui est toujours annoncé, Nestor est moins ambitieux, mais il est léger, prêt à être utilisé et complètement documenté. De plus, Nestor est mieux adapté aux transformations source à source de Fortran.
  • Keywords:

    Library, Program Transformations, HPF, Parallelization, Object Oriented.
  • Keywords (in french):

    Bibliothèque, Transformation de Programmes, HPF, Parallélisation, Orienté Objet.
  • Availability: Electronic copy only.
  • Citation: Not published yet.
  • Size: 2+19p
  • Format: Compressed PostScript
  • Get it

A multithreaded runtime environments with thread migration for HPF and C* data-parallel compilers.

  • By: Luc Bouge , Phil Hatcher , Raymond Namyst , Christian Perez
  • Number: RR1998-43
  • Date: September 1998
  • Abstract:

    This paper studies the benefits of compiling data-parallel languages onto a multithreaded runtime environment providing dynamic thread migration facility. Each abstract process is mapped onto a thread, so that dynamic load balancing can be achieved by migrating threads among the processing nodes. We describe and evaluate an implementation of this idea in the Adaptor HPF and the UNH C* data-parallel compilers. We show that no deep modifications of the compilers are needed, and that the overhead of managing threads can be kept small. As an experimental validation, we report on an HPF implementation of the Gauss Partial Pivoting algorithm. We show that the initial BLOCK data distribution with our dynamic load balancing scheme can reach the performance of the optimal CYCLIC distribution.
  • Abstract (in french):

    Ce papier étudie les avantages de la compilation de langages à parallélisme de données sur des environements multiprogrammés offrant la migration dynamique de processus légers. Chaque processus abstrait est mappé dans un processus léger. Ainsi, l'équilibrage dynamique de charge peut être réalisé par la migration de processus légers entre les noeuds de calculs. Nous décrivons et évaluons une implémentation de cette idée dans les compilateurs à parallélisme de données Adaptor (HPF) et UNH-C* (C*). Nous montrons que des modifications profondes des compilateurs sont nécessaires et que le surcoût de gestion des processus légers peut être maintenu faible. Comme validation, nous reportons sur une implémentation en HPF de l'algorithme de pivot partiel de Gauss. Nous montrons que la distribution de donnée initial (BLOC) peut conduire aux performances optimals de la distribution CYCLIC avec l'aide d'un équilibrage de charge.
  • Keywords:

    Data-Parallel Languages, Compiler, HPF, C*, Thread Migration.
  • Keywords (in french):

    Langages à Parallélisme de Données, Compilateur, HPF, C*, Migration de Processus Léger.
  • Availability: Electronic copy only.
  • Citation: Proc. 1998 Intl Conf. on Parallel Architectures and Compilation
  • Size: 2+20p
  • Get it

Simulations of graph automata.

  • By: Codrin Nichitiu , Eric Remila
  • Number: RR1998-44
  • Date: September 1998
  • Abstract:

    We state a definition of the simulation of graph automata, which are machines built by putting copies of the same finite-state automaton at the vertices of a regular graph, reading the states of the neighbors. The graphs considered here are planar, with the elementary cycles of the same length, and form regular tilings of the hyperbolic plane. Thereafter, we present some results of simulation between such graph automata, comparing them to the cellular automata on Cayley graphs, and we conclude with a possible speed hierarchy.
  • Abstract (in french):

    Nous posons une définitions de la simulation de graphes d'automates, qui sont des machines construites en plaçant des copies du même automate fini dans les sommets d'un graphe régulier, lisant les états des voisins. Les graphes considérés ici sont planaires, avec les cycles élémentaires de même longueur, et forment des pavages réguliers du plane hyperbolique. Par la suite, nous présentons quelques résultats de simulation entre de tels graphes d'automates, en les comparant aux automates cellulaires sur des graphes de Cayley, et nous concluons avec une hiérarchie possible de vitesse de simulation.
  • Keywords:

    Graph Automata, Simulation, Finite State Automata, Regular Graphs, Hyperbolic Tilings, Cayley Graphs, cellular Automata.
  • Keywords (in french):

    Graphes d'Automates, Simulation, Automate Fini, Graphes Réguliers, Pavages Hyperboliques, Graphes de Cayley, Automates Cellulaires.
  • Availability: Electronic copy only.
  • Citation: Already published as Interner Bericht 19/98, ISSN 1432-7864, at Karlsruhe University, and presented at MFCS'98 Satellite Workshop on Cellular Automata.
  • Size: 2+11p
  • Format: Compressed PostScript
  • Get it

A few results on table-based methods.

  • By: Jean-Michel Muller
  • Number: RR1998-46
  • Date: October 1998
  • Abstract:

    Table-based methods are frequently used to implement functions. We examine some methods introduced in the literature, and we introduce a generalization of the bipartite table method, named the multipartite table method.
  • Abstract (in french):

    Les méthodes à base de tables sont de plus en plus utilisées pour implanter des fonctions. Nous examinons quelques méthodes suggérées antérieurement, puis nous proposons une généralisation de la méthode des ``tables bipartites'', appelée méthode des ``tables multipartites''.
  • Keywords:

    Elementary Functions, Computer Arithmetic, Table-Based Methods.
  • Keywords (in french):

    Fonctions Elémentaires, Arithmétique des Ordinateurs, Méthodes à Base de Tables.
  • Availability: Electronic copy only.
  • Citation: Not published yet.
  • Size: 2+7p
  • Format: Compressed PostScript
  • Get it

A Geometrical Hierarchy of Graphs via Cellular Automata.

  • By: Bruno Martin
  • Number: RR1998-47
  • Date: October 1998
  • 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):

    Historiquement, les automates cellulaires ont été défini sur les réseaux $\IZ^n$, mais cette définition peut être étendue aux graphes de degré borné. Étant donnée une notion de simulation entre des automates cellulaires définis sur des structures différentes (c'est à dire entre des graphes d'automates), nous pouvons en déduire un ordre sur les graphes. Dans ce papier, nous relions cet ordre à des propriétés de ces graphes et explicitons l'ordre pour la plupart des graphes courrant.
  • 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: This paper was accepted and presented at the satellite workshop on cellular automata of the conference MFCS'98.
  • Size: 2+16p
  • Format: Compressed PostScript
  • Get it

A near-optimal solution to a two-dimensional cutting stock problem.

  • By: Claire Kenyon , Eric Remila
  • Number: RR1998-48
  • Date: October 1998
  • Abstract:

    We present an asymptotic fully polynomial approximation scheme for strip-packing, or packing rectangles into a rectangle of fixed width and minimum height, a classical $NP$-hard cutting-stock problem. The algorithm finds a packing of $n$ rectangles whose total height is within a factor of $(1+\epsilon )$ of optimal (up to an additive term), and has running time polynomial both in $n$ and in $1/\epsilon$. It is based on a reduction to fractional bin-packing.
  • Abstract (in french):

    Nous présentons un schéma totalement polynomial d'approximation pour la mise en boite de rectangles dans une boite de largeur fixée, avec hauteur minimale, qui est un probleme $NP$-dur classique, de coupes par guillotine. L'algorithme donne un placement des rectangles, dont la hauteur est au plus egale a $(1+\epsilon )$ (hauteur optimale) et a un temps d'execution polynomial en $n$ et en $1/\epsilon$. Il utilise une reduction au probleme de la mise en boite fractionaire.
  • Keywords:

    Bin-Packing, Strip-Packing, Approximation Scheme.
  • Keywords (in french):

    Algorithmes de Mise en Boite, Schéma d'Approximation.
  • Availability: Electronic copy only.
  • Citation: To appear in Mathematics of Operation Research.
  • Size: 2+15p
  • Format: Compressed PostScript
  • Get it

Algorithmic Issues on Heterogeneous Computing Platforms.

  • By: Pierre Boulet , Fabrice Rastello , Yves Robert , Jack Dongarra , Frederic Vivien
  • Number: RR1998-49
  • Date: October 1998
  • Abstract:

    This paper discusses some algorithmic issues when computing with a heterogeneous network of workstations (the typical poor man's parallel computer). Dealing with processors of different speeds requires to use more involved strategies than 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). We introduce a static distribution strategy that can be refined on the fly, and we show that it is well-suited to parallelizing scientific computing applications such as finite-difference stencils or LU decomposition.
  • Abstract (in french):

    Cet article traite de problèmes algorithmiques liés à l'implémentation de programmes parallèles sur un réseau de stations hétérogène (typiquement la machine parallèle du programmeur pauvre). Si dans le cadre d'un réseau de machines homogènes, une distribution cyclique des données est souvent optimale, elle n'est plus du tout adaptée à cette nouvelle configuration. Plusieurs stratégies sont envisageables : en particulier, s'opposent les distributions effectuées dynamiquement (surcoût de communications) à celles effectuées statiquement (mauvaise estimations due aux variations de charge des machines). Ici, nous découpons l'espace d'itération en tranches ; à la fin de l'exécution d'une tranche, connaissant le temps passé par chaque processeur au calcul, nous réévaluons leur vitesse ; Nous redistribuons alors les données de manière optimale pour l'exéecution de la tranche suivante. Finalement, nous montrons par des experimentations que notre approche est appropriée pour de nombreux noyaux de calcul scientifique comme la décomposition LU ou des problèmes aux différences finies.
  • Keywords:

    Tiling, Heterogeneous Computing Platforms, Load Balancing, Distributed Memory, Different-Speed Processors, Communication-Computation Overlap, Mapping, LU decomposition, Relaxation.
  • Keywords (in french):

    Pavage, Machines Hétérogènes, Equilibrage de Charge, Mémoire Partagée, Vitesses de Processeurs Différentes, Recouvrement Calcul-Communication, Distribution, Décomposition LU, Problèmes de Relaxation.
  • Availability: Electronic copy only.
  • Citation: Not published yet.
  • Size: 2+20p
  • Format: Compressed PostScript
  • Get it

On the complexity of loop fusion.

  • By: Alain Darte
  • Number: RR1998-50
  • Date: October 1998
  • Abstract:

    Loop fusion is a program transformation that combines several loops into one. It is used in parallelizing compilers mainly for increasing the granularity of loops and for improving data reuse. The goal of this report is to study, from a theoretical point of view, several variants of the loop fusion problem -- identifying polynomially solvable cases and NP-complete cases -- and to make the link between these problems and some scheduling problems that arise from completely different areas. We study, among others, the fusion of loops of different types, and the fusion of loops when combined with loop shifting.
  • Abstract (in french):

    La fusion de boucles est une transformation de programme qui combine plusieurs boucles en une seule. Elle est utilisée dans les compilateurs-paralléliseurs, principalement pour augmenter la granularité des boucles et pour améliorer la réutilisation des données. Le but de ce rapport est d'étudier d'un point de vue théorique plusieurs variantes du problème de fusion de boucles -- en identifiant les cas solubles en temps polynomial et les cas NP-complets -- et d'établir le lien entre ces problèmes et quelques problèmes d'ordonnancement provenant de domaines complètement différents. Nous étudions notamment le problème de la fusion de boucles typées ainsi que le problème de la fusion de boucles avec décalage.
  • Keywords:

    Parallelization, Loop Fusion, Loop Distribution, Complexity.
  • Keywords (in french):

    Parallélisation, Fusion de Boucles, Distribution de Boucles, Complexité
  • Availability: Electronic copy only.
  • Citation: Not published yet.
  • Size: 2+17p
  • Format: Compressed PostScript
  • Get it

A Framework for Defining Object-Calculi.

  • By: Frederic Lang , Pierre Lescanne , Luigi Liquori
  • Number: RR1998-51
  • Date: December 1998
  • Abstract:

    In this paper, we give a general framework for the foundation of an operational (small step) semantics of object-based languages with an emphasis on functional and imperative issues. The framework allows classifying very naturally object-based calculi according to their main implementation techniques of inheritance, namely "delegation" and "embedding". This distinction comes easily from the choice of the rules we make. Our framework is founded on two previous works, namely the "Lambda Calculus of Objects" of Fischer, Honsell, and Mitchell for the object aspects and the lambda-sigma-w-a of Benaissa, Lang, Lescanne, and Rose for the description of the operational semantics and sharing. The former is the formalization of a small delegation-based language which contains both lambda calculus and object primitives to create, update, and send messages to objects, while the latter is designed to provide a generic description of functional language implementations and is based on a calculus of explicit substitutions extended with addresses to speak about memory management. The framework is presented as a set of "modules", each of which captures a peculiar aspect of object-calculi (functional vs. imperative, delegation vs. embedding, and any combination of them). Our framework satisfies some crucial properties, namely "confluence" on the functional fragment (the final result does not depend on the sequence of computations i.e., on the evaluation strategy), "operational soundness" (our calculi yield the same results on the same data as in the Lambda Calculus of Objects), "subject reduction" (programs preserve types), "type soundness" (a typed program can not go wrong as invoking an unknown method on an object).
  • Abstract (in french):

    Dans cet article, nous définissons un système général pour la fondation d'une sémantique opérationnelle (à pas réduit) des langages basés sur les objets, en insistant sur des problèmes propres aux langages fonctionnels ou impératifs. Dans ce cadre, nous pouvons classifier très naturellement les calculs basés sur les objets selon leur principale technique d'implantation de l'héritage, notamment "délégation" et "emboîtement". Cette distinction est faite simplement dans le choix des règles. Notre système se fonde essentiellement sur deux travaux précédents, le Lambda Calcul des Objets de Fisher, Honsell, et Mitchell pour les aspects objets, et le calcul lambda-sigma-w-a de Benaissa, Lang, Lescanne, et Rose pour la description de la sémantique opérationnelle et du partage. Le premier est la formalisation d'un petit langage basé sur la délégation qui contient à la fois le lambda calcul et des primitives sur les objets permettant de les créer, de les modifier, et de leur envoyer des messages, tandis que le second est conçu pour donner une description générique des langages fonctionnels et est basé sur un calcul de substitution explicite étendu avec des adresses pour modéliser la gestion de la mémoire. Le système est présenté sous la forme d'un ensemble de "modules", chacun décrivant un aspect particulier des calculs à objets (fonctionnel ou impératif, délégation ou emboîtement, et toute combinaison de ceux-ci). Notre système satisfait des propriétés cruciales comme la "confluence" sur le fragment fonctionnel (le résulat final ne dépend pas de la séquence des calculs, c'est-à-dire de la stratégie d'évaluation), la "correction opérationnelle" (nos calculs retournent le même résultat pour les mêmes données que le Lambda Calcul des Objets), l'"auto réduction" (les programmes préservent les types), et la "sûreté du typage'' (un programme typé ne peut pas mener à une erreur d'exécution comme invoquer une méthode inconnue sur un objet).
  • Keywords:

    Functional and Imperative Object-Based Languages, Operational Semantics, Implementation Issues, Memory Management, Type System, Delegation vs. Embedding.
  • Keywords (in french):

    Langages Basés sur les Objets, Fonctionnels et Impératifs, Sémantique Opérationnelle, Problèmes d'Implantation, gestion de la Mémoire, Système de Types, Délégation ou Emboîtement.
  • Availability: Electronic copy only.
  • Citation: Not pubblished yet.
  • Size: 2 + 33p
  • Format: Compressed Postscript
  • Get it

Linear Ensemble Methods for Multiclass Discrimination.

  • By: Yann Guermeur , Helene Paugam-Moisy
  • Number: RR1998-52
  • Date: December 1998
  • Abstract:

    We consider the case of a discrimination problem for which several classifiers are available. The object of this study is the combination of the class posterior probability estimates provided by these classifiers, in order to obtain better estimates and concomitantly a better discriminant function. The ensemble method is the multivariate linear regression. We specify the optimization problem to which training amounts and we characterize the sets of optimal solutions corresponding to the main convex objective functions. Means to assess and control the generalization capabilities are also investigated.
  • Abstract (in french):

    Nous considérons le cas d'un problème de discrimination pour lequel plusieurs classifieurs sont disponibles. L'objet de cette étude est la combinaison des estimations des probabilités a posteriori des classes fournies par ces classifieurs, afin d'obtenir de meilleures estimations et, de manière concomitante, une meilleure fonction de discrimination. Le modèle de combinaison considéré est la régression linéaire multivariée. Nous spécifions le problème d'optimisation auquel se réduit l'apprentissage et caractérisons les ensembles de solutions optimales correspondant aux principales fonctions objectif convexes. Nous étudions également le moyen d'évaluer et de contrôler les performances en généralisation.
  • Keywords:

    Discrimination, Probability Estimation, Linear Regression.
  • Keywords (in french):

    Discrimination, Estimation de Probabilités, Régression Linéaire.
  • Availability: Electronic copy only.
  • Citation: Extended version of a talk presented at SFC'98.
  • Size: 2+8p
  • Format: Compressed PostScript
  • Get it