Local memory requirement of universal routing schemes.

  • By: Pierre Fraigniaud , Cyril Gavoille
  • Number: RR1996-01
  • Date: January 1996
  • Abstract:

    In this paper, we deal with the compact routing problem, that is the problem of implementing routing schemes that use a minimum memory size on each router. A universal routing scheme is a scheme that applies to all networks. In [13], Peleg and Upfal showed that one can not implement a universal routing scheme with less than a total of Omega(n^{1+1/(2s+4)}) memory bits for any routing scheme satisfying that the maximum ratio between the lengths of the routing paths and the lengths of the shortest paths, that is the stretch factor, is bounded by s. In [6], Fraigniaud and Gavoille improve this bound by proving that universal routing schemes of stretch factors at most 2 use a total of Omega(n^2) memory bits in the worst-case. Recently, Gavoille and Pérennès [9] showed that, in fact, in the worst-case, Theta(n) routers of an n-node network may require up to Omega(n log n) memory bits for shortest path routing. In this paper, we extend this result by showing that, for any constant e, 0 < e < 1, Omega(n^e) routers of an n-node network may require up to Omega(n log n) memory bits even if each routing path is of length up to twice the distance between its source and its destination.
  • Abstract (in french):

    Dans cet article, nous abordons le problème du routage compact, qui est la mise en oeuvre des stratégies de routages utilisant une taille mémoire minimum pour chaque routeur. Une stratégie de routage universel est une stratégie qui s'applique à tous les réseaux. Dans [13], Peleg et Upfal ont montré qu'il n'y a aucun espoir de la réaliser avec moins de Omega(n^{1+1/(2s+4)}) bits mémoire au total pour toute stratégie de routage dont le rapport maximum entre la longueur des chemins de routage et la longueur des plus courts chemins, le facteur d' élongation, est borné par s. Dans [6], Fraigniaud et Gavoille améliorent cette borne en montrant que toute stratégie de routage universel de facteur d'élongation au plus 2 utilise un total de Omega(n^2) bits mémoire dans le pire cas. Récemment, Gavoille et Pérennès [9] ont montré, en fait, que Theta(n) routeurs d'un réseau de n noeuds peuvent chacun nécessiter localement de Omega(n log n) bits pour toute fonction de routage de plus courts chemins. Dans cet article, nous étendons ce résultat en montrant que, pour toute constante e, 0 < e < 1, Omega(n^e) routeurs d'un réseau de n noeuds nécessitent jusqu'à Omega(n log n) bits chacun si la longueur des chemins de routage est au plus deux fois plus longue que la longueur des plus courts chemins.
  • Keywords:

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

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

Parallel visualization of texture-mapped digital elevation models.

  • By: Sylvain Contassot-Vivier , Serge Miguet
  • Number: RR1996-02
  • Date: January 1996
  • Abstract:

    We propose in this paper, a parallel implementation of a ground visualization algorithm.Our input data consist in a Digital Elevation Model (DEM) covering a rectangular region, together with a raster image of the same area (the texture). The goal of the algorithm is to compute in parallel, images of the DEM from any point of view while mapping the texture onto the surface. The main originality of our approach concerns the distribution of the data, leading to a load-balanced and scalable parallel algorithm. We use a workload estimation to partition the output image, and then redistribute the input data according to this division. A special attention is payed on the data stutures used for minimizing the cost of communications.
  • Abstract (in french):

    Nous proposons dans ce rapport, une implémentation parallèle d'un algorithme de visualisation de terrains. Les données initiales consistent en un Modèle Numérique de Terrain (MNT) couvrant une région rectangulaire, ainsi qu'une image raster de la même région (la texture). Le but de l'algorithme est de calculer en parallèle, des images du terrain de n'importe quel point de vue tout en plaquant la texture sur la surface. La principale originalité de notre approche concerne la distribution des données, menant à un algorithme ayant un bon équilibrage des charges et s'adaptant bien au nombre de processeurs utilisés. Nous utilisons une estimation de la charge pour partitionner l'image à calculer, puis nous redistribuons les données initiales sur les processeurs en fonction du partitionnement. Une attention particulière est portée sur les stuctures de données utilisées de façon à réduire le coup des communications.
  • Keywords:

    Parallelism, 3D Visualization, Texture-Mapping, Load Balancing, Data Repartition.
  • Keywords (in french):

    Parallélisme, visualisation 3D, plaquage de texture, équilibrage de charges, répartition des données.
  • Availability: Paper copy available.
  • Citation: Published in Proceedings of IWPIA'4 : Fourth International Workshop on Parallel Image Analysis, Lyon, France, 1995.
  • Size: 2+12p
  • Format: Compressed PostScript
  • Get it

A note on the XRAM and PRAM models.

  • By: Pierre Fraigniaud
  • Number: RR1996-03
  • Date: January 1996
  • Abstract:

    In this paper, we deal with the XRAM model introduced in [3]. We mainly show that the original definition of the XRAM model was not consistent, and must be slightly modified. Therefore, we modify the definition of the XRAM model to make it consistent, and we study the consequence of this modification on the complexity theory developed in the XRAM model. The new model modifies, in particular, the definition of a problem on a XRAM, and thus on a PRAM and on a RAM since these two models are particular cases of the XRAM. However, we show that, though theoretically important, this modification has no practical consequence on the complexity theory developed on the XRAM model.
  • Abstract (in french):

    Cet article traite du modèle XRAM introduit dans [3] et de ses implications sur le modèle PRAM. Il rectifie en particulier la définition originelle du modèle XRAM pour rendre ce modèle robuste vis-à-vis de l'isomorphisme de graphe.
  • Keywords:

    PRAM, Complexity.
  • Keywords (in french):

    PRAM, complexité.
  • Availability: Paper copy available.
  • Citation: Not published yet.
  • Size: 2+12p
  • Format: Compressed PostScript
  • Get it

On the removal of anti and output dependences.

  • By: Pierre-Yves Calland , Alain Darte , Yves Robert , Frederic Vivien
  • Number: RR1996-04
  • Date: February 1996
  • Abstract:

    In this paper we build upon results of Padua and Wolfe, who introduce two graph transformations to eliminate anti and output dependences. We first give a unified framework for such transformations. Then, given a loop nest, we aim at determining which statements should be transformed so as to break artificial cycles involving anti or output dependences. The problem of finding the mininum number of statements to be transformed is shown to be NP-complete in the strong sense, and we propose two efficient heuristics.
  • Abstract (in french):

    Dans ce papier nous unifions deux transformations de graphe de dépendances introduites par Padua et Wolfe dans le but d'éliminer les anti dépendances et les dépendances de sortie. Etant donné un nid de boucles, notre but est de déterminer quelles instructions doivent être transformées pour casser les cycles artificiels contenant des anti dépendances ou des dépendances de sortie. Nous montrons que trouver le minimum d'instructions à transformer est un problème NP-complet au sens fort, et nous proposons deux heuristiques.
  • Keywords:

    Node Splitting, Anti Dependences, Output Dependences, Dependence Graph, NP-completeness, Heuristics.
  • Keywords (in french):

    Anti dépendances, dépendances de sortie, graphe de dépendance, NP-complétude, heuristiques.
  • Availability: Electronic copy only.
  • Citation: Not published yet.
  • Size: 2+17p
  • Format: Compressed PostScript
  • Get it

On the optimality of Allen and Kennedy's algorithm for parallelism extraction in nested loops.

  • By: Alain Darte , Frederic Vivien
  • Number: RR1996-05
  • Date: February 1996
  • Abstract:

    We explore the link between dependence abstractions and maximal parallelism extraction in nested loops. Our goal is to find, for each dependence abstraction, the minimal transformations needed for maximal parallelism extraction. The result of this paper is that Allen and Kennedy's algorithm is optimal when dependences are approximated by dependence levels. This means that even the most sophisticated algorithm cannot detect more parallelism than found by Allen and Kennedy's algorithm, as long as dependence level is the only information available. In other words, loop distribution is sufficient for detecting maximal parallelism in dependence graphs with levels.
  • Abstract (in french):

    Nous étudions les relations entre représentations des dépendances et extraction maximale du parallélisme dans les nids de boucles. Nous recherchons, pour chaque représentation des dépendances, la plus petite transformation capable d'extraire le maximum de parallélisme. Nous prouvons dans cet article que l'algorithme d'Allen et Kennedy est optimal quand les dépendances sont approximées par des niveaux de dépendance: aucun algorithme, aussi sophistiqué soit-il, ne peut détecter plus de parallélisme que l'algorithme d'Allen et Kennedy, si la seule information disponible sur les dépendances est le niveau de la dépendance. Autrement dit, la distribution de boucles suffit à détecter le maximum de parallélisme dans les graphes de dépendance étiquetés par niveaux.
  • Keywords:

    Nested Loops, Automatic Parallelization, Dependence Analysis, Allen and Kennedy's Algorithm.
  • Keywords (in french):

    Nids de boucles, parallélisation automatique, analyse de dépendance, algorithme d'Allen et Kennedy.
  • Availability: Paper copy available.
  • Citation: Not published yet.
  • Size: 2+34p
  • Format: Compressed PostScript
  • Get it

Optimal fine and medium grain parallelism detection in polyhedral reduced dependence graphs.

  • By: Alain Darte , Frederic Vivien
  • Number: RR1996-06
  • Date: April 1996
  • Abstract:

    This paper presents an optimal algorithm for detecting fine or medium grain parallelism in nested loops whose dependences are described by an approximation of distance vectors by polyhedra. In particular, it is optimal for direction vectors: this result generalizes, to the case of several statements, Wolf and Lam's algorithm which is optimal for a single statement. Our algorithm relies on a dependence uniformization process and on parallelization techniques related to system of uniform recurrence equations.
  • Abstract (in french):

    Ce rapport présente un algorithme de parallélisation de boucles qui est optimal pour toute représentation des dépendances fournissant une approximation polyédrique des vecteurs de distance. En particulier, il est optimal pour les vecteurs de direction ce qui généralise au cas de plusieurs instructions l'algorithme de Wolf et Lam qui est optimal pour les nids ne contenant qu'une seule instruction. Notre algorithme est basé sur un procédé d'uniformisation des dépendances et sur une technique de parallélisation issue des systèmes d'équations récurrentes uniformes.
  • Keywords:

    Automatic Parallelization, Multi-dimensional Schedule, Loop Nest, System Of Uniform Recurrence Equations, Dependence Analysis, Polyhedral Reduced Dependence Graph.
  • Keywords (in french):

    Parallélisation Automatique, Ordonnancement Multi-dimensionnel, Nid De Boucles, Systèmes D' équationsrécurrentes Uniformes, Analyse De Dépendances, Graphe De Dépendance Réduit Polyédrique.
  • Availability: Electronic copy only.
  • Citation: Submitted.
  • Size: 2+31p
  • Format: Compressed PostScript
  • Get it

Comparative study of three connectionist models on a classification problem.

  • By: Richard Baron , Helene Paugam-Moisy , Mirta B. Gordon , J.-M. Torres Moreno
  • Number: RR1996-07
  • Date: April 12, 1996
  • Abstract:

    In this paper, we compare three neural learning models, on the sonar target classification problem of Gorman and Sejnowski, in two ways. First, we compare the performance on training and testing sets, in the usual sense. Second, we investigate in the database, in order to compare the examples which are hard to be learned and the patterns which are ill-classified, in generalization. The neural networks involved in these comparisons are a classical multilayered network, a wavelet network, and a evolutive architecture named ``Monoplane''. In spite of several differences in the characteristics of their learning algorithms, these neural networks perform similarly on the classification problem, and the patterns which are hard to classify are nearly the same, whatever the model be. Several distance measures are then computed on the database, but we show that none of them allows to explain the misclassification phenomenon. We conclude that hard to classify patterns depend on the database more on than the learning model.
  • Abstract (in french):

    Dans cet article, trois modèles connexionistes sont comparés, sur le problème de classification des signaux sonar de Gorman et Sejnowski. Tout d'abord, les performances en apprentissage et en généralisation sont comparées. Puis, la base d'exemple est analysée, afin de caractériser les exemples mal appris et mal reconnus. Les trois modèles mis en oeuvre sont, un réseau multi-couches classique, un réseau d'ondelettes, et une architecture incrémentale, appelée ``Monoplan''. Malgré les différences des algorithmes d'apprentissage utilisés, ces trois modèles se comportent de manière similaire pour la tâche de classification, et les exemples mal classés sont a peu près les mêmes, quel que soit le modèle. Des mesures de distances sont alors utilisées, mais aucune d'elles ne permet d'expliquer complètement les cas de mauvaise classification. Nous concluons que les exemples difficiles à classer dépendent de la base d'exemple, plus que du modèle mis en oeuvre.
  • Keywords:

    Classification, Learning, Neural Networks, Monoplane, Wavelet Networks.
  • Keywords (in french):

    Classification, Apprentissage, Réseaux De Neurones, Monoplan, Réseau d'ondelettes.
  • Availability: Paper copy available.
  • Citation: English version of a french paper presented at the conference JFA'96 [Journees Francaises d'Apprentissage], (1996),p.275-287.
  • Size: 2+12p
  • Format: Compressed PostScript
  • Get it

Lower Bounds for Shortest Path Interval Routing.

  • By: Cyril Gavoille , Stephane Perennes
  • Number: RR1996-08
  • Date: April 1996
  • Abstract:

    Interval Routing was introduced to reduce the size of the routing tables: a router finds the direction to forward a message by determining the interval that contains the destination address of the message, each interval being associated to one particular direction. In this paper, we give lower bounds for the minimum number of intervals per edge needed to achieve shortest path routings for the class of 3-regular networks. We prove a tight lower bound of Theta(n) intervals for a 3-regular network of order at most n. Moreover, for the particular case of 3-regular planar networks, we establish a lower bound of Omega(sqrt{n}) intervals.
  • Abstract (in french):

    Le routage par intervalles a été introduit pour réduire la taille des tables de routage : un routeur trouve la direction pour communiquer un message en déterminant l'intervalle contenant l'adresse de destination du message, chaque intervalle étant associé à une direction particulière. Dans cet article, nous donnons une borne inférieure du nombre minimum d'intervalles par arête nécessaire pour effectuer un routage de plus courts chemins pour la classe des réseaux 3-réguliers. Nous prouvons une borne inférieure optimale de Theta(n) intervalles pour un réseau 3-régulier d'ordre au plus n. De plus, pour la classe des réseaux 3-réguliers et planaires, nous établissons une borne inférieure de Omega(sqrt{n}) intervalles.
  • Keywords:

    Compact Routing In Distributed Networks, Shortest Path Interval Routing, 3-regular Graphs, Planar Graphs.
  • Keywords (in french):

    Routage Compact Dans Réseaux Distribués, Routage Par Intervalles Et De Plus Courts Chemins, Graphes 3-réguliers, Graphes Planaires.
  • Availability: Electronic copy only.
  • Citation: Published in the proceedings of SIROCCO'96.
  • Size: 2+13p
  • Format: Compressed PostScript
  • Get it

Utilisation de processus legers pour l'execution de programmes a parallelisme de donnees : etude experimentale.

  • By: Christian Perez
  • Number: RR1996-09
  • Date: April 1996
  • Abstract:

    This paper studies the use of threads to support the execution of data-parallel programs. The overhead induced by the multithreaded environment is experimentally studied : global synchronization, thread creation, communication, thread migration. We propose some simple criteria to determine the ``right'' size of threads with respect to the expected overhead. We use the PM2 multithreaded environment which provides thread migration facilities.
  • Abstract (in french):

    Ce rapport présente une étude de quelques aspects importants des processus légers pour leur utilisation à l'exécution de programmes à parallélisme de données. La surcharge de l'environnement d'exécution, le coût des synchronisations globales, de création de processus légers, le comportement des processus légers vis-à-vis des communications ainsi que le coût de la migration des processus légers sont étudiés. Nous en déduisons des critères simples pour la détermination de la ``bonne'' taille des processus légers en relation avec le surcoût engendré. L'environnement d'exécution choisi est PM2 car il intègre la migration de processus légers.
  • Keywords:

    Data parallel languages, compilation, multithreaded environment, threads, experimental cost study.
  • Keywords (in french):

    Langages à parallélisme de données, compilation, environnement d'exécution multithread, processus légers, étude expérimentale des coûts.
  • Availability: Paper copy available.
  • Citation: Not published yet.
  • Size: 2+22p
  • Format: Compressed PostScript
  • Get it

Proving data-parallel programs: a unifying approach.

  • By: David Cachera , Gil Utard
  • Number: RR1996-10
  • Date: May 1996
  • Abstract:

    We define an axiomatic semantics for a common kernel of existing data-parallel languages. We introduce an assertional language which enables us to define a weakest liberal precondition calculus which has the Definability Property, and a proof system (a la Hoare) which has the completeness Property. Moreover, our axiomatic semantics integrates two previous works in the definition of proof systems for data-parallel programs. This work sheds a new light on the logical complexity of proving data-parallel programs.
  • Abstract (in french):

    Nous définissons une sémantique axiomatique pour un noyau commun à des langages data-parallèles existants. Nous introduisons un langage d'assertions qui nous permet à la fois de définir un calcul des plus faibles préconditions qui a la propriété de définissabilité, et un système de preuve à la Hoare qui est complet. De plus, notre sémantique axiomatique intègre deux travaux précédents sur la définition de systèmes de preuve pour les programmes data-parallèles. Ce travail apporte un nouveau point de vue sur la complexité de la preuve de programmes data-parallèles.
  • Keywords:

    Verifying And Reasoning About Programs, Data-parallel Languages, Proof System, Hoare Logic.
  • Keywords (in french):

    Spécification Et Validation De Programmes, Langages Data-parallèles, Système De Preuve, Logique De Hoare.
  • Availability: Electronic copy only.
  • Citation: To appear in Parallel Processing Letters (1996).
  • Size: 2+17p
  • Format: Compressed PostScript
  • Get it

