Intel® oneAPI Threading Building Blocks
Ask questions and share information about adding parallelism to your applications when using this threading library.

Question about wait_for_all()

Anastopoulos__Nikos
292 Views

Hi,

I am trying to figure out what exactly happens when a task calls wait_for_all(), in a scenario like this one:

------------------------------------------------------------
FibTask& a = *new(allocate_child() ) FibTask(n-1,&x);
FibTask& b = *new(allocate_child() ) FibTask(n-2,&y);
set_ref_count(3);
spawn(b);
spawn(a);
wait_for_all();

//continuation code
------------------------------------------------------------

Suppose that the above task ("parent") executes in worker thread W0. According to what is described in TBBs manuals, in the first spawn task b will be pushed on W0's de-queue, and then task a. From this point on, tasks a and b are available for stealing by other workers or for execution by W0. Let's say that b and a are stolen by two other workers (but I believe my questions below are also valid if W0 is the only worker). Then, W0 will execute wait_for_all(), and I'm seeing the following possible scenarios:

A) wait_for_all() will cause W0 to sleep or busy-wait, until it is notified that a and b are finished. I don't think this is likely, though, since W0 would remain inexploitable, and this is something that TBBs would try to avoid. Also, notification could be quite expensive, if it implies some kind of OS intervention (system calls) and/or happens quite frequently.

B) wait_for_all() will cause the parent task to push itself in W0's de-queue, in an attempt to free W0. But if the parent is pushed into W0's queue head, W0 will constantly dequeue, execute and enqueue the parent task (if we assume that all other workers are busy), essentially performing
some kind of polling for a's and b's termination. But in this way W0 will be prevented from exploiting potential parallelism created on other workers, by stealing tasks from them.

C) wait_for_all() will cause the parent task to be suspended, somehow, in a way that frees W0 for further use. When a and b terminate, the parent will be resumed, somehow.

What of the above is actually happening?

0 Kudos
4 Replies
RafSchietekat
Valued Contributor III
292 Views

The data structure is a "deque", not a "de-queue". The mechanism is a combination of c and a. Notification cost is amortised by spinning before sleeping.

0 Kudos
Anastopoulos__Nikos
292 Views

Raf Schietekat wrote:

The mechanism is a combination of c and a. Notification cost is amortised by spinning before sleeping.

Thanks for the answer. So, I guess that it is the parent task that goes to sleep (after spinning), and not the worker thread itself, right?

Also, where is the parent task put while suspended? In the queue, or in some other, special place? Is it prioritized somehow in order to resume as soon as possible when its children terminate? And finally, will it be resumed by the worker from which it was suspended, or it can be stolen by other workers? 

Thanks in advance.

0 Kudos
RafSchietekat
Valued Contributor III
292 Views

The parent task is being executed by a thread, which, while the dependencies have not finished, and as if it were executing a subroutine, will try to find work, and if unsuccessful will spin and eventually go to sleep (except for the master thread, which keeps spinning in the current implementation). The parent task is just a frame on the stack, together with whatever else is above it, until it becomes active again, which may be an indefinite time after the dependencies have finished. The task therefore remains associated with the same thread throughout its execution.

What is the higher-level question?

0 Kudos
Anastopoulos__Nikos
292 Views

Raf Schietekat wrote:

The parent task is being executed by a thread, which, while the dependencies have not finished, and as if it were executing a subroutine, will try to find work, and if unsuccessful will spin and eventually go to sleep (except for the master thread, which keeps spinning in the current implementation). The parent task is just a frame on the stack, together with whatever else is above it, until it becomes active again, which may be an indefinite time after the dependencies have finished. The task therefore remains associated with the same thread throughout its execution.

This clears things a lot, thank you. 

Raf Schietekat wrote:

What is the higher-level question?

There was not any particular high-level question. I was just trying to figure out how task suspension/resumption works in TBBs, since, as far as I understand, the library lacks any mechanism for context save and restore. 

0 Kudos
Reply