1.. _Parallelizing_Flow_Graph:
2
3Parallelizing Data Flow and Dependency Graphs
4=============================================
5
6
7In addition to loop parallelism, the |full_name| library also supports graph parallelism.
8It's possible to create graphs that are highly scalable, but it is also possible to
9create graphs that are completely sequential.
10
11
12Using graph parallelism, computations are represented by nodes and the
13communication channels between these computations are represented by
14edges. When a node in the graph receives a message, a task is spawned to
15execute its body object on the incoming message. Messages flow through
16the graph across the edges that connect the nodes. The following
17sections present two examples of applications that can be expressed as
18graphs.
19
20
21The following figure shows a *streaming* or *data flow* application
22where a sequence of values is processed as each value passes through the
23nodes in the graph. In this example, the sequence is created by a
24function F. For each value in the sequence, G squares the value and H
25cubes the value. J then takes each of the squared and cubed values and
26adds them to a global sum. After all values in the sequence are
27completely processed, sum is equal to the sum of the sequence of squares
28and cubes from 1 to 10. In a streaming or data flow graph, the values
29actually flow across the edges; the output of one node becomes the input
30of its successor(s).
31
32
33.. container:: fignone
34   :name: simple_data_flow_title
35
36
37   **Simple Data Flow Graph**
38
39
40   .. container:: imagecenter
41
42
43      |image0|
44
45
46The following graphic shows a different form of graph application. In
47this example, a dependence graph is used to establish a partial ordering
48among the steps for making a peanut butter and jelly sandwich. In this
49partial ordering, you must first get the bread before spreading the
50peanut butter or jelly on the bread. You must spread on the peanut
51butter before you put away the peanut butter jar, and likewise spread on
52the jelly before you put away the jelly jar. And, you need to spread on
53both the peanut butter and jelly before putting the two slices of bread
54together. This is a partial ordering because, for example, it doesn't
55matter if you spread on the peanut butter first or the jelly first. It
56also doesn't matter if you finish making the sandwich before putting
57away the jars.
58
59
60.. container:: fignone
61   :name: dependence_graph_make_sandwitch
62
63
64   **Dependence Graph for Making a Sandwich**
65
66
67   .. container:: imagecenter
68
69
70      |image1|
71
72
73While it can be inferred that resources, such as the bread, or the jelly
74jar, are shared between ordered steps, it is not explicit in the graph.
75Instead, only the required ordering of steps is explicit in a dependence
76graph. For example, you must "Put jelly on 1 slice" **before** you "Put
77away jelly jar".
78
79
80The flow graph interface in the oneTBB library allows you to express
81data flow and dependence graphs such as these, as well as more
82complicated graphs that include cycles, conditionals, buffering and
83more. If you express your application using the flow graph interface,
84the runtime library spawns tasks to exploit the parallelism that is
85present in the graph. For example, in the first example above, perhaps
86two different values might be squared in parallel, or the same value
87might be squared and cubed in parallel. Likewise in the second example,
88the peanut butter might be spread on one slice of bread in parallel with
89the jelly being spread on the other slice. The interface expresses what
90is legal to execute in parallel, but allows the runtime library to
91choose at runtime what will be executed in parallel.
92
93
94The support for graph parallelism is contained within the namespace
95``oneapi::tbb::flow`` and is defined in the ``flow_graph.h`` header file.
96
97
98.. |image0| image:: Images/flow_graph.jpg
99.. |image1| image:: Images/flow_graph_complex.jpg
100   :width: 440px
101   :height: 337px
102
103