HeteroPar'07: List of accepted papers
 

 

Invited Talks:

Toni Cortes, Computer Architecture Department (DAC) in the Universitat Politècnica de Catalunya (UPC)

Title: Adapting RAID technology to large heterogeneous clusters
 
Abstract: Current clusters tend to have heterogeneous resources and storage
devices a no exception. Current high performance solutions to access data
such a RAID technology are not able to handle this heterogeneity in a nice
way. Thus new distribution algorithms have to be devised to use these
heterogeneous storage devices taking the most of their potential. In
addition, these distribution algorithms have to be easy to use and also need
to be scalable, meaning that the addition of more storage resources to the
cluster does not imply a redistribution of all data as would happen in most
RAID technologies.

Yves Robert, LIP, ENS Lyon

Title: Algorithms for heterogeneous platforms.

Abstract: In this talk we provide several examples to
illustrate key algorithmic concepts required to efficiently
execute applications on heterogeneous clusters and grids.

The idea is to give a lively exposition of the necessity to
inject whatever static knowledge is available into the design
of typical applications, such as master-slave tasking,
numerical kernels, and job workflows. We claim that this is the
key to an efficient deployment of these applications onto
large-scale distributed computational platforms.

The talk will proceed through examples to explain how to cope
with resource selection, memory constraints, platform
heterogeneity, etc. 

 

Regular Talks:

 

Anne Benoit and Yves Robert. Complexity Results for Throughput and Latency Optimization of Replicated and Data-parallel Workflows

Anne Benoit, Veronika Rehn-Sonigo and Yves Robert. Multi-criteria scheduling of pipeline workflows

Laurent Choy, Serge Petiton and Mitsuhisa Sato. Toward power-aware computing with Dynamic Voltage Scaling for heterogeneous Grid

Werner Mach and Erich Schikuta. Performance Analysis of Parallel Database Sort Operations in a Heterogenous Grid Environment

Jacques-Mohcine Bahi, Jean-Claude Charr, raphaël couturier and David Laiymani. A Parallel  Algorithm to  Solve  Large Stiff  ODE  Systems on Grid Systems

Louis-Claude Canon and Emmanuel Jeannot. A Comparison of Robustness Metrics for Scheduling DAGs on Heterogeneous Systems

Francisco Jose Martinez Zaldivar, Antonio M. Vidal and Domingo Gimenez. A pipelined parallel OSIC algorithm based on the square root Kalman filter for heterogeneous networks

Alexey Lastovetsky and Vladimir Rychkov. Building the communication performance model of heterogeneous clusters based on a switched network

Sascha Hunold, Thomas Rauber and Gudula Rünger. Dynamic Scheduling of Multi-Processor Tasks on Clusters of Clusters

 

List of Abstracts
 

Anne Benoit and Yves Robert. Complexity Results for Throughput and Latency Optimization of Replicated and Data-parallel Workflows

Abstract: Mapping applications onto parallel platforms is a challenging problem,
even for simple application patterns such as pipeline or fork
graphs. Several antagonist criteria should be optimized for workflow
applications, such as throughput and latency (or a combination).
In this paper, we consider a simplified model with no communication cost,
and we provide an exhaustive list of complexity results for different
problem instances.
Pipeline or fork stages can be replicated in order to
increase the throughput of the workflow, by sending consecutive
data sets onto different processors. In some cases, stages can
also be data-parallelized, i.e. the computation of one single data set
is shared between several processors. This leads to a decrease of the
latency and an increase of the throughput.
Some instances of this simple model
are shown to be NP-hard, thereby
exposing the inherent complexity of the mapping problem.
We provide polynomial
algorithms for other problem instances. Altogether, we provide solid
theoretical foundations for the study of mono-criterion or bi-criteria
mapping optimization problems.

 

Anne Benoit, Veronika Rehn-Sonigo and Yves Robert. Multi-criteria scheduling of pipeline workflows

Abstract: Mapping workflow applications onto parallel platforms is a challenging
problem, even for simple application patterns such as pipeline graphs.
Several antagonist criteria should be optimized, such as throughput and
latency (or a combination). In this paper, we study the complexity of
the bi-criteria mapping problem for pipeline graphs on communication
homogeneous platforms. In particular, we assess the complexity of the
well-known chains-to-chains problem for different-speed processors,
which turns out to be NP-hard.
We provide several efficient polynomial bi-criteria heuristics, and
their relative performance is assessed through simulation.

 

Laurent Choy, Serge Petiton and Mitsuhisa Sato. Toward power-aware computing with Dynamic Voltage Scaling for heterogeneous Grid

Abstract: Energy conservation is a dynamic topic of research in High Performance Computing and Cluster Computing. Power-aware computing for heterogeneous world-wide Grid is a new track of research. In this work, we study and evaluate the impact of the heterogeneity of the computing  nodes of a Grid platform on the energy consumption. We propose to take advantage of the slack-time caused by the heterogeneity in order to save energy with no significant loss of performance by using Dynamic Voltage Scaling (DVS) in a distributed eigensolver. We show that using DVS only  during the slack-time does not penalize the performances but it does not provide significant energy savings. If DVS is applied to all the execution, we get important global and local energy savings (respectively up to 9% and 20%) without a significant rise of the wall-clock times.

 

Werner Mach and Erich Schikuta. Performance Analysis of Parallel Database Sort Operations in a Heterogenous Grid Environment

