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

Information on TBB Scheduler and Task Stealing

abhishek84
Beginner
590 Views

Hi all,

I am trying to get some information on the details of the TBB scheduler code in task.cpp. I basically want to profile how well the random task scheduler performs by tracking each instance of a false negative -- that is, one thread tries to steal a task from another randomly selected task queue, and fails to do so despite the fact that other task queues in fact do have tasks available.

Tracking this behavior boils down to maintaing an occupancy status per taskpool which gets modified on every task insertion and deletion. Looking through the code, I think that void GenericScheduler::spawn( task& first, task*& next ) sees the insertion of a task in the relevant queue. Therefore, I have inserted a counter increment at:

if( arena_slot==&dummy_slot ) {
try_enter_arena();
__TBB_ASSERT( arena_slot->steal_end&1, NULL );
} else {
acquire_task_pool(); GATHER_STATISTIC(acquire_task++);
}

TaskPool* tp = dummy_slot.task_pool;
next = tp->array;
tp->array = &first;

#ifdef(MY_COUNTER)
counter++
#endif

Similarly, it seems that there are two points where the tasks are removed from the task pool. The first is in

task* GenericScheduler::get_task( depth_type d ) called by the main scheduler loop wait_for_all. The second point is when a task is actually stolen which is in

task* GenericScheduler::steal_task( UnpaddedArenaSlot& arena_slot, depth_type d ) {

...

TaskPool* tp = arena_slot.task_pool;
depth_type i = tp->prefix().steal_begin;
if( i i = d;
for(; i<=steal_end>>1; ++i ) {

if( result = tp->array ) {

tp->array = result->prefix().next;

#ifdef(MY_COUNTER)
counter--
#endif

...

}

Unfortunately, just tracking these points do not suffice as my queue occupancies become negative. It therefore seems that I have missed some points in the code where tasks are added. Does anyone know where these additional points might be and where I should look for them?

Thanks!

0 Kudos
7 Replies
Dmitry_Vyukov
Valued Contributor I
590 Views
Quoting - abhishek84

I think that void GenericScheduler::spawn( task& first, task*& next ) sees the insertion of a task in the relevant queue. Therefore, I have inserted a counter increment at:

if( arena_slot==&dummy_slot ) {
try_enter_arena();
__TBB_ASSERT( arena_slot->steal_end&1, NULL );
} else {
acquire_task_pool(); GATHER_STATISTIC(acquire_task++);
}

TaskPool* tp = dummy_slot.task_pool;
next = tp->array;
tp->array = &first;

#ifdef(MY_COUNTER)
counter++
#endif

You don't take into account that spawn() can enqueue a bunch of tasks, not only single task. You must use something like:

#ifdef(MY_COUNTER)
counter += number_of_spawned_tasks;
#endif


0 Kudos
abhishek84
Beginner
590 Views
Quoting - Dmitriy V'jukov

You don't take into account that spawn() can enqueue a bunch of tasks, not only single task. You must use something like:

#ifdef(MY_COUNTER)
counter += number_of_spawned_tasks;
#endif


Hi Dmitry

Thank you for the clarification. I had suspected this after making my post but did want to ensure that this was the problem. Given this issue, is there an easy way for me to figure out how many tasks are being inserted? Is there some sort of parameter or variable in the spawn that yields this information?

Thank you!

0 Kudos
Dmitry_Vyukov
Valued Contributor I
590 Views
Quoting - abhishek84

Hi Dmitry

Thank you for the clarification. I had suspected this after making my post but did want to ensure that this was the problem. Given this issue, is there an easy way for me to figure out how many tasks are being inserted? Is there some sort of parameter or variable in the spawn that yields this information?

Thank you!

I don't see such parameters/variables, I think that you can do something like this:

[cpp]void GenericScheduler::spawn( task& first, task*& next ) {
__TBB_ASSERT( assert_okay(), NULL );
TBB_TRACE(("%p.internal_spawn entern", this ));
task* first_ptr = &first;
task** link = &first_ptr;
size_t number_of_spawned_tasks = 0;
for( task* t = first_ptr; ; t=*link )
{
number_of_spawned_tasks += 1;
...
}

#ifdef(MY_COUNTER)
counter += number_of_spawned_tasks;
#endif


[/cpp]

0 Kudos
Dmitry_Vyukov
Valued Contributor I
590 Views
Quoting - abhishek84

task* GenericScheduler::steal_task( UnpaddedArenaSlot& arena_slot, depth_type d ) {

...

TaskPool* tp = arena_slot.task_pool;
depth_type i = tp->prefix().steal_begin;
if( i i = d;
for(; i<=steal_end>>1; ++i ) {

if( result = tp->array ) {

tp->array = result->prefix().next;

#ifdef(MY_COUNTER)
counter--
#endif

...

}

It seems that you are working with not latest release. However be aware that in latest releases there is another issue - mailboxes. Single task can reside in thread's work-stealing deque AND in another thread's mailbox SIMULTANEOUSLY.

get_task() function copes with it internally. But steal_task() doesn't. I.e. steal_task() can return such task, and then the task will be discarded, because it's already consumed through get_task().

If you will be working with latest version you must account for this.

0 Kudos
Dmitry_Vyukov
Valued Contributor I
590 Views
Quoting - abhishek84
I am trying to get some information on the details of the TBB scheduler code in task.cpp. I basically want to profile how well the random task scheduler performs by tracking each instance of a false negative -- that is, one thread tries to steal a task from another randomly selected task queue, and fails to do so despite the fact that other task queues in fact do have tasks available.

I am curious what do you mean by "how well the random task scheduler performs"? What sources of false-negatives are you looking for?

I see only 2 possible sources of false-negatives:

(1) thread is unable to steal too "low-level" tasks, i.e.:

task* GenericScheduler::steal_task( UnpaddedArenaSlot& arena_slot, depth_type d ) {
task* result = NULL;
ExponentialBackoff backoff;
bool sync_prepare_done = false;
depth_type steal_end = arena_slot.steal_end;
for(;;) {
if( steal_end>>1 ) {
// Nothing of interest to steal
if( sync_prepare_done )
ITT_NOTIFY(sync_cancel, &arena_slot);
goto done;
}


(2) thread fails to "strip the proxy" after task stealing:

t = steal_task( *victim, d );
if( !t ) goto fail;
if( is_proxy(*t) ) {
t = strip_proxy((task_proxy*)t);
if( !t ) goto fail;
GATHER_STATISTIC( ++proxy_steal_count );
}

If you are trying to track these sources of false-negatives, then probably it's easier to insert statistics collection directly into the places marked with bold.

0 Kudos
Dmitry_Vyukov
Valued Contributor I
590 Views
Quoting - Dmitriy V'jukov

I am curious what do you mean by "how well the random task scheduler performs"? What sources of false-negatives are you looking for?

I see only 2 possible sources of false-negatives:

Oh, stop. I see. Are you trying to track situation when thread chooses "wrong" thread for stealing? I.e. thread 1 tries to steal work from thread 2, but thread 2 also doesn't have any work. But there is thread 3 which do has some work to steal.

0 Kudos
abhishek84
Beginner
590 Views
Quoting - Dmitriy V'jukov

Oh, stop. I see. Are you trying to track situation when thread chooses "wrong" thread for stealing? I.e. thread 1 tries to steal work from thread 2, but thread 2 also doesn't have any work. But there is thread 3 which do has some work to steal.

Hi Dmitriy

First off, thank you very much for your detailed responses. As for what exactly I am trying to track, yes, the false negatives are indeed the case when a thread chooses the "wrong" thread for stealing. That is precisely what I am attempting to track.

In terms of getting the number of spawned tasks, I implemented your suggestion and that definitely solves the occupancy problems I was seeing before. Thank you for mentioning the issue of mailboxes as well. I had completely overlooked this and it would be interesting to study this aspect too!

Abhishek

0 Kudos
Reply