An Integrated Approach for Processor Allocation and Scheduling of Mixed-Parallel Applications∗

Computationally complex applications can often be viewed as a collection of coarse-grained data-parallel tasks with precedence constraints. Researchers have shown that combining task and data parallelism (mixed parallelism) can be an effective approach for executing these applica-tions, as compared to pure task or data parallelism. In this paper, we present an approach to determine the appropri-ate mix of task and data parallelism, i.e., the set of tasks that should be run concurrently and the number of processors to be allocated to each task. An iterative algorithm is proposed that couples processor allocation and scheduling, of mixed-parallel applications on compute clusters so as to minimize the parallel completion time (makespan). Our algorithm it-eratively reduces the makespan by increasing the degree of data parallelism of tasks on the critical path that have good scalability and a low degree of potential task parallelism. The approach employs a look-ahead technique to escape local minima and uses priority based backfill scheduling to efficiently schedule the parallel tasks onto processors. Eval-uation using benchmark task graphs derived from real ap-plications as well as synthetic graphs shows that our algo-rithm consistently performs better than CPR and CPA, two previously proposed scheduling schemes, as well as pure task and data parallelism.