On the relations between dynamical systems and boolean circuits.

  • By: Pascal Koiran
  • Number: RR1993-01
  • Date: December 21, 1992
  • Abstract:

    We study the computational capabilities of dynamical systems defined by iterated functions on [0,1]^n. The computations are performed with infinite precision on arbitrary real numbers, like in the model of analog computation recently proposed by Hava Siegelmann and Eduardo Sontag. We concentrate mainly on the low-dimensional case and on the relations with the Blum-Shub-Smale model of computation over the real numbers.
  • Keywords:

    Analog Computation, Non-Uniform Complexity, Dynamical Systems.
  • Availability: Electronic copy only.
  • Size: 2+13p
  • Format: Compressed PostScript
  • Get it

The Surjectivity Problem for 2D Cellular Automata.

  • By: Bruno Durand
  • Number: RR1993-02
  • Date: October 10, 1993
  • Abstract:

    The surjectivity problem for 2D Cellular Automata was proved undecidable in 1989 by Jarkko Kari. The proof consists in a reduction of a problem concerning finite tilings to this problem. This reduction uses a special and very sophisticated tile set. In this article, we present a much more simple tile set which can play the same role.
  • Keywords:

    Cellular Automata, Surjectivity, Decidability.
  • Availability: Paper copy available.
  • Citation: Published in FCT'93, Lecture Notes in Computer Science, Springer Verlag, August 1993. To appear in Journal of Computer and System Sciences.
  • Size: 2+10p
  • Format: Compressed PostScript
  • Get it

Mapping Uniform Loop Nests onto Distributed Memory Architectures.

  • By: Alain Darte , Yves Robert
  • Number: RR1993-03
  • Date: January 7, 1993
  • Abstract:

    This paper deals with scheduling, mapping and partitioning techniques for uniform loop nests. Target machines are SPMD distributed memory parallel computers. We use affine-by-statement scheduling and affine-by-variable mapping to synthesize a virtual grid architecture from the original loop nest. The virtual grid architecture is then partitioned into a physical processor grid. The key to the mapping strategy is the communication graph, which enables us to derive optimal mappings, i.e. where the number of communications is proved to be minimal. The partitioning technique extends the methods developed for systolic array design methodologies to loop nests with several statements.
  • Keywords:

    Loop Nest, Uniform Dependence Algorithm, Convex Domain, Communication Graph, Affine Schedule, Affine Mapping, Partitioning, SPMD Code.
  • Availability: Electronic copy only.
  • Citation: Published in Parallel Computing 20, pp. 679-710, 1994.
  • Size: 2+37p
  • Format: Compressed PostScript
  • Get it

The cellular developmental of neural networks: the interaction of learning and evolution.

  • By: Frederic Gruau , Darrell Whitley
  • Number: RR1993-04
  • Date: January 15, 1993
  • Abstract:

    A grammar tree is used to encode a cellular developmental process that can develop whole families of Boolean neural networks for computing parity and symmetry. The development process resembles biological cell division. A genetic algorithm is used to find a grammar tree that yields both architecture and weights specifying a particular neural network for solving specific Boolean functions. The current study particularly focuses on the addition of learning to the development process and the evolution of grammar trees. Three ways of adding learning to development process are explored. Two of these exploit the Baldwin effect by changing the fitness landscape without using Lamarkian learning. The third strategy is Lamarkian in nature. Results for these three modes of combining learning with genetic search are compared against genetic search without learning. Our results suggest that merely using learning to change the fitness landscape may be as effective as Lamarkian strategies at improving search.
  • Keywords:

    Genetic Algorithm, Neural Networks, Baldwin Effect, Lamarkian.to Evolutionnary Computation.
  • Availability: Electronic copy only.
  • Citation: Published in Evolutionnary computation, VIN3, Mit Press, Kenneth Dejong ed, 1993.
  • Size: 2+25p
  • Format: Compressed PostScript
  • Get it

Inversion of 2D cellular automata: some complexity results.

  • By: Bruno Durand
  • Number: RR1993-05
  • Date: January 20, 1993
  • Abstract:

    In this paper, we prove the co-NP-completeness of the following decision problem: "given a 2-dimensional cellular automaton A, is A injective when restricted to finite configurations not greater than its length?" In order to prove this result, we introduce two decision problems concerning respectively Turing Machines and tilings that we prove NP-complete. We then present a transformation of problems concerning tilings into problems concerning cellular automata.
  • Keywords:

    Cellular Automata, Inversion, Reversibility, Complexity.
  • Availability: Paper copy available.
  • Citation: Published in MFCS'93, Lecture note in Computer Science, Springer Verlag, September 1993. To appear in Theoretical Computer Science.
  • Size: 2+19p
  • Format: Compressed PostScript
  • Get it

