Kaushik Ravindran
	kaushikr@eecs.berkeley.edu University of California, Berkeley Advisor: Kurt Keutzer GSRC theme:  concurrent Expected graduation:  Jan, 2008

Research Overview:  Efficient Task Allocation and Scheduling of Concurrent Applications to Many Core Multiprocessor Systems

Multiprocessor architectures are increasingly popular platforms for high performance embedded applications. An important step in deploying applications on multiprocessors is the allocation and scheduling of concurrent tasks to the processing and communication resources of the platform. When the application workload and task execution profiles can be reliably estimated at compile time, it is viable to determine an application mapping statically. Static scheduling is also relevant to rapid design space exploration for microarchitectures and systems.

Owing to the theoretical hardness of multiprocessor scheduling, a number of heuristic and approximation algorithms have been proposed. However, these approaches lack the flexibility necessary to accommodate diverse implementation and resource constraints that arise in practical scheduling problems. As an alternative, we study methods based on mathematical and constraint programming approaches for static scheduling. These approaches can flexibly enforce complex implementation constraints and are hence suitable for practical scheduling problems. However, the drawback of using generic solvers is that they suffer prohibitive run times even on modestly sized problem instances. To alleviate this difficulty, we advance strategies based on problem decompositions, tight lower bound computations and search guidance through heuristic methods to speed up constraint programming for a representative scheduling problem. While previous constraint formulations only handle scheduling problems with fewer than 30 tasks, our solver efficiently solves problems with over 150 tasks. The inherent flexibility, coupled with improved run times from a decomposition strategy, posit constraint optimization as a powerful tool for resource constrained scheduling problems.

Our scheduling methods are part of a design space exploration framework developed in our group for deploying network processing applications on two embedded multiprocessor platforms: Intel IXP network processors and Xilinx FPGA based soft multiprocessors. Using this exploration framework, we derived efficient implementations that met or surpassed the performance of hand tuned solutions for common network applications, including IPv4 packet forwarding, Network Address Translation and Diffserv.