Here's how tasks got introduced by Larry:
A task is similar to a lambda function in C#. The task directive is used to describe an explicit task as follows (C/C++ is used for the examples for convenience, there are analogs for Fortran):
#pragma omp task [clauses]
{
// code
}
When a thread encounters the task directive, the data environment is captured. That environment, together with the code represented by the structured block, constitutes the generated task. The task may be executed immediately or may be queued for execution.
Aside from the fact that referring to lambda functions as something from C# would be like introducing Dorian Gray as a fictional
character from the major Hollywood movie the rest of the paragraph looks
remarkably similar to the concepts from the Cilk language. And this is a "good thing" (tm). Cilk grew out of practical needs
for coding a very diverse set of applications on shared memory systems. Pretty much every singly new keyword that Cilk introduced
has a war story of how it came about. It is not perfect (no parallel framework is) but it can be considered an important
yardstick for evaluating aspiring parallel frameworks for C-like languages. My very firm personal belief is that if Cilk semantics
can NOT be easily expressed then a framework has serious issues. With that in mind, lets see how OpenMP 3.0 tasking model stacks up. It looks like it is fair to say that #pragma omp task is like a spawn and inlet keywords rolled into one and #pragma omp taskwait is like sync, right? Not quite. The biggest difference is that in OpenMP 3.0 it is now possible for a procedure to spawn a bunch of tasks, exit but have the children tasks happily running (Cilk's implicit sync just before the return statement doesn't apply in OpenMP 3.0). This is bad news for runtime ("cactus stack" optimizations become very hard to do) and bad news for debugging and analysis (what should the stack of such an "orphan" task look like?). It also widens the gap between the syntax structure of the program and its semantics. Is it good for anybody? Is it good for you? I'm really curious to see your comments. For now, however, here's my first bullet on "what's wrong with OpenMP 3.0 tasking model" list:
- Orphan tasks
| Cilk: | OpenMP 3.0: | |
cilk int fib (int n)
{
int x = 0;
inlet void summer (int result)
{
x += result;
return;
}
if (n<2) return n;
else {
summer(spawn fib (n-1));
summer(spawn fib (n-2));
return (x);
}
}
|
int fib(int n)
{
int res = 0;
if (n<2) return n;
else
{
#pragma omp task
{
#pragma omp atomic
res += fib(n-1);
}
#pragma omp task
{
#pragma omp atomic
res += fib(n-2);
}
}
#pragma omp taskwait
return res;
}
|
- Lack of support for speculative tasks
#pragma omp parallel
{
#pragma omp single private(p)
{
p = listhead ;
while (p) {
#pragma omp task
process (p)
p=next (p) ;
}
}
}
First of all, we no longer know the size of the entire job like we used to in case of the #pragma omp parallel for.
Which mens that for a list of gazillion items we will either have to create gazillion tasks at once (not likely) or
to suspend/resume tasks that are trying to create more tasks (how is runtime to know who is the real producer?).
Also, we can no longer give scheduler any hints as to how many iterations of the loop body would constitute a
reasonable chunk to be given to one thread (scheduling clauses are not applicable to tasks). The API now got much simpler:
we can produce as many tasks as we see fit; and runtime is responsible for scheduling worker threads in order
to complete all of them. In a sense, we find ourselves
dealing with a classical Producer-consumer problem.
With a crucial complication that we have no explicit control over the size of the queue, nor do we have any
way for establishing explicit communication between the producer and the consumer. We are left to the mercy of
a runtime (and hacks like untied tasks as explained in the BOF slides). We sure deserve better, and
with that I give you my list of what's wrong with OpenMP 3.0 tasking model:
- Lack of support for task queue management
- Lack of support for speculative tasks
- Orphan tasks
![[RSS Newsfeed]](/themes/sotto/images/valid-rss.png)