Non-clairvoyant scheduling with precedence constraints

ABSTRACT

We consider Edmonds's model (1999) extended by precedence constraints. In our setting, a scheduler has to schedule non-clairvoyantly jobs consisting in DAGs of tasks arriving over time, each task going through phases of different degrees of parallelism, unknown to the scheduler. As in the original model without precedence constraints, the scheduler is only informed of the arrival and the completion of each task, at the time of these events, and nothing more. Furthermore, it is not aware of the DAG structure of each job beforehand neither of the precise characteristics of the phases of the tasks that compose each job.

We consider the preemptive strategy Equi○Equi, that divides the processors evenly among the alive jobs and then divides the processing power alloted to each job evenly among its alive tasks. We show that whatever how complex the precedences are, Equi○Equi is (2 + ε)-speed 0(κ/ε)-competitive for the flowtime metric, where κ is the maximum number of independent tasks in each job. That is to say, the flowtime of the schedule computed by EquioEqui is at a constant ratio of the optimal flowtime as soon as Equi is given slightly more than twice the resources as the optimum it is compared to. Interestingly, the extra speed needed to obtain a competitive algorithm, namely (2+ε), is the same in presence of precedence constraints, as in the original setting without precedences studied by Edmonds in 1999. This means that the maximum load that the system can handle without diverging, is the same with or without precedence constraints.

Furthermore, we propose a simple scheme to analyze a special class of schedulers, namely Equi-schedulers, which allows to obtain upper and lower bounds on particular precedences structures, such as independent chains, IN-trees, OUT-trees and Serial-parallel DAGs.

REFERENCES

• 1: Yossi Azar , Leah Epstein, On-Line Scheduling with Precedence Constraints, Proceedings of the 7th Scandinavian Workshop on Algorithm Theory, p.164-174, July 05-07, 2000
• 2: Jeff Edmonds, Scheduling in the dark, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.179-188, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301299]
• 3: Jeff Edmonds , Donald D. Chinn , Tim Brecht , Xiaotie Deng, Non-clair voy ant multiprocessor scheduling of jobs with changing execution characteristics, Journal of Scheduling, v.6 n.3, p.231-250, May/June 2003 [doi>10.1023/A:1022952324290]
• 4: Jeff Edmonds , Suprakash Datta , Patrick Dymond, TCP is competitive against a limited adversary, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA [doi>10.1145/777412.777440]
• 5: J. Edmonds and K. Pruhs. Multicast pull scheduling: When fairness is fine. Algorithmica, 36(3):315--330, 2003.
• 6: A. Feldmann, M.-Y. Kao, J. Sgall, and S.-H. Teng. Optimal online scheduling of parallel jobs with dependencies. J. of Combinatorial Optimization, 1:393--411, 1998.
• 7: Yuxiong He, Wen Jing Hsu, and Charles E. Leiser-son. Provably efficient online non-clairvoyant adaptive scheduling. In Proc. of IEEE Parallel and Distributed Processing Symposium (IPDPS), pages 1--10, 2007.
• 8: Bala Kalyanasundaram , Kirk Pruhs, Speed is as powerful as clairvoyance, Journal of the ACM (JACM), v.47 n.4, p.617-643, July 2000 [doi>10.1145/347476.347479]
• 9: Keqin Li, Average-case performance analysis of scheduling random parallel tasks with precedence constraints on mesh connected multicomputer systems, Journal of Parallel and Distributed Computing, v.66 n.8, p.1090-1102, August 2006 [doi>10.1016/j.jpdc.2005.06.012]
• 10: Rajeev Motwani , Steven Phillips , Eric Torng, Nonclairvoyant scheduling, Theoretical Computer Science, v.130 n.1, p.17-47, Aug. 1, 1994 [doi>10.1016/0304-3975(94)90151-1 ]
• 11: J. Robert and N. Schabanel. Non-clairvoyant batch set scheduling: Fairness is fair enough. In Proc. of 15th European Symposium on Algorithms (ESA), volume LNCS 4698, pages 741--753, 2007.
• 12: Julien Robert , Nicolas Schabanel, Pull-based data broadcast with dependencies: be fair to users, not to items, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.238-247, January 07-09, 2007, New Orleans, Louisiana

INDEX TERMS

Keywords:
equi-partition, fairness, non-clairvoyant algorithm, online scheduling, precedences