Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

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