Intent:

This pattern addresses the question "How can you group the tasks that make up a problem decomposition in a way that simplifies the job of managing dependencies?"

Motivation:

This pattern constitutes the first step in analyzing dependencies among the tasks of a problem decomposition. In developing the problem's task decomposition, we urged the designer to think of the problem in terms of tasks that can execute concurrently. While we did not emphasize it during the task decomposition, it is clear that these tasks do not constitute a flat set. For example, tasks derived from the same high-level operation in the algorithm are naturally grouped together. Other tasks may not be related in terms of the original problem but have similar constraints on their concurrent execution and can thus be grouped together.

In short, there is considerable structure to the set of tasks. These structures -- these groupings of tasks -- simplify a problem's dependency analysis. If a group shares a temporal constraint, you can satisfy that constraint once for the whole group. If a group of tasks must work together on a shared data structure, the required synchronization can be worked out once for the whole group. If the tasks in a group are independent in every way, it may simplify the design and increase the available concurrency (thereby letting you scale to more processing elements) to group them together.

In each case, the idea is to define groups of tasks that share constraints and simplify the problem of managing constraints by dealing with groups rather than individual tasks.

Applicability:

Use this pattern when

• You have decomposed your problem into tasks that can execute concurrently (perhaps using the DecompositionStrategy pattern) and understand both the problem can be broken down into semi-independent tasks (its task decomposition) and how its data must be decomposed to support those tasks (its data decomposition).

Implementation:

Constraints among tasks fall into a few major categories, as follows.

• The easiest dependency to understand is a temporal dependency -- i.e., a constraint placed on the order in which a collection of tasks executes. If task A depends on the results of task B, for example, then task A must wait until task B completes before it can execute. We can usually think of this case in terms of data flow: task A is blocked waiting for the data to be ready from task B; when B completes, the data flows into A.

• Another form of ordering constraint occurs when a collection of tasks must run at the same time. For example, in many data-parallel problems, the original problem domain is divided into multiple regions that can be updated in parallel. Typically, the update of any given region requires information about the boundaries of its neighboring regions. If all of the regions are not processed at the same time, the parallel program could stall (deadlock) as some regions wait for data from inactive regions.

• Finally, a more subtle ordering constraint occurs when tasks in a group are truly independent of each other. These tasks do not have an ordering constraint between them. This is an important feature of a set of tasks (because it means they can execute in any order, including concurrently), and it is important to clearly note when this holds.

The goal of this design pattern is to group tasks based on these constraints, because

• By grouping tasks, you simplify the establishment of partial orders between tasks since order constraints can be applied to the group rather than to individual tasks.

• Grouping tasks allows you to make clear which tasks must execute concurrently.

For a given problem and decomposition, there may be many ways to group tasks. The goal is to pick a grouping of tasks that simplifies the dependency analysis. To clarify this point, think of the dependency analysis as finding and satisfying constraints on the concurrent execution of a program. When tasks share a set of constraints, it simplifies the dependency analysis to group them together.

There is no single way to find task groups. We suggest the following approach, keeping in mind that while you cannot think about task groups without considering the constraints themselves, at this point in the design it is best to do so as abstractly as possible -- identify the constraints and group tasks to help resolve them, but try not to get bogged down in the details.

• First, look at how you decomposed the original problem. In most cases, a high-level operation (e.g., solving a matrix) or a large iterative program structure (e.g., a loop) plays a key role in defining the decomposition. This is the first place to look for grouping tasks. The tasks that correspond to a high-level operation naturally group together.

  At this point, you have many small groups of tasks. In the next step, you'll look at the constraints shared between the tasks within a group. If the tasks share a constraint -- usually in terms of the update of a shared data structure -- keep them as a distinct group. Your algorithm design will need to ensure that these tasks execute at the same time. For example, many problems involve the concerted update of a shared data structure by a set of tasks. If these tasks do not run concurrently, the program could deadlock.

• Next, ask yourself if any other task groups share the same constraint. If so, merge the groups together. Large task groups give you flexibility in your design and make it easier for you to scale to large parallel systems. They also can simplify load balancing by giving you more ways to overlap concurrent execution of tasks within a group.

• The next step is to look at constraints between groups of tasks. This is easy when groups have a clear temporal ordering or when a distinct chain of data moves between groups. The more complex case, however, is when otherwise independent task groups share constraints between groups. In these cases, it may be useful to merge these into a larger group of independent tasks -- once again because large task groups usually make for more scheduling flexibility and better scalability.

Examples:

Molecular dynamics.

In the Examples section of the DependencyAnalysis pattern we described the problem of designing a parallel molecular dynamics program. In that discussion, we defined the following tasks:

• Tasks that find the vibrational forces on an atom.

• Tasks that find the rotational forces on an atom.

• Tasks that find the long-range forces on an atom.

• Tasks that update the position of an atom.

• A task to update the neighbor list for all the atoms (a single task because we have decided to leave this part of the computation sequential).

Let's consider how these can be grouped together. As a first pass, each item in the above list corresponds to a high-level operation in the original problem and defines a task group. If you were to dig deeper into the involved functions, you'd see that in each case, the updates implied in the function are independent except for the need to manage the sum into the force array.

We next want to see if we can merge any of these groups. Going down the list, the tasks in first two groups are independent, but share the same constraints. In both cases, coordinates for a small neighborhood of atoms are read and local contributions are made to the force array, so we can merge these into a single group for bonded interactions. The other groups have distinct temporal or ordering constraints and therefore can't be merged.