Scheduling algorithms for workow optimization
Kunal Agrawal, Anne Benoît, Yves Robert · 2009
Pipelined workows are a popular programming paradigm for parallel applications. In these workows, the computation is divided into several stages and these stages are connected to each other through rst-in rst-out channels. In order to execute these workows on a parallel machine, we must rst determine the mapping of the stages onto the various processors on the machine. After nding the mapping, we must compute the schedule | the order in which the various stages execute on their assigned processors. In this paper, we explore the scheduling problem for linear workows, assuming that the mapping is given. Linear workows are a special case of workows for which the dependencies between stages can be represented by a linear graph. The objective of the scheduling algorithm is either to maximize throughput or to minimize latency or both. We consider two realistic execution models: the one-port model and the multi-port model. In both models, nding a schedule to minimize latency is easy. However, computing the schedule to minimize period (maximize throughput) is NP-hard in the one-port model, but can be done in polynomial time in the multi-port model. We also present an approximation algorithm to minimize period in the one-port model. Finally, the bi-criteria problem, which consists in nding a schedule respecting a given period and a given latency, is NP-hard in both models.