Nadathur Rajagopalan Satish and 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},
    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