Asymptotically Optimal Algorithm for Laplace Task Graphs on
Heterogeneous Platforms

O.Beaumont, P.Ramet, and J.Roman

LaBRI UMR CNRS 5800, ENSEIRB, University Bordeaux 1, France
Domaine Universitaire
351, cours de la Libération
33405 Talence Cedex
FRANCE

{obeaumont,ramet, roman}@labri.fr

Abstract. In this paper, we focus on the scheduling of Laplace task
graph on a general platform where both communication links and
processing units are heterogeneous. In this context, it is known that
deriving optimal algorithm, in the sense of makespan minimization, is
NP-Complete, and several inapproximation results have been proved.
Nevertheless, we provide an asymptotically optimal algorithm in this
general context. Moreover, we expect that this methodology can be
extended to more general task graphs, especially for nested loops
where the inner-most loop is parallel.