Task Allocation and Scheduling of Concurrent Applications to Multiprocessor Systems
Kaushik Ravindran
EECS Department, University of California, Berkeley
Technical Report No. UCB/EECS-2007-149
December 13, 2007
http://www2.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-149.pdf
Programmable multiprocessors are increasingly popular platforms for high performance embedded applications. An important step in deploying applications on multiprocessors is to allocate and schedule concurrent tasks to the processing and communication resources of the platform. When the application workload and execution profiles can be reliably estimated at compile time, it is viable to determine an application mapping statically. Many applications from the signal processing and network processing domains are statically scheduled on multiprocessor systems. Static scheduling is also relevant to design space exploration for micro-architectures and systems.
Owing to the computational complexity of optimal static scheduling, a number of heuristic methods have been proposed for different scheduling conditions and architecture models. Unfortunately, these methods lack the flexibility necessary to enforce implementation and resource constraints that complicate practical multiprocessor scheduling problems. While it is important to find good solutions quickly, an effective scheduling method must also reliably capture the problem specification and flexibly accommodate diverse constraints and objectives.
This dissertation is an attempt to develop insight into efficient and flexible methods for allocating and scheduling concurrent applications to multiprocessor architectures. We conduct our study in four parts. First, we analyze the nature of the scheduling problems that arise in a realistic exploration framework. Second, we evaluate competitive heuristic, randomized, and exact methods for these scheduling problems. Third, we propose methods based on mathematical and constraint programming for a representative scheduling problem. Though expressiveness and flexibility are advantages of these methods, generic constraint formulations suffer prohibitive run times even on modestly sized problems. To alleviate this difficulty, we advance several strategies to accelerate constraint programming, such as problem decompositions, search guidance through heuristic methods, and tight lower bound computations. The inherent flexibility, coupled with improved run times from a decomposition strategy, posit constraint programming as a powerful tool for multiprocessor scheduling problems. Finally, we present a toolbox of practical scheduling methods, which provide different trade-offs with respect to computational efficiency, quality of results, and flexibility. Our toolbox is composed of heuristic methods, constraint programming formulations, and simulated annealing techniques. These methods are part of an exploration framework for deploying network processing applications on two embedded platforms: Intel IXP network processors and Xilinx FPGA based soft multiprocessors.
Advisors: Kurt Keutzer
BibTeX citation:
@phdthesis{Ravindran:EECS-2007-149,
Author= {Ravindran, Kaushik},
Title= {Task Allocation and Scheduling of Concurrent Applications to Multiprocessor Systems},
School= {EECS Department, University of California, Berkeley},
Year= {2007},
Month= {Dec},
Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-149.html},
Number= {UCB/EECS-2007-149},
Abstract= {Programmable multiprocessors are increasingly popular platforms for high performance embedded applications. An important step in deploying applications on multiprocessors is to allocate and schedule concurrent tasks to the processing and communication resources of the platform. When the application workload and execution profiles can be reliably estimated at compile time, it is viable to determine an application mapping statically. Many applications from the signal processing and network processing domains are statically scheduled on multiprocessor systems. Static scheduling is also relevant to design space exploration for micro-architectures and systems.
Owing to the computational complexity of optimal static scheduling, a number of heuristic methods have been proposed for different scheduling conditions and architecture models. Unfortunately, these methods lack the flexibility necessary to enforce implementation and resource constraints that complicate practical multiprocessor scheduling problems. While it is important to find good solutions quickly, an effective scheduling method must also reliably capture the problem specification and flexibly accommodate diverse constraints and objectives.
This dissertation is an attempt to develop insight into efficient and flexible methods for allocating and scheduling concurrent applications to multiprocessor architectures. We conduct our study in four parts. First, we analyze the nature of the scheduling problems that arise in a realistic exploration framework. Second, we evaluate competitive heuristic, randomized, and exact methods for these scheduling problems. Third, we propose methods based on mathematical and constraint programming for a representative scheduling problem. Though expressiveness and flexibility are advantages of these methods, generic constraint formulations suffer prohibitive run times even on modestly sized problems. To alleviate this difficulty, we advance several strategies to accelerate constraint programming, such as problem decompositions, search guidance through heuristic methods, and tight lower bound computations. The inherent flexibility, coupled with improved run times from a decomposition strategy, posit constraint programming as a powerful tool for multiprocessor scheduling problems. Finally, we present a toolbox of practical scheduling methods, which provide different trade-offs with respect to computational efficiency, quality of results, and flexibility. Our toolbox is composed of heuristic methods, constraint programming formulations, and simulated annealing techniques. These methods are part of an exploration framework for deploying network processing applications on two embedded platforms: Intel IXP network processors and Xilinx FPGA based soft multiprocessors.},
}
EndNote citation:
%0 Thesis %A Ravindran, Kaushik %T Task Allocation and Scheduling of Concurrent Applications to Multiprocessor Systems %I EECS Department, University of California, Berkeley %D 2007 %8 December 13 %@ UCB/EECS-2007-149 %U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-149.html %F Ravindran:EECS-2007-149