Boissinot, Benoit, Brisk, Philip, Darte, Alain, Rastello, Fabrice
The static single information (SSI) form, proposed by Ananian, then in a more general form by Singer, is an extension of the static single assignment (SSA) form. The latter is a well-established...
Boissinot, Benoit, Brisk, Philip, Darte, Alain, Rastello, Fabrice
The static single information (SSI) form, proposed by Ananian, then in a more general form by Singer, is an extension of the static single assignment (SSA) form. The latter is a well-established...
Program Termination and Worst Time Complexity With Multi-Dimensional Affine Ranking Functions (2009)
Alias, Christophe, Darte, Alain, Feautrier, Paul, Gonnord, Laure, Quinson, Clément
A standard method for proving the termination of a flowchart program is to exhibit a ranking function, i.e., a function from the program states to a well-founded set, which strictly decreases at each...
Program Termination and Worst Time Complexity With Multi-Dimensional Affine Ranking Functions (2009)
Alias, Christophe, Darte, Alain, Feautrier, Paul, Gonnord, Laure, Quinson, Clément
A standard method for proving the termination of a flowchart program is to exhibit a ranking function, i.e., a function from the program states to a well-founded set, which strictly decreases at each...
Program Termination and Worst Time Complexity with Multi-Dimensional Affine Ranking Functions (2009)
Alias, Christophe, Darte, Alain, Feautrier, Paul, Gonnord, Laure, Quinson, Clément
A standard method for proving the termination of a flowchart program is to exhibit a ranking function, i.e., a function from the program states to a well-founded set, which strictly decreases at each...
Program Termination and Worst Time Complexity with Multi-Dimensional Affine Ranking Functions (2009)
Alias, Christophe, Darte, Alain, Feautrier, Paul, Gonnord, Laure, Quinson, Clément
A standard method for proving the termination of a flowchart program is to exhibit a ranking function, i.e., a function from the program states to a well-founded set, which strictly decreases at each...
Alain Darte, Robert Schreiber, Gilles Villard
We investigate the problem of memory reuse in order to reduce the memory needed to store an array variable. We develop techniques that can lead to smaller memory requirements in the synthesis of...
1. STATIC OPTIMIZATION OF BARRIER SYNCHRONIZATION (2008)
We want to perform compile-time analysis of an SPMD program and place barriers in it to synchronize it correctly, minimizing the runtime cost of the synchronization. This is the barrier minimization...
Revisiting Out-of-SSA Translation for Correctness, Code Quality, and Efficiency (2008)
Boissinot, Benoit, Darte, Alain, Rastello, Fabrice, Dupont De Dinechin, Benoît, Guillon, Christophe
Static single assignment (SSA) form is an intermediate program representation in which many code optimizations can be performed with fast and easy-to-implement algorithms. However, some of these...
Revisiting Out-of-SSA Translation for Correctness, Code Quality, and Efficiency (2008)
Boissinot, Benoit, Darte, Alain, Rastello, Fabrice, Dupont De Dinechin, Benoît, Guillon, Christophe
Static single assignment (SSA) form is an intermediate program representation in which many code optimizations can be performed with fast and easy-to-implement algorithms. However, some of these...
Revisiting Out-of-SSA Translation for Correctness, Code Quality, and Efficiency (2008)
Boissinot, Benoit, Darte, Alain, Rastello, Fabrice, Dupont De Dinechin, Benoît, Guillon, Christophe
Static single assignment (SSA) form is an intermediate program representation in which many code optimizations can be performed with fast and easy-to-implement algorithms. However, some of these...
Revisiting Out-of-SSA Translation for Correctness, Code Quality, and Efficiency (2008)
Boissinot, Benoit, Darte, Alain, Rastello, Fabrice, Dupont De Dinechin, Benoît, Guillon, Christophe
Static single assignment (SSA) form is an intermediate program representation in which many code optimizations can be performed with fast and easy-to-implement algorithms. However, some of these...
On the Removal of Anti and Output Dependences (2007)
Frdric Vivien, Pierre-yves Call, Alain Darte, Alain Darte, Yves Robert, ...
: In this paper we build upon results of Padua and Wolfe [8], who introduce two graph transformations to eliminate anti and output dependences. We first give a unified framework for such...
Alain Darte, Robert Schreiber, B. Ramakrishna Rau, Frederic Vivien
Constructing and exploiting linear schedules with prescribed parallelism
Loop parallelization algorithms: (2007)
Loop Parallelization Algorithms, Pierre Boulet, Pierre Boulet, Alain Darte, Alain Darte, Georges-andr Silber, ...
Unit de recherche associe au CNRS n1398
Laboratoire de l'Informatique du (2007)
Ecole Normale, Suprieure Lyon, Alain Darte Septembre, Alain Darte
Unit de recherche associe au CNRS n1398 Mathematical tools for loop transformations: from systems of uniform recurrence equations to the polytope model
Latin Hyper-Rectangles for Ecient Parallelization of Line-Sweep Computations (2007)
Multipartitioning is a strategy for partitioning multi-dimensional arrays among a collection of processors so that line-sweep computations can be performed eciently. The principal property of a...
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...
In this paper, we compare three nested loops parallelization algorithms (Allen and Kennedy's algorithm, Wolf and Lam's algorithm and Darte and Vivien's algorithm) that use different...
Unit Mixte, Alain Darte, Alain Darte, Robert Schreiber, ...
A constructive solution to the juggling problem in systolic array synthesis
Parallel Processing Letters c fl World Scientific Publishing Company (2007)
This paper is devoted to the construction of multi-dimensional schedules for a system of uniform recurrence equations. We show that this problem is dual to the problem of computability of a system of...
On the Complexity of Spill Everywhere under SSA Form (2007)
Bouchez, Florent, Darte, Alain, Rastello, Fabrice
Compilation for embedded processors can be either aggressive (time consuming cross-compilation) or just in time (embedded and usually dynamic). The heuristics used in dynamic compilation are highly...
Improvements to Conservative and Optimistic Register Coalescing (2007)
Bouchez, Florent, Darte, Alain, Rastello, Fabrice
Register coalescing is used, as part of register allocation, to reduce the number of register copies. Developing efficient register coalescing heuristics is particularly important to get rid of the...
On the Complexity of Spill Everywhere under SSA Form (2007)
Bouchez, Florent, Darte, Alain, Rastello, Fabrice
Compilation for embedded processors can be either aggressive (time consuming cross-compilation) or just in time (embedded and usually dynamic). The heuristics used in dynamic compilation are highly...
On the Complexity of Spill Everywhere under SSA Form (2007)
Bouchez, Florent, Darte, Alain, Rastello, Fabrice
Compilation for embedded processors can be either aggressive (time consuming cross-compilation) or just in time (embedded and usually dynamic). The heuristics used in dynamic compilation are highly...
Improvements to Conservative and Optimistic Register Coalescing (2007)
Bouchez, Florent, Darte, Alain, Rastello, Fabrice
Register coalescing is used, as part of register allocation, to reduce the number of register copies. Developing efficient register coalescing heuristics is particularly important to get rid of the...
Lattice-Based Array Contraction: From Theory to Practice (2007)
École Normale, Supérieure Lyon, Fabrice Baray, Alain Darte, École Normale, Supérieure Lyon, ...
We build on prior work on intra-array memory reuse, for which a general theoretical framework was proposed based on lattice theory. Intra-array memory reuse is a way of reducing the size of a...
On the complexity of register coalescing (2006)
Bouchez, Florent, Darte, Alain, Rastello, Fabrice
21 pages, figures, 35 références bibliographiques
Register allocation : what does Chaitin's NP-completeness proof really prove ? (2006)
Bouchez, Florent, Darte, Alain, Rastello, Fabrice
14 pages, figures, 21 références bibliographiques
On the complexity of register coalescing (2006)
Florent Bouchez, Alain Darte, Fabrice Rastello
Memory transfers are becoming more important to optimize, for both performance and power consumption. With this goal in mind, new register allocation schemes are developed, which revisit not only the...
Register Allocation: What does Chaitin’s NP-completeness Proof Really Prove? (2006)
École Normale, Supérieure Lyon, Florent Bouchez, Alain Darte, Fabrice Rastello, École Normale, ...
Register allocation is one of the most studied problem in compilation. It is considered as an NP-complete problem since Chaitin, in 1981, showed that assigning temporary variables to k machine...
On the Complexity of Register Coalescing (2006)
École Normale, Supérieure Lyon, Florent Bouchez, Alain Darte, Fabrice Rastello, École Normale, ...
Due to the increasing latencies of memory accesses and recent developments on the SSA form, it has become important to revisit the spilling (load/store insertion) and register coalescing (removal of...
Florent Bouchez, Alain Darte, Fabrice Rastello
Register allocation is one of the most studied problems in compilation. It is considered as an NP-complete problem since Chaitin et al., in 1981, modeled the problem of assigning temporary variables...
Register allocation and spill cmoplexity under SSA (2005)
Bouchez, Florent, Darte, Alain, Guillon, Christophe, Rastello, Fabrice
32 p., figures, 14 références bibliographiques
Hardware/Software Interface for Multi-Dimensional Processor Arrays (2005)
On most recent systems on chip, the performance bottleneck is the on-chip communication medium, bus or network. Multimedia applications require a large communication bandwidth between the processor...
Hardware/Software Interface for Multi-Dimensional Processor Arrays (2005)
École Normale, Supérieure Lyon, Alain Darte, Steven Derrien, Tanguy Risset, École Normale, ...
On most recent systems on chip, the performance bottleneck is the onchip communication medium, bus or network. Multimedia applications require a large communication bandwidth between the processor...
Darte, Alain, Schreiber, Robert
(eng) We want to perform compile-time analysis of an SPMD program and place barriers in it to synchronize it correctly, minimizing the runtime cost of the synchronization. This is the barrier...
Lattice-Based Memory Allocation. (2004)
Darte, Alain, Schreiber, Rob, Villard, Gilles
(eng) We investigate the technique of storing multiple array elements in the same memory cell, with the goal of reducing the amount of memory used by an array variable. This reduction is both...
Lattice-Based Memory Allocation (2004)
École Normale, Supérieure Lyon, Alain Darte, Rob Schreiber, Gilles Villard, École Normale, ...
We investigate the technique of storing multiple array elements in the same memory cell, with the goal of reducing the amount of memory used by an array variable. This reduction is both important and...
Lattice-based memory allocation (2003)
Alain Darte, Alain Darte, Rob Schreiber, Rob Schreiber, Gilles Villard, ...
We investigate the technique of storing multiple array elements in the same memory cell, with the goal of reducing the amount of memory used by an array variable. This reduction is both important and...
Lattice-Based Memory Allocation (2003)
Alain Darte, Rob Schreiber, Gilles Villard
We investigate the problem of memory reuse, for reducing the necessary memory size, in the context of compilation of dedicated processors. Memory reuse is a well-known concept when allocating...
Generalized multipartitioning for multi-dimensional arrays (2002)
Alain Darte, Daniel Chavarría-miranda, Robert Fowler, John Mellor-crummey
Multipartitioning is a strategy for parallelizing computations that require solving 1D recurrences along each dimension of a multi-dimensional array. Previous techniques for multipartitioning yield...
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
Generalized Multipartitioning for Multi-dimensional Arrays (2002)
Alain Darte, Daniel Chavarra-Miranda, Robert Fowler, John Mellor-Crummey
Multipartitioning is a strategy for parallelizing computations that require solving 1D recurrences along each dimension of a multi-dimensional array. Previous techniques for multipartitioning yield...
Constructing and exploiting linear schedules with prescribed parallelism (2002)
Frederic Vivien, Alain Darte, Alain Darte, Robert Schreiber, Robert Schreiber, B. Ramakrishna Rau, ...
systolic array, multicluster VLIW, linear schedule We present two new results of importance in code generation for and synthesis of synchronously scheduled parallel processor arrays and multicluster...
Generalized multipartitioning for multi-dimensional arrays (2002)
Alain Darte, Daniel Chavarría-miranda, Robert Fowler, John Mellor-crummey
Multipartitioning is a strategy for parallelizing computations that require solving 1D recurrences along each dimension of a multi-dimensional array. Previous techniques for multipartitioning yield...
Generalized multipartitioning for multi-dimensional arrays (2002)
Alain Darte, John Mellor-crummey, Robert Fowler, Daniel Chavarría-miranda
Multipartitioning is a strategy for decomposing multi-dimensional arrays into tiles and mapping the resulting tiles onto a collection of processors. This class of partitionings enables efficient...
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...
Efficient Parallelization of Line-Sweep Computations. (2001)
Chavarría-Miranda, Daniel, Darte, Alain, Fowler, Robert, Mellor-Crummey, John
(eng) Multipartitioning is a strategy for partitioning multi-dimensional arrays on a collection of processors. With multipartitioning, computations that require solving 1D recurrences along each...
Loop parallelization algorithms: from parallelism extraction to code generation (2001)
Pierre Boulet, Alain Darte, Georges-André Silber, Frédéric Vivien
Generalized multipartitioning (2001)
Alain Darte, Daniel Chavarría-miranda, Robert Fowler, John Mellor-crummey
Multipartitioning is a strategy for partitioning multidimensional arrays among a collection of processors. With multipartitioning, computations that require solving one-dimensional recurrences along...
Loop parallelization algorithms (2001)
Summary. This chapter is devoted to a comparative survey of loop parallelization algorithms. Various algorithms have been presented in the literature, such as those introduced by Allen and Kennedy,...
On efficient parallelization of linesweep computations (2001)
Alain Darte, Daniel Chavarra-miranda, Robert Fowler, John Mellor-crummey
Multipartitioning is a strategy for partitioning multidimensional arrays among a collection of processors so that line-sweep computations can be performed e#ciently. The principal property of a...
Generalized multipartitioning (2001)
Alain Darte, Daniel Chavarra-miranda, Robert Fowler, John Mellor-crummey
Multipartitioning is a strategy for partitioning multidimensional arrays among a collection of processors. With multipartitioning, computations that require solving one-dimensional recurrences along...
Generalized multipartitioning (2001)
Alain Darte, Daniel Chavarría-miranda, Robert Fowler, John Mellor-crummey
Multipartitioning is a strategy for partitioning multidimensional arrays among a collection of processors. With multipartitioning, computations that require solving one-dimensional recurrences along...
On efficient parallelization of linesweep computations (2001)
Alain Darte, Daniel Chavarría-miranda, Robert Fowler, John Mellor-crummey
Multipartitioning is a strategy for partitioning multidimensional arrays among a collection of processors so that line-sweep computations can be performed efficiently. The principal property of a...
Loop Shifting for Loop Parallelization. (2000)
Darte, Alain, Huard, Guillaume
(eng) The automatic detection of parallel loops is a well-known problem. Sophisticated polynomial algorithms have been proposed to produce code transformations that reveal parallel loops, in an...
A constructive solution to the juggling problem in systolic array synthesis (2000)
Alain Darte, Robert Schreiber, B. Ramakrishna, Rau Frédéric Vivien
We describe a new, practical, constructive method for solving the well-known conflict-free scheduling problem for the locally sequential, globally parallel (LSGP) case of systolic array synthesis....
A constructive solution to the juggling problem in systolic array synthesis (2000)
Alain Darte, Robert Schreiber, B. Ramakrishna, Rau Frederic Vivien
We describe a new, practical, constructive method for solving the well-known conflict-free scheduling problem for the locally sequential, globally parallel (LSGP) case of systolic array synthesis....
Scheduling the Computations of a Loop Nest with Respect to a Given Mapping (2000)
Alain Darte, Claude Diderich, Marc Gengler, Frédéric Vivien
. When parallelizing loop nests for distributed memory parallel computers, we have to specify when the dierent computations are carried out (computation scheduling), where they are carried out...
A constructive solution to the juggling problem in systolic array synthesis (2000)
B. Ramakrishna Rau, Frédéric Vivien, Alain Darte, Alain Darte, Robert Schreiber, Robert Schreiber, ...
systolic array synthesis, affine scheduling © Copyright Hewlett-Packard Company 2000 We describe a new, practical, constructive method for solving the well-known conflict-free scheduling systolic...
A constructive solution to the juggling problem in systolic array synthesis. (1999)
Darte, Alain, Schreiber, Robert, Rau, B. Ramakrishna, Vivien, Frédéric
(eng) We describe a new, practical, constructive method for solving the well-known conflict-free scheduling problem for the locally sequential, globally parallel (LSGP) case of systolic array...
Loop Shifting for Loop Compaction (1999)
The idea of decomposed software pipelining is to decouple the software pipelining problem into a cyclic scheduling problem without resource constraints and an acyclic scheduling problem with resource...
The Nestor library: a tool for implementing Fortran source to source transformations (1999)
. We describe Nestor, a library to easily manipulate Fortran programs through a high level internal representation based on C++ classes. Nestor is a research tool that can be used to quickly...
Loop Shifting for Loop Compaction (1999)
Unit Mixte, Alain Darte, Alain Darte, Guillaume Huard, ...
The idea of decomposed software pipelining is to decouple the software pipelining problem into a cyclic scheduling problem without resource constraints and an acyclic scheduling problem with resource...
On the Complexity of Loop Fusion (1999)
Loop fusion is a program transformation that combines several loops into one. It is used in parallelizing compilers mainly for increasing the granularity of loops and for improving data reuse. The...
On the complexity of loop fusion. (1998)
(eng) Loop fusion is a program transformation that combines several loops into one. It is used in parallelizing compilers mainly for increasing the granularity of loops and for improving data reuse....
The Nestor library: a tool for implementing Fortran source to source transformations. (1998)
Silber, Georges-Andre, Darte, Alain
(eng) We describe Nestor, a library to easily manipulate Fortran programs through a high level internal representation based on C++ classes. Nestor is a research tool that can be used to quickly...
The Nestor library: a tool for implementing Fortran source to source transformations (1998)
École Normale, Supérieure Lyon, Georges-andré Silber, Alain Darte, Georges-andré Silber, Alain Darte, ...
Unité de recherche associée au CNRS n o 1398
SPI On the complexity of loop fusion (1998)
École Normale, Supérieure Lyon, École Normale, Supérieure Lyon, Alain Darte, Alain Darte
Loop fusion is a program transformation that combines several loops into one. It is used in parallelizing compilers mainly for increasing the granularity of loops and for improving data reuse. The...
Loop parallelization algorithms: From parallelism extraction to code generation (1998)
Pierre Boulet, Alain Darte, Georges-andr Silber
In this paper, we survey loop parallelization algorithms, analyzing the dependence representations they use, the loop transformations they generate, the code generation schemes they require, and...
Circuit Retiming Applied to Decomposed Software Pipelining (1998)
Pierre-Yves Calland, Alain Darte, Yves Robert
This paper elaborates on a new view on software pipelining, called decomposed software pipelining, and introduced by Gasperoni and Schwiegelshohn, and by Wang, Eisenbeis, Jourdan, and Su. The...
The Nestor library: a tool for implementing Fortran source to source transformations (1998)
Source Transformations, Georges-André Silber, Georges-andr Silber, Alain Darte, Alain Darte
We describe Nestor, a library to easily manipulate Fortran programs through a high level internal representation based on C++ classes. Nestor is a research tool that can be used to quickly implement...
On the Complexity of Loop Fusion (1998)
Unit Mixte, Alain Darte, Alain Darte
Loop fusion is a program transformation that combines several loops into one. It is used in parallelizing compilers mainly for increasing the granularity of loops and for improving data reuse. The...
Linear programming methods, optimizations on polytopes, manipulations of integral matrices, are now commonly used in the field of automatic parallelization, for example for detecting dependences,...
Circuit Retiming Applied to Decomposed Software Pipelining (1998)
Pierre-Yves Calland, Alain Darte, Yves Robert
This paper elaborates on a new view on software pipelining, called decomposed software pipelining, and introduced by Gasperoni and Schwiegelshohn, and by Wang, Eisenbeis, Jourdan, and Su. The...
Loop parallelization algorithms: From parallelism extraction to code generation (1998)
Pierre Boulet, Alain Darte, Georges-andre Silber, Frederic Vivien
In this paper, we survey loop parallelization algorithms, analyzing the dependence representations they use, the loop transformations they generate, the code generation schemes they require, and...
Loop parallelization algorithms : from parallelism extraction to code generation. (1997)
Boulet, Pierre, Darte, Alain, Silber, Georges-Andre, Vivien, Frédéric
(eng) In this paper, we survey loop parallelization algorithms, analyzing the dependence representations they use, the loop transformations they generate, the code generation schemes they require,...
Plugging Anti and Output Dependence Removal Techniques Into Loop Parallelization Algorithms (1997)
Frdric Vivien, Pierre-yves Call, Alain Darte, Alain Darte, Yves Robert, ...
: 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...
Plugging Anti and Output Dependence Removal Techniques Into Loop Parallelization Algorithms (1997)
Pierre-Yves Calland, Alain Darte, Yves Robert, Frédéric Vivien
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...
Plugging Anti and Output Dependence Removal Techniques into Loop Parallelization Algorithms (1997)
Pierre-yves Calland, Alain Darte, Yves Robert, Frederic Vivien, Eric Vivien
. 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...
Optimal Fine and Medium Grain Parallelism Detection in Polyhedral Reduced Dependence Graphs (1997)
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...
Loop Parallelization Algorithms: From Parallelism Extraction to Code Generation (1997)
Pierre Boulet, Alain Darte, Georges-André Silber, Frédéric Vivien
In this paper, we survey loop parallelization algorithms, analyzing the dependence representations they use, the loop transformations they generate, the code generation schemes they require, and...
Plugging Anti and Output Dependence Removal Techniques into Loop Parallelization Algorithms (1997)
Pierre-yves Calland, Alain Darte, Yves Robert, Frederic Vivien
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...
Brandes, Thomas, Chaumette, Serge, Counilh, Marie-Christine, Darte, Alain, Desprez, Frédéric, Mignot, Jean-Christophe, ...
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...
Combining retiming and scheduling techniques for loop parallelization and loop tiling. (1996)
Darte, Alain, Silber, Georges-Andre, Vivien, Frédéric
(eng) 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...
Plugging Anti and Output Dependence Removal Techniques into Loop Parallelization Algorithms (1996)
Calland, Pierre-Yves, Darte, Alain, Robert, Yves, Vivien, Frédéric
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...
On the Removal of Anti and Output Dependences (1996)
Calland, Pierre-Yves, Darte, Alain, Robert, Yves, Vivien, Frédéric
In this paper we build upon results of Padua and Wolfe~\cite{PaduaWo86}, who introduce two graph transformations to eliminate anti and output dependences. We first give a unified framework for such...
On the removal of anti and output dependences. (1996)
Calland, Pierre-Yves, Darte, Alain, Robert, Yves, Vivien, Frédéric
(eng) 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...
Darte, Alain, Vivien, Frédéric
(eng) 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...
Brandes, Thomas, Chaumette, Serge, Counilh, Marie-Christine, Darte, Alain, Desprez, Frédéric, Mignot, Jean-Christophe, ...
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...
Plugging Anti and Output Dependence Removal Techniques into Loop Parallelization Algorithms (1996)
Calland, Pierre-Yves, Darte, Alain, Robert, Yves, Vivien, Frédéric
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...
On the Removal of Anti and Output Dependences (1996)
Calland, Pierre-Yves, Darte, Alain, Robert, Yves, Vivien, Frédéric
In this paper we build upon results of Padua and Wolfe~\cite{PaduaWo86}, who introduce two graph transformations to eliminate anti and output dependences. We first give a unified framework for such...
Brandes, Thomas, Chaumette, Serge, Counilh, Marie-Christine, Darte, Alain, Desprez, Frédéric, Mignot, Jean-Christophe, ...
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...
Plugging Anti and Output Dependence Removal Techniques into Loop Parallelization Algorithms (1996)
Calland, Pierre-Yves, Darte, Alain, Robert, Yves, Vivien, Frédéric
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...
On the Removal of Anti and Output Dependences (1996)
Calland, Pierre-Yves, Darte, Alain, Robert, Yves, Vivien, Frédéric
In this paper we build upon results of Padua and Wolfe~\cite{PaduaWo86}, who introduce two graph transformations to eliminate anti and output dependences. We first give a unified framework for such...
On the removal of anti and output dependences (1996)
Ecole Normale, Supérieure Lyon, Alain Darte, Yves Robert, Frederic Vivien, Pierre-yves Calland, ...
Unité de recherche associée au CNRS n°1398 On the removal of anti and output dependences
for loop parallelization and loop tiling (1996)
Alain Darte, Georges-andre Silber, Frederic Vivien, Alain Darte, Georges-andre Silber, Frederic Vivien
Unité de recherche associée au CNRS n°1398 Combining retiming and scheduling techniques for loop parallelization and loop tiling
for parallelism extraction in nested loops (1996)
Ecole Normale, Supérieure Lyon, Alain Darte, Frederic Vivien, Alain Darte, Frederic Vivien, ...
Unité de recherche associée au CNRS n°1398 On the optimality ofAllenand Kennedy's algorithm for parallelism extraction in nested loops
A characterization of one-to-one modular mappings (1996)
Alain Darte, Michele Dion, Yves Robert, Alain Darte, Michele Dion, Yves Robert, ...
In this paper, we deal with modular mappings as introduced by LeeandFortes [14, 13, 12], and we build upon their results. Our main contribution is a characterization of one-to-one modular mappings...
On the optimality of Allen and Kennedy's algorithm for parallelism extraction in nested loops (1996)
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...
On the removal of anti and output dependences (1996)
Pierre-yves Calland, Alain Darte, Yves Robert
In this paper we build upon results of Padua and Wolfe [9], who introduced two graph transformations to break dependence paths including anti and output dependences. We first formalize these two...
Pierre Boulet, Alain Darte, Tanguy Risset, Yves Robert
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...
Combining Retiming and Scheduling Techniques for Loop Parallelization and Loop Tiling (1996)
Ecole Normale, Georges-André Silber, Frédéric Vivien, Suprieure Lyon, Alain Darte, Alain Darte
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...
On the Removal of Anti and Output Dependences (1996)
Ecole Normale, Suprieure Lyon, Pierre-yves Calland, Frédéric Vivien, Pierre-yves Calland, Alain Darte, ...
In this paper we build upon results of Padua and Wolfe [8], who introduce two graph transformations to eliminate anti and output dependences. We first give a unified framework for such...
Plugging Anti and Output Dependence Removal Techniques Into Loop Parallelization Algorithms (1996)
Ecole Normale, Suprieure Lyon, Pierre-yves Calland, Pierre-yves Calland, Alain Darte, Alain Darte, ...
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...
On the Removal of Anti and Output Dependences (1996)
In this paper we build upon results of Padua and Wolfe [9], who introduced two graph transformations to break dependence paths including anti and output dependences. We first formalize these two...
Combining Retiming and Scheduling Techniques for Loop Parallelization and Loop Tiling (1996)
Alain Darte, Georges-Andre Silber, Frederic Vivien, Eric Vivien, Communicated (name Of
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...
On the Removal of Anti and Output Dependences (1996)
Pierre-yves Calland, Alain Darte, Yves Robert, Frédéric Vivien
In this paper we build upon results of Padua and Wolfe [9], who introduced two graph transformations to break dependence paths including anti and output dependences. We rst formalize these two...
A New Guaranteed Heuristic for the Software Pipelining Problem (1995)
Calland, Pierre-Yves, Darte, Alain, Robert, Yves
We present yet another heuristic for the software pipelining problem. We believe this heuristic to be of interest because it brings a new insight to the software pipelining problem by establishing...
A new guaranteed heuristic for the software pipelining problem. (1995)
Calland, Pierre-Yves, Darte, Alain, Robert, Yves
(eng) We present yet another heuristic for the software pipelining problem. We believe this heuristic to be of interest because it brings a new insight to the software pipelining problem by...
A comparison of nested loops parallelization algorithms. (1995)
Darte, Alain, Vivien, Frédéric
(eng) In this paper, we compare three nested loops parallelization algorithms (Allen and Kennedy's algorithm, Wolf and Lam's algorithm and Darte and Vivien's algorithm) that use different...
A Characterization of One-to-One Modular Mappings. (1995)
Darte, Alain, Dion, Michèle, Robert, Yves
(eng) In this paper, we deal with modular mappings as introduced by Lee and Fortes, and we build upon their results. Our main contribution is a characterization of one-to-one modular mappings that is...
A New Guaranteed Heuristic for the Software Pipelining Problem (1995)
Calland, Pierre-Yves, Darte, Alain, Robert, Yves
We present yet another heuristic for the software pipelining problem. We believe this heuristic to be of interest because it brings a new insight to the software pipelining problem by establishing...
A New Guaranteed Heuristic for the Software Pipelining Problem (1995)
Calland, Pierre-Yves, Darte, Alain, Robert, Yves
We present yet another heuristic for the software pipelining problem. We believe this heuristic to be of interest because it brings a new insight to the software pipelining problem by establishing...
A new guaranteed heuristic for the software pipelining problem (1995)
Ecole Normale, Supérieure Lyon, Alain Darte, Yves Robert, Pierre-yves Calland, Alain Darte, ...
Unité de recherche associée au CNRS n°1398 A new guaranteed heuristic for the software pipelining problem
A New Guaranteed Heuristic for the Software Pipelining Problem (1995)
Ecole Normale, Suprieure Lyon, Pierre-yves Calland, Pierre-yves Calland, Alain Darte, Alain Darte, ...
We present yet another heuristic for the software pipelining problem. We believe this heuristic to be of interest because it brings a new insight to the software pipelining problem by establishing...
A New Guaranteed Heuristic for the Software Pipelining Problem (1995)
Pierre-yves Call, Alain Darte, Alain Darte, Yves Robert, Yves Robert
: We present yet another heuristic for the software pipelining problem. We believe this heuristic to be of interest because it brings a new insight to the software pipelining problem by establishing...
Affine-by-Statement Scheduling of Uniform and Affine Loop Nests over Parametric Domains (1995)
This paper deals with parallel scheduling techniques for uniform and affine loop nests. We deal with affine-by-statement scheduling, a powerful extension of Lamport's hyperplane method where...
Vincent Bouchitté, Pierre Boulet, Alain Darte, Yves Robert
This paper deals with the problem of evaluating HPF style array expressions on massively parallel distributed-memory computers (DMPCs). This problem has been addressed by Chatterjee et al. under the...
A comparison of nested loops parallelization algorithms (1995)
Ecole Normale, Supérieure Lyon, Alain Darte, Frederic Vivien, Alain Darte, Frederic Vivien, ...
Unité de recherche associée au CNRS n°1398 A comparison of nested loops parallelization algorithms
Automatic Parallelization Based on Multi-Dimensional Scheduling (1994)
Ecole Normale, Frédéric Vivien, Suprieure Lyon, Alain Darte, Alain Darte
In the scope of uniform recurrence equations, we study an algorithm first proposed by Karp, Miller and Winograd for detecting cycles of null weight in cyclic graphs. We show how this algorithm can be...
On The Alignment Problem (1994)
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...
Constructive Methods for Scheduling Uniform Loop Nests (1994)
This paper surveys scheduling techniques for loop nests with uniform dependences. First we introduce the hyperplane method and related variants. Then we extend it by using a different affine...
Affine-by-Statement Scheduling of Uniform Loop Nests over Parametric Domains (1993)
this report we deal with affine-by-statement scheduling, a high-level technique for the parallelization of loop nests with uniform dependences. Affineby -statement scheduling can be viewed as a...
Mapping Uniform Loop Nests onto Distributed Memory Architectures (1993)
This paper deals with scheduling, mapping and partitioning techniques for uniform loop nests. It is shown how the different techniques of scheduling, of mapping and of partitioning are linked and how...
Scheduling Uniform Loop Nests (1992)
This paper surveys scheduling techniques for uniform loop nests. First we introduce the hyperplane method and related variants. Then we extend it by using a different affine scheduling for each...
Affine-by-Statement Scheduling: Extensions for Affine Dependences and Several Parameters (1992)
Introduction This short report is a companion paper of the research report [1]. It cannot be read without it. We present here two extensions of affine-by-statement scheduling for loop nests. The...
Regular Partitioning for synthesizing fixed-size systolic arrays (1991)
Extending the projection method for the synthesis of systolic arrays, we present a procedure for the design of fixed-size systolic arrays using a technique called "locally sequential globally...
Regular Partitioning for synthesizing fixed-size systolic arrays (1991)
Extending the projection method for the synthesis of systolic arrays, we present a procedure for the design of fixed-size systolic arrays using a technique called "locally sequential globally...
Linear Scheduling Is Nearly Optimal (1991)
Alain Darte, Leonid Khachiyan, Yves Robert
This paper deals with the problem of finding optimal schedulings for uniform dependence algorithms. Given a convex domain, let T f be the total time needed to execute all computations using the free...
Linear Scheduling is Nearly Optimal (1991)
Alain Darte, Leonid Khachiyan, Yves Robert, Lyon Cedex
This paper deals with the problem of finding optimal schedulings for uniform dependence algorithms. Given a convex domain, let T f be the total time needed to execute all computations using the free...
Partitioning for Array Processors (1990)
Alain Darte, Jean-marc Delosme
This paper proposes a systematic method for mapping algorithms into fixed size array processors, in using the usual projection followed by a partioning. The paper is organised as following: section 2...