Classification, Customization, and Characterization: Using MILP for Task Allocation and Scheduling

Abhijit Davare, Jike Chong, Qi Zhu, Douglas Michael Densmore and Alberto L. Sangiovanni-Vincentelli

EECS Department
University of California, Berkeley
Technical Report No. UCB/EECS-2006-166
December 11, 2006

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-166.pdf

Task allocation and scheduling for heterogeneous multi-core platforms must be automated for such platforms to be successful. Techniques such as Mixed Integer Linear Programming (MILP) provide the ability to easily customize the allocation and scheduling problem to application or platform-specific peculiarities. The representation of the core problem in a MILP form has a large impact on the solution time required. In this paper, we investigate a variety of such representations and propose a taxonomy for them. A promising representation is chosen with extensive computational characterization. The MILP formulation is customized for a multimedia case study involving the deployment of a Motion JPEG encoder application onto a Xilinx Virtex II Pro FPGA platform. We demonstrate that our approach can produce solutions that are competitive with manual designs.


BibTeX citation:

@techreport{Davare:EECS-2006-166,
    Author = {Davare, Abhijit and Chong, Jike and Zhu, Qi and Densmore, Douglas Michael and Sangiovanni-Vincentelli, Alberto L.},
    Title = {Classification, Customization, and Characterization: Using MILP for Task Allocation and Scheduling},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {2006},
    Month = {Dec},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-166.html},
    Number = {UCB/EECS-2006-166},
    Abstract = {Task allocation and scheduling for heterogeneous multi-core platforms must be automated for such platforms to be successful. Techniques such as Mixed Integer Linear Programming (MILP) provide the ability to easily customize the allocation and scheduling problem to application or platform-specific peculiarities. The representation of the core problem in a MILP form has a large impact on the solution time required. In this paper, we investigate a variety of such representations and propose a taxonomy for them. A promising representation is chosen with extensive computational characterization. The MILP formulation is customized for a multimedia case study involving the deployment of a Motion JPEG encoder application onto a Xilinx Virtex II Pro FPGA platform. We demonstrate that our approach can produce solutions that are competitive with manual designs.}
}

EndNote citation:

%0 Report
%A Davare, Abhijit
%A Chong, Jike
%A Zhu, Qi
%A Densmore, Douglas Michael
%A Sangiovanni-Vincentelli, Alberto L.
%T Classification, Customization, and Characterization: Using MILP for Task Allocation and Scheduling
%I EECS Department, University of California, Berkeley
%D 2006
%8 December 11
%@ UCB/EECS-2006-166
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-166.html
%F Davare:EECS-2006-166