5.1 Tasking Model

Tasking facilitates the parallelization of applications where units of work are generated dynamically, as in recursive structures or while loops.

In OpenMP, an explicit task is specified using the task directive. The task directive defines the code associated with the task and its data environment. The task construct can be placed anywhere in the program: whenever a thread encounters a task construct, a new task is generated.

When a thread encounters a task construct, it may choose to execute the task immediately or defer its execution until a later time. If task execution is deferred, then the task in placed in a conceptual pool of tasks that is associated with the current parallel region. The threads in the current team will take tasks out of the pool and execute them until the pool is empty. A thread that executes a task might be different from the thread that originally encountered it.

The code associated with a task construct will be executed only once. A task is tied if the code is executed by the same thread from beginning to end. A task is untied if the code can be executed by more than one thread, so that different threads execute different parts of the code. By default, tasks are tied, and a task can be specified to be untied by using the untied clause with the task directive.

Threads are allowed to suspend execution of a task region at a task scheduling point in order to execute a different task. If the suspended task is tied, then the same thread later resumes execution of the suspended task. If the suspended task is untied, then any thread in the current team may resume the task execution.

The OpenMP specification defines the following task scheduling points for tied tasks:

• The point of encountering a task construct

• The point of encountering a taskwait construct

• The point of encountering a taskyield construct

• The point of encountering an implicit or explicit barrier

• The completion point of the task

As implemented in the Oracle Solaris Studio compilers, these scheduling points are also the task scheduling points for untied tasks.

In addition to explicit tasks specified using the task directive, the OpenMP specification introduces the notion of implicit tasks. An implicit task is a task generated by the implicit parallel region, or generated when a parallel construct is encountered during execution. The code for each implicit task is the code inside the parallel construct. Each implicit task is assigned to a different thread in the team and is tied; that is, the implicit task is always executed from beginning to end by the thread to which it is initially assigned.

All implicit tasks generated when a parallel construct is encountered are guaranteed to be complete when the master thread exits the implicit barrier at the end of the parallel region. On the other hand, all explicit tasks generated within a parallel region are guaranteed to be complete on exit from the next implicit or explicit barrier within the parallel region.

The OpenMP 3.1 specifiction defines various types of tasks that the programmer may choose to reduce the overhead of tasking.

An undeferred task is a task for which execution is not deferred with respect to its generating task region. That is, its generating task region is suspended until execution of the undeferred task is completed. An example of an undeferred task is a task with an if clause expression that evaluates to false. In this case, an undeferred task is generated, and the encountering thread must suspend the current task region, for which execution cannot be resumed until the task with the if clause is completed.

An included task is a task for which execution is sequentially included in the generating task region. That is, it is undeferred and executed immediately by the encountering thread.An example of an included task is a task that is a descendent of a final task (described below).

The distinction between an included task and an undeferred task is subtle. In the case of an undeferred task, the generating task region is suspended until execution of the undeferred task is completed, but the undeferred task may not be executed immediately as soon as it is encountered. The undeferred task may be placed in the conceptual pool and executed at a later time by the encountering thread or by some other thread; in the meantime, the generating task is suspended. Once the execution of the undeferred task is completed, the generating task can resume.

In the case of included task, the included task is executed immediately by the encountering thread as soon as it is encountered. The task is not placed in the pool to be executed at a later time. The generating task is suspended until the execution of the included task is completed. Once the execution of the included task is completed, the generating task can resume.

A merged task is a task whose data environment is the same as that of its generating task region. When a mergeable clause is present on a task construct, and the generated task is an undeferred task or an included task, then the implementation may choose to generate a merged task instead. If a merged task is generated, then the behavior is as though there was no task directive at all

A final task is a task that forces all of its child tasks to become final and included tasks. When a final clause is present on a task construct and the final clause expression evaluates to TRUE, the generated task will be a final task. All descendents of that final task will be both final and included tasks.