Abstract: This paper presents an analytical comparison of parallel sort algorithms in a generalized multiprocessor framework and a simplified, heterogenous Grid Environment.

Based on the well renowned method of Bitton et al. we develop a concise but comprehensive analytical model for the well-known Binary Merge Sort and Bitonic Sort algorithm.

We concentrate on a limited number of characteristic parameters to keep the
analytical model clear and focused. We justify that a meaningful  model can be built
upon only three characteristic parameter sets, describing node processing
performance, the I/O and the disk bandwidth, which are the parameters for the
optimization the Grid workflow by a smart brokerage mechanism. Based on these
results the paper proves that by a smart enhancement of the algorithms exploiting
the specifics of the Grid the well-known results of Bitton et al. for a homogenous
multi-processor architecture are to be invalidated and reversed for a heterogenous Grid environment.

 

Jacques-Mohcine Bahi, Jean-Claude Charr, raphaël couturier and David Laiymani. A Parallel  Algorithm to  Solve  Large Stiff  ODE  Systems on Grid Systems

Abstract: This paper introduces a parallel  algorithm to solve large stiff ODE systems
in a geographically distant cluster environment. This algorithm is based on the
coupling of the Waveform Relaxation  concept and the CVODE algorithm. With respect  to the standard PVODE  algorithm, it
allows to drastically reduce the number of messages exchanged between nodes.  It
is  a  coarse  grained  algorithm  well suited  for  distant  grid  environments
connected  via  high  latency networks.  In  this  paper  our work  consists  in
analyzing the  execution times taken by  the PVODE solver and  our algorithm
and in explaining the benefits brought by this work.

 

Louis-Claude Canon and Emmanuel Jeannot. A Comparison of Robustness Metrics for Scheduling DAGs on Heterogeneous Systems

Abstract: A schedule is said robust if it is able to absorb some degree of uncertainty in tasks duration while maintaining a stable solution. This intuitive notion of robustness has led to a lot of different interpretations and metrics. However, no comparison of these different metrics have ever been preformed. In this paper, we perform an experimental study of these different metrics and show how they are correlated to each other in the case of task scheduling, with dependencies between tasks.

 

Francisco Jose Martinez Zaldivar, Antonio M. Vidal and Domingo Gimenez. A pipelined parallel OSIC algorithm based on the square root Kalman filter for heterogeneous networks

Abstract: This paper describes a pipelined parallel algorithm for the Ordered Succesive Interference Cancellation
(OSIC) decoding procedure proposed in V-BLAST wireless MIMO systems. It is based
on an algorithm that solves the Recursive Least Squares (RLS) problem, and is derived from a block version of the square root version of the Kalman filter.
It has been parallelized in a pipelined way getting a good efficiency
in a heterogeneous network of computers.
The  pipeline organization of the parallel algorithm is an unidirectional and unidimensional graph, as a daisy chain network, specially suitable in
a heterogeneous environment, allowing to get a high degree of scalability in the parallel system.
Although the optimum load balance for this algorithm is dynamic, we derive a static load balance scheme with good results.

 

Alexey Lastovetsky and Vladimir Rychkov. Building the communication performance model of heterogeneous clusters based on a switched network

Abstract: Analytical communication performance models play an important role in prediction of the execution time of parallel applications on multiprocessors. Apart from designing such a model, accurate estimation of the values of its parameters is one of the main issues. This paper deals with a heterogeneous analytical communication model designed for prediction of MPI communications on heterogeneous clusters based on a switched network. Accurate estimation of the parameters of this model is a particularly challenging task due to a large number of the parameters. In this paper, we present a solution of the task based on a carefully designed set of communication experiments, which not only allows us to obtain the accurate estimation of the parameters but also tries to minimise the total execution time of the experiments. Experiments demonstrating the accuracy and efficiency of the proposed solution are also presented.

 

Sascha Hunold, Thomas Rauber and Gudula Rünger. Dynamic Scheduling of Multi-Processor Tasks on Clusters of Clusters

Abstract: Using a mixed-parallel approach for designing parallel applications
  often leads to faster execution times than using a pure
  data-parallel paradigm. A mixed-parallel application consists of
  tasks which can be executed concurrently and these tasks can be
  implemented in a data-parallel way. A task which is assigned to a
  number of available processors is called a multi-processor tasks
  (M-tasks).  A mixed-parallel program which consists of M-tasks can
  be represented by a direct acyclic graph (DAG) where the edges
  denote data dependencies between the M-tasks.
  
  Scheduling such DAGs onto clusters of clusters or grid environments
  is a challenging task. Most approaches to mixed-parallel task
  scheduling assume that the entire DAG is known beforehand. However,
  in practice the DAG might be generated only at runtime, e.g.
  depending on the internal state an M-tasks may generate a different
  number of children.
  
  In this article we tackle the problem of scheduling a dynamically
  generated DAG of M-tasks. At first, we outline the need of such a
  scheduling approach in the context of TGrid. Then, we propose a
  dynamic scheduling algorithm called Reuse Processors Algorithm
  (RePA). The main objective of RePA is to reduce the redistribution
  costs by reusing as many parent processors as possible during
  assignment step. The algorithm was implemented using the SimGrid toolkit
  and is evaluated by comparing the makespan of the schedules produced
  by RePA and M-HEFT.