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://www2.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://www2.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://www2.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-42.html
%F Satish:EECS-2008-42