Rounding of Floating Point Intervals.

  • By: Marc Daumas , David W. Matula
  • Number: RR1993-06
  • Date: March 1993
  • Abstract:

    Infinitely precise arithmetic is not always attainable with reasonable resource. Many function return explicit or implicit interval outputs.Yet, the IEEE standard does not allow efficient use of this information. We present how the IEEE rounding mechanisms can be extended to accept interval rounding which is shown to be a first natural step toward non infinitely precise rounding. Along with the proposal of this faithful rounding for non-infinitely precise operation, we present the intrinsic properties of this new rounding mechanism.
  • Keywords:

    Computer Arithmetic, Floating Point, Interval, Rounding.
  • Availability: Electronic copy only.
  • Citation: Published in Proceedings IMACS/GAMM International Symposium SCAN 93, Vienna, Austria, 1993. Published in Interval Computations, no. 4, pp. 28-45, 1994.
  • Size: 2+12p
  • Format: Compressed PostScript
  • Get it

One-way Cellular Automata on Cayley Graphs.

  • By: Zsuzsanna Roka
  • Number: RR1993-07
  • Date: March 18, 1993
  • Abstract:

    The notion of one-dimensional one-way cellular automata has been introduced to model cellular automata with only a one-way communication between two neighbor cells. In this paper, we generalize this notion to cellular automata working on different communication graphs. We present some necessary and/or sufficient conditions for a cellular automaton to be simulated by a one-way cellular automaton having the same underlying graph, and we give some bounds on the simulation-time of this mimic.
  • Keywords:

    Cellular Automata, One-way Cellular Automata, Cayley Graphs.
  • Availability: Paper copy available.
  • Citation: Published in Theoretical Computer Science, 132, pp 259-290, 1994, (the preliminary version).
  • Size: 2+47p
  • Format: Compressed PostScript
  • Get it

Axiomatic Semantics of Data-Parallel Languages; Automatization of Programs Verification.

  • By: Laurent Mounier , Gil Utard
  • Number: RR1993-08
  • Abstract:

    We give a Hoare-like proof system for the data-parallel language L, and we present an automatic tool to aid program correctness proof. After recalling L's operational semantics, we define an axiomatic semantics. We illustrate proof of L programs with two examples. Then we extend our semantics to weakest precondition, and we deduce techniques for mechanizing program verification from Gordon's verification condition method. We prove its correctness, and we present an implementation of this method in the CENTAUR system.
  • Keywords:

    Data-Parallel Languages, Axiomatic Semantics, Weakest Precondition, Program Verification, Program Verification Tools, CENTAUR.
  • Availability: Paper copy available.
  • Size: 2+48p
  • Format: Compressed PostScript
  • Get it

Ultra-fast parallel contour tracking, with applications to thinning.

  • By: Afonso Ferreira , Stephane Ubeda
  • Number: RR1993-09
  • Date: May 10, 1993
  • Abstract:

    This paper proposes a parallel algorithm for contour tracking of binary pictures. Given an object contour composed by O(N) pixels, our algorithm computes in constant time the next layer of the contour of that object, using the weakest parallel model, i.e., an Exclusive Read Exclusive Write (EREW) Parallel Random Acces Machine (PRAM). As an application of the technique we show a work-optimal parallel thinning algorithm for binary pictures, based on Pavlidis' characterisation of a skeleton. Our algorithm improves on previous solutions by producing a list of coordinates corresponding to the skeleton contour in O(N) time with O(N) processors in an EREW PRAM, where N is the width of the picture.
  • Keywords:

    Pattern recognition, Skeleton, Parallel complexity, PRAM.
  • Availability: Paper copy available.
  • Citation: Published in PR 27, vol 7, 1994.
  • Size: 2+15p
  • Format: Compressed PostScript
  • Get it

Dataflow dot product on networks of heterogeneous digit-serial arithmetic units.

  • By: Jean Duprat , Mario Fiallos-Aguilar
  • Number: RR1993-10
  • Date: March 30, 1992
  • Abstract:

    In this paper we deal with a new high precision computation of the dot product. The key idea is to use hundreds of digit-serial arithmetic units that allow a massive digit-level pipelining. Parallel discrete-event simulations performed on a memory-distributed massively parallel computer show that with a limited number of arithmetic units, the computation of dot product when performed using a ``classical'' algorithmic technique (i.e. serial cumulative multiplications) is almost as fast as the case where an ``optimal'' divide-and-conquer algorithmic technique is used. Interconnection networks for both algorithmic techniques are considered.
  • Keywords:

    Dataflow, Dot Product, Massive Pipelining, Digit On-Line Computation.
  • Availability: Paper copy available.
  • Size: 2+17p
  • Format: Compressed PostScript
  • Get it

