# Scheduling Task Dependence Graphs with Variable Task Execution Times onto Heterogeneous Multiprocessors

### Nadathur Rajagopalan Satish, Kaushik Ravindran and Kurt Keutzer

###
EECS Department

University of California, Berkeley

Technical Report No. UCB/EECS-2008-42

April 21, 2008

### http://www.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-42.pdf

We present a statistical optimization approach for a scheduling a task dependence graph 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, or average-case analysis 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 of execution times of different tasks. 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 a H.264 video processing application.

We present two scheduling algorithms based on statistical makespan analysis. The first is a heuristic based on a critical path analysis of the task dependence graph. The other is a simulated annealing algorithm using incremental timing analysis. Both algorithms take as input the required statistical guarantee, and can thus be easily re-used for different required guarantees. We show that optimization methods based on statistical analysis show a 25-30% improvement in makespan over methods based on static worst-case analysis.

BibTeX citation:

@techreport{Satish:EECS-2008-42, Author = {Satish, Nadathur Rajagopalan and Ravindran, Kaushik and Keutzer, Kurt}, Title = {Scheduling Task Dependence Graphs with Variable Task Execution Times onto Heterogeneous Multiprocessors}, Institution = {EECS Department, University of California, Berkeley}, Year = {2008}, Month = {Apr}, URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-42.html}, Number = {UCB/EECS-2008-42}, Abstract = {We present a statistical optimization approach for a scheduling a task dependence graph 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, or average-case analysis 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 of execution times of different tasks. 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 a H.264 video processing application. We present two scheduling algorithms based on statistical makespan analysis. The first is a heuristic based on a critical path analysis of the task dependence graph. The other is a simulated annealing algorithm using incremental timing analysis. Both algorithms take as input the required statistical guarantee, and can thus be easily re-used for different required guarantees. We show that optimization methods based on statistical analysis show a 25-30% improvement in makespan over methods based on static worst-case analysis.} }

EndNote citation:

%0 Report %A Satish, Nadathur Rajagopalan %A Ravindran, Kaushik %A Keutzer, Kurt %T Scheduling Task Dependence Graphs with Variable Task Execution Times onto Heterogeneous Multiprocessors %I EECS Department, University of California, Berkeley %D 2008 %8 April 21 %@ UCB/EECS-2008-42 %U http://www.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-42.html %F Satish:EECS-2008-42