Performance of work conserving schedulers and scheduling of some synchronous dataflow graphs
U. Kanade · 2004
We know a lot about competitive or approximation ratios of scheduling algorithms. This, though, cannot be translated into direct bounds on the schedule produced by a scheduling algorithm, because often the optimal solution is intractable. We derive a methodology to find absolute bounds on the scheduling of jobs with precedence constraints on parallel identical machines. Our bounds hold for a large class of online and offline scheduling algorithms: the “work conserving” scheduling algorithms. We apply this methodology to prove that an important class of synchronous dataflow graphs – the parallelized pipelines – has very good performance characteristics when scheduled by a work conserving scheduler. Real time guarantees and granularity design for these dataflow graphs are discussed. We argue that parallelized pipelines should be dynamically scheduled on multiprocessor architectures.