schedule a directed acyclic graph using continuations

[Alexander_Herz]

I want to schedule a DAG of tasks, where the source and sink of the dag must be in the same task.
So the source/sink task spawns the childs of the source and block-waits for the result (somehow).
E.g. :

source
/ | \\
t2 t3 t4
| \\ | |
| t5 |
t7 \\ |
\\ t6
\\ /
sink

I would like to use contuniations for everything but the sink (which as said needs to block-wait as sink and source must be in the same task). Using a continuation is easy, when 2 tasks have only one successor
(e.g. t4 and t5 must execute before t6) so t6 is a continuation with t4 and t5 as childs.
I have no idea how to setup the continuations when there are multiple successors, e.g.
t5 is successor of t2 and t3. additionally, t7 is successor of t2.
Do I have to allocate t2 twice as child (doesn't make any sense).

Thx,
Alex

[robert-reed]

Have you looked into the possibility of using TBB Flow Graph to define your DAGs rather than trying to write and maintain your own continuationcode (and struggling with how to order the continuations)?

[RafSchietekat · Accepted solution]

"Have you looked into the possibility of using TBB Flow Graph to define your DAGs rather than trying to write and maintain your own continuationcode (and struggling with how to order the continuations)?"
Isn't that for continuously flowing data? This looks more like a one-shot situation.

But I'm not sure I understand how "continuations" would be used here. I understand those to be a technical alternative to blocking call for children (parent->children->continuation instead of parent->children->parent), to avoid holding up a frame on the stack, but still logically implementing recursion. In this case it's just a DAG of tasks that is set up and executed, apparently in one direction, i.e., without recursion. You can do that all from the source/sink task. Use the number of predecessors as the reference count in each task, choose a subtree to set up parent/child relationships, and implement the missing links as explicit reference decrements at the end of a predecessor's execution. The tasks can be either ad-hoc for their topology, or have a dynamic set of (additional) successors, probably at some additional cost. Did I miss anything?

[Alexander_Herz]

There is no continous data flow here, so the flow graph won't help me. Doing explicit refcounting and maintaining my own references on the successor task appears to be the only viable solution. I was just supprised, that the inherent parent/child relationship used by the tbb tasks is not flexible enough to handle this case ...

Thx,
Alex

[RafSchietekat]

"I was just supprised, that the inherent parent/child relationship used by the tbb tasks is not flexible enough to handle this case ..."
Having a single successor ("parent") is probably more common (that API is already complex enough), and tasks are probably more of a technical layer (where experts are not afraid to enter). Have a look at "General Acyclic Graphs of Tasks" in the Tutorial: it doesn't even consider a spanning subtree (all the tasks are root tasks, all dependencies are explicit).

[Alexander_Herz]

Ah, this is exactly the example I was looking for. It should be part of the examples that come with the actual library download and not be hidden in some obscure pdf :)

I find the implicit assumption of recursive tasks (parent/child api) rather unintuitive because it is tailored towards a specific usage of tasks. The general case (n predecessors with m successors) could easily handle that as well. Even worse, most of the documentation never mentions the more general case or that you are actually allowed to do refcounting to achieve this (I read most of the pdfs and the oreilly book).

So far, in most cases where I used the api in any way not shown in the documentation I ran into problems, which is not very nice for a general purpose library. Second guessing the implementation isn't exactly fun :(

Alex

[Alexey-Kukanov]

In fact, the flow graph has also support for control flow, which is your case. I think it should actually work for you; consider giving it a try.

[Alexey-Kukanov]

Quoting Alexander Herz

I find the implicit assumption of recursive tasks (parent/child api) rather unintuitive because it is tailored towards a specific usage of tasks. The general case (n predecessors with m successors) could easily handle that as well. Even worse, most of the documentation never mentions the more general case or that you are actually allowed to do refcounting to achieve this (I read most of the pdfs and the oreilly book).

So far, in most cases where I used the api in any way not shown in the documentation I ran into problems, which is not very nice for a general purpose library. Second guessing the implementation isn't exactly fun :(

The TBB tasks were designed, and evolved incrementally since that, as the low-level mechanism for efficient implementation of high-level constructions: parallel algorithms, and recently the flow graph. Later we added the functions to directly manipulate the task reference counter; it was absent when the TBB book was written. The example was added to the tutorial at the time the functionality was added, or soon after (as far as I can tell, it's the revision 1.15 dated August 2009; and of course the API is mentioned in the Reference since the same time. So, while theremight becases where the documentation is insufficient, I do not think this is one of these cases.

As for running into problems when you use the API in a non-documented way, why exactly is it a surprise to you, and why you think it's"not nice"? The documentation describes how the library is intended to be used; if you go beyond that, you always certainly step into some grey area, perhaps relying on non-documented features that may change. Or do I misinterpret your words somehow?

Anyway, thanks for your opinion. If you can point to specific functionality that in your opinion is not documented enough, or have other suggestions of what can be improved, please tell us, and we will try to do better.