Mapping Linear Workflows with Computation/Communication Overlap

This paper presents theoretical results for mapping and scheduling linear workflows onto heterogeneous platforms. We use a realistic architectural model, representative of current multi-threaded systems. Our model has bounded communication capabilities and full computation/communication overlap. In these workflow applications, the goal is often to maximize throughput or to minimize latency. We present several complexity results, and approximation algorithms, for these two criteria. We also consider the implications of adding feedback loops to linear chain applications.