Mapping linear workflows with computation/communication overlap - LARA - Libre accès aux rapports scientifiques et techniques Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2008

Mapping linear workflows with computation/communication overlap


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.
Fichier principal
Vignette du fichier
LIP-RR_08-21.pdf (263.65 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-02102769 , version 1 (17-04-2019)


  • 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⟩
51 Consultations
122 Téléchargements


Gmail Mastodon Facebook X LinkedIn More