Value-maximizing deadline scheduling and its application to animation rendering

Eric Anderson, Dirk Beyer, Kamalika Chaudhuri, Terence Kelly, Norman Salazar, Cipriano Santos, Ram Swaminathan, Robert Endre Tarjan, Janet Wiener, Yunhong Zhou

Research output: Contribution to conferencePaper

8 Scopus citations

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.

Original languageEnglish (US)
Pages299-308
Number of pages10
StatePublished - Dec 1 2005
Externally publishedYes
EventSeventeenth Annual ACM Symposium on Parallelism in Algorithms and Architectures - Las Vegas, NV, United States
Duration: Jul 18 2005Jul 20 2005

Other

OtherSeventeenth Annual ACM Symposium on Parallelism in Algorithms and Architectures
CountryUnited States
CityLas Vegas, NV
Period7/18/057/20/05

All Science Journal Classification (ASJC) codes

  • Engineering(all)

Fingerprint Dive into the research topics of 'Value-maximizing deadline scheduling and its application to animation rendering'. Together they form a unique fingerprint.

Cite this