Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences


UC Berkeley


2008 Research Summary

Leveraging Task and Data Level Parallelism in Multi-Core Processors

View Current Project Information

Nadathur Rajagopalan Satish and Kurt Keutzer

Task allocation and scheduling is an important step in mapping parallel tasks to heterogeneous multiprocessors. On the other hand, recent multi-core architectures have been leveraging data-level parallelism through SIMD and multi-threading. In this research, we present a constraint optimization framework for static task allocation and scheduling, as well as an approach to extend it to handle tasks that are data-parallel.

Typical formulations suffer prohibitive run times even on medium-sized problems with less than 30 tasks. A strategy to speed up constraint optimization is presented for a representative multiprocessor scheduling problem. Our decomposition strategy enhances constraint optimization to robustly handle instances with over 100 tasks. Moreover, the extensibility of constraint formulations permits realistic application and resource constraints, which is a limitation of common heuristic methods for scheduling. The inherent extensibility, coupled with improved run times from a decomposition strategy, posit constraint optimization as a powerful tool for resource constrained scheduling and multiprocessor design space exploration.

N. Satish, K. Ravindran and K. Keutzer, "A Decomposition-based Constraint Optimization Approach for Statically Scheduling Task Graphs with Communication Delays to Multiprocessors," Proceedings of the 10th International Conference on Design Automation and Test in Europe (DATE 07), April 2007, pp. 57-62.