Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences


UC Berkeley


2009 Research Summary

Efficient Task Allocation and Scheduling of Concurrent Applications to Multiprocessor Systems

View Current Project Information

Kaushik Ravindran, Nadathur Rajagopalan Satish and Kurt Keutzer

Gigascale Systems Research Center and Center for Hybrid and Embedded Software Systems CCR-0225610

Static compile time task allocation and scheduling is an important step in deploying concurrent applications on multiprocessors. When the application workload and parallel tasks are known at compile time, it is viable to determine an application mapping statically. Signal processing applications derived from static data flow specifications can be statically scheduled on multiprocessors. Static scheduling is also relevant to rapid design space exploration (DSE) 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.