How to use TBB parallel_for

Well, now that we've installed and configured TBB libs on our (Linux) machine, we can start playing with various parallelism constructs provided by TBB and use them to gain meaningful efficiency in our day-to-day problem solving.
Why stress on "meaningful"? We'll talk about it later in this column.

Here's a working code with execution timing difference b/w a multiplication job using sequential for and a TBB parallel_for. I've put in comments to explain use of important statements in the code.

//These includes are the ones reqd to use TBB lib's parallel_for
#include "/tbb/tbb20_20070927oss_src/include/tbb/blocked_range.h"
#include "/tbb/tbb20_20070927oss_src/include/tbb/parallel_for.h"
#include "/tbb/tbb20_20070927oss_src/include/tbb/task_scheduler_init.h"

#include < iostream>
#include < stdlib>
#include < sys/time.h>

#define MULTIPLIER 3.1456

//Just something I found at koders for timing
#define TIMERSUB(a, b, result) \
do { \
(result)->tv_sec = (a)->tv_sec - (b)->tv_sec; \
(result)->tv_usec = (a)->tv_usec - (b)->tv_usec; \
if ((result)->tv_usec < 0) { \
--(result)->tv_sec; \
(result)->tv_usec += 1000000; \
} \
} while (0)

using namespace tbb;
using namespace std;

typedef long long mytime_t;

// This structure contains an important part needed to be defined
// for TBB's parallel_for. We need to have UDT's with overloaded
// operators wrapping up the serial functionality that we want
// to break into parallel execution. In this case, I use a struct
// (could have used a class too) that encapsulates an array of
// input and output float numbers and has operator() defined to
// perform a serial for operation on input.

struct myNumbers {
float* ptr_input;
float* ptr_output;

//Just a constructor with an initialization list for use in the parallel_for call
myNumbers(float* input, float* output):ptr_input(input),ptr_output(output){}

// This is the actual body that's called in parallel_for by the TBB runtime.
// This code comes as a struct/class definition as the compiler
// expands and inlines this code as part of the template process.
// The TBB runtime takes the range blocked_range and breaks
// up the for loop in parallel threads to fit the the no. of
// processors/cores. The no. of processors/cores and thus the no.
// of threads to break this operation into are calculated by the
// TBB runtime and thus the developer using the TBB library can
// just concentrate on the functionality w/o worrying about the
// parallelizing math involved.
void operator()(const blocked_range &range)const {
for (int i = range.begin(); i!= range.end(); i++)
ptr_output[i] = ptr_input[i] * MULTIPLIER;
}
};

int main(size_t argc, char* argv[]) {
// for timing execution
timeval t_start, t_end, t_result, tbb_start, tbb_end, tbb_result;
mytime_t singlethread_time, tbb_time;
int i = 0;
float* ptr_input;
float* ptr_outputSingle;
float* ptr_outputTBB;

// Initialize the TBB runtime...
task_scheduler_init init;
if( argc != 2 ) {
cout<<"Usage: "<<< " \n";
return 1;
}
int numElements = atoi(argv[1]);
if( numElements <= 1 ) {
cout<<"Array size "<<<" reqd an integer > 1\n";
return 1;
}
ptr_input = new float[numElements];
ptr_outputSingle = new float[numElements];
ptr_outputTBB = new float[numElements];

for(i = 0; i < numElements; i++) {
ptr_input[i] = i;
ptr_outputSingle[i] = 0;
ptr_outputTBB[i] = 0;
}
//Time the execution using plain sequential for
gettimeofday(&t_start,NULL);
for( i=0; i < numElements; i++ ) {
ptr_outputSingle[i] = ptr_input[i] * MULTIPLIER;
}
gettimeofday(&t_end,NULL);
TIMERSUB(&t_start,&t_end,&t_result);
singlethread_time = (mytime_t)(t_result.tv_sec + t_result.tv_usec);

//Time the execution using TBB parallel_for
gettimeofday(&tbb_start,NULL);
parallel_for(blocked_range(0,numElements),
myNumbers(ptr_input,ptr_outputTBB), auto_partitioner());
gettimeofday(&tbb_end,NULL);
TIMERSUB(&tbb_start,&tbb_end,&tbb_result);
tbb_time = (mytime_t)(tbb_result.tv_sec + tbb_result.tv_usec);

//Verify that the outputs match
for(i=0; i < numElements; i++) {
if( ptr_outputSingle[i] != ptr_outputTBB[i] ) {
cout << ptr_input[i] << " * " << MULTIPLIER <<" = " <<
ptr_outputSingle[i] << " AND " << ptr_outputTBB[i] << endl;
}
}

cout << "Sequential for execution time: " << singlethread_time << " units"<< endl;
cout << "TBB parallel_for execution time: " << tbb_time << " units" << endl;
return 0;
}

I used a Makefile for this, but we can also do it as (assuming the file as simple_for.cpp):
g++ -O2 -DNDEBUG -o ./simple_for simple_for.cpp -ltbb

Now, let's talk about "meaningful" efficiency gains:
I ran this code on my Linux machine with args (numElements) as: 10, 100, 1000 and found some performance improvement when using TBB parallel_for (assuming that execution timings are reported correctly). But when I ran this for numbers beyond 10000, I found that serial for does it in lesser time. No No No buddy.... don't even think about parallel_for having a constraint here in terms of breaking things up into smaller chunks of serial for(s). Intel (and others who support parallelism) specifically take into account Amdahl's Law and Gustafson's Law while proposing TBB to developers. So there's some level of optimization provided in TBB (based on practical load/figures and processor configuration that one's using). Like in this case I could overcome this limit of 10000 by providing a "grainsize" to the blocked_range() constructor as:
parallel_for(blocked_range(0,numElements,10),myNumbers(ptr_input,ptr_outputTBB));
Here, the 3rd arg to blocked_range() is grainsize and I saw more performance improvements for larger iterations if I keep reducing it (finally to 10) starting from an initial grainsize of 1000. Also observe that I've not used auto_partitioner arg in the call to parallel_for if I use grainsize in blocked_range constructor. Using a partitioner for deciding range of parallel chunks for your processing subsystem is one of the new features provided in TBB and with auto_partitioner the TBB runtime chooses a chunk size automatically optimized for parallelizing iterations on the underlying processing subsystem.

Refer TBB Getting Started Doc for more details on how to select the right grainsize for your iterations and for partitioner details.
In short: grainsize specifies the number of iterations for a “reasonable size”
chunk to feed the processor. If the iteration space has more than grainsize iterations, parallel_for splits it into separate subranges that are scheduled separately.

Yo! So we'd a gr8 start with TBB parallel_for demonstrating it's might in multicore/multi-processor environments. There's a lot more to parallel algos in TBB library. Not only that, there's a whole bunch of customized STL constructs that now work in tandem with multi-threaded code w/o the developer worrying about maintaining the threading infrastructure. Lemme explore some more of these features next week when I come back after the X-mas vacations. Till then, happy parallelizing!!!