Mapping linear workflows with computation/communication overlap

Abstract : This paper presents theoretical results related to mapping and scheduling linear workowsonto heterogeneous platforms. We use a realistic architectural model with bounded communication capabilities and full computation/communication overlap. This model is representativeof current multi-threaded systems. In these workow applications, the goal is often to maximizethroughput or to minimize latency. We present several complexity results related to both thesecriteria.To be precise, we prove that maximizing the throughput is NP-complete even for homogeneous platforms and minimizing the latency is NP-complete for heterogeneous platforms.Moreover, we present an approximation algorithm for throughput maximization for linear chainapplications on homogeneous platforms, and an approximation algorithm for latency minimization for linear chain applications on all platforms where communication is homogeneous (theprocessor speeds can differ). In addition, we present algorithms for several important specialcases for linear chain applications. Finally, we consider the implications of adding feedbackloops to linear chain applications.
Document type :
Reports
Complete list of metadatas

Cited literature [20 references]  Display  Hide  Download

https://hal-lara.archives-ouvertes.fr/hal-02102769
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 4:06:47 PM
Last modification on : Friday, April 19, 2019 - 1:38:13 AM

File

LIP-RR_08-21.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02102769, version 1

Collections

Citation

Kunal Agrawal, Anne Benoit, Yves Robert. Mapping linear workflows with computation/communication overlap. [Research Report] LIP RR-2008-21, Laboratoire de l'informatique du parallélisme. 2008, 23p. ⟨hal-02102769⟩

Share

Metrics

Record views

30

Files downloads

24