Assessing Contention Effects of All-to-All Communications on Clusters and Grids (2008)
Steffenel, Luiz Angelo, Martinasso, Maxime, Trystram, Denis
One of the most important collective communication patterns used in scientific applications is the complete exchange, also called All-to-All. Although efficient algorithms have been studied for...
Assessing Contention Effects of All-to-All Communications on Clusters and Grids (2008)
Steffenel, Luiz Angelo, Martinasso, Maxime, Trystram, Denis
One of the most important collective communication patterns used in scientific applications is the complete exchange, also called All-to-All. Although efficient algorithms have been studied for...
Dumitrescu, Bogdan, Doreille, Mathias, Roch, Jean-Louis, Trystram, Denis
This paper presents a discussion on 2D block mappings for the sparse Cholesky factorization on parallel MIMD architectures with distributed memory. It introduces the fan-in algorithm in a general...
Dumitrescu, Bogdan, Doreille, Mathias, Roch, Jean-Louis, Trystram, Denis
This paper presents a discussion on 2D block mappings for the sparse Cholesky factorization on parallel MIMD architectures with distributed memory. It introduces the fan-in algorithm in a general...
Adaptive and Hybrid Algorithms: classification and illustration on triangular system solving (2008)
Cung, Van-Dat, Danjean, Vincent, Dumas, Jean-Guillaume, Gautier, Thierry, Huard, Guillaume, Raffin, Bruno, ...
We propose in this article a classification of the different notions of hybridization and a generic framework for the automatic hybridization of algorithms. Then, we detail the results of this...
Adaptive and Hybrid Algorithms: classification and illustration on triangular system solving (2008)
Cung, Van-Dat, Danjean, Vincent, Dumas, Jean-Guillaume, Gautier, Thierry, Huard, Guillaume, Raffin, Bruno, ...
We propose in this article a classification of the different notions of hybridization and a generic framework for the automatic hybridization of algorithms. Then, we detail the results of this...
Construction d'un modèle mathématique des contraintes s'excerçant sur un annulaire de ciment dans un puits de pétrole. Obtention d'un grand système linéaire creux à matrice symétrique...
Construction d'un modèle mathématique des contraintes s'excerçant sur un annulaire de ciment dans un puits de pétrole. Obtention d'un grand système linéaire creux à matrice symétrique...
Construction d'un modèle mathématique des contraintes s'excerçant sur un annulaire de ciment dans un puits de pétrole. Obtention d'un grand système linéaire creux à matrice symétrique...
Construction d'un modèle mathématique des contraintes s'excerçant sur un annulaire de ciment dans un puits de pétrole. Obtention d'un grand système linéaire creux à matrice symétrique...
A 3/2-Dual Approximation Algorithm for Scheduling Independent Monotonic Malleable Tasks (2008)
Mounié, Grégory, Rapine, Christophe, Trystram, Denis
A malleable task is a computational unit which may be executed on any arbitrary number of processors whose execution time depends on the amount of resources alloted to is. This paper presents a new...
A 3/2-Dual Approximation Algorithm for Scheduling Independent Monotonic Malleable Tasks (2008)
Mounié, Grégory, Rapine, Christophe, Trystram, Denis
A malleable task is a computational unit which may be executed on any arbitrary number of processors whose execution time depends on the amount of resources alloted to is. This paper presents a new...
Adaptive Approaches for Efficient Parallel Algorithms on Cluster-based Systems (2008)
Nasri, Wahid, Steffenel, Luiz Angelo, Trystram, Denis
Few years ago, there was a huge development of new parallel and distributed systems. Due to many reasons, such as the inherent heterogeneity, the diversity, and the continuous evolution of such...
Adaptive Approaches for Efficient Parallel Algorithms on Cluster-based Systems (2008)
Nasri, Wahid, Steffenel, Luiz Angelo, Trystram, Denis
Few years ago, there was a huge development of new parallel and distributed systems. Due to many reasons, such as the inherent heterogeneity, the diversity, and the continuous evolution of such...
Analysis of Scheduling Algorithms with Reservations (2007)
Eyraud-Dubois, Lionel, Mounié, Grégory, Trystram, Denis
In this work, we analyze the problem of scheduling a set of independent jobs on a homogeneous parallel computer. This problem has been widely studied from both a theoretical perspective (complexity...
Analysis of Scheduling Algorithms with Reservations (2007)
Eyraud-Dubois, Lionel, Mounié, Grégory, Trystram, Denis
In this work, we analyze the problem of scheduling a set of independent jobs on a homogeneous parallel computer. This problem has been widely studied from both a theoretical perspective (complexity...
Dynamic Load Balancing for Adaptive Mesh Ocean Circulation Model (2007)
Blayo, Eric, Debreu, Laurent, Mounié, Grégory, Trystram, Denis
This paper reports the parallel implementation of adaptive mesh refinement within finite difference ocean circulation models. The implementation is based on the model of Malleable Tasks with...
1-optimality of static BSP computations: scheduling independent chains as a case study (2007)
Goldman, Alfredo, Mounié, Grégory, Trystram, Denis
The aim of this work is to study a specific scheduling problem under the machine-independent model BSP. The problem of scheduling a set of independent chains in this context is shown to be a...
Dynamic Load Balancing for Adaptive Mesh Ocean Circulation Model (2007)
Blayo, Eric, Debreu, Laurent, Mounié, Grégory, Trystram, Denis
This paper reports the parallel implementation of adaptive mesh refinement within finite difference ocean circulation models. The implementation is based on the model of Malleable Tasks with...
1-optimality of static BSP computations: scheduling independent chains as a case study (2007)
Goldman, Alfredo, Mounié, Grégory, Trystram, Denis
The aim of this work is to study a specific scheduling problem under the machine-independent model BSP. The problem of scheduling a set of independent chains in this context is shown to be a...
Scheduling on Large Scale Distributed Platforms: From Models to Implementations (2007)
Dutot, Pierre-François, Eyraud, Lionel, Mounié, Grégory, Trystram, Denis
In this paper, we will investigate two complementary computational models that have been proposed recently: Parallel Task (PT) and Divisible Load (DL). The Parallel Task (i.e. tasks that require more...
Scheduling on Large Scale Distributed Platforms: From Models to Implementations (2007)
Dutot, Pierre-François, Eyraud, Lionel, Mounié, Grégory, Trystram, Denis
In this paper, we will investigate two complementary computational models that have been proposed recently: Parallel Task (PT) and Divisible Load (DL). The Parallel Task (i.e. tasks that require more...
Adaptive Performance Modeling on Hierarchical Grid Computing Environments (2007)
Nasri, Wahid, Steffenel, Luiz Angelo, Trystram, Denis
In the past, efficient parallel algorithms have always been developed specifically for the successive generations of parallel systems (vector machines, shared-memory machines, distributed-memory...
Assessing Contention Effects on MPI_Alltoall Communications (2007)
Steffenel, Luiz Angelo, Martinasso, Maxime, Trystram, Denis
One of the most important collective communication patterns used in scientific applications is the complete exchange, also called All-to-All. Although efficient algorithms have been studied for...
Adaptive Performance Modeling on Hierarchical Grid Computing Environments (2007)
Nasri, Wahid, Steffenel, Luiz Angelo, Trystram, Denis
In the past, efficient parallel algorithms have always been developed specifically for the successive generations of parallel systems (vector machines, shared-memory machines, distributed-memory...
Assessing Contention Effects on MPI_Alltoall Communications (2007)
Steffenel, Luiz Angelo, Martinasso, Maxime, Trystram, Denis
One of the most important collective communication patterns used in scientific applications is the complete exchange, also called All-to-All. Although efficient algorithms have been studied for...
Kubiak, Wieslaw, Penz, Bernard, Trystram, Denis
Nous montrons dans ce rapport que le problème qui consiste à ordonnancer un ensemble de chaines de taches unitaires indépendantes sur une machine parallèle à processeurs uniformes est...
Kubiak, Wieslaw, Penz, Bernard, Trystram, Denis
Nous montrons dans ce rapport que le problème qui consiste à ordonnancer un ensemble de chaines de taches unitaires indépendantes sur une machine parallèle à processeurs uniformes est...
Scheduling Moldable Tasks for Dynamic {SMP} Clusters in {S}o{C} Technology (2006)
Masko, Lukasz, Dutot, Pierre-François, Mounié, Grégory, Trystram, Denis, Tudruj, Marek
The paper presents an algorithm for scheduling parallel programs for execution in a parallel architecture based on dynamic SMP processor clusters with data transfers on the fly. The algorithm is...
A best-compromise bicriteria scheduling algorithm for malleable tasks (2006)
Dutot, Pierre-François, Trystram, Denis
We consider in this paper the problem of scheduling a set of inde- pendent parallel tasks (jobs) with respect to two criteria, namely, the makespan (time of the last finishing job) and the minsum...
Scheduling on hierarchical clusters using malleable tasks (2006)
Dutot, Pierre-François, Trystram, Denis
The model of malleable task (MT) was introduced some years ago and has been proved to be an efficient way for implementing parallel applications. It considers a target application at a larger level...
Scheduling Moldable Tasks for Dynamic {SMP} Clusters in {S}o{C} Technology (2006)
Masko, Lukasz, Dutot, Pierre-François, Mounié, Grégory, Trystram, Denis, Tudruj, Marek
The paper presents an algorithm for scheduling parallel programs for execution in a parallel architecture based on dynamic SMP processor clusters with data transfers on the fly. The algorithm is...
A best-compromise bicriteria scheduling algorithm for malleable tasks (2006)
Dutot, Pierre-François, Trystram, Denis
We consider in this paper the problem of scheduling a set of inde- pendent parallel tasks (jobs) with respect to two criteria, namely, the makespan (time of the last finishing job) and the minsum...
Scheduling on hierarchical clusters using malleable tasks (2006)
Dutot, Pierre-François, Trystram, Denis
The model of malleable task (MT) was introduced some years ago and has been proved to be an efficient way for implementing parallel applications. It considers a target application at a larger level...
Scheduling Moldable Tasks for Dynamic {SMP} Clusters in {S}o{C} Technology (2005)
Masko, Lukasz, Dutot, Pierre-François, Mounié, Grégory, Trystram, Denis, Tudruj, Marek
Abstract. The paper presents an algorithm for scheduling parallel programs for execution in a parallel architecture based on dynamic SMP processor clusters with data transfers on the fly. The...
A best-compromise bicriteria scheduling algorithm for malleable tasks (2005)
Dutot, Pierre-François, Trystram, Denis
We consider in this paper the problem of scheduling a set of inde- pendent parallel tasks (jobs) with respect to two criteria, namely, the makespan (time of the last finishing job) and the minsum...
Bi-criteria Algorithm for Scheduling Jobs on Cluster Platforms (2005)
Dutot, Pierre-Francois, Eyraud, Lionel, Mounié, Grégory, Trystram, Denis
We describe in this paper a new method for building an efficient algorithm for scheduling jobs in a cluster. Jobs are considered as parallel tasks (PT) which can be scheduled on any number of...
An Approximation algorithm for scheduling Trees of Malleable Tasks (2005)
Lepère, Renaud, Mounié, Grégory, Trystram, Denis
This work presents an approximation algorithm for scheduling the tasks of a parallel application. These tasks are considered as malleable tasks (MT in short), which means that they can be executed on...
Dynamic Load Balancing for Ocean Circulation Model with Adaptive Meshing (2005)
Blayo, Eric, Debreu, Laurent, Mounié, Grégory, Trystram, Denis
This paper reports the parallel implementation of adaptive mesh refinement within finite difference ocean circulation models. The implementation is based on the model of {\it Malleable Tasks} with...
Dynamic Load Balancing for Ocean Circulation Model with Adaptive Meshing (2005)
Blayo, Eric, Debreu, Laurent, Mounié, Grégory, Trystram, Denis
This paper reports the parallel implementation of adaptive mesh refinement within finite difference ocean circulation models. The implementation is based on the model of {\it Malleable Tasks} with...
Bi-criteria Algorithm for Scheduling Jobs on Cluster Platforms (2005)
Dutot, Pierre-Francois, Eyraud, Lionel, Mounié, Grégory, Trystram, Denis
We describe in this paper a new method for building an efficient algorithm for scheduling jobs in a cluster. Jobs are considered as parallel tasks (PT) which can be scheduled on any number of...
An Approximation algorithm for scheduling Trees of Malleable Tasks (2005)
Lepère, Renaud, Mounié, Grégory, Trystram, Denis
This work presents an approximation algorithm for scheduling the tasks of a parallel application. These tasks are considered as malleable tasks (MT in short), which means that they can be executed on...
SCHEDULING ON LARGE SCALE DISTRIBUTED PLATFORMS: FROM MODELS TO IMPLEMENTATIONS (2005)
Dutot, Pierre-François, Eyraud, Lionel, Mounié, Grégory, Trystram, Denis
In this paper, we will investigate two complementary computational models that have been proposed recently: Parallel Task (PT) and Divisible Load (DL). The Parallel Task (i.e. tasks that require more...
SCHEDULING ON LARGE SCALE DISTRIBUTED PLATFORMS: FROM MODELS TO IMPLEMENTATIONS (2005)
Dutot, Pierre-François, Eyraud, Lionel, Mounié, Grégory, Trystram, Denis
In this paper, we will investigate two complementary computational models that have been proposed recently: Parallel Task (PT) and Divisible Load (DL). The Parallel Task (i.e. tasks that require more...
Models for scheduling on large scale platforms: which policy for which application? (2004)
Dutot, Pierre-Francois, Eyraud, Lionel, Mounié, Grégory, Trystram, Denis
In the recent years, there was a huge development of low cost large scale parallel systems. The design of efficient parallel algorithms has to be reconsidered by the influence of new parameters of...
Scheduling Parallel Tasks: Approximation Algorithms (2004)
Dutot, Pierre-Francois, Mounié, Grégory, Trystram, Denis
Scheduling is a crucial problem in parallel and distributed processing. It consists of determining where and when the tasks of parallel programs will be executed. The design of parallel algorithms...
Scheduling Parallel Tasks: Approximation Algorithms (2004)
Dutot, Pierre-Francois, Mounié, Grégory, Trystram, Denis
Scheduling is a crucial problem in parallel and distributed processing. It consists of determining where and when the tasks of parallel programs will be executed. The design of parallel algorithms...
Models for scheduling on large scale platforms: which policy for which application? (2004)
Dutot, Pierre-Francois, Eyraud, Lionel, Mounié, Grégory, Trystram, Denis
In the recent years, there was a huge development of low cost large scale parallel systems. The design of efficient parallel algorithms has to be reconsidered by the influence of new parameters of...
Efficient Approximation Algorithms for Scheduling Malleable Tasks (2004)
Mounié, Grégory, Rapine, Christophe, Trystram, Denis
A malleable task is a computational unit which may be executed on any arbitrary number of processors, its execution time depend- ing on the amount of resources allotted to it. According to the...
Efficient Approximation Algorithms for Scheduling Malleable Tasks (2004)
Mounié, Grégory, Rapine, Christophe, Trystram, Denis
A malleable task is a computational unit which may be executed on any arbitrary number of processors, its execution time depend- ing on the amount of resources allotted to it. According to the...
Bi-criteria Algorithm for Scheduling Jobs on Cluster Platforms (2004)
Dutot, Pierre-Francois, Eyraud, Lionel, Mounié, Grégory, Trystram, Denis
We describe in this paper a new method for building an efficient algorithm for scheduling jobs in a cluster. Jobs are considered as parallel tasks (PT) which can be scheduled on any number of...
Bi-criteria Algorithm for Scheduling Jobs on Cluster Platforms (2004)
Dutot, Pierre-Francois, Eyraud, Lionel, Mounié, Grégory, Trystram, Denis
We describe in this paper a new method for building an efficient algorithm for scheduling jobs in a cluster. Jobs are considered as parallel tasks (PT) which can be scheduled on any number of...
Models for scheduling on large scale platforms: which policy for which application? (2004)
Dutot, Pierre-Francois, Eyraud, Lionel, Mounié, Grégory, Trystram, Denis
In the recent years, there was a huge development of low cost large scale parallel systems. The design of efficient parallel algorithms has to be reconsidered by the influence of new parameters of...
Bi-criteria Algorithm for Scheduling Jobs on Cluster Platforms (2004)
Dutot, Pierre-Francois, Eyraud, Lionel, Mounié, Grégory, Trystram, Denis
We describe in this paper a new method for building an efficient algorithm for scheduling jobs in a cluster. Jobs are considered as parallel tasks (PT) which can be scheduled on any number of...
Models for scheduling on large scale platforms: which policy for which application? (2004)
Dutot, Pierre-Francois, Eyraud, Lionel, Mounié, Grégory, Trystram, Denis
In the recent years, there was a huge development of low cost large scale parallel systems. The design of efficient parallel algorithms has to be reconsidered by the influence of new parameters of...
Scheduling UET Trees with Communication Delays on Two Processors (2003)
In this paper, we present a new linear time algorithm for scheduling uect (Unit Execution and Communication Time) trees on two identical processors: CBoS (clusters based on subtrees). The chosen...
Some Models for Scheduling Parallel Programs with (2003)
Evripidis Bampis, Denis Trystram
The aim of this paper is to present and analyze models for designing parallel programs. In the context of some extensions of the most popular execution models (precedence graphs, dataflow, PRAM), we...
Construction of Phylogenetic Trees on parallel (2003)
Gilles Parmentier, Denis Trystram
A novel approach for the construction of phylogenetic trees on large parallel clusters of PC is presented in this work. Computation of multiple alignment of biological sequences and phylogenetic tree...
Scheduling a Divisible Task in a 2-Dimensional Toroidal Mesh (2003)
Maciej Drozdowski, Denis Trystram
In this paper, a problem of scheduling an arbitrarily divisible task is considered. Taking into account both communication delays and computation time we propose a scheduling method which minimizes...
Scheduling Parallel Tasks: Approximation Algorithms (2003)
Dutot, Pierre-Francois, Mounié, Grégory, Trystram, Denis
Scheduling is a crucial problem in parallel and distributed processing. It consists of determining where and when the tasks of parallel programs will be executed. The design of parallel algorithms...
Scheduling Parallel Tasks: Approximation Algorithms (2003)
Dutot, Pierre-Francois, Mounié, Grégory, Trystram, Denis
Scheduling is a crucial problem in parallel and distributed processing. It consists of determining where and when the tasks of parallel programs will be executed. The design of parallel algorithms...
Scheduling on hierarchical clusters using Malleable Tasks (2002)
The model of malleable task (MT) was introduced some years ago and has been proved to be an efficient way for implementing parallel applications. It considers a target application at a larger level...
Exchanging Messages of Different Sizes (2002)
Alfredo Goldman, Rua Do Matao, Joseph G. Peters, Denis Trystram
This paper deals with the study of the exchange of messages among a set of processors linked through an interconnection network. We focus on general, non-uniform versions of message exchange problems...
1-optimality of static BSP computations: scheduling independent chains as a case study (2002)
Alfredo Goldman, Gregory Mounie, Denis Trystram
The aim of this work is to study a specific scheduling problem under the machine-independent model BSP. The problem of scheduling a set of independent chains in this context is shown to be a...
Near optimal algorithms for scheduling independent chains in BSP (2002)
Alfredo Goldman, Gregory Mouni E, Denis Trystram
The aim of this work is to show that scheduling a set of independent chains on a parallel machine under the BSP model is a difficult optimization problem which can be easily approximated in practice....
Dynamic Load Balancing for Ocean Circulation Model with Adaptive Meshing (2002)
Eric Blayo, Laurent Debreu, Denis Trystram
This paper reports the parallel implementation of adaptive mesh refinement within finite difference ocean circulation models. The implementation is based on the model of Malleable Tasks with...
Dynamic Load Balancing for Adaptive Mesh Ocean Circulation Model (2002)
Eric Blayo, Laurent Debreu, Denis Trystram
This paper reports the parallel implementation of adaptive mesh refinement within finite difference ocean circulation models. The implementation is based on the model of Malleable Tasks with...
Efficient Approximation Algorithms for Scheduling Malleable Tasks (2002)
Gregory Mounie, Christophe Rapine, Denis Trystram
A malleable task is a computational unit which may be executed on any arbitrary number of processors, its execution time depending on the amount of resources allotted to it. According to the standard...
An Approximation Algorithm for Scheduling Trees of Malleable Tasks (2002)
This work presents an approximation algorithm for scheduling the tasks of a parallel application. These tasks are considered as malleable tasks (MT in short), which means that they can be executed on...
Malleable Tasks: An Efficient Model For Solving Actual Parallel Applications (2001)
Renaud Lepere, Gregory Mounie, Denis Trystram, Borut Robi C
The purpose of this paper is to promote the model of Malleable Tasks for efficiently solving actual parallel applications. Malleable Tasks are presented and discussed in regard to other classical...
Approximation Algorithms for Scheduling Malleable Tasks Under Precedence Constraints (2001)
Renaud Lep Ere, Denis Trystram, Gerhard J. Woeginger
This work presents approximation algorithms for scheduling the tasks of a parallel application that are subject to precedence constraints. The considered tasks are malleable which means that they can...
Approximation Algorithms for Scheduling Malleable Tasks Under Precedence Constraints (2001)
Denis Trystram, Gerhard J. Woeginger
This work presents approximation algorithms for scheduling the tasks of a parallel application that are subject to precedence constraints. The considered tasks are malleable which means that they may...
Scheduling on hierarchical clusters using malleable tasks (2001)
Dutot, Pierre-François, Trystram, Denis
The model of malleable task (MT) was introduced some years ago and has been proved to be an efficient way for implementing parallel applications. It considers a target application at a larger level...
Phase-by-Phase Schedules for identical Malleable Tasks (2001)
sive layers with a global synchronization. If we restrict to identical MT, the problem is in O(nm) and we may nd the optimal solution with an algorithm using dynamic programming techniques. We can...
A 3/2-Dual Approximation Algorithm for Scheduling Independent Monotonic Malleable Tasks (2001)
Mounié, Grégory, Rapine, Christophe, Trystram, Denis
A malleable task is a computational unit which may be executed on any arbitrary number of processors whose execution time depends on the amount of resources alloted to is. This paper presents a new...
A 3/2-Dual Approximation Algorithm for Scheduling Independent Monotonic Malleable Tasks (2001)
Mounié, Grégory, Rapine, Christophe, Trystram, Denis
A malleable task is a computational unit which may be executed on any arbitrary number of processors whose execution time depends on the amount of resources alloted to is. This paper presents a new...
Dynamic Load Balancing for Adaptive Mesh Ocean Circulation Model (2000)
Blayo, Eric, Debreu, Laurent, Mounié, Grégory, Trystram, Denis
This paper reports the parallel implementation of adaptive mesh refinement within finite difference ocean circulation models. The implementation is based on the model of Malleable Tasks with...
An Approximation algorithm for scheduling Trees of Malleable Tasks (2000)
Lepère, Renaud, Mounié, Grégory, Trystram, Denis
This work presents an approximation algorithm for scheduling the tasks of a parallel application. These tasks are considered as malleable tasks (MT in short), which means that they can be executed on...