Mixed Parallel Programming Models Using Parallel Tasks

Introduction

Large modular parallel applications can be decomposed into a set of cooperating parallel tasks. This set of parallel tasks and their cooperation or coordination structure are a flexible representation of a parallel program for the specific application. The flexibility in scheduling and mapping the parallel tasks can be exploited to achieve efficiency and scalability on a specific distributed memory platform by choosing a suitable mapping and scheduling of the tasks. Each parallel task is responsible for the computation of a specific part or module of the application, and can be executed on an arbitrary number of processors. The terms multiprocessor tasks, malleable tasks and moldable tasks have been used to denote such parallel tasks. In the following, we use the term multiprocessor task (M-task). An M-task can be implemented using an SPMD programming model (basic M-task) or can be hierarchically composed of other M-tasks and thereby support nested parallelism (composed M-task). The advantage of the M-task programming model is to exploit coarse-grained parallelism between M-tasks and fine-grained parallelism within basic M-tasks in the same program and thus the potential parallelism and scalability can be increased.

Each M-task provides an interface consisting of a set of input and output parameters. These parameters are parallel data structures that are distributed among the processors executing the M-task according to a predefined distribution scheme, e.g. a block-wise distribution of an array. A data dependence between M-tasks M₁ and M₂ arises if M₁ produces output data required as an input for M₂. Such data dependencies might lead to data re-distribution operations if M₁ and M₂ are executed on different sets of processors or if M₁ produces its output in a different data distribution than expected by M₂. Control dependencies are introduced by coordination operators, e.g. loop constructs for the repeated execution of an M-task or constructs for the conditional execution of an M-task. The data and control dependencies between M-tasks can be captured by a graph representation. Examples are macro dataflow graphs(Ramaswamy, Sapatnekar, & Banerjee, 1997) or series-parallel (SP) graphs(Rauber & Rünger, 2000).

The actual execution of an M-task program is based on a schedule of the M-tasks that has to take the data and control dependencies into account. M-tasks that are connected by a data or control dependence have to be executed subsequently. For independent M-tasks both, a concurrent execution on disjoint processor groups or an execution one after another are possible. The optimal schedule depends on the structure of the application and on the communication and computing performance of the parallel target platform. For the same application a pure data parallel schedule that executes all M-tasks consecutively on all available processors might lead to the best results on one platform but a mixed task and data parallel schedule may result in lower execution times on another platform. Thus, the parallel programming with M-tasks offers a very flexible programming style exploiting different levels of granularity and making parallel programs easily adoptable to a specific parallel platform.