Channels ▼
RSS

Tools

The Intel Threading Building Blocks Flow Graph


Intel Threading Building Blocks (TBB) 4.0 includes flow graph as a fully supported feature. The flow graph supports both static and dynamic dependency graphs, as well as reactive graphs that respond to and pass data messages. Introduced as a Community Preview feature in Intel TBB 3.0 Update 5, the flow graph interface has been refined and improved based on several months of user feedback [1].

Numerous development teams across the media, gaming, financial services, and technical computing segments have been evaluating the flow graph as an Intel TBB 3.0 Community Preview feature. Before the flow graph was available, some event-based and reactive programs were simply impractical to implement using Intel TBB. In other cases, users were either writing complex code that used the low-level Intel TBB tasking interface directly, or were over-constraining their parallelism to use an Intel TBB pipeline. The flow graph provides a more natural fit for many applications, while maintaining or improving performance over other Intel TBB-based solutions.

An Overview of the Flow Graph Interface

An Intel TBB flow graph consists of three primary components: a graph object, nodes, and edges. The graph object provides methods to run tasks in the context of the graph and to wait for the graph to complete. Nodes generate, transform, or buffer messages. Edges wire the graph together, connecting the nodes that send messages to the nodes that should receive them. There are several types of nodes, as shown in Figure 1. There are functional nodes that execute user code, buffering nodes, nodes that join and split messages, and several other miscellaneous node types [2].

Figure 1: The node types supported by the Intel Threading Building Blocks flow graph.

A Dependence Graph Example

Figure 2 shows an approach to implementing a wave-front computation using a set of continue_node objects. In this example, each computation must wait for the computation above it and the computation to its left to complete before it can start executing. A continue_node starts executing when it receives a continue_msg from each of its predecessors.

Figure 2: Using an Intel TBB flow graph to express a wave-front calculation.

In Listing One, this approach is used to implement a blocked wavefront calculation, where each computation updates a BxB block of the matrix values. The for loop in function run_graph creates the set of the continue_node objects. In the listing, the continue_node constructor is passed a reference to the graph object g and a function object (or in this case a lambda expression) that calls update_block on its block.

Listing One: An implementation of a blocked wave-front calculation.

// M and N are the number of rows and columns in the matrix 
// MB and NB are the number of blocks in the rows and columns 
// B is the block size (BxB squares) 
 
using namespace tbb;  
using namespace tbb::flow; 
 
double value[M][N];  
 
graph g; 
continue_node<continue_msg> *node[MB][NB]; 
 
double run_graph( ) { 
 value[M-1][N-1] = 0; 
   for( int i=MB; --i>=0; ) { 
    for( int j=NB; --j>=0; ) { 
     node[i][j] = 
      new continue_node<continue_msg>( g, 
        [=]( const continue_msg& ) { update_block( i, j ); } ); 
      if ( i + 1 < MB ) make_edge( *node[i][j], *node[i+1][j] ); 
      if ( j + 1 < NB ) make_edge( *node[i][j], *node[i][j+1] ); 
   } 
 } 
 node[0][0]-<try_put(continue_msg()); 
 g.wait_for_all(); 
 for( int i=0; i<MB; ++i ) 
    for( int j=0; j<NB; ++j ) 
         delete node[i][j]; 
 return value[M-1][N-1]; 
 } 

Once the flow graph is set up in the example, a continue_msg is put to the node in the upper left corner, node[0][0], to start the wave front through the graph. The call to g.wait_for_all() blocks until the entire wave-front computation completes.

A complete description of this example and complete source code can be found in "Implementing a wave-front computation using the Intel Threading Building Blocks flow graph."


Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 

Video