On the tiling of torus Taxb with hm and vn.

  • By: Eric Remila
  • Number: RR1993-11
  • Abstract:

    We prove that the study of the tileability of torus T a x b (obtained by identifying opposite sides of a rectangle a x b) with tiles hm (horizontal rectangle with length m and width 1) and vn (vertical rectangle with length n and width 1) can be limited to the case when (a, m), (b, n) and (m, n) are pairs of relatively prime integers. With this condition, if integers a and b are both large enough, the totus T a x b can be tiled with tiles hm and vn. That gives a linear algorithm of tiling.
  • Keywords:

    Tiling, Torus.
  • Availability: Paper copy available.
  • Citation: Submitted to Theoretical Computer Science.
  • Size: 2+14p
  • Format: Compressed PostScript
  • Get it

CC+: an extenstion of the Calculus of Constructions with fixpoints.

  • By: Philippe Audebaud
  • Number: RR1993-12
  • Date: July 19, 1993
  • Abstract:

    We follow an original idea by Constable and Smith, providing a way to reason about non terminating computatinos in a typed framework. A previous study has been developped by Smith within Nuprl. Its adaptation to CC (the Calculus of Constructions) led to a conservative extension, where strong normalisation for beta reductions is preserved. We recover alternative codings already presented by Krivine and Parigot within AF2 system. Thus the computational behaviour for terms representing the integers is improved. Moreover, as expected, all partial recursive functions are definable. All these results easily extend to all usual data structures.
  • Keywords:

    Calculus of Constructions, Recursivity, Datatypes.
  • Availability: Paper copy available.
  • Citation: Submitted to Proceedings BRA Types, Bastad 1992.
  • Size: 2+14p
  • Format: Compressed PostScript
  • Get it

Optimal domino-tilability of convex polyominoes.

  • By: Thomas Chaboud
  • Number: RR1993-13
  • Date: May 12, 1993
  • Abstract:

    Not available by FTP.
  • Availability: Paper copy available. Not available by FTP.

Scheduling a scattering-gathering sequence on hypercubes.

  • By: Henri-Pierre Charles , Pierre Fraigniaud
  • Number: RR1993-14
  • Date: May 18, 1993
  • Abstract:

    The scattering problem refers to the gossiping and the broadcasting problems. It consists in distributing a set of data from a single source such that each component is destinated to a distinct address. The gathering operation is the reverse of the scattering operation. This paper studies the problem of pipelining a scattering-gathering sequence in order to overlap these operations. We first give a general solution for distributed memory parallel computers, and next we particularly study this problem on hypercubes.
  • Keywords:

    Broadcasting, Scattering, Gathering, Distributed Memory Computer.
  • Availability: Electronic copy only.
  • Citation: Published in Parallel Processing Letters Nr. 92-133.
  • Size: 2+11p
  • Format: Compressed PostScript
  • Get it

Construction of DO Loops from Systems of Affine Constraints.

  • By: Jean-Francois Collard , Paul Feautrier , Tanguy Risset
  • Number: RR1993-15
  • Date: May 18, 1993
  • Abstract:

    Most parallelization techniques for DO loop nests are based on reindexation. Reindexation yields a new iteration space, which is a convex integer polyhedron defined by a set of affine constraints. Parallel code generation needs thus to scan all the integer points of this convex, thereby requiring the construction of a new DO loop nest. We detail an algorithm for this purpose, which relies on a parametrized version of the Dual Simplex. We show how the resulting loop nest and especially the loop bounds can be kept simple and streamlined, so as not to reduce the benefits of parallelization.
  • Keywords:

    Automatic Parallelization, Convex Integer Polyhedron, Code Generation.
  • Availability: Electronic copy only.
  • Citation: To appear in Parallel Processing Letters.
  • Size: 2+24p
  • Format: Compressed PostScript
  • Get it

On the redundancy of real number representation systems.

  • By: Christophe Mazenc
  • Number: RR1993-16
  • Date: May 18, 1993
  • Abstract:

    In this paper, a set of definitions describing general real number representation systems is presented. Our purpose is to find a sufficiently wide model definition including classical systems (signed-digit notation,linear numeration systems, p-adic numbers, symmetric level index arithmetic...) but specific enough to make it possible to build some practical results. We focuse on the redundancy property and the relationships between redundancy, on-line and digit-parallel calculus.
  • Keywords:

    Number Representation Systems, Redundancy, On-Line Arithmetic.
  • Availability: Paper copy available.
  • Size: 2+11p
  • Format: Compressed PostScript
  • Get it

