Intent:

This pattern is used for task-based decompositions in which the dependencies between tasks cannot be separated from the execution of the tasks. The dependencies must be dealt with in the body of the task.

Motivation:

Task-based algorithms present two distinct challenges to the software designer. First, the tasks must be partitioned among the units of execution (UEs) so the computational load is evenly distributed. The second challenge is to manage the dependencies between tasks. If multiple tasks update the same data structure, the programmer must ensure that the updates do not interfere with each other.

Sometimes you get lucky and the dependencies can be pulled outside the execution of the tasks. In many cases, however, you have no choice but to explicitly deal with the dependencies.

Let's consider an example to make this situation clearer. Consider a problem in which a large irregular data structure is iteratively updated by a collection of tasks. The problem is iterative, so within the tasks, data is repeatedly read and written. You can't use a trick to pull the management of this data outside of the tasks. The data is irregular, however, so a geometric decomposition cannot be used to organize the concurrency in the problem effectively.

For this case, the designer must create a set of tasks and explicitly manage the data. The designer must create an algorithm that maps the tasks onto the UEs and ensures that they make acceptably efficient progress on the problem More importantly, the reads and writes of the shared data must be managed so that consistent data is provided in a timely manner.

This pattern will discuss the issues this designer must consider and provide advice on how to effectively deal with them.

Applicability:

This pattern can be used when:

• The problem is represented as a collection of concurrent tasks.
• Dependencies between the tasks are written and read by multiple tasks in the course of the program's execution. In other words, the data shared between tasks is read/write data.

In effect, this pattern should be used when no other pattern will work. This pattern is less structured than most of the other patterns. This makes it more difficult to apply in your design. Hence, before you get too involved with this pattern, make absolutely sure you can't transform your problem into one that uses a simpler pattern (see the Related Patterns section).

Structure:

Implementations of this pattern include the following key elements:

• A mechanism to define a set of tasks and schedule their execution onto a set of UEs.
• Some mechanism to isolate and protect access to shared data.
• Some mechanism to ensure that data is available where it is needed.

Usage:

Like most of the AlgorithmStructure patterns, this pattern is typically used to provide high-level structure for an application; that is, the application is typically structured as an instance of this pattern.

Consequences:

Algorithms using this pattern are prone to a number of serious errors. A common trait of this pattern is the lack of regular structure in the interaction between tasks. There is no data decomposition or replicated data to help organize the interaction between tasks. Hence, it's a bit too easy to made mistakes with this interaction and cause race conditions, deadlock, or seriously degraded efficiency due to tasks waiting around for needed data.

Implementation:

The first step is to make really sure this is the right pattern to use. Look at any shared data and make sure that it is both written and read during the course of the concurrent execution of tasks. Read-only data can be copied, or if there is shared-memory support in the target system, you don't need to do anything special to make it available (though note that on modern cache-based architectures, you can sometimes significantly improve performance by copying data even on a shared memory system). Write-once or accumulate data can be written to local data and then recombined into the shared data structures after the concurrently executing tasks are finished. It is only when the data is both read and written during task execution that you need to use this pattern.

I need to discuss the different way this pattern looks when message passing or shared memory systems are the architectural target.

Key elements.

A mechanism to define a set of tasks and schedule their execution onto a set of UEs.

A set of tasks are represented and scheduled for execution on multiple units of execution (UEs). Usually, the tasks correspond to iterations of a loop, in which case we implement this pattern by splitting the loop between multiple UEs. The key to making algorithms based on this pattern run well is to effectively schedule their execution so the load is balanced between the UEs. The approaches used for this scheduling are similar to those described for the EmbarrassinglyParallel pattern.

Safe access to shared data.

The set of tasks cooperatively updates one or more objects. A key issue here is avoiding race conditions, which is particularly important for shared-memory environments..

Shared memory available when it is needed.

This pertains to efficiency. UEs stalled waiting for shared memory are not productive. Taken to the extreme, a UE may wait on data that will never become available -- the dreaded situation of deadlock. This is to be avoided, and is particularly important for message-passing environments.

Examples:

Something goes here.

Known Uses:

Something goes here.

Related Patterns:

This pattern is similar to many other patterns. Sometimes, the algorithm can be changed to make the dependencies separable, in which case the problem transforms into one that fits the SeparableDependencies pattern. To see if this is the case, look at the data shared between tasks. If it is read-only, write-once, or accumulation data, then the dependencies can be pulled outside the collection of tasks and the SeparableDependencies pattern can be used.

When the shared data is read/write data, you can't use tricks to pull its management out of the group of executing tasks. If the decomposition of the shared data defines a useful strategy for driving the design of the parallel algorithm, then your problem is more effectively considered as a GeometricDecomposition problem. The GeometricDecomposition pattern is very closely related to this pattern; they differ only in the focus placed on the tasks as opposed to the data decomposition. In many cases, the same problem can be attacked with either pattern.

References:

Does something go here?