Parallel Programming Frameworks: What are the building blocks?

Building Blocks of a parallel application Framework

Keywords: functors, work, task, application framework, types, Task Queue

Problem Statement:

1. Lightweight: Shall provide a lightweight application scheduler that can be programmed to explicitly control cpu-core assignment to a specific task, if so desired.

2. Object-Oriented: Shall allow user defined types and classes that can be added as tasks or jobs for parallel execution into the framework.

3. Flexible: Shall provide well known scheduling policies that handle the creation and synchronization of threads in an explicit way.

4. Simple Tasks: Shall allow the definition and execution of very simple application tasks that make up a larger problem.

Concepts useful to our Framework

The following is a brief discussion of a few concepts that can be used as the building blocks to a parallel framework.

Using Functors to define a Task

Functors are fist class types similar to a class and can be used to define a specific task such as findMinimum in an array. These objects can be passed into a Work or a Task object, redefining their behaviour. These offer the simplicity of a function as well as hold state information. We can find some way to employ this versatile concept in our framework.


typedef struct _findMinimum {

_findMinimum (IData* idata) : _dataInterface(idata){
_dataSetRef = (int*) _dataInterface->getData();
};
~_findMinimum (){};


int operator()(int start, int end)
{
int min = getMinimum ();

if (min == -1){
return min;
}

// declares an iterator
int It = min + 1;

for (; It <= end; It++){ if (_dataSetRef[It] < _dataSetRef[min]){ min = It; } } setMinimum (min); return min; } IData *_dataInterface; IDataOut* _dataOutInterface; int* _dataSetRef; } findMinimum;


Holding Tasks in a Basket - the Task Queue

A task queue becomes a central concept used as a holding basket for the application tasks that are executing in parallel. Tasks can exist in various states in the queue, ready to execute or completed.

A queue provides the ability to drop in the work object created and schedule it for execution by a particular type of thread. The assignment of the number of Worker threads and their type to do certain types of jobs is done by the scheduler that manages the Team of Threads. A queue plays a central role in this.

The queue is accessed initially by the main thread that creates the tasks and later by the worker and monitor threads. This calls for synchronizing access to the queue using a semaphore or a mutex object.

Team of Threads

A Team is a lightweight scheduler that needs to be discussed in some detail. A team of threads are created by our lightweight scheduler on behalf of the application.

The concept here is to allow the application to focus on specifying the task to execute. The Team of threads chose the task to execute from the queue depending on their workType. There are threads that are hard threads bound to CPU-cores and others that are soft threads and all of them execute the tasks in parallel.

The Team object gives us the ability to control the Thread affinity that we discussed earlier.

Notice the concept of using worker threads with different affinity and to do specific type of tasks. For example, I can chose to designate or give different responsibility to some threads such as monitoring or supervisory role. Some other threads purely go from round to round executing a functor.

Here is Part I of the series of articles on Hands-on Programming for Parallelism using Multi-Cores

Here is Part II of the series of articles on How to assign a cpu core to a Thread?

Here is Part III of the series of articles on These Thread Libraries offer Help

Here is Part IV of the series of articles on Building Blocks of a Parallel Framwork

Here is Part V of the series of articles on Rampaging Threads - Erecting an Effective Barrier

Parallel Programming: These Thread Libraries offer Help

Here is Part I of the series of articles on Hands-on Programming for Parallelism using Multi-Cores

Here is Part II of the series of articles on How to assign a cpu core to a Thread?

Two important libraries that attempt to provide a generic programming framework supporting parallel execution of application level tasks are openMp and Intel's Thread building blocks. Both of these libraries have one thing in common. They are capable of creating a team of threads implicitly and assign iterations or tasks to execute in parallel using those threads.

openMP

This is the result of an industry effort to create a portable and unified standard of shared-memory parallelism. Support for openMP is widely present in compilers and the two most popular ones GCC and Microsoft's VS supports this.

The advantage are, these compiler directives for parallel programming are widely available and are easier to use and specify in a program. As an example,



