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

Graph with multiple roots, multiple leaves



How do we implement an acyclic dependency graph which has multiple roots and/or multiple leaves?

EG if we take the graph in ; without link X0,1-X0,2 we get a tree with two roots.

If we remove link X2,0-X2,1 we get a tree with two leaves. 

What does the code for these two graphs look like?



0 Kudos
1 Reply
Valued Contributor III

I would be careful about words like "root" and "leaf", because with TBB task trees the root is the successor of its descendants, not the predecessor, so that might be confusing. In an alternative implementation, you could even specify a spanning tree with x2,3 as the root task and additional references to fill out the dag, so...

To come back to the question, in any dag you should be able to spawn all the tasks without predecessors, and then run a loop where you use wait_for_all() on each of the tasks without successors (essential for synchronisation, don't forget to set up one extra reference for each of them), execute() them, copy their values, and destroy them. You could even do that loop in parallel if you have many such tasks, but otherwise it is not essential for performance even if the rest of the graph is very large. The User Guide just shows a special case with only one of each kind, also allowing the spawn() and the wait_for_all() to be merged in a single call.

Other approaches are also possible, but I'm taking your requirements at face value.



0 Kudos