Parallel Implementation of RBF Neural Networks.

  • By: Vladimir Demian , Frederic Desprez , Helene Paugam-Moisy , Makan Pourzandi
  • Number: RR1996-11
  • Date: June 1996
  • Abstract:

    This report presents several parallel implementations, on a MIMD machine, of a learning algorithm called OLS (Orthogonal Least Squares) for RBF (Radial Basis Function) neural networks. The sequential version is first described, and a straightforward parallel version is proposed. Two variants are developed, one of them reducing the complexity of the algorithm, and the other one improving the load balancing. An alternative is proposed for the storage of initial or intermediate data on local memory and discussed, according to the size of the application.
  • Abstract (in french):

    Ce rapport présente plusieurs implémentations parallèles, sur machine MIMD, de l'algorithme d'apprentissage OLS (Orthogonal Least Squares) pour les réseaux neuronaux RBF (Radial Basis Function). La version séquentielle est rappelée, puis une première parallélisation est exposée. Deux variantes sont ensuite proposées, l'une réduisant la complexité de l'algorithme, l'autre améliorant l'équilibrage des charges. On discute de l'opportunité de stocker, en mémoire locale, des données initiales ou intermédiaires, en fonction de la taille de l'application.
  • Keywords:

    RBF Neural Networks, Parallel Algorithms, Load Balancing.
  • Keywords (in french):

    Réseaux RBF, Algorithmes Parallèles, Equilibrage de Charge.
  • Availability: Paper copy available.
  • Citation: Published in Proceedings of EuroPar'96, LNCS, vol.1124, Spinger, (1996), p.243-250.
  • Size: 2+20p
  • Format: Compressed PostScript
  • Get it

Simple sequences strain error analysis.

  • By: Marc Daumas
  • Number: RR1996-12
  • Date: June 1996
  • Abstract:

    Past studies on floating point arithmetic have presented unexpected behaviors of some compound floating point operations. All the simple examples share the same all or nothing option: they either give the good result or a total miss. These examples are derived from simple mathematical properties including the cancelation of the floating point addition. Some work has been intended on more complex systems computing efficiently the practical bounds, but no detailed analysis is available. The Kla's Increasing and Decreasing Sequences (KIDS) shows many shades of unpredictable error accumulation for a very simple sequence of multiplications. We will present the results of experiment with KIDS and our first steps towards an analysis.
  • Abstract (in french):

    Des travaux antérieurs sur l'arithmétique flottante ont mis en avant le comportement original de certaines suites d'opérations en notation à virgule flottante. Les exemples décrits partage le même comportement tout ou rien : il donnent soit le bon résultat soit un résultat entièrement erroné. Ces résultats sont la conséquence de propriétés mathématiques simples, dont la cancellation de l'addition en notation flottante. Des travaux sont disponibles sur des problèmes beaucoup plus larges, mais ils ne proposent pas toujours une analyse détaillée du comportement de chaque opérateur séparément. Des produits de facteurs évalués en ordre croissant et décroissant proposés par Kla (en anglais Kla's Increasing and Decreasing Sequences) présentent un continuum de comportements originaux pour une expression très simple. Nous présentons ici les résultats expérimentaux et nos premiers éléments d'analyse.
  • Keywords:

    Computer Arithmetic, Floating Point Notation, Error Analysis.
  • Keywords (in french):

    Arithmétique des Ordinateurs, Notation à Virgule Flottante, Analyse de l'Erreur.
  • Availability: Electronic copy only.
  • Citation: Published in Real Numbers and Computers, pp. 85-97, 1996.
  • Size: 2+16p
  • Format: Compressed PostScript
  • Get it