int min = 0;
#pragma omp parallel sections shared(min)
{
#pragma omp section
{
for (It = 0; It < NItems; It++){ // process an iteration } } }

The above code inserts a compiler directive "omp parallel sections" that tells the compiler that a series of parallel code blocks start here.

It is the second directive "omp section" that specifies one such code block. The compiler can then implicitly create a team of threads. Each thread can then be assigned to process a range of the iterations. Notice the specification of a shared variable min. This is a variable the team of threads will share.

Some of the disadvantages with omp are,

1. You are dependent on implicit code generated by the compiler behind your back. This adds a specific risk to your application as it would depending on a third-party tool that inserts code in a dynamic fashion. Is there a guarantee that this will work seemlessly across all of your platforms and scale well, when the number of cores decreases or increases? If you are a technical lead or manager for a product, you must be comfortable with the risk.

2. There is nothing in the OMP directives to suggest object oriented development for parallel computing. While it may not preclude that, the idea of compiler directives strewn across your code makes readability a question.

Intel Thread Building Blocks

Intel TBB is a C++ template based library for loop-level parallelism that works on the idea of tasks and seem to offer promise. I must admit, I am yet to familiarize myself with this library. When I do, I would love to post an article here as part of this series.

Making a case for a more explicit Approach

A parallel framework that offers the advantages of a solid set of generic algorithms and containers as well as allow explicit programmer control over the parallel scheduling is more desirable as an opinion.

In the next article here, a few concepts based on an attempt to create such a framework is discussed.

Here is Part I of the series of articles on Hands-on Programming for Parallelism using Multi-Cores

Here is Part II of the series of articles on How to assign a cpu core to a Thread?

Here is Part III of the series of articles on These Thread Libraries offer Help

Here is Part IV of the series of articles on Building Blocks of a Parallel Framwork

Here is Part V of the series of articles on Rampaging Threads - Erecting an Effective Barrier

Parallel Programming Frameworks - How to assign a CPU core to a Thread?

Here is Part I of the series of articles on Hands-on Programming for Parallelism using Multi-Cores.

Explicitly Programming Threads

Threads can be explicitly created in programs either using Posix standard Thread library APIs available on Linux platforms and the Windows threads based on Win32 APIs. Application programs typically defer the assignment of these threads to a specific processor core to the Operating System scheduler.

Overriding the Scheduler to assign a CPU cores to a Thread - Is this possible?

If the CPU has four or eight cores, an application can now assign a specific core to a thread. Sometimes this is referred to as hardware thread. There is typically an assignment of the CPU core to the process or more explicitly to a thread. This is typically accomplished by programming a bit mask known as a thread affinity mask. For example on a windows platform, using the following API, an application can override the scheduler to assign a specific core to a thread,



#include
#include

// Set OpenMP thread affinity
void set_thread_affinity () {

#pragma omp parallel default(shared)
{
DWORD_PTR mask = (1 << omp_get_thread_num()); SetThreadAffinityMask( GetCurrentThread(), mask ); } }

The SetThreadAffinityMask function is the function that assigns a cpu core to a thread. This API can assign upto 64 processors and more can be assigned by specifying a thread's current processor group.

omp.h header needs some explanation. This is strictly not required. OMP stands for openMP which is a standard for parallel programming implemented by most compiler vendors including GCC and Visual Studio and provides for APIs and compiler directives to create compiler supported implicit parallelism. As an example, the compiler can insert code to create a team of threads to process a for loop that can be parallelized based on directives in the program.

On Linux platforms the following APIs offer a similar facility. The pthread_setaffinity_np API is available to you when using Posix APIs to create threads.


int sched_setaffinity(pid_t pid,size_t cpusetsize,cpu_set_t *mask);
pthread_setaffinity_np();


Here is Part I of the series of articles on Hands-on Programming for Parallelism using Multi-Cores

Here is Part II of the series of articles on How to assign a cpu core to a Thread?

Here is Part III of the series of articles on These Thread Libraries offer Help

Here is Part IV of the series of articles on Building Blocks of a Parallel Framwork

Here is Part V of the series of articles on Rampaging Threads - Erecting an Effective Barrier

Parallel Frameworks: Rampaging threads - Erecting an effective barrier

Rampaging threads - Erecting an effective barrier

Keywords: threads, semaphores, mutex, barrier, framework, Task Queue

Threads are independent units of execution. Notice that you can assign hard threads to work on hard problems and soft threads to other issues. Not all tasks are the same in terms of their hunger for CPU!

There is an occasional need to coordinate the entry of a team of threads into the next round of execution. Assuming each thread when let loose picks up the type of job that is designated for self or already has a job assigned to it that requires more than one round of execution.

The problem is to wait for all threads (a type of threads) to reach a designated barrier for the round and then let them loose to the next round! This may be required to setup or adjust the state prior to the next round of execution! For e.g., it may be the updated of a shared state variable or one that is referenced by all threads going into the next round!

An example is selection sort that requires the minimum for the next round to be adjusted prior to searching for a new minimum!

The Barrier object

My idea of a barrier is one where our thread that holds a reference to a ThreadObject finds a reference to a barrier object and calls either the synchronize() or barrierWait() function.

These two functions have a slightly different purpose, former is called by a worker thread and the later by a monitor thread. These function(s) do a few things!

a. Allow a thread to test a condition expression after holding a mutex!
b. Each thread that enters this testing condition manages to increment the thread count
at the barrier. When the last of the expected number of worker threads arrives at the barrier, this is signalled as an event. The barrier object is setup to expect nTeamThreads.
c. There is a monitor thread that waits on the last thread event! It sets up the state required to proceed to the next round. It flags all the worker threads to go ahead to the next round!

Notice the use of two events. One that effectively stops the rampaging threads from going any further until flagged by the monitor!

Monitor simply waits for the arrival of last thread at the barrier before setting up the state for the next round!

There is more code to be placed here.


class ThreadBarrier
{
public:
ThreadBarrier(int nSyncThreads) : _nSynchronizedThreads(nSyncThreads)
{
startupState();
};

virtual ~ThreadBarrier(void){
shutdownState();
};

bool synchronize(void){

bool syncComplete = false;
lock();

// condition expression test

unlock();

return syncComplete;
}

void reset_Barrier(void){
lock();

_nthreads_atBarrier = 0;

unlock();
}

void barrierWait(void){
WaitForSingleObject(_BarrierWaitEvent, INFINITE);
}
}



Here is Part I of the series of articles on Hands-on Programming for Parallelism using Multi-Cores

Here is Part II of the series of articles on How to assign a cpu core to a Thread?

Here is Part III of the series of articles on These Thread Libraries offer Help

Here is Part IV of the series of articles on Building Blocks of a Parallel Framwork

Hands-on Programming for Parallelism using Multi-Cores

Here is Part I of the series of articles on Hands-on Programming for Parallelism using Multi-Cores

Here is Part II of the series of articles on How to assign a cpu core to a Thread?

Here is Part III of the series of articles on These Thread Libraries offer Help

Here is Part IV of the series of articles on Building Blocks of a Parallel Framwork

Here is Part V of the series of articles on Rampaging Threads - Erecting an Effective Barrier

Multi-Cores - Why this needs your attention?

Multi core CPUs are everywhere. Chances are good that the desktop machine you are reading this on, is running a multi-core CPU. They have even found their way into large server farms run by Google.

As processor speeds increase, the increasing power consumption can eventually catch up with that of a rocket exhaust.

Miniaturizing the cpu cores and putting multiple units of execution on the same CPU die alleviates the enormous power consumption problem that Intel and others face.

This is precisely why I think multi-cores are here to stay and programming multi-cores deserves some consideration of your time.

Multi-Cores - Is this new technology?

superscalar CPUs implement a form of parallelism called instruction level parallelism. The CPU executes more than one instruction per clock cycle. Savvy compiler programmers can put more than one parallel execution unit to work within a single processor.

Programming a superscalar CPU requires knowledge of its assembly language and the CPU architecture. Any library code written is most likely non-portable to other platforms.

Today's CPU evolution to multi-cores makes parallel programming possible at the application level. There are a few emerging techniques and tools that show promise. However, this is still an art and hence the plan here to examine the concepts in a series of handson articles.