Skip to Main content Skip to Navigation

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 :
Complete list of metadatas

Cited literature [31 references]  Display  Hide  Download
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 4:06:47 PM
Last modification on : Monday, November 16, 2020 - 9:58:08 AM


Files produced by the author(s)


  • HAL Id : hal-02102769, version 1



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⟩



Record views


Files downloads