Applying semi-systolic techniques to SIMD programming.

  • By: Tanguy Risset
  • Number: RR1993-17
  • Date: June 12, 1993
  • Abstract:

    In this paper, we present various implementations of the Algebraic Path Problem on a SIMD machine (the MasPar MP-1). The parallel algorithms are derived from systolic arrays and pseudo-systolic arrays recently synthesized for the Algebraic Path Problem. Performance comparisons are given, our goal is to show that systolic techniques are not efficient for SIMD programming, and to consider possible extensions.
  • Keywords:

    APP, Local Broadcast, MasPar, SIMD, Sytolic.
  • Availability: Paper copy available.
  • Citation: Published in Proceedings IFIP WG 0-3, Applications in parallel and distributed computing, 1994.
  • Size: 2+23p
  • Format: Compressed PostScript
  • Get it

Towards simple massively parallel systems: Bus based parallel computers and new communication patterns.

  • By: Afonso Ferreira , Alfredo Goldman vel Lejbman , Siang Wun Song
  • Number: RR1993-18
  • Date: June 30, 1993
  • Abstract:

    In most distributed memory MIMD multiprocessors, processors are connected by a point-to-point interconnection network, usually modeled by a graph where processors are nodes and communication links are edges. Since interprocessor communication frequently constitutes serious bottlenecks, several architectures were proposed that enhance point-to-point topologies with the help of multiple bus systems so as to improve the communication efficiency. In this paper we demonstrate the interest of parallel architectures where the communication means are constituted solely by busses. These architectures can use the power of bus technologies, providing a new way to interconnect much more processors in a simple and efficient manner. We first show how to use (hyper) graph theoretic concepts in order to model inter-processor communication in such networks and then give extremely efficient algorithms for broadcast and gossiping.
  • Keywords:

    Massively Parallel Architectures, Multiple Bus Systems, Global Communication, Communication Models, Hypergraphs And Applications, Broadcasting, Gossiping.
  • Availability: Electronic copy only.
  • Citation: Published in Proceedings PARLE'94, Lecture Notes in Computer Science, 1994. Published in Proceedings CONPAR'94, Lecture Notes in Computer Science, 1994.
  • Size: 2+17p
  • Format: Compressed PostScript
  • Get it

Dictionary Machine on SIMD Architectures.

  • By: Michel Gastaldo
  • Number: RR1993-19
  • Date: June 30, 1993
  • Abstract:

    This paper presents an implementation of a dictionary machine on a SIMD architecture. The goal of this study is to propose a practical implementation with good performances, taking into account the SIMD mode of computation. We suggest an elegant solution to the main difficulty, the load balancing problem, and then we analyze experimental results obtained on our machine.
  • Keywords:

    Dictionary Machine, SIMD, Load Balancing, Parallel Data Structure.
  • Availability: Electronic copy only.
  • Citation: Submited to Parallel Computing.
  • Size: 2+18p
  • Format: Compressed PostScript
  • Get it

A Graph-Theoretic Approach to the Alignment Problem.

  • By: Alain Darte , Yves Robert
  • Number: RR1993-20
  • Date: July 1993
  • Abstract:

    This paper deals with the problem of aligning data and computations when mapping uniform or affine loop nests onto SPMD distributed memory parallel computers. For affine loop nests we formulate the problem by introducing the communication graph, which can be viewed as the counterpart for the mapping problem of the dependence graph for scheduling. We illustrate the approach with several examples to show the difficulty of the problem. In the simplest case, that of perfect loop nests with uniform dependences, we show that minimizing the number of communications is NP-complete, although we are able to derive a good alignment heuristic in most practical cases.
  • Keywords:

    Loop Nest, Uniform Dependences, Affine Dependences, Alignment Problem, The Owner Computes Rule, Convex Domain, Communication Graph, Mapping Strategies.
  • Availability: Electronic copy only.
  • Citation: To appear in Parallel Processing Letters, 1994.
  • Size: 2+18p
  • Format: Compressed PostScript
  • Get it

Code generation in automatic parallelizers.

  • By: Jean-Francois Collard
  • Number: RR1993-21
  • Date: December 7, 1993
  • Abstract:

    Literature on automatic parallelization generally focuses on data dependency analysis but seldom on code generation. However, this topic is of the utmost importance since the parallelism extracted by the compiler has to be expressed in a high-level language and to fit target architectures. This report describes a comprehensive code generation scheme for parallelizing compilers.
  • Keywords:

    Automatic Parallelization, Scheduling, Code Generation.
  • Availability: Electronic copy only.
  • Citation: Published in Proceedings International Conference on Applications in Parallel and Distributed Computing, IFIP W.G. 10.3, North Holland, pp 185-194, 1994.
  • Size: 2+21p.
  • Format: Compressed PostScript
  • Get it