Plugging anti and output dependence removal techniques into loop parallelization algorithms.

  • By: Pierre-Yves Calland , Alain Darte , Yves Robert , Frederic Vivien
  • Number: RR1996-13
  • Date: June 1996
  • Abstract:

    In this paper we shortly survey some loop transformation techniques which break anti or output dependences, or artificial cycles involving such ``false'' dependences. These false dependences are removed through the introduction of temporary buffer arrays. Next we show how to plug these techniques into loop parallelization algorithms (such as Allen and Kennedy's algorithm). The goal is to extract as many parallel loops as the intrinsic degree of parallelism of the nest authorizes, while avoiding a full memory expansion. We try to reduce the number of temporary arrays that we introduce, as well as their dimension.
  • Abstract (in french):

    Dans ce rapport, nous présentons une rapide synthèse des techniques uselles pour l'élimination des ``fausses dépendances'' (anti-dépendances et dépendances en sortie). Ces techniques requièrent le plus souvent l'emploi de tableaux auxiliaires. Nous montrons comment intégrer ces techniques dans les algorithmes de parallélisation de boucles (comme celui d'Allen et Kennedy). Notre objectif est d'obtenir autant de boucles parallèles que le programme original en contient potentiellement, tout en évitant une expansion mémoire complète. Nous tentons de réduire le nombre de tableaux auxiliaires introduits, ainsi que leur dimension.
  • Keywords:

    Array Renaming, Array expansion, Node Splitting, Anti Dependences, Output Dependences, dependence Graph, Parallelization Algorithm, Allen-Kennedy, Heuristics.
  • Keywords (in french):

    Renommage, Expansion, Anti Dépendances, Dépendances de Sortie, Graphe de Dépendance, Algorithme de Parallélisation, Allen-Kennedy, Heuristiques.
  • Availability: Electronic copy only.
  • Citation: Submitted.
  • Size: 2+15p
  • Format: Compressed PostScript
  • Get it

On-line Arithmetic based Reprogrammable Hardware Implementation of Multilayer Perceptron Back-Propagation.

  • By: Bernard Girau , Arnaud Tisserand
  • Number: RR1996-14
  • Date: June 1996
  • Abstract:

    A digital hardware implementation of a whole neural network learning is described. It uses on-line arithmetic on {\sc fpga}s. The modularity of our solution avoids the development problems that occur with more usual hardware circuits. A precise analysis of the computations required by the back-propagation algorithm allows us to maximize the parallelism of our implementation.
  • Abstract (in french):

    Nous présentons une implantation matérielle numérique d'un apprentissage de réseau de neurones. Cette implantation utilise une arithmétique en ligne et est proposée sur {\sc fpga}. La modularité de notre solution permet d'éviter les problèmes de développement inhérents aux circuits numériques plus classiques. Une analyse précise des calculs requis par l'algorithme de rétro-propagation du gradient nous amène à une implantation fortement parallèle.
  • Keywords:

    On-Line Arithmetic, Neural Networks, {\sc fpga}, Back-Propagation.
  • Keywords (in french):

    Arithmétique en Ligne, Réseaux de Neurones, {\sc fpga}, Rétro-Propagation.
  • Availability: Electronic copy only.
  • Citation: Published in proceedings of the Fifth International Conference on Microelectronics for Neural Networks and Fuzzy Systems : MicroNeuro'96, February 12-14, 1996. Lausanne Switzerland. (ISBN 0-8186-7373-7).
  • Size: 2+11p
  • Format: Compressed PostScript
  • Get it

Un problème d'ordonnancement en milieu hétérogène appliqué aux réseaux de neurones.

  • By: Richard Baron , Xavier-Francois Vigouroux
  • Number: RR1996-15
  • Date: July 1996
  • Abstract:

    Neural networks are well known as universal approximators. But the performance of neural network depends on several parameters. Finding the best set of parameters has no theoretical answer. Neural network users are forced to try different sets of parameters, and then, choose the best among them. In this paper, we present a parallel solution, based on a master-slave software architecture. Tests are reported on two platforms (workstations network and Cray T3D), using the PVM environment. The load-balancing problem is also addressed. Results are given, for the approximation and the speed-up of the parallel execution.
  • Abstract (in french):

    Les réseaux de neurones constituent des approximateurs universels. Mais leurs performances dépendent de plusieurs paramètres dont aucune méthode théorique ne permet de déterminer les valeurs. Il faut donc tester différentes configurations, ce qui représente un énorme coût en temps, afin d'extraire le choix d'un bon ensemble de paramètres. Nous proposons une solution parallèle s'appuyant sur le modèle maître-esclave. Une implémentation a été réalisée sur différentes machines cibles (réseau de stations et Cray T3D) utilisant le système PVM, et prenant en compte le problème de l'équilibrage de charge. Des résultats sont donnés, concernant la qualité de l'approximation, et l'accélération apportée par le calcul en parallèle.
  • Keywords:

    Neural Networks, Mapping, Scheduling, Load Balancing, Master/Slave, Parallelism.
  • Keywords (in french):

    Réseaux de Neurones, Placement, Ordonnancement, Equilibrage de Charge, Architecture Maître-Esclave.
  • Availability: Paper copy available.
  • Citation: Not published yet.
  • Size: 2+13p
  • Format: Compressed PostScript
  • Get it

Size of multilayer networks for exact learning: analytic approach.

  • By: Andre Elisseeff , Helene Paugam-Moisy
  • Number: RR1996-16
  • Date: July 1996
  • Abstract:

    This report presents a new result about the size of a multilayer neural network computing real outputs for exact learning of a finite set of real samples. The architecture of the network is feedforward, with one hidden layer and several outputs. Starting from a fixed training set, we consider the network as a function of its weights. We derive, for a wide family of transfer functions, a lower and an upper bound on the number of hidden units for exact learning, given the size of the dataset and the dimensions of the input and output spaces.
  • Abstract (in french):

    Ce rapport présente un nouveau résultat sur la taille d'un réseau de neurones multicouche, qui calcule des sorties réelles, pour l'apprentissage exact d'un ensemble fini d'exemples réels. L'architecture du réseau est feedforward, avec une couche cachée et plusieurs sorties. Partant d'une base d'exemples fixée, on considère le réseau comme une fonction de ses poids. Pour une large famille de fonctions de transfert, et sous l'hypothèse d'un apprentissage exact, on établit une borne inférieure et une borne supérieure sur le nombre d'unités cachées, en fonction de la taille de la base d'exemples ainsi que des dimensions des espaces d'entrée et de sortie.
  • Keywords:

    Multilayer Neural Networks, Architecture, Dimension.
  • Keywords (in french):

    Réseaux Neuronaux Multicouches, Architecture, Dimension.
  • Availability: Paper copy available.
  • Citation: Extended version of a paper to be published in May 1997, in Proceedings of NIPS*96, Denver, Colorado (US), December 1996.
  • Size: 2+19p
  • Format: Compressed PostScript
  • Get it

Optimization of the ScaLAPACK LU Factorization Routine Using Communication/Computation Overlap.

  • By: Frederic Desprez , Stephane Domas , Bernard Tourancheau
  • Number: RR1996-17
  • Date: July 1996
  • Abstract:

    This paper presents some works on the ScaLAPACK LU factorization. First, a complexity analysis is given. It allows to compute the optimal block size for the block scattered distribution used in ScaLAPACK LU. It also gives the communication phases that are interesting to overlap. Second, two optimizations based on computations/communications overlap are given with experimental results on Intel Paragon system.
  • Abstract (in french):

    Ce papier présente différents travaux sur la factorisation LU de ScaLAPACK. En premier lieu, une analyse de complexité est donnée. Elle permet de calculer la taille de bloc optimale pour la distribution bloc cyclique utilisée dans ScaLAPACK. Elle donne également les phases de communications intéressantes à recouvrir. En second lieu, deux optimisations utilisant les recouvrements calculs/communications sont données ainsi que les résultats expérimentaux obtenus sur Intel Paragon.
  • Keywords:

    LU, ScaLAPACK, Communication/Computation Overlapping.
  • Keywords (in french):

    LU, ScaLAPACK, Recouvrement Calcul/Communication.
  • Availability: Electronic copy only.
  • Citation: Extended version of a paper to be published in Proc. of EuroPar'96, Lyon (F), August 1996.
  • Size: 2+15p
  • Format: Compressed PostScript
  • Get it

Communication Issues in Parallel Systems with Optical Interconnections.

  • By: Pascal Berthome , Afonso Ferreira
  • Number: RR1996-18
  • Date: July 1996
  • Abstract:

    In classical massively parallel computers, the complexity of the interconnection networks is much higher than the complexity of the processing elements themselves. However, emerging optical technologies may provide a way to reconsider very large parallel architectures where processors would communicate by optical means. In this paper, we compare some optically interconnected parallel multicomputer models with regard to their communication capabilities. We first establish a distinction of such systems, based on the independence of the communication elements embedded in the processors (transmitters and receivers). Then, motivated by the fact that in multicomputers some communication operations have to be very efficiently performed, we study communication problems, namely, broadcast and multi-broadcast, under the hypothesis of bounded fanout. Our results take also into account a bounded number of available wavelengths.
  • Abstract (in french):

    Dans les ordinateurs massivement parallèles classiques, la complexité du réseau d'interconnexion est de loin plus importante que la complexité des processeurs eux-mêmes. Cependant, les technologies naissantes en optique pourraient être un moyen de reconsidérer le problème des architectures très massivement parallèles; dans ce cas, les processeurs communiqueraient avec des supports optiques. Dans ce papier, nous comparons quelques modèles de machines parallèles par rapport à leurs capacités à communiquer optiquement. Nous établissons une distinction entre ces différents systèmes basée sur l'indépendance des éléments communicants associés à chaque processeur (émetteur et récepteur). Ensuite, comme certaines opérations de communication doivent être effectuées efficacement dans les machines parallèles, nous étudions quelques problèmes de communication globale, en particulier la diffusion et la multi-diffusion, sous la contrainte de fanout borné. Nos résultats prennent aussi en compte des limitations sur le nombre de canaux (longueurs d'onde) disponibles dans le système.
  • Keywords:

    Optical Passive Star, broadcast, multi-broadcast, ORPC.
  • Keywords (in french):

    Étoile Passive Optique, diffusion, multi-diffusion, modèle ORPC.
  • Availability: Electronic copy only.
  • Citation: To appear in International Journal of Foundations of Computer Science, Special Issue on Interconnection Networks.
  • Size: 2+18p
  • Format: Compressed PostScript
  • Get it

Improved embeddings in POPS networks through stack-graph models.

  • By: Pascal Berthome , Afonso Ferreira
  • Number: RR1996-19
  • Date: July 1996
  • Abstract:

    In last year's MPPOI, Gravenstreter and Melhem presented optimal embeddings of ring and torus communications on the POPS architecture, for the case where the number of nodes (n) and the Optical Passive Star (OPS) coupler degree (d) are powers of two. In the same conference, Bourdin, Ferreira and Marcus proposed stack-graphs as a good model for OPS--based architectures. In this paper we show that directed stack-complete graphs with loops (stack-K+n for short) perfectly model POPS. As a consequence, we settle the question with respect to ring embeddings, presenting optimal embeddings for all values of n and d, based on Euler tours on K+n. We also show how to optimally embed de Bruijn (B(g,D)) communications on POPS when g is the number of groups in the POPS topology, using the fact that K+g is also a B(g,1).
  • Abstract (in french):

    Durant la conférence MPPOI'95, Gravenstreter et Melhem ont présenté des plongements de l'anneau et du tore dans l'architecture optique POPS. Les résultats n'ont été que partiellement donnés dans le cas où le nombre de noeuds (n) et le degré (d) des étoiles passives optiques (OPS) sont des puissances de deux. Dans la même conférence, Bourdin, Ferreira et Marcus ont proposé les stacks-graphs comme un bon modèle pour des architectures basées sur les étoiles passives optiques. Dans ce papier, nous montrons que les stacks-graphs complets orientés avec boucles (stack-K+n) sont des modèles adéquats pour l'architecture POPS. En conséquence, nous résolvons entièrement le problème du plongement dans le cas de l'anneau, avec des plongements optimaux pour toutes les valeurs de n et d; la solution est basée sur des parcours eulériens de K+n. Nous montrons aussi comment plonger de manière optimale le graphe de Bruijn (B(g,D)) sur le POPS, si g est le nombre de groupes de la topologie POPS. Pour cela nous utilisons le fait que K+g est isomorphe à B(g,1).
  • Keywords:

    Partitioned Optical Passive Star topology (POPS), Embedding, Ring Embedding, De Bruijn Embedding.
  • Keywords (in french):

    Topologie POPS, Plongement, Anneau, De Bruijn.
  • Availability: Electronic copy only.
  • Citation: To appear in MPPOI'96 (Third International Conference on Massively Parallel Processing using Optical Interconnections.
  • Size: 2+11p
  • Format: Compressed PostScript
  • Get it

Topologically Defined Isosurfaces.

  • By: Jacques-Olivier Lachaud
  • Number: RR1996-20
  • Date: July 1996
  • Abstract:

    In this research report, we present a new process for defining and building the set of configurations of Marching-Cubes algorithms. Our aim is to extract a topologically correct isosurface from a volumetric surface. Our approach exploits the underlying discrete topology of voxels and especially their connectedness. Our main contribution is to provide a formal proof of the validity of the generated isosurface according to the chosen connectedness. The generated isosurface is a closed, oriented surface without singularity with no self-intersection. Furthermore, we demonstrate that it does not intersect the adjacency map (a volumetric embedding of the adjacency graph) of the foreground and of the background, thus separating the foreground from the background. Finally we show that the graph defining the isosurface is closely linked to the surfel-adjacency graph of the digital surface of the same image.
  • Abstract (in french):

    Dans ce rapport de recherche, nous présentons une nouvelle méthode pour définir et construire l'ensemble des configurations d'algorithmes de type Marching-Cubes. Son objectif est d'extraire une isosurface topologiquement correcte d'une image volumique. Notre approche exploite la topologie discrète sous-jacente des voxels et, plus particulièrement, la connexité. Notre principale contribution réside dans l'apport d'une preuve formelle de la validité de la surface extraite, qui dépend des connexités choisies. L'isosurface obtenue est une surface orientée et fermée, sans singularité ni auto-intersection. De plus, nous démontrons qu'elle n'intersecte pas la carte d'adjacence (une extension volumique du graphe d'adjacence) du fond et des objets. Enfin, nous montrons que le graphe définissant l'isosurface est étroitement lié au graphe de surfel-adjacence de la surface discrète de la même image.
  • Keywords:

    Isosurface Extraction, Marching-Cubes, surface Topology, Digital Geometry.
  • Keywords (in french):

    Extraction d'Isosurfaces, Marching-Cubes, Topologie des surfaces, Géométrie Discrète.
  • Availability: Paper copy available.
  • Citation: To appear in DGCI'96 (6th Discrete Geometry for Computer Imagery).
  • Size: 2+28p
  • Format: Compressed PostScript
  • Get it

Construction des cercles planchers par automates cellulaires plan.

  • By: Laure Tougne
  • Number: RR1996-21
  • Date: August 1996
  • Abstract:

    We propose us to construct in real time particular discrete circles : the ``floor circles'', with the help of a two-dimensional cellular automaton. The definition of this circle is based on the following idea : in the first octant, whatever the chosen discretisation may be, a discrete circle is composed of vertical segments. We show that if we consider all the circles the radius of which is greater or equal to zero, the extremities of these segments belong to a beam of parabolas. So, for example, the ``floor circle'' is the circle which is based on the parabolas the equation of which are $y=\lfloor \sqrt{2kx+k^2} \rfloor$, one of the possible discretisations of the real parabolas $y=\sqrt{2kx+k^2}$. Thus, the construction of the ``floor circle'' implies the construction of the parabolas $y=\lfloor \sqrt{2kx+k^2} \rfloor$ with $k \geq 0$ (denoted by $H_k$ with $k \geq 0$), which can be done in real time with a cellular automaton.
  • Abstract (in french):

    Nous nous proposons de construire en temps réel des cercles discrets particuliers : les cercles planchers, à l'aide d'un automate cellulaire plan. La définition de ce cercle discret est basée sur l'idée suivante : dans le premier octant, quelle que soit la discrétisation choisie, un cercle discret est composé de segments verticaux. Et, on montre que si on considère tous les cercles de rayon supérieur ou égal à zéro, les extrémités de ces segments appartiennent à un faisceau de paraboles. Ainsi, par exemple, le ``cercle plancher'' est le cercle qui s'appuie sur les paraboles d'équation $y=\lfloor \sqrt{2kx+k^2} \rfloor$, une discrétisation possible des paraboles réelles $y=\sqrt{2kx+k^2}$. Construire le ``cercle plancher'' par automate cellulaire implique donc la construction des paraboles $y=\lfloor \sqrt{2kx+k^2} \rfloor$ pour $k \geq 0$ (notée $H_k$ avec $k \geq 0$), qui peut être effectuée en temps réel par un automate cellulaire.
  • Keywords:

    Cellular Automata, Discrete Circles, Construction of Figures.
  • Keywords (in french):

    Automates Cellulaires Plans, Cercles Discrets, Construction de Figures.
  • Availability: Paper copy available.
  • Size: 2+65p
  • Format: Compressed PostScript
  • Get it

Modelization and simulation of parallel relational query execution plans using DPL graphs and High-level Petri nets.

  • By: Lionel Brunie , Harald Kosch
  • Number: RR1996-22
  • Date: September 1996
  • Abstract:

    This report presents a novel representation model of parallel relational query execution plans, called DPL graphs. This model allows to deal with any kind of parallel architecture and any kind of parallel execution strategy. Based on an analysis of execution dependencies between operators, this model allows to precisely represent communications, run-time control mechanisms, scheduling constraints or specific processing strategies (e.g. bucket processing). This report especially focus on the modelization and the simulation of the data and control flows which are realized using high-level Petri nets.
  • Abstract (in french):

    Dans ce rapport nous introduisons un nouveau modèle de représentation d'un plan d'exécution parallèle d'une requête relationnelle, appele DPL graphs. Ce modèle nous permet de modéliser toutes sortes de stratégies d'exécution parallèles sur n'importe quelle architecture parallèle. Il se base sur une analyse complète des dépendences existantes entre des opérateurs relationels exécutés en parallèle et intégre en même temps les communications, le contrôle d'exécution, les contraintes d'ordonnancement et de traitements spécifiques (ex. traitement par bucket). Ce rapport se concentre sur la modélisation et la simulation du flux de contrôle et de données qui sont réalisées à l'aide de réseaux de Petri.
  • Keywords:

    Parallel Databases, Parallel Query Optimization, Parallel Query Execution Plan, Scheduling Graph, High-Level Petri Nets.
  • Keywords (in french):

    Bases de Données Parallèles, Optimisation de Requêtes Pour l'Exécution Parallèle, Plan d'Exécution Parallèle, Graph d`Ordonnancement, Réseau de Petri.
  • Availability: Electronic copy only.
  • Citation: Europar 96, LNCS Series 1123, Springer Verlag.
  • Size: 2+33p
  • Format: Compressed PostScript
  • Get it

$d$-Dimensional Range Search on Multicomputers.

  • By: Afonso Ferreira , Claire Kenyon , Andrew Rau-Chaplin , Stephane Ubeda
  • Number: RR1996-23
  • Date: August 1996
  • Abstract:

    Given a set $L$ of $n$ points in the $d$-dimensional Cartesian space $E^d$, and a query specifying a domain $q$ in $E^d$, the Range Search problem consists in identifying the subset $R(q)$ of the points of $L$ contained in $q$. The Range Tree data-structure represents a particularly good balance between storage space and search time. The structure requires $O(n\log^{d-1} n)$ space and construction time, but supports an $O(\log^dn)$ time search algorithm. In this paper, we describe a set of efficient scalable algorithms for the construction and manipulation of a distributed analog to the sequential range tree data structure. We then show how to perform $O(n)$ independent range searches on a distributed range tree, in parallel. These parallel construction and search algorithms are both optimal in the {\em Coarse Grained Multicomputer} model (also referred to as the weak-CREW BSP model), in the sense that their running times are the sequential time divided by the number of processors, plus a constant number of parallel communication rounds (i.e., h-relations in BSP context).
  • Abstract (in french):

    Prenons un ensemble de $n$ points dans un espace cartésien $E^d$, ainsi qu'une requête $q$ définissant un domaine de $E^d$. On appelle {\em Range Search} le problème consistant à identifier le sous-ensemble $r(q)$ de points de $L$ contenu dans $q$. Le {\em Range Tree} est une structure de données offrant un excellent compromis entre la taille mémoire nécessaire à son stockage et le temps de réponse au problème. Il nécessite $O(n \log^{d-1} n)$ emplacements mémoire et permet de traiter une requête en $O(\log^dn)$ unités de temps. Dans cet article, nous présentons des algorithmes efficaces et extensibles pour construire et manipuler une version distribuée du {\em Range Tree} comparable à la version séquentielle. Nous montrons comment répondre à $O(n)$ requêtes indépendantes en parallèle. Les algorithmes de construction du {\em Range Tree} distribué et de réponses aux requêtes sont optimaux dans le modèle de machine à gros grains (aussi appelé modèle weak CREW-BSP), optimal signifiant que le temps d'exécution en parallèle est égal au temps d'exécution en séquentiel divisé par le nombre de processeurs, auquel on doit ajouter le temps nécessaire à un nombre constant d'étapes de communication (ou de {\em h-relations} dans le contexte du modèle BSP).
  • Keywords:

    Multidimensional Search, Parallel Algorithm, Distributed Data Structures, Coarse Grained Multicomputers.
  • Keywords (in french):

    Recherche Multidimensionnelle, Algorithme Parallele, Structure de Donnees Distribuee, Machine Parallele a Gros Grain.
  • Availability: Paper copy available.
  • Citation: Not published yet.
  • Size: 2+18p
  • Format: Compressed PostScript
  • Get it

Optimal Subdivision and Complexity of Discrete Surfaces in the Dividing-Cubes algorithm.

  • By: Fatima Boumghar , Serge Miguet , Jean-Marc Nicod
  • Number: RR1996-24
  • Date: September 1996
  • Abstract:

    This report presents a particular implementation, and experiments on the Dividing-Cubes algorithm whose the aim is to extract and display an iso-surface from a three-dimensional (3D) medical image. The regular subdivision of the voxels allows the projection of a subdivided voxel, on the raster image, to be at most equal to the size of a pixel. We optimize the subdivision parameters to get a compromise between a good representation of the image and a minimization of the memory space. Then, we exhibit a complexity model for discrete surfaces obtained by regular subdivisions of cells. We use it for estimating the number of points that will be generated by the Dividing-Cubes algorithm to represent the surface of 3D medical objects. Under the assumption that surfaces have uniform orientations in the space, and can be locally be assimilated to planes, we show that the average number of points is a quadratic function of the subdivision factors. We give analytical expressions of the coefficients in the quadratic form. Some results obtained on a medical image and on an artificial one illustrate the validity of our formulations.
  • Abstract (in french):

    Nous présentons dans ce rapport une implémentation particulière de l'algorithme des Dividing-Cubes dont le but est d'extraire et de visualiser une iso-surface quelconque d'une image médicale 3D. La subdivision régulière des voxels permet à la projection sur l'image d'un voxel subdivisé d'être au plus égale à la taille d'un pixel. Nous proposons ici une optimisation des paramètres de subdivision permettant d'établir un compromis entre une bonne représentation de l'image et une minimisation de l'espace mémoire utilisé. Nous exposons ensuite un modèle de complexité pour des surfaces discrètes obtenues par subdivisions régulières de cellules. Nous utiliserons un tel modèle pour estimer le nombre de points générés par l'algorithme des Dividing-Cubes pour la représentation de surfaces des images médicales 3D. Sous l'hypothèse que les surfaces ont des orientations uniformes dans l'espace et qu'elles peuvent donc être assimilées à des plans, nous montrons que le nombre moyen de points est une fonction quadratique des paramètres de subdivision.
  • Keywords:

    Computer Graphics, Medical Imaging, Surface Rendering, Discrete Geometry, Discrete Surfaces.
  • Keywords (in french):

    Synthèse d'Images, Imagerie Médicale, Visualisation, Géométrie Discrète, Surfaces Discrètes.
  • Availability: Electronic copy only.
  • Citation: Published in DGCI'96.
  • Size: 2+18p
  • Format: Compressed PostScript
  • Get it

A decision procedure for Direct Predicate Calculus. Study and implementation in the system Coq.

  • By: Jean-Christophe Filliatre
  • Number: RR1996-25
  • Date: February 1995
  • Abstract:

    The paper of J. Ketonen and R. Weyhrauch [6] defines a decidable fragment of first-order predicate logic - Direct Predicate Calculus - as the subset which is provable in Gentzen sequent calculus without the contraction rule, and gives an effective decision procedure for it. This report is a detailed study of this procedure. We extend the decidability to non-prenex formulas. We prove that the intuitionnistic fragment is still decidable, with a refinement of the same procedure. An intuitionnistic version has been implemented in the system Coq [2] using a translation into natural deduction.
  • Abstract (in french):

    L'article de J. Ketonen et R. Weyhrauch [6] définit un fragment décidable du calcul des prédicats du premier ordre - le Calcul des Prédicats Direct - comme le sous-ensemble prouvable dans le calcul des séquents de Gentzen sans utiliser la règle de contraction, et en donne une procédure de décision effective. Ce rapport présente une étude détaillée de cette procédure. Nous étendons la décidabilité au cas des formules non nécessairement prénexes. Nous montrons que le fragment intuitionniste est également décidable, par un raffinement de la même procédure. Une version intuitionniste de cette algorithme a été implémentée dans le système Coq [2].
  • Keywords:

    Predicate Calculus, Sequent Calculus, Decision Procedures, Proof Search, Intuitionnistic Logic.
  • Keywords (in french):

    Calcul des Prédicats, Calcul des Séquents, Procédures de Décision, Recherche de Preuves, Logique Intuitionniste.
  • Availability: Paper copy available.
  • Citation: Not published yet.
  • Size: 2+32p
  • Format: Compressed PostScript
  • Get it

Proof reconstruction (preliminary version).

  • By: Judicael Courant
  • Number: RR1996-26
  • Date: September 1996
  • Abstract:

    In the field of formal methods, rewriting techniques and provers by consistency in particular appear as powerful tools for automating deduction. However, these provers suffer limitations as they only give a (non-readable) trace of their progress and a yes/no answer where the user would expect a detailed explicit proof. Therefore, we propose a general mechanism to build an explicit proof from the running of a generic class of inductionless induction provers. We then show how it applies to Bouhoula's SPIKE prover, and give examples of proofs built by this method.
  • Abstract (in french):

    Dans le domaine des méthodes formelles, les techniques de réécriture et les prouveurs par récurrence implicite sont des outils puissants pour automatiser le processus de preuve. Cependant, ces prouveurs donnent une trace du déroulement de la preuve peu compréhensible, alors que l'utilisateur lambda aimerait avoir une preuve explicite détaillée. Nous proposons un mécanisme général permettant de construire une preuve explicite à partir de la trace du déroulement d'une preuve pour une classe générique de démonstrateurs par récurrence implicite. Nous montrons comment ce procédé s'applique au prouveur SPIKE de Bouhoula, et donnons des exemples de preuves construites par cette méthode.
  • Keywords:

    Rewriting, Theorem Prover, Natural Deduction, Inductionless Induction, SPIKE, Coq.
  • Keywords (in french):

    Réécriture, Démonstrateur, Déduction Naturelle, Récurrence Implicite, SPIKE, Coq.
  • Availability: Paper copy available.
  • Citation: Not published yet.
  • Size: 2+14p
  • Format: Compressed PostScript
  • Get it

The Data-Parallel Programming Model: a Semantic Perspective (Final Version).

  • By: Luc Bouge
  • Number: RR1996-27
  • Date: September 1996
  • Abstract:

    We provide a short introduction to the data-parallel programming model. We argue that parallel computing often makes little distinction between the execution model and the programming model. This results in poor programming and low portability. Using the "GOTO considered harmful" analogy, we show that data parallelism can be seen as a way out of this difficulty. We show that important aspects of the data-parallel model were already present in earlier approaches to parallel programming, and demonstrate that the data-parallel programming model can be characterized by a small number of concepts with simple semantics.
  • Abstract (in french):

    Nous présentons une courte introduction au modèle de programmation à parallélisme de données. Nous montrons que la distinction entre modèle d'exécution et modèle de programmation a souvent été mal comprise dans le calcul parallèle. Ceci conduit à une programmation de faible qualité et peu portable. À partir de l'analogie "Les GOTO sont-ils nuisibles?", nous montrons que le parallélisme de données peut être une solution à cette difficulté. Il apparaît que des aspects importants de ce modèle étaient déjà présents dans la programmation parallèle classique. Nous montrons que le modèle de programmation à parallélisme de données peut être caractérisé par un petit nombre de concepts sémantiques simples.
  • Keywords:

    Concurrent Programming, Specifying and Verifying and Reasoning about Programs, Semantics of Programming Languages, Data Parallelism, Task Parallelism.
  • Keywords (in french):

    Programmation parallèle, Spécification et Validation de Programmes, Sémantique des Langages de Programmation, Parallélisme de Données, Parallélisme de Tâches.
  • Availability: Electronic copy only.
  • Citation: An early version of this paper has been published in French in "Technique et science informatiques (TSI)", Special issue on Data-Parallel Languages, Vol. 12, No. 5, 1993, p. 541-562. This paper has been published in "The Data Parallel Programming Model", G.-R. Perrin, Alain Darte (Eds.), Lecture Notes in Computer Science Tutorial Series, 1996, p. 4--26.
  • Size: 2+19p
  • Format: Compressed PostScript
  • Get it

HPFIT: A Set of Integrated Tools for the Parallelization of Applications Using High Performance Fortran.

  • By: Alain Darte , Frederic Desprez , Jean-Christophe Mignot , Thomas Brandes , Serge Chaumette , Marie-Christine Counilh , Jean Roman
  • Number: RR1996-28
  • Date: September 1996
  • Abstract:

    In this report, we present the HPFIT project whose aim is to provide a set of interactive tools integrated in a single environment to help users to parallelize scientific applications to be run on distributed memory parallel computers. HPFIT is built around a restructuring tool called TransTOOL which includes an editor, a parser, a dependence analysis tool and an optimization kernel. Moreover, we provide the users with a clean interface, so that developers of tools around High Performance Fortran can easily integrate their software within our tool.
  • Abstract (in french):

    Dans ce rapport, nous présentons le projet HPFIT dont le but est de fournir un ensemble d'outils interactifs intégrés dans un seul environnement pour aider les utilisateurs à paralléliser des applications scientifiques sur des machines parallèles à mémoire distribuée. HPFIT est bâti autour d'un outil de restructuration appelé TransTOOL qui inclut un editeur, un analyseur syntaxique, un outil d'analyse de dépendances et un noyau d'optimisation. De plus, nous fournissons une interface propre pour aider les développeurs d'outils autour d'High Performance Fortran à intégrer leurs logiciels à l'intérieur de notre outil.
  • Keywords:

    Semi-Automatic Parallelization, High Performance Fortran, Development Tools.
  • Keywords (in french):

    Parallélisation Semi-Automatique, High Performance Fortran, Outils de Développement.
  • Availability: Electronic copy only.
  • Citation: Third Workshop on Environments and Tools for Parallel and Scientific Computing, Chateau de Faverge, France, August 1996.
  • Size: 2+32p
  • Format: Compressed PostScript
  • Get it

Formal validation of data-parallel programs: a two-component assertional proof system for a simple language.

  • By: Luc Bouge , David Cachera , Yann Le Guyadec , Gil Utard , Bernard Virot
  • Number: RR1996-29
  • Date: October 1996
  • Abstract:

    We present a proof system for a simple data-parallel kernel language called L. This proof system is based on a two-component assertion language. We define a weakest preconditions calculus and analyse its definability properties. This calculus is used to prove the completeness of the proof system. We also present a two-phase proof methodology, yielding proofs similar to those for scalar languages. We finally discuss other approaches.
  • Abstract (in french):

    Nous présentons un système de preuve pour un langage data-parallèle simple, le langage L. Ce système de preuve est fondé sur un langage d'assertions à deux composantes. Nous définissons un calcul des plus faibles préconditions et analysons ses propriétés de définissabilité. Nous utilisons ce calcul pour prouver la complétude du système de preuve. Nous présentons également une méthodologie de preuve en deux phases. Les preuves obtenues sont semblables à celles données pour les langages scalaires. Nous discutons finalement d'autres approches.
  • Keywords:

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

    Programmation Parallèle, Spécification et Validation de Programmes, Sémantique des Langages de Programmation, Langages Data-Parallèles, Système de Preuve, Logique de Hoare, Plus Faibles Préconditions.
  • Availability: Electronic copy only.
  • Citation: To appear in Theoretical Computer Science.
  • Size: 2+33p
  • Format: Compressed PostScript
  • Get it

A module calculus enjoying the subject-reduction property. (Preliminary Version)

  • By: Judicael Courant
  • Number: RR1996-30
  • Date: October 1996
  • Abstract:

    The module system of SML is a small typed language of its own. As is, one would expect a proof of its soundness following from a proof of subject reduction, but none exists. As a consequence the theoretical study of reductions is difficult, and for instance, the question of normalization of the module calculus can not even be asked. In this paper, we build a variant of the SML module system --- inspired from recent works --- which enjoys the subject reduction property. This was the initial motivation. Besides our system enjoys other type-theoretic properties: the obtained calculus is strongly normalizing, there are no syntactic restrictions on module paths, it enjoys a purely applicative semantic, every module has a principal type, and type inference is decidable. Moreover we conjecture that type abstraction --- achieved through an explicit declaration of the signature of a module at its definition --- is preserved.
  • Abstract (in french):

    Le système de modules de SML est un vrai petit langage typé. Alors qu'on pourrait attendre une preuve de la consistance des systèmes de modules découlant de l'étude des réductions de modules, en particulier d'une preuve d'autoréduction, aucune preuve de ce genre ne semble exister. Or cela est un préliminaire nécessaire à toute étude des réductions, et en particulier à la question de la normalisation du système de modules. Dans ce rapport, nous construisons une variante du système de modules de SML, inspirée de travaux récents, qui possède la propriété d'autoréduction. Cette motivation initiale conduit par ailleurs à un système de modules possédant des propriétés théoriques remarquables: le calcul de modules est fortement normalisant, aucune restriction syntaxique sur les chemins d'accès n'est nécessaire, la sémantique de notre système est purement applicative, tout module possède un type principal, et l'inférence de type est décidable. Nous conjecturons par ailleurs que l'abstraction de type --- obtenue par un mécanisme de déclaration explicite de la signature d'un module lors de sa définition --- est préservée.
  • Keywords:

    Module Systems, Subject-Reduction, Normalization, Type Inference, SML, Lambda-Calculus.
  • Keywords (in french):

    Systèmes de Modules, Autoréduction, Normalisation, Inférence de Type, SML, Lambda-Calcul.
  • Availability: Electronic copy only.
  • Citation: Not published yet.
  • Size: 2+14p
  • Format: Compressed PostScript
  • Get it

A module calculus for Pure Type Systems. (Preliminary Version)

  • By: Judicael Courant
  • Number: RR1996-31
  • Date: October 1996
  • Abstract:

    Several proof-assistants rely on the very formal basis of Pure Type Systems. However, some practical issues raised by the development of large proofs lead to add other features to actual implementations for handling namespace management, for developing reusable proof libraries and for separate verification of distincts parts of large proofs. Unfortunately, few theoretical basis are given for these features. In this paper we propose an extension of Pure Type Systems with a module calculus adapted from SML-like module systems for programming languages. Our module calculus gives a theoretical framework addressing the need for these features. We show that our module extension is conservative, and that type inference in the module extension of a given PTS is decidable under some hypotheses over the considered PTS.
  • Abstract (in french):

    Plusieurs assistants de preuves sont fondés sur les Systèmes de Types Purs (PTS). Cependant, des considérations pratiques provenant du développement de grandes preuves conduisent à ajouter aux implémentations des mécanismes permettant une gestion rationnelle des noms, le développement de bibliothèques de preuves réutilisables, et la vérification séparée des différentes parties d'un gros développement. Alors que la correction des PTS utilisés est théoriquement bien fondé, ces mécanismes sont en revanche peu étudiés, alors qu'ils peuvent mettre en péril la correction de l'ensemble de l'outil de démonstration. Pour répondre à ce problème, nous proposons dans ce rapport une extension des PTS par un système de modules similaire à celui de SML pour le langage de programmation ML. Notre système de modules donne un cadre théorique rigoureux pour l'étude des mécanismes que nous avons cités. Nous montrons que l'extension proposée est conservative, et que l'inférence de type est décidable moyennant quelques hypothèses raisonnables sur le PTS considéré.
  • Keywords:

    Module Systems, PTS, Higher-Order Type Systems, Subject-Reduction, Normalization, Type Inference.
  • Keywords (in french):

    Systèmes de Modules, PTS, Systèmes de Types d'Ordre Supérieur, Autoréduction, Normalisation, Inférence de Type.
  • Availability: Electronic copy only.
  • Citation: Not published yet.
  • Size: 2+18p
  • Format: Compressed PostScript
  • Get it

A logical framework for proving Alpha programs.

  • By: Luc Bouge , David Cachera
  • Number: RR1996-32
  • Date: October 1996
  • Abstract:

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

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

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

    Programmation Parallèle, Equations Récurrentes, Spécification et Validation de Programmes, Sémantique des Langages de Programmation, Langages Data-Parallèles, Méthode de Preuve, Invariants.
  • Availability: Paper copy available.
  • Citation: Not published yet.
  • Size: 2+22p
  • Comment: A revised version is available as Research Report RR1997-16,
  • Format: Compressed PostScript
  • Get it

Load balancing HPF programs by migrating virtual processors.

  • By: Christian Perez
  • Number: RR1996-33
  • Date: October 1996
  • Abstract:

    This paper explores the integration of load balancing features in the data parallel language HPF targeting semi-regular applications. We show that the HPF virtual processors are good candidates to be the unit of migration. Then, we compare 3 possible implementations and show that threads provide a good tradeoff between efficiency and ease of implementation. We finally describe a preliminary implementation. The experimental results, obtained with the Gaussian elimination with partial pivoting are promising.
  • Abstract (in french):

    Ce papier étudie l'intégration dans le langage HPF d'un équilibrage de charge visant les applications semi-régulières. Nous montrons que les processeurs virtuels du langage sont de bons candidats pour être l'unité de migration. Nous comparons alors 3 implémentations possibles et il apparaît que les processus légers représentent un bon compromis entre l'efficacité et la facilité d'implémentation. Nous décrivons ensuite notre implémentation préliminaire. Les résultats expérimentaux obtenus avec l'élimination de Gauss avec pivot partiel sont prometteurs.
  • Keywords:

    Data Parallel Languages, HPF, Compilation, Multi-Thread Environment, Thread Migration.
  • Keywords (in french):

    Langages à Parallélisme de Données, HPF, Compilation, Environnement d'Exécution Multi-Thread, Migration de Processus Légers.
  • Availability: Paper copy available.
  • Citation: Not published yet.
  • Size: 2+21p
  • Format: Compressed PostScript
  • Get it

Combining retiming and scheduling techniques for loop parallelization and loop tiling.

  • By: Alain Darte , Georges-Andre Silber , Frederic Vivien
  • Number: RR1996-34
  • Date: November 1996
  • Abstract:

    Tiling is a technique used for exploiting medium-grain parallelism in nested loops. It relies on a first step that detects sets of permutable nested loops. All algorithms developed so far consider the statements of the loop body as a single block, in other words, they are not able to take advantage of the structure of dependences between different statements. In this report, we overcome this limitation by showing how the structure of the reduced dependence graph can be taken into account for detecting more permutable loops. Our method combines graph retiming techniques and graph scheduling techniques. It can be viewed as an extension of Wolf and Lam's algorithm to the case of loops with multiple statements. Loop independent dependences play a particular role in our study, and we show how the way we handle them can be useful for fine-grain loop parallelization as well.
  • Abstract (in french):

    ``Loop tiling'' est une technique utilisée pour exploiter du parallélisme à grain moyen dans les boucles imbriquées. Elle repose sur une première étape de détection de boucles permutables. Tous les algorithmes développés jusqu'à maintenant considéraient les instructions du corps du nid de boucles comme un bloc indissociable. En d'autres termes, ils ne pouvaient pas tirer profit de la structure des dépendances entre différentes instructions. Dans ce rapport, nous surmontons cette limitation en montrant comment la structure du graphe de dépendance réduit peut être prise en compte pour détecter plus de boucles permutables. Notre méthode combine des techniques de synchronisation et d'ordonnancement de graphes. Elle peut être vue comme une extension de l'algorithme de Wolf et Lam au cas de boucles comportant plusieurs instructions. Les dépendances qui ne sont pas portées par une boucle (loop independent dependences) jouent un rôle particulier dans notre étude et nous montrons comment la façon particulière dont nous les traitons peut être utile également pour la parallélisation à grain fin.
  • Keywords:

    Automatic parallelization, nested loops, permutable loops, tiling, medium grain.
  • Keywords (in french):

    Parallélisation automatique, nids de boucles, boucles permutables, tiling, grain moyen.
  • Availability: Electronic copy only.
  • Citation: Not published yet.
  • Size: 2+11p
  • Format: Compressed PostScript
  • Get it

Simulation d'écoulement tridimensionnel autour d'une aile de parapente.

  • By: L. Giraudeau , Georges Perrot , S. Petit, Bernard Tourancheau
  • Number: RR1996-35
  • Date: November 1996
  • Abstract:

    This report presents our work for the design, model and implementation of a 3D air flow simulation software using the singularity method. The aim was the computation of the performance parameters of a wing at different speeds (between 10-60 km/h) with perfect uncompressible fluid and permanent flow hypothesis in order to help out with the design of paragliders. Sections 1 and 2 presents the model, design and the implementation and the results we obtained are in section 3.
  • Abstract (in french):

    Ce rapport présente le modèle, la conception et l'implémentation d'un code tridimensionnel de simulation d'écoulement de fluide utilisant la méthode des singularités. Notre but était de calculer les paramètres d'une aile à différentes vitesses (comprises entre 10 et 60 km/h) avec des hypothèses de fluide parfait incompressible en écoulement permanent pour pouvoir améliorer la conception de parapentes. Les chapitres 1 et 2 présentent le modèle, la conception et l'implémentation. Le chapitre 3 apporte une validation du code et les résultats obtenus.
  • Keywords:

    Singularity Method, Gliding, Aerodynamics, Perfect Uncompressible Fluid, Permanent Flow, Paraglider.
  • Keywords (in french):

    Méthode des Singularités 3D, Vol Libre, Aérodynamique, Fluide Parfait Incompressible, Ecoulement Permanent, Parapente.
  • Availability: Electronic copy only.
  • Citation: Not published yet.
  • Size: 2+29p
  • Format: Compressed PostScript
  • Get it

Broadcasting and Multicasting by Shortest Path in Cut-through Routed Networks.

  • By: Johanne Cohen , Pierre Fraigniaud , Jean-Claude Konig , Andre Raspaud
  • Number: RR1996-36
  • Date: November 1996
  • Abstract:

    This paper addresses the one-to-all broadcasting problem, and the one-to-many broadcasting problem. Broadcasting is the information dissemination problem which consists, for a node of a network, to send a same piece of information to all the other nodes. Multicasting is a partial broadcasting in the sense that only a subset of nodes forms the destination set. Both problems have many applications in parallel and distributed computing. In this paper, we study these problems under both line model,and cut-through model. We present a new time optimal broadcasting and multicasting algorithm in both line model and cut-through model. We show how the behavior of this algorithm can again be improved in case of tree networks. We will also show that most of the optimization problems relative to the maximization of the efficiency of broadcasting or multicasting algorithms in term of switching times or vertex load are NP-complete.
  • Abstract (in french):

    Ce papier traite des problèmes de diffusion et de multidiffusion. La diffusion à partir d'un processeur u est l'opération qui consiste à envoyer un message à tous les processeurs à partir de l'initiateur unique u. Une multidiffusion est une diffusion partielle : l'ensemble de destinations est une partie des noeuds du réseau. Ces types de problèmes sont liés aux communications globales structurées telles que celles définies dans la bibliothèque MPI. Dans cet article, nous considérons deux modes de communication, le mode communications arêtes-disjointes et le mode commutation de circuits. Nous nous concentrons uniquement sur le nombre d'étapes. Nous montrons principalement qu'il est non seulement possible de diffuser optimalement dans le mode commutation de circuits, mais aussi que toutes les communications réalisées à chaque étape de la diffusion peuvent s'effectuer sur des plus courts chemins. Ce papier traite aussi de nombreux autres paramètres comme la charge des sommets, etc. Nous montrons que minimiser ces paramètres sont des problèmes NP-complets.
  • Keywords:

    Broadcasting, Multicasting, Line Model, Circuit-Switched, Cut-Through Model.
  • Keywords (in french):

    Diffusion, Multidiffusion, Mode Communication Arêtes-Disjointes, Mode Commutation de Circuit.
  • Availability: Electronic copy only.
  • Citation: Submitted.
  • Size: 2+22p
  • Format: Compressed PostScript
  • Get it

Multilayer neural networks: one or two hidden layers~?

  • By: Graham Brightwell , Claire Kenyon , Helene Paugam-Moisy
  • Number: RR1996-37
  • Date: November 1996
  • Abstract:

    We study the number of hidden layers required by a multilayer neural network with threshold units to compute a function f from R^d to {0,1}. In spite of similarity with the characterization of linearly separable Boolean functions, this problem presents a higher level of complexity. Gibson characterized the functions of R^2 which are computable with just one hidden layer, under the assumption that there is no ``multiple intersection point'' and that f is only defined on a compact set. We consider the restriction of f to the neighbourhood of a multiple intersection point or of infinity, and give necessary and sufficient conditions for it to be locally computable with one hidden layer. We show that adding these conditions to Gibson's assumptions is not sufficient to ensure global computability with one hidden layer by exhibiting a new non-local configuration, the ``critical cycle'', which implies that f is not computable with one hidden layer. We conjecture that the problem can be completely solved in R^2. Several results can be extended to R^d, for all d>2, but the complete problem in higher dimensions is more challenging.
  • Abstract (in french):

    Nous étudions le nombre de couches cachées nécessaires à un réseau multicouche d'unités à seuil pour calculer exactement une fonction de R^d dans {0,1}. Bien que lié à la caractérisation des fonctions booléennes linéairement séparables, ce problème présente un niveau de complexité supplémentaire. Gibson caractérise les fonctions de R^2 qui sont réalisables avec une seule couche cachée, sous les hypothèses qu'il n'y a pas de points d'intersection multiple entre les hyperplans définissant f et que f est définie sur un ensemble compact. Sur la restriction de f au voisinage d'un point multiple ou de l'infini, nous caractérisons le fait que f soit localement réalisable avec une seule couche cachée. La réunion de ces conditions et des hypothèses de Gibson n'est pas suffisante pour assurer que f soit globalement réalisable avec une seule couche cachée. En effet, nous définissons une nouvelle configuration non locale, le ``cycle critique", pour laquelle f n'est pas réalisable avec une seule couche cachée. Nous conjecturons que le problème pourra maintenant être complètement résolu dans R^2. Plusieurs résultats s'étendent à R^d, pour tout d>2, mais le problème complet, en dimension supérieure à deux, demeure plus difficile.
  • Keywords:

    Multilayer Neural Networks, Architecture, Classification, Complexity.
  • Keywords (in french):

    Réseaux Neuronaux Multicouches, Architecture, Classification, Complexité.
  • Availability: Electronic copy only.
  • Citation: Extended version of a paper to be published in April or May 1997, in Proc. of NIPS'96, Denver, Colorado (US), December 1996.
  • Size: 2+28p
  • Format: Compressed PostScript
  • Get it