Nadathur Rajagopalan Satish

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2009-19

January 29, 2009

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2009/EECS-2009-19.pdf

Single-chip multiprocessors are now commonly present in both embedded and desktop systems. A key challenge before a programmer of modern systems is to productively program the multiprocessor devices present in these systems and utilize the parallelism available in them. This motivates the development of automated tools for parallel application development. An important step in such an automated flow is allocating and scheduling the concurrent tasks to the processing and communication resources in the architecture. When the application workload and execution profiles are known or can be estimated at compile time, then we can perform the allocation and scheduling statically at compile time. Many applications in signal processing and networking can be scheduled at compile time. Compile time scheduling incurs minimal overhead while running the application. It is also relevant to rapid design-space exploration of micro-architectures.

Scheduling problems that arise in realistic application deployment and design space exploration frameworks can encompass a variety of objectives and constraints. In order for scheduling techniques to be useful for realistic exploration frameworks, they must therefore be sufficiently extensible to be applied to a range of problems. At the same time, they must be capable of producing high quality solutions to different scheduling problems. Further, such techniques must be computationally efficient, especially when they are used to evaluate many micro-architectures in a design space exploration framework.

The focus of this dissertation is to provide guidance in choosing scheduling methods that best trade-off the flexibility with solution time and quality of the resulting schedule. We investigate and evaluate representatives of three broad classes of scheduling methods: heuristics, evolutionary algorithms and constraint programming. In order to evaluate these techniques, we consider three practical task-level scheduling problems: task allocation and scheduling onto multiprocessors, resource allocation and scheduling data transfers between CPU and GPU memories, and scheduling applications with variable task execution times and dependencies onto multiprocessors. We use applications from the networking, media and machine learning domains to benchmark our techniques. The above three scheduling problems, while all arising from practical mapping concerns, require different models, have differing constraints and optimize for different objectives. The diversity of these problems gives us a base for studying the extensibility of scheduling methods. It also helps provide a more holistic view of the merits of different scheduling approaches in terms of their efficiency and quality of solutions produced on general scheduling problems.

<b>Advisor:</b> Kurt Keutzer

Advisors: Kurt Keutzer

---

BibTeX citation:

@phdthesis{Satish:EECS-2009-19,
    Author= {Satish, Nadathur Rajagopalan},
    Title= {Compile Time Task and Resource Allocation of Concurrent Applications to Multiprocessor Systems},
    School= {EECS Department, University of California, Berkeley},
    Year= {2009},
    Month= {Jan},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2009/EECS-2009-19.html},
    Number= {UCB/EECS-2009-19},
    Abstract= {Single-chip multiprocessors are now commonly present in both embedded and desktop systems. A key challenge before a programmer of modern systems is to productively program the multiprocessor devices present in these systems and utilize the parallelism available in them. This motivates the development of automated tools for parallel application development. An important step in such an automated flow is allocating and scheduling the concurrent tasks to the processing and communication resources in the architecture. When the application workload and execution profiles are known or can be estimated at compile time, then we can perform the allocation and scheduling statically at compile time. Many applications in signal processing and networking can be scheduled at compile time. Compile time scheduling
incurs minimal overhead while running the application. It is also relevant to rapid design-space exploration of micro-architectures.

Scheduling problems that arise in realistic application deployment and design space exploration frameworks can encompass a variety of objectives and constraints. In order for scheduling techniques to be useful for realistic exploration frameworks, they must therefore be sufficiently extensible to be applied to a range of problems. At the same time, they must be capable of producing high quality solutions to different scheduling problems. Further, such techniques must be computationally efficient, especially when they are used to evaluate many micro-architectures in a design space exploration framework. 

The focus of this dissertation is to provide guidance in choosing scheduling methods that best trade-off the flexibility with solution time and quality of the resulting schedule. We investigate and evaluate representatives of three broad classes of scheduling methods: heuristics, evolutionary algorithms and constraint programming. In order to evaluate these techniques, we consider three practical task-level scheduling problems: task allocation and scheduling onto multiprocessors, resource allocation and scheduling data transfers between CPU and GPU memories, and scheduling applications with variable task execution times and dependencies onto multiprocessors. We use applications from the networking, media and machine learning domains to benchmark our techniques. The above three scheduling problems, while all arising from practical mapping concerns, require different models, have differing constraints and optimize for different objectives. The diversity of these problems gives us a base for studying the extensibility of scheduling methods. It also helps provide a more holistic view of the merits of different scheduling approaches in terms of their efficiency and quality of solutions produced on general scheduling problems. 

<b>Advisor:</b> Kurt Keutzer},
}

EndNote citation:

%0 Thesis
%A Satish, Nadathur Rajagopalan 
%T Compile Time Task and Resource Allocation of Concurrent Applications to Multiprocessor Systems
%I EECS Department, University of California, Berkeley
%D 2009
%8 January 29
%@ UCB/EECS-2009-19
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2009/EECS-2009-19.html
%F Satish:EECS-2009-19