Dependency Flow Graph Example

In the following example, five computations A-E are set up with the partial ordering shown below in “A simple dependency graph.”. For each edge in the flow graph, the node at the tail of the edge must complete its execution before the node at the head may begin.

../../../../_images/dep_graph.jpg

A simple dependency graph.

#include <cstdio>
#include "tbb/flow_graph.h"

using namespace tbb::flow;

struct body {
    std::string my_name;
    body(const char *name) : my_name(name) {}
    void operator()(continue_msg) const {
        printf("%s\n", my_name.c_str());
    }
};

int main() {
    graph g;

    broadcast_node< continue_msg > start(g);
    continue_node<continue_msg> a(g, body("A"));
    continue_node<continue_msg> b(g, body("B"));
    continue_node<continue_msg> c(g, body("C"));
    continue_node<continue_msg> d(g, body("D"));
    continue_node<continue_msg> e(g, body("E"));

    make_edge(start, a);
    make_edge(start, b);
    make_edge(a, c);
    make_edge(b, c);
    make_edge(c, d);
    make_edge(a, e);

    for (int i = 0; i < 3; ++i) {
        start.try_put(continue_msg());
        g.wait_for_all();
    }

    return 0;
}

In this example, nodes A-E print out their names. All of these nodes are therefore able to use struct body to construct their body objects.

In function main, the flow graph is set up once and then run three times. All of the nodes in this example pass around continue_msg objects. This type is used to communicate that a node has completed execution.

The first line in function main instantiates a graph object g. On the next line, a broadcast_node named start is created. Anything passed to this node will be broadcast to all of its successors. The node start is used in the for loop at the bottom of main to launch the execution of the rest of the flow graph.

In the example, five continue_node objects are created, named a - e. Each node is constructed with a reference to graph g and the function object to invoke when it runs. The successor / predecessor relationships are set up by the make_edge calls that follow the declaration of the nodes.

After the nodes and edges are set up, the try_put in each iteration of the for loop results in a broadcast of a continue_msg to both a and b. Both a and b are waiting for a single continue_msg, since they both have only a single predecessor, start.

When they receive the message from start, they execute their body objects. When complete, each of them forwards a message to a successor, and so on. The graph uses tasks to execute the node bodies as well as to forward messages between the nodes, allowing computation to execute concurrently when possible.

See also: