Asymptotically optimal algorithm for Laplace task graphs on heterogeneous platforms - Archive ouverte HAL Access content directly
Conference Papers Year : 2003

Asymptotically optimal algorithm for Laplace task graphs on heterogeneous platforms

(1, 2) , (1, 3) , (3, 4)
1
2
3
4

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 asymtotically optimal algorithm in this general context. Moreover, we expect that this methodolgy can be extended to more general task graphs, especially for nested loops where the inner-most loop is parallel.

Keywords

Not file

Dates and versions

inria-00346587 , version 1 (11-12-2008)

Identifiers

  • HAL Id : inria-00346587 , version 1

Cite

Olivier Beaumont, Pierre Ramet, Jean Roman. Asymptotically optimal algorithm for Laplace task graphs on heterogeneous platforms. Fifth International Conference on Parallel Processing and Applied Mathematics, Workshop HeteroPar, 2003, Czestochowa, Poland. pp.880--887. ⟨inria-00346587⟩
54 View
0 Download

Share

Gmail Facebook Twitter LinkedIn More