Monitoring the behavior of parallel programms: how to be scalable?

  • By: Jean-Yves Peterschmitt, Bernard Tourancheau, Xavier-Francois Vigouroux
  • Number: RR1993-22
  • Date: August 26, 1993
  • Abstract:

    It is easy to find errors and inefficient parts of a sequential program, by using a standard debugger/profiler, but there is no such tool in a parallel environment. The only way to study the race conditions of a parallel program is to execute it and collect data about its execution. The programmer can then use the generated trace files and specialized tuning tools to visualize and improve the behavior of the program: idle processors, communications, etc. The problem in large parallel systems is that these tools have to deal with an enormous amount of data. The classical approach to monitor and trace analysis i.e. sequential, event driven, post-mortem monitoring) is no longer realistic. To avoid this bottleneck, we introduced PIMSY (Parallel Implementation of a Monitoring System). The main idea of PIMSY is to let the trace data distributed among the parallel storage and to distribute the program (or the programs) that deal with the trace data.
  • Keywords:

    Monitoring, Scalability.
  • Availability: Electronic copy only.
  • Size: 2+15p
  • Format: Compressed PostScript
  • Get it

Recursive Construction of Periodoc Steady State for Neural Networks.

  • By: Martin Matamala
  • Number: RR1993-23
  • Date: December 11, 1993
  • Abstract:

    We present a strategy in order to build neural networks with long steady state periodic behavior. This strategy allows us to obtain 2^n non equivalent neural networks of size n, when the equivalence relation is the dynamical systems one. As a particular case, we build a neural networks with n neurons admitting a cycle of period 2^n.
  • Keywords:

    Neural Networks, Dynamical Systems.
  • Availability: Paper copy available.
  • Size: 2+20p
  • Format: Compressed PostScript
  • Get it

Trace2au: Audio Monitoring Tools for Parallel Programs.

  • By: Jean-Yves Peterschmitt , Bernard Tourancheau
  • Number: RR1993-24
  • Date: August 9, 1993
  • Abstract:

    It is not easy to reach the best performances you can expect of a parallel computer. We therefore have to use monitoring programs to study the performances of parallel programs. We introduce here a way to generate sound in real-time on a workstation, with no additional hardware, and we apply it to such monitoring programs.
  • Keywords:

    Monitoring, Parallelism, Sound on a Workstation, Sonification.
  • Availability: Paper copy available.
  • Size: 2+20p
  • Format: Compressed PostScript
  • Get it

Computing over the Reals with Addition and Order.

  • By: Pascal Koiran
  • Number: RR1993-25
  • Date: August 24, 1993
  • Abstract:

    We provide a fairly complete picture of the complexity theory of additive real machines. This model of computation is a restriction of the real Turing machine of Blum, Shub & Smale, since addition and subtraction are the only legal arithmetic operations. Removing the order relation < on R yields an even weaker class of machines, which is also studied. Our main results are: - characterizations of the classes of recognizable boolean languages; - equivalence of real and digital nondeterminism; - a simpler proof of Meer's P_lin <> NP_lin result.
  • Keywords:

    Computational Complexity, Real Machines, Polyhedra.
  • Availability: Paper copy available.
  • Citation: Published in Theoretical Computer Science 133, pp 35-48, 1994.
  • Size: 2+9p
  • Format: Compressed PostScript
  • Get it

A digit-serial divider for fine grain heterogeneous parallel-pipelined processing.

  • By: Mario Fiallos-Aguilar , Jean Duprat
  • Number: RR1993-26
  • Date: September 16, 1993
  • Abstract:

    We design a new radix 2 (i.e., serial, most significant digit first) floating-point divider which performs its arithmetic operation in mode both for the exponent and the mantissa. We have performed parallel discrete-event simulations of the circuit on a memory-distributed massively parallel computer.
  • Keywords:

    Fine Grain Parallelisme, Heterogeneous Processing, Digit On-Line Computation.
  • Availability: Paper copy available.
  • Size: 2+11p
  • Format: Compressed PostScript
  • Get it

