Value-maximizing deadline scheduling and its application to animation rendering

ABSTRACT

We describe a new class of utility-maximization scheduling problem with precedence constraints, the disconnected staged scheduling problem (DSSP). DSSP is a nonpreemptive multiprocessor deadline scheduling problem that arises in several commercially-important applications, including animation rendering, protein analysis, and seismic signal processing. DSSP differs from most previously-studied deadline scheduling problems because the graph of precedence constraints among tasks within jobs is disconnected, with one component per job. Another difference is that in practice we often lack accurate estimates of task execution times, and so purely offline solutions are not possible. However we do know the set of jobs and their precedence constraints up front and therefore some offline planning is possible.Our solution decomposes DSSP into an offline job selection phase followed by an online task dispatching phase. We model the former as a knapsack problem and explore several solutions to it, describe a new dispatching algorithm for the latter, and compare both with existing methods. Our theoretical results show that while DSSP is NP-hard and inapproximable in general, our two-phase scheduling method guarantees a good performance bound for many special cases. Our empirical results include an evaluation of scheduling algorithms on a real animation-rendering workload; we present a characterization of this workload in a companion paper. The workload records eight weeks of activity on a 1,000-CPU cluster used to render portions of the full-length animated feature film Shrek 2 in 2004. We show that our improved scheduling algorithms can substantially increase the aggregate value of completed jobs compared to existing practices. Our new task dispatching algorithm LCPF performs well by several metrics, including job completion times as well as the aggregate value of completed jobs.

REFERENCES

