Community
cancel
Showing results for 
Search instead for 
Did you mean: 
peter_h_2
Beginner
41 Views

Graph with multiple roots, multiple leaves

Hello

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

EG if we take the graph in  https://software.intel.com/en-us/node/506110 ; 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?

Cheers

PH

0 Kudos
1 Reply
RafSchietekat
Black Belt
41 Views

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.

 

 

Reply