I was working on finishing a Parallel systems assignment in which we had to implement a prefix framework. The nice thing about the framework is that if you have N threads (or processes) working on a problem in parallel, then a sequential approach would require N stages to combine the result. But using the prefix framework, we can pair up the results and combine the result in logN stages.
I had worked in Java Threads, and found them quite interesting particularly because you just needed a minimal knowledge of threads to start working with them. pthreads, however, were slightly …un-object like, hence it made a bit of a mess to get an object oriented behaviour from them.
The core of the tree combination is the combineTree function, which is a function of the thread instance (i made up classes to represent different aspects of the problem). The function is as follows;
void LocalThreadContext::combineTree()
{
int * rs;
for(int stride=1;stride<(NUM_THREADS-sequenceID);stride*=2)
{
if((sequenceID%(2*stride))==0)
{
g->combineFunction(&lRes,g->children[sequenceID+stride].getLocalResult());
///Display logic..... just something to make it look like a tree.
#if DEBUG_CONSOLE
pthread_mutex_lock(&consoleMutex );
printf("\n");
for(int j=1;j<=stride;j*=2)
printf("\t");
printf("Combining %d with %d",sequenceID, sequenceID+stride);
pthread_mutex_unlock(&consoleMutex );
#endif
/////End of display logic!
}
}
}
The DEBUG_CONSOLE is something you might use if you are debugging and would like a nice tree-like representation of the combining-logic.
It was fun, but the problem of expressing arbitrary problems in such a framework remains something i would need to work on (if i get some time, which i won’t!).
The threads start off by locking on the result variable, so that no thread attempts to combine its result before the result has been computed. The thread would be given a global thread context, which would define how the thread is to use the data provided to it (int array or double array etc) and how to combine its result with the result of another thread (sum problem has different behavior compared to two_max problem). The thread would perform the function on each of the data elements it is provided and then combine the result using the function provided. The complete code is available here
