Modeling Complex Systems with Graphs in Threading Building Blocks Share your comment!


Parallel programming isn’t always just a simple matter of writing loops that run at the same time. While that might work for certain individual algorithms, bigger software systems are certainly more complex and require a type of parallel programming that goes beyond simple loops and spawning C++ threads.   

Instead, most systems are more likely to be along the lines of, “Step A must precede all steps, but Steps B and C can run in parallel.” And you might even have more complexity like, “Step B1 follows step B, and Step C1 follows both Step B1 and C.” Such systems can be diagrammed using a directed graph. A directed graph is a type of graph that contains nodes with arrows pointing between nodes. In this case, each node represents a task to perform.

Modeling such systems directly can be difficult and result in bugs. And that’s where the graph classes in Threading Building Blocks help. TBB includes several classes as part of the tbb:flow namepsace, such as a basic graph class, and a basic node class.

The Importance of Communications Between Nodes 

Nodes can provide functions that execute, or they can serve as message handlers. The idea here is that you can have your nodes communicate with each other and send data back and forth between them. This goes beyond the simple matter of having them execute in an order determined by the graph. Helping with this are other node classes derived from the basic node class. (In fact, the basic node class really provides nothing more than a virtual destructor.)

In addition to the node class, there are two other classes that serve as abstract bases: sender and receiver. These classes give a node communication capabilities. Both are template classes and abstract; as such you need to derive new classes from them.

Send, Receive, Continue Classes 

The receiver class includes a virtual abstract function called try_put. This is called to “put” an item into this receiver. Similarly, the sender class includes a function called try_get. This is called to get an item from this sender. (That seems a bit backwards to me in terms of nomenclature, but that’s okay.)

A class called continue_receiver is derived from receiver, which takes as a template parameter a continue_msg. This abstract class provides the methods necessary for executing nodes in order without having to pass messages between them. The idea is simple: This class includes an abstract function called execute, as well as the try_put function. Additionally, it includes a constructor that has as a parameter the number of preceding nodes. When those preceding nodes call try_put this number of times, the execute function gets called. (By providing this count, you can have the node wait for more than one node.)

But remember, continue_receiver is an abstract class. There’s also a class called continue_node. This class is derived from continue_receiver, as well as graph_node. It includes the continue_receiver functionality I just described; and by deriving it from graph_node, it can serve as a node inside a graph. But beyond that it also implements the sender abstract class. Why? Because while this node will execute after other nodes, it in turn might need to notify nodes after it to execute as well. In other words, this class servers as both a receiver and a sender, and can therefore function inside a graph, waiting for its time to run, and then notifying subsequent nodes of this same class to run.

That’s the basics of how this works. We don’t have room to get into actual code yet, and there are still more classes to explore. But next week I’ll look at some simple code to demonstrate what I’ve covered so far. I encourage you to take a look at the documentation.   

Have you worked with the graphs at all? Have you run into any stumbling blocks or problems? Let me know in the comments below.

Posted on November 2, 2012 by Jeff Cogswell, Geeknet Contributing Editor