Intel® Software Network

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!

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

void GenericScheduler::spawn( task& first, task*& next ) {
    __TBB_ASSERT( assert_okay(), NULL );
    TBB_TRACE(("%p.internal_spawn enter\n", 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

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.

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<d ) {
// 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.

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