Toward Optimizing Latency under Throughput Constraints for Application Workflows on Clusters

Abstract. In many application domains, it is desirable to meet some user-defined performance requirement while minimizing resource usage and optimizing addi-tional performance parameters. For example, application workflows with real-time constraints may have strict throughput requirements and desire a low la-tency or response-time. The structure of these workflows can be represented as di-rected acyclic graphs of coarse-grained application tasks with data dependences. In this paper, we develop a novel mapping and scheduling algorithm that mini-mizes the latency of workflows that act on a stream of input data, while satisfying throughput requirements. The algorithm employs pipelined parallelism and intel-ligent clustering and replication of tasks to meet throughput requirements. La-tency is minimized by exploiting task parallelism and reducing communication overheads. Evaluation using synthetic benchmarks and application task graphs shows that our algorithm 1) consistently meets throughput requirements even when other existing schemes fail, 2) produces lower-latency schedules, and 3) results in lesser resource usage.