Intel® Threading Building Blocks Version 3.0 Update 5 Introduces Graph as a Community Preview Feature.

There are some applications that, even on systems with shared memory, are best organized as computations that explicitly pass messages. These messages may contain data or simply act as signals that a computation has completed. The new class graph and its associated nodes can be used to express such applications. These classes are available as a Community Preview (CP) feature in Intel® Threading Building Blocks Version 3.0 Update 5. You can download the open-source version of this release at www.threadingbuildingblocks.org and are encouraged to provide feedback about its features and design via the forum.

There are three types of components used to implement a graph: a graph object, nodes and edges.

A user first creates a graph object. This object acts as the owner of all tasks created on behalf of the graph and its nodes. In many ways its like a task_group, and users can call wait_for_all on the graph object if they need to wait for all of the tasks related to the graph to complete.

Next users create the nodes and edges. Nodes process or buffer messages as they pass through them. There are some node types that invoke user-provided function objects, while others direct, buffer or combine messages in a pre-specified way. The user creates nodes and then links them together by calling the functions make_edge or make_edges.

In future posts over the coming weeks, I will provide several example applications that highlight key features of the graph and its node types. A detailed description of class graph and the different node types are provided in Appendix D of the Intel® Threading Building Blocks Reference Manual.

As with all Community Preview features, the graph must be explicitly enabled by setting its macro before including its header:

#define TBB_PREVIEW_GRAPH 1
#include "tbb/graph.h"

Below are brief descriptions of the node types currently provided in graph.h. In future posts, I will use these nodes to construct several example applications.

The first three node types invoke user-provided function objects and are used to wrap user computations:

template < typename OType > class source_node;
A source_node has no predecessors in the graph. It generates messages of a generic type OType by calling a user-provided body object. The generated message is broadcast to all of its successors.

template < typename IType, typename OType > class function_node;
A function_node receives messages of a generic type IType, applies a body object to each message, and broadcasts its output of type OType to its successors in the graph.

template < typename OType > class executable_node;
An executable_node receives messgaes of a type continue_msg. When it has received a continue_msg from each of its predecessors, it invokes its body object to generate a message of type OType that is passes to its successors in the graph.

The remaining 10 node types all perform pre-defined operations that buffer, direct or combine messages:

class contine_node;
A continue_node receives continue_msg messages. When it receives a message from each of its predecessors, it forwards a single continue_msg to all of its successors.

template < typename T > class broadcast_node;
A node that broadcasts each incoming message to all of its successors.

template < typename T > class write_once_node;
A write_once_node buffers a single item that cannot be over written. The value may be cleared explicitly, after which a new value may be set.

template < typename T > class overwrite_node;
An overwrite_node buffers a single item that can be over written.

template < typename T > class buffer_node;
A buffer_node is an unbounded buffer of messages of type T. Messages are forwarded in arbitrary order.

template < typename T > class queue_node;
A queue_node is an unbounded buffer of messages of type T. Messages are forwarded in first-in first-out order.

template < typename T > class priority_queue_node;
A priority_queue_node is an unbounded buffer of messages of type T. Messages are forwarded in priority order.

template < typename T > class sequencer_node;
A sequencer_node is an unbounded buffer of messages of type T. Messages are forwarded in sequence order.

template < typename T > class limiter_node;
A limiter_node limits the number of messages that may pass through it. It contains an embedded continue_node that may be used to decrement the count to allow additional items through.

template < typename T1, typename T2, … > class join_node;
A join_node creates a std::tuple<T1,T2,…> from a set of messages received at its inputs.

For more complete information about compiler optimizations, see our Optimization Notice.

Comments

Humm... sounds like Join calculus combined with actor-oriented system. Nice!

All about lock-free algorithms, multicore, scalability, parallel computing and related topics:
http://www.1024cores.net


This is very interesting. I was wondering if you had any comments on using this for the problem described in my previous forum posting here:
http://software.intel.com/en-us/forums/showthread.php?t=73305&o=a&s=lr

I ended up modeling my solution after Arch Robison's post here:
http://software.intel.com/en-us/forums/showpost.php?p=115072

Thanks!


e4lam, I think that graph might solve your problem. Graphs can be constructed dynamically, they can be re-used, and you can add or remove edges dynamically. And graphs persist, so you can re-execute them multiple times. The key to dynamically building graphs is to use buffers for the continue messages. I plan to write a blog soon to show how this can be done, but it must wait on a bug-fix in writeonce_node that will be available in the next release of TBB. So please stay tuned...