Scheduler bypass semantics?

[Charles_Tucker]

I'm currently working on altering the scheduler decisions made, to experiment with other methods and contrast them against the work-stealing approach that is currently core to TBB. In enforcing specific task execution orders, it came to my attention that there are two places where scheduler decisions are effectively bypassed (spawn_and_wait_for_all, and returned task*s). Given that the TBB interface doesn't actually specifiy scheduling order (i.e. work-stealing is not guaranteed), are the scheduler-bypasses semantically meaningful? Put another way, does TBB guarantee that the task returned from an execution is the next task executed on that worker thread?

To put the question one last time, if I swap out the work-stealing scheduler, must I honor returned tasks as the next execution, instead of simply spawning them and making a normal decision? The difference is between a hint and an explicit bypass semantic, and it's not clear to me which is true.

[Charles_Tucker]

Another place that this seems to come up is internally, deep within the triple-loop of wait_for_all, in switch case task::executing, where the scheduler will select the continuation of a task if the continuation is ready, and there was no returned task, to execute next. I think this can be safely changed (so long as the continuation is spawned), given that my scheduler decisions don't allow for the same spawn/get_task elimination.

[AJ13]

Quoting - Charles Tucker

Another place that this seems to come up is internally, deep within the triple-loop of wait_for_all, in switch case task::executing, where the scheduler will select the continuation of a task if the continuation is ready, and there was no returned task, to execute next. I think this can be safely changed (so long as the continuation is spawned), given that my scheduler decisions don't allow for the same spawn/get_task elimination.

Check task.c:2227... the t_next = t->execute().... I think this is where the decision is honored or not... but I'm not a scheduling expert. This seems to be the only place that execute() is really called.

[RafSchietekat]

"Put another way, does TBB guarantee that the task returned from an execution is the next task executed on that worker thread?"
According to "8.1 Scheduling Algorithm" in the latest "Reference (Open Source).pdf" (revision 1.13), yes, although this could still be merely descriptive instead of prescriptive. From a brief look at the code, the only thing that could intervene is cancel_group_execution(). I don't know whether any non-NULL return values currently are more than "just" hints.

But regardlessly the nature of concurrency is that anything can happen between the end of one task execution and the start of another, so why couldn't that be rescheduled onto the same thread, if parent-child relationships at least are observed? Required-concurrency problems could still throw a wrench in the works, though, as they sometimes do, even if the reference manual does not take them into account. You'll often be paying a (significant?) performance price for ignoring the hint, of course (due to cache-locality issues), and I bet it'll look really silly if the interjected task blocks, so what do you have in mind to make all that worthwhile?

[Alexey-Kukanov]

Quoting - Charles Tucker

I'm currently working on altering the scheduler decisions made, to experiment with other methods and contrast them against the work-stealing approach that is currently core to TBB. In enforcing specific task execution orders, it came to my attention that there are two places where scheduler decisions are effectively bypassed (spawn_and_wait_for_all, and returned task*s). Given that the TBB interface doesn't actually specifiy scheduling order (i.e. work-stealing is not guaranteed), are the scheduler-bypasses semantically meaningful? Put another way, does TBB guarantee that the task returned from an execution is the next task executed on that worker thread?

To put the question one last time, if I swap out the work-stealing scheduler, must I honor returned tasks as the next execution, instead of simply spawning them and making a normal decision? The difference is between a hint and an explicit bypass semantic, and it's not clear to me which is true.

Returning a task object from execute() is explicit bypass semantics. As Raf correctly noted, it can only be skipped if the corresponding task group is cancelled; and neither thread will execute cancelled tasks.

Execution of the single task passed to spawn_root_and_wait/spawn_and_wait_for_all on the same thread is also guaranteed, according tothe TBB Reference.

Immediate execution of a ready continuation task is an optimization; as you may see it is not guaranteed.

However if you are experimenting with different scheduling policies, I do not see why you should oblige to the TBB guarantees. In my opinion, experimentation is the process of changing assumptions and seeing what happens then :)