Parallel Interval Order Recognition and Construction of Interval Representations.

  • By: Michael A. Bender , Michel Gastaldo , Michel Morvan
  • Number: RR1993-27
  • Date: September 1993
  • Abstract:

    Parallel algorithms for recognizing and representing interval orders are proposed for different models of parallel random access machines (PRAM). The algorithms accept as input a transitively-closed directed graph with N nodes and M edges. They run in time O(log N) with O(N +M) processors and O(N +M) space and in constant time with O(N^2) processors and O(N^2) space depending on the data structure and the PRAM model used. Optimal probabilistic algorithms for PRAM are also presented as well as algorithms for distributed-memory machines.
  • Keywords:

    Parallel Algorithms, PRAM, Partial Order, Interval Order.
  • Availability: Paper copy available.
  • Citation: To appear in Theoretical Computer Science.
  • Size: 2+18p
  • Format: Compressed PostScript
  • Get it

Object borders, surfaces and contours in 3D digital images.

  • By: Laurent Perroton
  • Number: RR1993-28
  • Date: June 1993
  • Abstract:

    The goal of this report is to present the notions of borders, surfaces and contours in 3D digital images. Properties of discrete notions of borders and surfaces are less trivial than in the continuous space. 3D discrete surfaces modelizations have noticeable properties. We expose the most important among the known ones and our original contributions about the hamiltonian paths and cycles. We present all those notions as different modelization of a single concept we call contour. We present an algorithm to extract such contours of objects, and we illustrate the interest of this approach by presenting an original sequential algorithm of the well known problem of connected components labeling. Two parallelization strategies of the contour tracking algorithm are then proposed, one using a data structure of list, the other one, a spatial distribution of the image over the processors.
  • Keywords:

    Volumic Imaging, Discrete Contour Tracking, Discrete Surface Tracking.
  • Availability: Electronic copy only.
  • Citation: Proc. IS & T/SPIE Symposium on Electronic Imaging, Science and Technology, 1994. Proc. 3rd International Workshop on Parallel Image Anaysis, Washington, 1994.
  • Size: 2+48p
  • Format: Compressed PostScript
  • Get it

Developing certified programs in Coq - The Program Tactic.

  • By: Catherine Parent
  • Number: RR1993-29
  • Date: September 9, 1993
  • Abstract:

    The system Coq is an environment for proof development based on the Calculus of Constructions extended by inductive definitions. Functional programs can be extracted from constructive proofs written in Coq. The extracted program and its corresponding proof are strongly related. The idea in this paper is to use this link to have another approach: to give a program and to generate automatically the proof from which it could be extracted. Moreover, we introduce a notion of annotated programs.
  • Keywords:

    Calculus of Constructions, Lambda-Calculus, Extraction.
  • Availability: Paper copy available.
  • Citation: Published in Proceedings International Workshop Types for Proofs and Programs, Ni jmegen, Lecture Note in Computer Science, vol 806, pp 291-312, 1993.
  • Size: 2+15p
  • Format: Compressed PostScript
  • Get it

Global properties of 2D cellular automata: Random NP-complete problems.

  • By: Bruno Durand
  • Number: RR1993-30
  • Date: October 10, 1993
  • Abstract:

    In this paper, we prove the co-RNP-completeness (RNP = Random NP) of the following decision problem: "given a 2-dimensional cellular automaton A (even with Von Neumann neighborhood), is A reversible when restricted to periodic configurations not greater than its length?" In order to prove this result, we introduce a polynomial reduction from problems concerning periodic tilings into problems concerning cellular automata. Then we add to tile sets and cellular automata two probability functions and we prove that these problems are not only co-NP-complete, but co-RNP-complete too. We also state the same results for cellular automata restricted to finite configurations.
  • Keywords:

    Cellular Automata, Reversibility, Complexity, Average Case Complexity.
  • Availability: Paper copy available.
  • Citation: Published in Proceedings STACS'95, Lecture Notes in Computer Science, Springer-Verlag ; To appear in Theoretical Computer Science, 1995.
  • Size: 2+13p
  • Format: Compressed PostScript
  • Get it

Stochastic resolution of a diffusion equation system on Volvox IS-860 preliminary study.

  • By: Makan Pourzandi , Bernard Tourancheau
  • Number: RR1993-31
  • Date: November 2, 1993
  • Availability: Paper copy available. Not available by FTP.

A primitive recursive algorithm for the Inf function.

  • By: Rene David
  • Number: RR1993-32
  • Date: November 2, 1993
  • Abstract:

    We give a primitive recursive algorithm (for the structure of integers - in unary - and lists of integers) that computes the minimum of two integers in linear time of this minimum. This algorithm refutes a conjecture of L. Colson.
  • Keywords:

    Primitive Recursive Algorithm.
  • Availability: Electronic copy only.
  • Citation: Note aux CRAS Paris t 317, serie I, pp 899-902, 1993.
  • Size: 2+5p
  • Format: Compressed PostScript
  • Get it

