Intel® oneAPI Threading Building Blocks
Ask questions and share information about adding parallelism to your applications when using this threading library.
Announcements
The Intel sign-in experience has changed to support enhanced security controls. If you sign in, click here for more information.
2452 Discussions

Graph with multiple roots, multiple leaves

peter_h_2
Beginner
200 Views

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
200 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