• 1: Thomas L. Adam , K. M. Chandy , J. R. Dickson, A comparison of list schedules for parallel processing systems, Communications of the ACM, v.17 n.12, p.685-690, Dec 1974 [doi>10.1145/361604.361619]
• 2: Guy E. Blelloch , Phillip B. Gibbons , Yossi Matias, Provably efficient scheduling for languages with fine-grained parallelism, Journal of the ACM (JACM), v.46 n.2, p.281-321, March 1999 [doi>10.1145/301970.301974]
• 3: Robert D. Blumofe , Charles E. Leiserson, Executing multithreaded programs efficiently, 1995
• 4: Robert D. Blumofe , Charles E. Leiserson, Space-Efficient Scheduling of Multithreaded Computations, SIAM Journal on Computing, v.27 n.1, p.202-229, Feb. 1998 [doi>10.1137/S0097539793259471]
• 5: Robert D. Blumofe , Charles E. Leiserson, Scheduling multithreaded computations by work stealing, Journal of the ACM (JACM), v.46 n.5, p.720-748, Sept. 1999 [doi>10.1145/324133.324234]
• 6: Abhijit Bose. Personal communication, September 2004.
• 7: Richard P. Brent, The Parallel Evaluation of General Arithmetic Expressions, Journal of the ACM (JACM), v.21 n.2, p.201-206, April 1974 [doi>10.1145/321812.321815]
• 8: Peter Brucker, Scheduling Algorithms, Springer-Verlag New York, Inc., Secaucus, NJ, 2001
• 9: Chandra Cheruki , Michael A. Bender, An Efficient Approximation Algorithm for Minimizing Makespan on Uniformly Related Machines, Proceedings of the 6th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.383-393, June 22-24, 1998
• 10: Chandra Chekuri and Sanjeev Khanna. Approximation algorithms for minimizing average weighted completion time. In Joseph Leung, editor, Handbook of Scheduling: Algorithms, Models, and Performance Analysis. CRC Press, 2004.
• 11: Fabián A. Chudak , David B. Shmoys, Approximation algorithms for precedence-constrained scheduling problems on parallel machines that run at different speeds, Journal of Algorithms, v.30 n.2, p.323-343, Feb. 1999 [doi>10.1006/jagm.1998.0987]
• 12: E. Coffman and Ronald Graham. Optimal scheduling for two processor systems. Acta Informatica, pages 200--213, 1972.
• 13: Directed acyclic graph manager (DAGMan) for Condor scheduler. http://www.cs.wisc.edu/condor/dagman/.
• 14: Jeffrey Dean and Sanjay Ghemawat. MapReduce: Simplified data processing on large clusters. In OSDI, December 2004.
• 15: Uriel Feige , Christian Scheideler, Improved bounds for acyclic job shop scheduling (extended abstract), Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.624-633, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276878]
• 16: Dror G. Feitelson , Larry Rudolph , Uwe Schwiegelshohn , Kenneth C. Sevcik , Parkson Wong, Theory and Practice in Parallel Job Scheduling, Proceedings of the Job Scheduling Strategies for Parallel Processing, p.1-34, April 05, 1997
• 17: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 18: Ron Graham. Bounds for certain multiprocessor anomalies. Bell Sys Tech J, 45:1563--1581, 1966.
• 19: Ronald Graham. Bounds on multiprocessing time anomalies. SIAM J Appl Math, 17:263--269, 1969.
• 20: L. A. Hall. Approximability of flow shop scheduling. Mathematical Programming, 82:175--190, 1998.
• 21: Les Hatton, The T Experiments: Errors In Scientific Software, IEEE Computational Science & Engineering, v.4 n.2, p.27-38, April 1997 [doi>10.1109/99.609829]
• 22: Les Hatton , Andy Roberts, How Accurate is Scientific Software?, IEEE Transactions on Software Engineering, v.20 n.10, p.785-797, October 1994 [doi>10.1109/32.328993]
• 23: Elisa Heymann , Miquel A. Senar , Emilio Luque , Miron Livny, Adaptive Scheduling for Master-Worker Applications on the Computational Grid, Proceedings of the First IEEE/ACM International Workshop on Grid Computing, p.214-227, December 17, 2000
• 24: ILOG Corporation. CPLEX and related software documentation. http://www.ilog.com.
• 25: David Johnson. The twelve open problems from {G&J}: Updates. J of Algorithms, 2(4):393--405, 1981.
• 26: Workshops on Job Scheduling Strategies for Parallel Processing (JSSPP). http://www.cs.huji.ac.il/~feit/parsched/index.html. Proceedings are published in Springer LNCS series: http://www.cs.huji.ac.il/~feit/parsched/lncs.html.
• 27: Richard M. Karp. Reducibility among combinatorial computations. In R. E. Miller and J. W. Thatcher, editors, Complexity of Computer Computations, pages 85--103. Plenum Press, 1972.
• 28: Hans Kellerer, Ulrich Pferschy, and David Pisinger. Knapsack Problems. Springer, 2004.
• 29: Klaus Jansen , Roberto Solis-Oba , Maxim Sviridenko, Makespan Minimization in Job Shops: A Linear Time Approximation Scheme, SIAM Journal on Discrete Mathematics, v.16 n.2, p.288-300, 2003 [doi>10.1137/S0895480199363908]
• 30: Jochen Krallmann , Uwe Schwiegelshohn , Ramin Yahyapour, On the Design and Evaluation of Job Scheduling Algorithms, Proceedings of the Job Scheduling Strategies for Parallel Processing, p.17-42, April 16, 1999
• 31: A. Kumar , R. Shorey, Performance Analysis and Scheduling of Stochastic Fork-Join Jobs in a Multicomputer System, IEEE Transactions on Parallel and Distributed Systems, v.4 n.10, p.1147-1164, October 1993 [doi>10.1109/71.246075]
• 32: Yu-Kwong Kwok , Ishfaq Ahmad, Static scheduling algorithms for allocating directed task graphs to multiprocessors, ACM Computing Surveys (CSUR), v.31 n.4, p.406-471, Dec. 1999 [doi>10.1145/344588.344618]
• 33: J. K. Lenstra and A. H. G. Rinnooy Kan. Complexity of scheduling under precedence constraints. Operations Research, 26(1):22--35, January 1978.
• 34: J. K. Lenstra , D. B. Shmoys , É. Tardos, Approximation algorithms for scheduling unrelated parallel machines, Mathematical Programming: Series A and B, v.46 n.3, p.259-271, Apr. 1990 [doi>10.1007/BF01585745]
• 35: David A. Lifka, The ANL/IBM SP Scheduling System, Proceedings of the Workshop on Job Scheduling Strategies for Parallel Processing, p.295-303, April 25, 1995
• 36: T. Kasami M. Fuju and N. Ninomiya. Optimal sequence of two equivalent processors. SIAM J Appl Math, 17(3):784--789, 1971.
• 37: Two Stage Optimization of Job Scheduling and Assignment in Heterogeneous Compute Farms, Proceedings of the 10th IEEE International Workshop on Future Trends of Distributed Computing Systems (FTDCS'04), p.119-124, May 26-28, 2004
• 38: Michael Pinedo. Scheduling: Theory, Algorithms, and Systems. Prentice-Hall, 2nd edition, 2002.
• 39: Platform Computing. LSF Scheduler. http://www.platform.com/products/LSFfamily/.
• 40: Platform Computing. Administering Platform LSF, February 2003. Chapter 14.
• 41: S. V. Sevastianov and G. J. Woeginger. Makespan minimization in open shops: A polynomial time approximation scheme. Mathematical Programming, 82:191--198, 1998.
• 42: Jiri Sgall, On-line Scheduling, Developments from a June 1996 seminar on Online algorithms: the state of the art, p.196-231, January 1998
• 43: Li ng Tan , Zahir Tari, Dynamic Task Assignment in Server Farms: Better Performance by Task Grouping, Proceedings of the Seventh International Symposium on Computers and Communications (ISCC'02), p.175, July 01-04, 2002
• 44: Adam Wierman , Mor Harchol-Balter, Classifying scheduling policies with respect to unfairness in an M/GI/1, ACM SIGMETRICS Performance Evaluation Review, v.31 n.1, June 2003
• 45: Francis Wray. The parallel implementation of closely coupled numerical algorithms. In A. Adey, editor, Parallel Processing in Engineering Applications. Springer, 1990.
• 46: Francis Wray. High performance numerically intensive applications on distributed memory parallel computers. In J. T. Devreese and P. E. Van Camp, editors, Scientific Computing on Supercomputers, volume III. Plenum, 1991.
• 47: Yunhong Zhou, Terence Kelly, Janet Wiener, and Eric Anderson. An extended evaluation of two-phase scheduling methods for animation rendering. In Proceedings of JSSPP {26}:JSSPP LNCS, Springer, 2005, to appear.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

General Terms:
Algorithms, Performance, Theory

Keywords:
animation rendering, deadline scheduling, multiprocessor job scheduling, simulation