The Inf function in the system F.

  • By: Rene David
  • Number: RR1993-33
  • Date: November 2, 1993
  • Abstract:

    We give a lambda term of type Nat, Nat->Nat in the system F that computes the minimum of 2 Church numerals in time O(inf.log(inf)). This refutes a conjecture of the "lambda folklore".
  • Keywords:

    Typed Lambda Calculus, Complexity.
  • Availability: Paper copy available.
  • Size: 2+12p
  • Format: Compressed PostScript
  • Get it

Experimental Evaluation of Affine Schedules for Matrix Multiplication on the MasPar Architecture.

  • By: Pierre Boulet , Jose A.B. Fortes
  • Number: RR1993-34
  • Date: October 22, 1993
  • Abstract:

    This paper reports an experimental study on the the suitability of systolic algorithms scheduling methods to the automatic parallelization of algorithms on SIMD computers. We consider the matrix multiplication on the MasPar MP-1 architecture. We comparatively study different scheduling methods and the blocking of the best resulting algorithms.
  • Keywords:

    SIMD, MasPar, Matrix Multiplication, Loop Nest, Uniform Dependence Algorithm, Affine Schedule, Blocking.
  • Availability: Paper copy available.
  • Citation: Published in Proceedings CONPAR'94-VAPP VI, Lecture Note in Computer Science, N° 854, pp 713-724, 1994.
  • Size: 2+17p
  • Format: Compressed PostScript
  • Get it

On NC-real complexity classes for additive circuits and their relations with NC.

  • By: Michel Cosnard , Martin Matamala
  • Number: RR1993-35
  • Date: October 27, 1993
  • Abstract:

    Based on the results of Blum, Shub and Smale, Meer, Cucker and Matamala and Koiran, we develop the study of real computation models restricted to additive operations. More specifically we introduce some complexity classes defined by algebraic circuits and we study their relationships with the real computation model. We show that the languages accepted by nonuniform additive circuits of polynomial size and polylogarithmic depth are those accepted by uniform additive circuits of polynomial size and polylogarithmic depth with advice. Moreover, we prove that binary languages accepted by real uniform circuits of polynomial size and polylogarithmic depth, when the test nodes in the circuit are equality test, are the languages belonging to NC; when the test nodes are inequality test, the class obtained is NC/Poly. We also prove that the class defined by family of algebraic circuits with polynomial size and polylogarithmic depth is strictly contained in the class defined by real additive Turing machines working in polynomial time.
  • Keywords:

    Parallel Computation Complexity, Real Computational Models, Algebraic Circuits.
  • Availability: Paper copy available.
  • Citation: Published in proceedings Mathematical Foundations of Computer Science, LNCS, Springer-Verlag, 1994.
  • Size: 2+14p
  • Format: Compressed PostScript
  • Get it

(Pen)-ultimate tiling?

  • By: Pierre Boulet , Alain Darte , Tanguy Risset , Yves Robert
  • Number: RR1993-36
  • Date: November 9, 1993
  • Abstract:

    In the framework of perfect loop nests with uniform dependences, tiling is a technique used to group elemental computation points so as to increase computation granularity and to reduce the overhead due to communication time. We review existing approaches from the literature, together with the optimization criteria that are used for determining a ``good'' or ``optimal'' tiling. Then we explain the need to introduce yet another criterion for defining ``optimal tiling'' in a scalable environment. Although our criterion is more complex than previously used ones, we are able to prove a theorem on optimality, and to provide a constructive method for defining the ``optimal tiling''.
  • Keywords:

    Loop Nest, Uniform Dependence Algorithm, Tiling, Convex Domain, Partitioning, SPMD Code.
  • Availability: Electronic copy only.
  • Citation: Published in INTEGRATION, the VLSI Journal 17, pp 33-51, 1994.
  • Size: 2+17p
  • Format: Compressed PostScript
  • Get it

Relations between models of parallel abstract machines.

  • By: Michel Cosnard , Pascal Koiran
  • Number: RR1993-37
  • Date: January 1993
  • Abstract:

    We formally introduced a new model of computations the RealRAM and its parallel counterpart the RealPRAM. We study the relationship between these models, classical computational models and two recently proposed parallel machine models, the real machine from Blum, Shub and Smale and the analog neural networks from Siegelman and Sontag. We propose a classification using simulations by dynamical systems. We also generalise the NC class and P-complete problems to real computations.
  • Keywords:

    Parallel Computation Complexity, Real Computational Models, Algebraic Circuits.
  • Availability: Electronic copy only.
  • Citation: Published in proceedings of the conference on Parallel Architectures and Their Efficient Use, First Heinz Nixdorf Symposium, Paderborn, Germany, 1992, Lecture Notes in Computer Science 678, 1993, 37-46.
  • Size: 10p
  • Format: Compressed PostScript
  • Get it

