- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content
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
#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
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!
Link Copied
- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content
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
#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
- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content
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!
- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content
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]
- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content
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
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.
- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content
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.
- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content
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.
- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content
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
![](/skins/images/872293744008A34B36F8ABF94A46CC66/responsive_peak/images/icon_anonymous_message.png)
- Subscribe to RSS Feed
- Mark Topic as New
- Mark Topic as Read
- Float this Topic for Current User
- Bookmark
- Subscribe
- Printer Friendly Page