1.. _Dependence_Graph:
2
3Dependence Graph
4================
5
6
7In a dependence graph, the nodes invoke body objects to perform
8computations and the edges create a partial ordering of these
9computations. At runtime, the library spawns and schedules tasks to
10execute the body objects when it is legal to do so according to the
11specified partial ordering. The following figure shows an example of an
12application that could be expressed using a dependence graph.
13
14
15.. container:: fignone
16   :name: dependence_graph_make_sandwitch
17
18
19   Dependence Graph for Making a Sandwich
20
21
22   .. container:: imagecenter
23
24
25      |image0|
26
27
28Dependence graphs are a special case of data flow graphs, where the data
29passed between nodes are of type oneapi::tbb::flow::continue_msg. Unlike a
30general data flow graph, nodes in a dependence graph do not spawn a task
31for each message they receive. Instead, they are aware of the number of
32predecessors they have, count the messages they receive and only spawn a
33task to execute their body when this count is equal to the total number
34of their predecessors.
35
36
37The following figure shows another example of a dependence graph. It has
38the same topology as the figure above, but with simple functions
39replacing the sandwich making steps. In this partial ordering, function
40A must complete executing before any other computation starts executing.
41Function B must complete before C and D start executing; and E must
42complete before D and F start executing. This is a partial ordering
43because, for example, there is no explicit ordering requirement between
44B and E or C and F.
45
46
47.. container:: fignone
48   :name: simple_dependence_graph
49
50
51   Simple Dependence Graph
52
53
54   .. container:: imagecenter
55
56
57      |image1|
58
59
60To implement this as a flow graph, continue_node objects are used for
61the nodes and continue_msg objects as the messages. A continue_node
62constructor takes two arguments:
63
64
65::
66
67
68   template< typename Body > continue_node( graph &g, Body body)
69
70
71The first argument is the graph it belongs to and the second is a
72function object or lambda expression. Unlike a function_node, a
73continue_node is always assumed to have unlimited concurrency and will
74immediately spawn a task whenever its dependencies are met.
75
76
77The following code snippet is an implementation of the example in this
78figure.
79
80
81::
82
83
84   typedef continue_node< continue_msg > node_t;
85   typedef const continue_msg & msg_t;
86
87
88   int main() {
89     oneapi::tbb::flow::graph g;
90     node_t A(g, [](msg_t){ a(); } );
91     node_t B(g, [](msg_t){ b(); } );
92     node_t C(g, [](msg_t){ c(); } );
93     node_t D(g, [](msg_t){ d(); } );
94     node_t E(g, [](msg_t){ e(); } );
95     node_t F(g, [](msg_t){ f(); } );
96     make_edge(A, B);
97     make_edge(B, C);
98     make_edge(B, D);
99     make_edge(A, E);
100     make_edge(E, D);
101     make_edge(E, F);
102     A.try_put( continue_msg() );
103     g.wait_for_all();
104     return 0;
105   }
106
107
108One possible execution of this graph is shown below. The execution of D
109does not start until both B and E are finished. While a task is waiting
110in the wait_for_all, its thread can participate in executing other tasks
111from the oneTBB work pool.
112
113
114.. container:: fignone
115
116
117   Execution Timeline for a Dependence Graph
118
119
120   .. container:: imagecenter
121
122
123      |image2|
124
125
126Again, it is important to note that all execution in the flow graph
127happens asynchronously. The call to A.try_put returns control to the
128calling thread quickly, after incrementing the counter and spawning a
129task to execute the body of A. Likewise, the body tasks execute the
130lambda expressions and then put a continue_msg to all successor nodes,
131if any. Only the call to wait_for_all blocks, as it should, and even in
132this case the calling thread may be used to execute tasks from the
133oneTBB work pool while it is waiting.
134
135
136The above timeline shows the sequence when there are enough threads to
137execute all of the tasks that can be executed concurrently in parallel.
138If there are fewer threads, then some tasks that are spawned will need
139to wait until a thread is available to execute them.
140
141
142.. |image0| image:: Images/flow_graph_complex.jpg
143   :width: 440px
144   :height: 337px
145.. |image1| image:: Images/dependence_graph.jpg
146.. |image2| image:: Images/execution_timeline_dependence.jpg
147
148