Pattern Name: SeparableDependencies

AlgorithmStructure Design Space


Intent:

This pattern is used for task-based decompositions in which the dependencies between tasks can be eliminated as follows: Necessary global data is replicated and (partial) results are stored in local data structures. Global results are then obtained by reducing (combining) results from the individual tasks.

Also Known As:

Motivation:

In general, task-based algorithms present two distinct challenges to the software designer: allocating the tasks among the processors so the computational load is evenly distributed; and managing the dependencies between tasks so that if multiple tasks update the same data structure, these updates do not interfere with each other.

This pattern represents an important class of problems in which these two issues can be separated. In these problems, dependencies can be pulled outside the set of concurrent tasks, allowing the tasks to proceed independently.

Consider an example, the classic N-body problem: A system contains N bodies that move in space, each exerting distance-dependent forces on each of the other N-1 bodies. The problem is to calculate the motion of the bodies. For each instant in time, each body has a position, a velocity, and a force vector. For each time instant, a sequential solution calculates the force vector incident on each body by summing the force contributions from each of the other N-1 bodies and then computing the new position and velocity of each particle using its force vector.

One way to parallelize the problem is to decompose the computation performed at each time instant into tasks such that each task is responsible for computing the position and velocity of a subset of the bodies along with the contribution of the forces from that subset on the rest of the system. These tasks are not independent, since each task needs to read the locations of the other bodies, and each task must update the force vectors of all the other bodies.

This problem has two features that can be exploited. First, during the calculation for a particular time instant, the location of each body is first read by the other tasks and then modified by only a single task; it is not read by any other task after it has been written. Therefore, dependencies between tasks involving the location data can be eliminated by replicating this data in all the tasks. Second, since the force vectors are the sums of forces due to each body, they can be computed in two stages as follows: Each task can compute a partial sum, placing the result in a task-local variable. Once all the tasks have computed their partial sums, these partial sums can then be summed (reduced) to give the desired local force vectors. As a result, all the dependencies between the tasks during the concurrent execution have been "pulled out" of the concurrent part of the computation.

The techniques described in the EmbarrassinglyParallel pattern can be applied to the now-independent tasks. Some dependencies between tasks can be eliminated by replacing global data structures with copies local to each UE. (In a shared-memory environment, it is possible for all tasks that do not modify the global data structure to share a single copy.) Others may be eliminated by writing results to a local object and then, in a logically separate step, reducing (merging) the local objects into a single object. In essence, the dependencies between tasks are eliminated from the concurrent part of the computation, thus making the construction of a parallel algorithm much simpler. The following figure illustrates the central idea of this pattern.

Applicability:

This pattern can be used when: