Task - tree sum


Introduction

This is a simple example that sums values in a tree. The example exhibits some speedup, but not a lot, because it quickly saturates the system bus on a multiprocessor. For good speedup, there needs to be more computation cycles per memory reference. The point of the example is to teach how to use the raw task interface, so the computation is deliberately trivial.


SerialSumTree.cpp

==============================================================================

Copyright 2005-2006 Intel Corporation. All Rights Reserved.

==============================================================================

#include "common.h" 

Value SerialSumTree( TreeNode* root ) { 

Value result = root->value; 

if( root->left ) 

result += SerialSumTree(root->left); 

if( root->right ) 

result += SerialSumTree(root->right); 

return result; 

} 

 


SimpleParallelSumTree.cpp

==============================================================================

Copyright 2005-2006 Intel Corporation. All Rights Reserved.

==============================================================================

#include "common.h" 

#include "tbb/task.h" 

class SimpleSumTask: public tbb::task { 

Value* const sum; 

TreeNode* root; 

public: 

SimpleSumTask( TreeNode* root_, Value* sum_ ) : root(root_), sum(sum_) {} 

task* execute() { 

if( root->node_count<1000 ) { 

*sum = SerialSumTree(root); 

} else { 

Value x, y; 

int count = 1; 

tbb::task_list list; 

if( root->left ) { 

++count; 

list.push_back( *new( allocate_child() ) SimpleSumTask(root->left,&x) ); 

} 

if( root->right ) { 

++count; 

list.push_back( *new( allocate_child() ) SimpleSumTask(root->right,&y) ); 

} 

// Argument to set_ref_count is one more than size of the list, 

// because spawn_and_wait_for_all expects an augmented ref_count. 

set_ref_count(count); 

spawn_and_wait_for_all(list); 

*sum = root->value; 

if( root->left ) *sum += x; 

if( root->right ) *sum += y; 

} 

return NULL; 

} 

}; 

Value SimpleParallelSumTree( TreeNode* root ) { 

Value sum; 

SimpleSumTask& a = *new(tbb::task::allocate_root()) SimpleSumTask(root,&sum);

tbb::task::spawn_root_and_wait(a); 

return sum; 

} 

 


OptimizedParallelSumTree.cpp

==============================================================================

Copyright 2005-2006 Intel Corporation. All Rights Reserved.

==============================================================================

#include "common.h" 

#include "tbb/task.h" 

class OptimizedSumTask: public tbb::task { 

Value* const sum; 

TreeNode* root; 

bool is_continuation; 

Value x, y; 

public: 

OptimizedSumTask( TreeNode* root_, Value* sum_ ) : root(root_), sum(sum_), is_continuation(false) {

} 

tbb::task* execute() { 

tbb::task* next = NULL; 

if( !is_continuation ) { 

if( root->node_count<1000 ) { 

*sum = SerialSumTree(root); 

} else { 

// Create tasks before spawning any of them. 

tbb::task* a = NULL; 

tbb::task* b = NULL; 

if( root->left ) 

a = new( allocate_child() ) OptimizedSumTask(root->left,&x); 

if( root->right ) 

b = new( allocate_child() ) OptimizedSumTask(root->right,&y); 

recycle_as_continuation(); 

is_continuation = true; 

set_ref_count( (a!=NULL)+(b!=NULL) ); 

if( a ) 

if( b ) spawn(*b); 

else 

a = b; 

next = a; 

} 

} else { *sum = root->value; 

if( root->left ) *sum += x; 

if( root->right ) *sum += y; 

} 

return next; 

} 

}; 

Value OptimizedParallelSumTree( TreeNode* root ) { 

Value sum; 

OptimizedSumTask& a = *new(tbb::task::allocate_root()) OptimizedSumTask(root,&sum);

tbb::task::spawn_root_and_wait(a); 

return sum; 

} 

 

The attached files below are needed for the complete program.

 

AdjuntoTamaño
Descargar main.cpp3.82 KB
Para obtener más información sobre las optimizaciones del compilador, consulte el aviso sobre la optimización.