Space-time transformation of while-loops using speculative execution.

  • By: Jean-Francois Collard
  • Number: RR1993-38
  • Date: November 4, 1993
  • Abstract:

    Automatic parallelization techniques of sequential programs have focused on nests of for-loops. This report describes a method to extend some of these techniques to while-loops enclosing a nest of for-loops. This kind of nest is common in numerical applications, where a while-loop iterates a convergent computation on a discrete space scanned by the nest of for-loops. We show how execution time can be dramatically reduced for these programs. Our method relies on speculative execution expressed as an affine scheduling function, as in recent automatic parallelization techniques of for-loops. We show how this schedule can be found automatically. We also address the problem of mapping the operations onto the processors.
  • Keywords:

    Automatic Parallelization, While Loop, Speculative Execution, Eager Execution.
  • Availability: Paper copy available.
  • Citation: Published in Proceedings 1994 Scalable High Performance Computing conference, Knoxville, Tennessee, USA, pp 429-436, 1994.
  • Size: 2+14p
  • Format: Compressed PostScript
  • Get it

Strategies of weight updating for parallel back-propagation.

  • By: Didier Girard , Helene Paugam-Moisy
  • Number: RR1993-39
  • Date: December 7, 1993
  • Abstract:

    One parallel implementation of the back-propagation algorithm consists in distributing the connections of the neural network among different processors. Another one is based on distributing the examples to be learned. After arguing in favour of the second method, this report presents several strategies of weight updating and compares their performances. These latter algorithms have been implemented on the Volvox machine of Archipel.
  • Keywords:

    Learning, Neural Networks, Back-propagation, Parallel Algorithms, MIMD Computers.
  • Availability: Paper copy available.
  • Citation: Proc. of the IFIP WG10.3 International Conference on Applications in Parallel and Distributed Computing Caracas, Venezuela, 18-22 april 1994. Extended version ; short version (2p) to appear.
  • Size: 2+8p
  • Format: Compressed PostScript
  • Get it

An incremental neural classifier on a MIMD computer.

  • By: Arnulfo Azcarraga, Helene Paugam-Moisy , Didier Puzenat
  • Number: RR1993-40
  • Date: December 21, 1993
  • Abstract:

    MIMD computers are among the best parallel architectures available. They are easily scalable with numerous processors and have potentially huge computing power. One area of application for such computers is the field of neural networks. This article presents a study, and two parallel implementations, of a specific neural incremental classifier of visual patterns. This neural network is incremental in that network units are created whenever the classifier is not able to recognize correctly a pattern. The dynamic nature of the model renders the parallel algorithms rather complex.
  • Keywords:

    Neural Network, Incremental Classifier, Pattern Recognition, MIMD Parallel Computer.
  • Availability: Electronic copy only.
  • Citation: Proc. of the IFIP WG10.3 International Conference on Applications in Parallel and Distributed Computing Caracas, Venezuela, april 1994.
  • Size: 2+11p
  • Format: Compressed PostScript
  • Get it

Multi-dimensional pipeline and array architectures for the on-line computation of the fast orthogonal transforms.

  • By: Hamid Bessalah
  • Number: RR1993-41
  • Date: December 12, 1993
  • Availability: Paper copy available. Not available by FTP.
  • Citation: Appeared in "Technologies avancées" 6, pp 1-14, CDTA ed, (sept 1994)

Specials cases of division.

  • By: Bob Doran
  • Number: RR1993-42
  • Date: December 16, 1993
  • Availability: Paper copy available. Not available by FTP.

A proof system for a simple data-parallel programming language.

  • By: Luc Bouge , Yann Le Guyadec , Bernard Virot , Gil Utard
  • Number: RR1993-43
  • Date: December 17, 1993
  • Abstract:

    We describe a small kernel language which encapsulates the semantic features of data-parallel control constructs as found in modern data-parallel languages. We give it a denotational semantics, and describe an assertional proof system in the style of Hoare's logic. Our contribution is to use two-part assertions, where the current extent of parallelism is specified using a separate boolean vector expression. The applicability of the proof system is demonstrated through an example.
  • Keywords:

    Concurrent Programming, Specifying and Verifying and Reasoning about Programs, Semantics of Programming Languages, Data-Parallel Languages, Proof System, Hoare Logic.
  • Availability: Electronic copy only.
  • Citation: Proceedings of the IFIP WG10.3 International Conference on Application in Parallel and Distributed Computing (Caracas, Venezuela, 18-22 April 1994. C. Girault Ed. ELSEVIER Science Pusblishers B.V.
  • Size: 2+10p
  • Format: Compressed PostScript
  • Get it