Mapping linear workflows with computation/communication overlap

Kunal Agrawal (1) , Anne Benoit (2) , Yves Robert (2)

1 CSAIL - Computer Science and Artificial Intelligence Laboratory [Cambridge]
2 LIP - Laboratoire de l'Informatique du Parallélisme

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.

Mots clés: Period; Mapping; Latency; Workflow; Scheduling; Pipeline graphs; Complexity results; Feedback loop

Domaines: Informatique [cs]

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⟩