Tous les exposés (et les repas) auront lieu au Labri (salle
178).
Quelques renseignements
pratiques
Le texte de la proposition d'Alpage est ici
15h30-15h45: pause
15h45-16h15 Cyril Gavoille (travail joint avec A. Labourel):
Distributed
Relationship Schemes for Trees
Nous présenterons une structure de données distribuées pour les arbres
supportant des requêtes entre sommets proches (à distance bornée). Alstrup,
Bille et Rauhe (SODA'03) ont proposé schéma de construction, et ont montré
l'intérêt de ces représentations pour les moteurs de recherche dans les bases de
données XML. Nous apporterons ici une amélioration à leur schéma.
16h15-16h45: Anne Benoit
(ENS Lyon): Scheduling
pipeline workflows to optimize throughput, latency and reliability
16h45-17h: pause
17h-17h30 Olivier Beaumont Nicolas
Bonichon Lionel Eyraud-Dubois(LaBRI):
Scheduling Divisible Tasks under Bounded
Multi-Port Model
In this paper, we discuss complexity issues for scheduling
divisible workloads on heterogeneous systems under the bounded multi-port model.
To our best knowledge, this paper is the first attempt to consider divisible
load scheduling
under a realistic communication model, where the master node can communicate
simultaneously to several slaves, provided that bandwidth constraints are not
exceeded. In this paper,
we concentrate on one round distribution schemes, where a given node starts its
processing only once all data has been received. Our main contributions
are (i) the proof that processors start working immediately after receiving
their work (ii) the study of the optimal schedule in the case of 2 processors
and (iii) the
proof that scheduling divisible load under the bounded multi-port model is
NP-complete. This last result strongly differs from divisible load literature
and represents the first
NP-completeness result when latencies are not taken into account.
17h30-18h: Ruslan Sadykov (LIX): Scheduling Malleable Jobs on 2 machines
Abstract : "Malleable jobs is a special type of the parallel jobs which
can be executed on more than one processor at the same time. A
particularity of the malleable jobs is that the number of processors a
job is executed on may change during the execution. With the emergence
of new production, communication and parallel computing system, the
usual scheduling requirement that a job is executed only on one
processor has become, in many cases, obsolete and unfounded. Therefore,
parallel jobs scheduling is becoming more and more widespread.
In the talk, we concentrate on the problem of scheduling malleable jobs
to minimize mean flow time. An algorithm for the 2-machine case and a
dominance property for the general case will be presented."
Scheduling problems are
already difficult on traditional parallel
machines. They become extremely challenging on heterogeneous clusters,
even when embarrassingly parallel applications are considered. In this paper we
deal
with the problem of scheduling multiple applications, made of collections of
independent
and identical tasks, on a heterogeneous
master-worker platform. The applications are submitted online, which
means that there is no a priori (static) knowledge of the workload
distribution at the beginning of the execution.
The objective is to minimize the maximum stretch,
i.e. the maximum ratio between the actual time an application has
spent in the system and the time this application would have spent if
executed alone.
On the theoretical side, we design an optimal algorithm for the offline
version of the problem (when all release
dates and application characteristics are known beforehand).
We also introduce several heuristics for the general case of online
applications.
On the practical side, we have conducted extensive simulations and MPI
experiments, showing that we are able to deal with very large problem
instances in a few seconds. Also, the solution that we compute
totally outperforms classical heuristics from the literature,
thereby fully assessing the usefulness of our approach.
10h30-11h: pause
11h-11h30: Hubert Larchevêque:
Construction
distribuée de groupes pour le calcul à grande échelle:
11h30-12h: François Bonnet (IRISA), avec
Roberto Baldoni, Alessia Milani, et Michel Raynal:
Anonymous Graph Exploration without Collision by Mobile Robots
Abstract: Considering a synchronous model for autonomous mobile robots moving on
a finite anonymous graph, this talk focuses on the Constrained Perpetual Graph
Exploration problem (CPGE). That problem requires each robot to perpetually
visits all the vertices of the graph, in such a way that no vertex hosts more
than one robot at a time, and each edge is traversed by at most one robot at a
time. I will present an upper bound k on the number of robots that can be placed
in the graph while keeping CPGE solvability. Interestingly, this upper bound is
related to the topology of the graph.
13h30-14h30: Raymond Namyst (LaBRI):
Ordonnancement sur machines hiérarchiques
14h30:14h45: Pause
14h45-15h15 Gilles Tredan (IRISA): Estimation dynamique du nombre de processus crashés dans un système asynchrone
It is well-known that, in an asynchronous system where
processes are prone to crash, it is impossible to design a
protocol that provides each process with the set of processes
that are currently alive. Basically, this comes from the fact
that it is impossible to distinguish a crashed process from a
process that is very slow or with which communications are
very slow. Nevertheless, designing protocols that provide
the processes with good approximations of the set of processes
that are currently alive remains a real challenge in
fault-tolerant distributed computing. This paper proposes
such a protocol. To that end, it considers a realistic computation
model where the processes are provided with nonsynchronized
local clocks and a function alpha(). That function
takes a local duration as a parameter, and returns an integer
that is an estimate of the number of processes that
can crash during that duration. A simulation-based experimental
evaluation of the protocol is also presented. The
experiments show that the protocol is practically relevant.
15h15-15h45: Tobias Moemke (ETH
Zürich): Reoptimization Problems: Hardness and Algorithms
The talk provides an overview of the concept of reoptimization. To this end
recent development in reoptimizing the travelling salesman problem and the
Steiner tree problem are discussed - including hardness results and
approximation algorithms.