Unite Mixte, Ecole Normale, Sup Lyon, Olivier Aumage, Olivier Aumage, ...
This paper introduces Madeleine II, an adaptive multi-protocol extension of the Madeleine portable communication interface. Madeleine II provides facilities to use multiple network protocols (VIA,...
for High Performance Networks (2007)
Ecole Normale, Superieure Lyon, Unite Mixte, Olivier Aumage, Olivier Aumage, ...
This report introduces a version of MPICH handling efficiently different networks simultaneously. The core of the implementation relies on a device called ch mad which is based on a generic...
Unite Mixte, Guillaume Mercier Juillet, Guillaume Mercier, Guillaume Mercier
Ch mad: un support efficace pour
The Topological Entropy of Iterated Piecewise Ane Maps is Uncomputable (2007)
Superieure Lyon, Unite Mixte, Ecole Normale, Ecole Normale, Sup Lyon, ...
We show that it is impossible to compute (or even to approximate) the topological entropy of a continuous piecewise ane function in dimension 4. The same result holds for saturated linear functions...
for Generic Curves and a Decision Algorithm for the Limit Theory (2007)
Superieure Lyon, Unite Mixte, Natacha Portier September, Ecole Normale, Ecole Normale, ...
It was recently shown that the theories of generic algebraic curves converge to a limit theory as their degrees go to innity. In this paper we give quantitative versions of this result and other...
Some Improvements on Multipartite Table Methods (2007)
Unite Mixte, Ecole Normale, Sup Lyon, Florent De Dinechin, Florent De Dinechin, ...
This paper presents an unified view of most previous table-lookup-andaddition methods: bipartite tables, SBTM, STAM and multipartite method. This new definition allows a more accurate computation of...
Nd Ed, Unite Mixte, Vincent Boudet, Vincent Boudet, Fabrice Rastello, ...
Vincent Boudet, Fabrice Rastello and Yves Robert March 1999 Research Report N o 1999-19 Ecole Normale Sup erieure de Lyon 46 Allee d'Italie, 69364 Lyon Cedex 07, France Telephone :...
Formalisms for Mobile Resource Control (2007)
Failing to control resources in mobile, concurrent and distributed systems may lead to important breakdowns or Denial of Service-like attacks. In order to address this problem, we present enhanced...
Fermi-Pasta-Ulam Chain. (2007)
Unite Mixte, Fabrice Rastello, Fabrice Rastello, Thierry Dauxois, Thierry Dauxois
Parallelization of the Numerical Lyapunov Calculation for the
Quantum Automata and Algebraic Groups (2007)
Ecole Normale, Superieure Lyon, Unite Mixte, Emmanuel Jeandel, Emmanuel Je, ...
We show that several problems which are known to be undecidable for probabilistic automata become decidable for quantum finite automata. Our main tool is an algebraic result of independent interest:...
On Poset Sandwich Problems Michel Habib (2007)
Unite Mixte, David Kelly, David Kelly, Emmanuelle Lebhar, Emmanuelle Lebhar, ...
A graph G s = (V, E s) is a sandwich for a pair of graph G t = (V, E t) and G = (V, E) if E t
Multiple Precision Interval Packages: Comparing Di#erent Approaches (2007)
Unite Mixte, M. Grimmer, M. Grimmer, K. Petras, K. Petras, ...
We give a survey on packages for multiple precision interval arithmetic, with the main focus on three specific packages. One is within a Maple environment, intpakX, and two are C/C++ libraries,...
On the Complexity of Polynomial Matrix Computations (2007)
Unite Mixte, Pascal Giorgi, Pascal Giorgi, Claude-pierre Jeannerod, Claude-pierre Jeannerod, ...
We study the link between the complexity of polynomial matrix multiplication and the complexity of solving other basic linear algebra problems on polynomial matrices. By polynomial matrices we mean n...
A Rank Theorem for Vandermonde Matrices (2007)
Ecole Normale, Superieure Lyon, Unite Mixte, Pascal Koiran, Pascal Koiran, ...
We show that certain matrices built from Vandermonde matrices are of full rank. This result plays a key role in the construction of the \limit theory of generic polynomials".
Formalisms for Mobile Resource Control (2007)
Failing to control resources in mobile, concurrent and distributed systems may lead to important breakdowns or Denial of Service-like attacks. In order to address this problem, we present enhanced...
On Ecient Parallelization of Line-Sweep Computations (2007)
Unite Mixte, Alain Darte, Robert Fowler, Ecole Normale, Sup Lyon, ...
Multipartitioning is a strategy for partitioning multi-dimensional arrays on a collection of processors. With multipartitioning, computations that require solving 1D recurrences along each dimension...
Ecole Normale Sup erieure de (2007)
Ecole Normale, Superieure Lyon, Unite Mixte
An algebraic method to compute a shortest path of local ips between two tilings
Bounded Polymorphism for Extensible Objects (2007)
Ecole Normale, Superieure Lyon, Unite Mixte, Luigi Liquori, Luigi Liquori
In the ECOOP'97 conference, the author of the present paper investigated a conservative extension, called Ob 1, of the first-order Object Calculus Ob 1 of Abadi and Cardelli, supporting method...
Superieure Lyon, Unite Mixte, Ecole Normale, Ecole Normale, Sup Lyon, ...
On the sensitivity of additive cellular automata in Besicovitch topologies
Tiling with bars under tomographic constraints (2007)
Unite Mixte, Eric Goles, Eric Goles, Ivan Rapaport, Ivan Rapaport
SPI Tiling with bars under tomographic constraints Christoph Durr
Loop Alignment for Memory Accesses Optimization (2007)
Unite Mixte, Ecole Normale, Sup Lyon, Antoine Fraboulet, Antoine Fraboulet, ...
Portable or embedded systems allow more and more complex applications like multimedia today. These applications and submicronic technologies have made the power consumption criterium crucial. We...
Ecole Normale, Superieure Lyon, Unite Mixte, C. Mongenet, C. Mongenet, ...
Workshop "Compilation et Parallelisation
Ecole Normale, Superieure Lyon, Unite Mixte, Ahmed Mostefaoui, Ahmed Mostefaoui, ...
In a multimedia system, I/O have a dramatic impact on the performance. Therefore, reducing I/O has become a key issue. The latter has been mostly addressed by using buering techniques. In this paper,...
Simulations of graph automata (2007)
Unite Mixte, Ecole Normale, Sup Lyon, Codrin Nichitiu, Codrin Nichitiu
We state a definition of the simulation of graph automata, which are machines built by putting copies of the same finite-state automaton at the vertices of a regular graph, reading the states of the...
Ecole Normale Sup erieure de (2007)
Ecole Normale, Superieure Lyon, Unite Mixte, Laurent Bienvenu, Laurent Bienvenu, ...
Distributed computing power: from local function to global computing
An optimal algorithm to generate tilings (2007)
Unite Mixte, Ecole Normale, Sup Lyon, Sebastien Desreux, Sebastien Desreux, ...
An optimal algorithm to generate
Algorithmic Issues on Heterogeneous Computing Platforms (2007)
Unite Mixte, Ecole Normale, Sup Lyon, Pierre Boulet, Pierre Boulet, ...
This paper discusses some algorithmic issues when computing with a heterogeneous network of workstations (the typical poor man's parallel computer). Dealing with processors of dierent speeds...
Laboratoire de l'Informatique du Parall elisme (2003)
Ecole Normale Superieure, Unite Mixte, Jean-michel Muller, Jean-michel Muller, Milos D. Ercegovac, ...
We adapt the radix-r digit-recurrence division algorithm to complex division. By prescaling the operands, we make the selection of quotient digits simple. This leads to a simple hardware...
Optimizing the translation out-of-SSA with renaming constraints (2003)
Unite Mixte, Ecole Normale, Sup Lyon, F. Rastello, F. Rastello, ...
Static Single Assignment form is an intermediate representation, that uses -functions to merge values at each confluent points of the control flow graph. functions are not machine instructions and...
Optimizing the translation out-of-SSA with renaming constraints (2003)
Unite Mixte, Ecole Normale, Sup Lyon, F. Rastello, F. Rastello, ...
Static Single Assignment form is an intermediate representation, that uses -functions to merge values at each confluent points of the control flow graph. functions are not machine instructions and...
A Brief Survey Of The Theory Of The π-Calculus (2003)
Ecole Normale, Superieure Lyon, Unite Mixte, Daniel Hirschkoff
This document collects some important results about the theory of Milner's #-calculus and related formalisms. We present the syntax and semantics of a monadic calculus, and discuss type systems...
New Results on Array Contraction (2002)
Unite Mixte, Guillaume Huard April, Alain Darte, Alain Darte, Guillaume Huard
this report, we prove two NP-complete results that characterize precisely the problem and we give a practical integer linear programming formulation to solve the problem exactly
New Complexity Results on Array Contraction and Related Problems (2002)
Unite Mixte, Guillaume Huard October, Ecole Normale, Sup Lyon, Alain Darte, ...
this report, we focus on the theoretical aspects of the problem. We prove several NP-complete results that characterize precisely its complexity and we provide an integer linear programming...
A Proposal for a Heterogeneous Cluster ScaLAPACK (Dense Linear Solvers) (2001)
Unite Mixte, Vincent Boudet, Fabrice Rastello, Yves Robert, Ecole Normale, ...
This paper discusses some algorithmic issues when computing with a heterogeneous network of workstations (the typical poor man's parallel computer). How is it possible to eÆciently implement...
Laboratoire de l'Informatique du Parall elisme (2001)
Ecole Normale Superieure, Unite Mixte, Christophe Monat, Christophe Monat, ...
This report addresses the problem of improving the execution performance of saturated reduction loops on xed-point instruction-level parallel Digital Signal Processors (DSPs). We rst introduce...
A Proposal for a Heterogeneous Cluster ScaLAPACK (Dense Linear Solvers) (2001)
Unite Mixte, Vincent Boudet, Fabrice Rastello, Yves Robert
This paper discusses some algorithmic issues when computing with a heterogeneous network of workstations (the typical poor man's parallel computer). How is it possible to eÆciently implement...
Partitioning a Square into Rectangles: NP-Completeness and Approximation Algorithms (2000)
Unite Mixte, Ecole Normale, Sup Lyon, Olivier Beaumont, Olivier Beaumont, ...
In this paper, we deal with two geometric problems arising from heterogeneous parallel computing: how to partition the unit square into p rectangles of given area s 1 ; s 2 ; : : : ; s p (such that P...
Partitioning a Square into Rectangles: NP-Completeness and Approximation Algorithms (2000)
Unite Mixte, Ecole Normale, Sup Lyon, Olivier Beaumont Vincent, Olivier Beaumont, ...
In this paper, we deal with two geometric problems arising from heterogeneous parallel computing: how to partition the unit square into p rectangles of given area s 1 ; s 2 ; : : : ; s p (such that P...
Transfer Theorems via Sign Conditions (2000)
Ecole Normale, Superieure Lyon, Unite Mixte, Pascal Koiran, Pascal Koiran
We show that P = PSPACE implies the collapse of the boolean polynomial hierarchy over any structure which admits "efficient enumeration of sign conditions". This fairly rich class of...
Heterogeneity Considered Harmful to Algorithm Designers (2000)
Unite Mixte, Ecole Normale, Sup Lyon, Olivier Beaumont, Olivier Beaumont, ...
In this paper, we deal with algorithmic issues on heterogeneous platforms. We show that static scheduling and load-balancing strategies are absolutely needed to achieve good performances, in contrast...
Damage Spreading and µ-sensitivity on CA (2000)
Unite Mixte, On Ca, Bruno Martin Fevrier, Bruno Martin
We show relations between new notions on cellular automata based on topological and measure-theoretical concepts: almost everywhere sensitivity to initial condition for Besicovitch pseudo-distance,...
Constant Multipliers for FPGAs (2000)
Florent De Dinechin, Vincent Lefèvre, Ecole Normale, Superieure Lyon, Unite Mixte
This paper presents a survey of techniques to implement multiplications by constants on FPGAs. It shows in particular that a simple and well-known technique, canonical signed recoding, can help...
Matrix-Matrix Multiplication on Heterogeneous Platforms (2000)
Unite Mixte, Ecole Normale, Sup Lyon, Olivier Beaumont, Olivier Beaumont, ...
In this paper, we address the issue of implementing matrix-matrix multiplication on heterogeneous platforms. We target two different classes of heterogeneous computing resources: heterogeneous...
Laboratoire de l'Informatique du Parall elisme (2000)
Unite Mixte, Ecole Normale Superieure, Sup Lyon, Olivier Beaumont, Olivier Beaumont, ...
In this paper, we deal with redistribution issues for dense linear algebra kernels on heterogeneous platforms. In this context, processors speeds may well vary during the execution of a large kernel,...
Efficient Communications in Multithreaded Runtime Systems (1999)
Luc Bouge, Jean-François Méhaut, Ecole Normale, Superieure Lyon, Unite Mixte
Most of existing multithreaded environments have an implementation built on top of standard communication interfaces such as MPI which ensures a high level of portability. However, such interfaces do...
Algorithmic Issues for (Distributed) Heterogeneous Computing Platforms (Extended Abstract) (1999)
Unite Mixte, Ecole Normale, Sup Lyon, Vincent Boudet, Vincent Boudet, ...
Vincent Boudet, Fabrice Rastello and Yves Robert March 1999 Research Report N o 1999-19 Ecole Normale Sup erieure de Lyon 46 Allee d'Italie, 69364 Lyon Cedex 07, France Telephone :...
Unite Mixte, Vincent Boudet Antoine, Ecole Normale, Sup Lyon, Antoine Petitet, ...
We study the implementation of dense linear algebra computations, such as matrix multiplication and linear system solvers, on two-dimensional (2D) grids of heterogeneous processors. For these...
The Complexity of Local Dimensions for Constructible Sets (1999)
Ecole Normale, Superieure Lyon, Unite Mixte, Pascal Koiran Janvier, Pascal Koiran
We show that deciding whether an algebraic variety has an irreducible component of codimension at least d is an NP C -complete problem for every xed d (and is in the Arthur-Merlin class if we assume...
A formalization of Static Analyses in System F (1999)
Ecole Normale, Superieure Lyon, Unite Mixte, Frederic Prost
In this paper, we propose a common theoretical framework for type based static functional analyses. The aim is to study the relationships between typing and program analysis. We present a variant of...
SOPHIE: a Tool for Collecting PHiPAC Metrics Of C Code (1999)
Ecole Normale, Superieure Lyon, Thomas Peugeot, Unite Mixte, ...
In designing ecient software for High Performance Real Time embedded signal processing applications, several performance issues must be addressed prior and during implementation. We present a tool...
Leader Election by d Dimensional Cellular Automata (1999)
Unite Mixte, Eric Rémila, Codrin Nichitiu, Codrin Nichitiu
We present a cellular algorithm in O(w 2 ) for the leader election problem on a finite connected subset F of ZZ d of diameter w, for any fixed d. The problem consists in finding an algorithm such...
Deciding Stability and Mortality of Piecewise Ane Dynamical Systems (1999)
Ecole Normale, Superieure Lyon, Unite Mixte, Vincent Blondel Olivier, Olivier Bournez, ...
We show that several global properties (attractivity, global asymptotic stability and mortality) of discrete time dynamical systems dened by iteration of piecewise-ane maps are undecidable. Such...
Unite Mixte, Vincent Boudet Antoine, Ecole Normale, Sup Lyon, Antoine Petitet, ...
We study the implementation of dense linear algebra computations, such as matrix multiplication and linear system solvers, on two-dimensional (2D) grids of heterogeneous processors. For these...
Towards Portable Hierarchical Placement for FPGAs (1999)
Ecole Normale, Superieure Lyon, Unite Mixte, Florent De Dinechin, Wayne Luk, ...
Field Programmable Gate Arrays (FPGAs) are usually programmed using languages and methods inherited from the domain of VLSI synthesis. These methods, however, have not always been adapted to the new...
Unite Mixte, Vincent Boudet, Ecole Normale, Sup Lyon, Antoine Petitet, ...
We study the implementation of dense linear algebra computations, such as matrix multiplication and linear system solvers, on two-dimensional (2D) grids of heterogeneous processors. For these...
Algorithms and Tools for (Distributed) Heterogeneous Computing: A Prospective Report (1999)
J. F. Mehaut, Y. Robert, Unite Mixte
We discuss algorithms and tools to help program and use metacomputing resources in the forthcoming years. Metacomputing with highly distributed heterogeneous environments stands to become a major, if...
The Price of Routing in FPGAs (1999)
Ecole Normale, Superieure Lyon, Unite Mixte, Florent De Dinechin
This paper studies an architectural issue concerning field programmable gate arrays (FPGAs). The observation of mainstream FPGA architectures leads to the following remark: in these circuits, the...
Lower Bounds Are not Easier over the Reals: Inside PH (1999)
Hervé Fournier, Ecole Normale, Superieure Lyon, Unite Mixte, Pascal Koiran March, ...
We prove that all NP problems over the reals with addition and order can be solved in polynomial time with the help of a boolean NP oracle. As a consequence, the "P = NP?" question over the...
The Complexity of Local Dimensions for Constructible Sets (1999)
Ecole Normale, Superieure Lyon, Unite Mixte, Pascal Koiran Janvier, Pascal Koiran
We show that deciding whether an algebraic variety has an irreducible component of codimension at least d is an NP C -complete problem for every xed d (and is in the Arthur-Merlin class if we assume...
Deciding Stability and Mortality of Piecewise Affine Dynamical Systems (1999)
Ecole Normale, Superieure Lyon, Unite Mixte, Vincent Blondel, Olivier Bournez, ...
We show that several global properties (attractivity, global asymptotic stability and mortality) of discrete time dynamical systems defined by iteration of piecewise-affine maps are undecidable. Such...
More on Scheduling Block-Cyclic Array Redistribution (1998)
Frédéric Desprez, Unite Mixte, Ecole Normale, Sup Lyon, ...
This article is devoted to the run-time redistribution of one-dimensional arrays that are distributed in a block-cyclic fashion over a processor grid. In a previous paper, we have reported how to...
A Geometrical Hierarchy of Graphs via Cellular Automata (1998)
Unite Mixte, Bruno Martin Octobre, Ecole Normale, Sup Lyon, Bruno Martin
Historically, cellular automata were defined on the lattices Z n , but the definition can be extended to bounded degree graphs. Given a notion of simulation between cellular automata defined on...
A Few Results on Table-Based Methods (1998)
Unite Mixte, Ecole Normale, Sup Lyon, Jean-Michel Muller
Table-based methods are frequently used to implement functions. We examine some methods introduced in the literature, and we introduce a generalization of the bipartite table method, named the...
A Framework for Defining Object-Calculi (Extended Abstract) (1998)
Frédéric Lang, Ecole Normale, Superieure Lyon, Unite Mixte, Pierre Lescanne, ...
Frederic Lang Pierre Lescanne Luigi Liquori Decembre 1998 Research Report N o RR 1998-51 Ecole Normale Sup erieure de Lyon 46 Allee d'Italie, 69364 Lyon Cedex 07, France Telephone :...
A Near-Optimal Solution to a Two-Dimensional Cutting Stock Problem (1998)
Ecole Normale, Eric Rémila, Superieure Lyon, Unite Mixte, Claire Kenyon, ...
We present an asymptotic fully polynomial approximation scheme for strippacking, or packing rectangles into a rectangle of fixed width and minimum height, a classical NP -hard cutting-stock problem....