Scheduling Applications with Variable Task Execution Times onto Heterogeneous Multiprocessors
Nadathur Rajagopalan Satish and Kurt Keutzer
Gigascale Systems Research Center
We investigate statistical optimization approaches for scheduling applications represented as task dependence graphs with variable task execution times onto a heterogeneous multiprocessor system. Scheduling methods in the presence of variations typically rely on worst-case timing estimates for hard real-time applications, and average-case estimates for other applications. However, a large class of soft real-time applications require only statistical guarantees on latency and throughput. We present a general statistical model that captures the probability distributions of task execution times as well as the correlations between them. We use a Monte-Carlo based technique to perform makespan analysis of different schedules based on this model. This approach can be used to analyze the variability present in a variety of soft real-time applications, including the H.264 video processing application.
We present two scheduling algorithms based on statistical makespan analysis--one a list-scheduling based heuristic and the other a simulated annealing approach. Both algorithms take into account the required statistical guarantee. We show that optimization approaches based on statistical analysis show up to a 30% improvement in makespan over methods based on static worst-case analysis.