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.

Case Study of a DRM Server

This article makes a case to build an industry-standard DRM Server as an open source project.


Goals and Non-Goals:

1. Why a DRM Server?

Digital market-place is inevitable. As the market-place mechanism for digital content establishes itself, the privacy and rights debates in the industry will have to eventually sort it out. It is highly likely that eventually, a level of DRM that is considered acceptable to both the content providers and the users will emerge.

Given that a DRM Server is an enabling piece of software for digital market-place, this is an attempt to study the building blocks for such a server.


2. Choice of DRM Standards to include in our case study:

The state of this technology is continually evolving and the industry is publishing standards at a rapid pace. There are standards from organizations like OMA that set standard for mobile DRM. The majority of the deployed DRM solutions and standards have come from a few leading industry players such as, Adobe, Microsoft and Apple.

A recent standard from Open Mobile Alliance or OMA provides some guidance on digital rights for streaming content to mobile platforms. This standard is known as the "Smartcard DRM profile".


3. Analysis to scope out the requirements:

Our initial focus is to analyze existing standards such as the Smartcard DRM profile as well to study the basic building blocks needed for our DRM server.

The early goals are to study and build prototypes for the various building blocks of a DRM server. The driving goal is to arrive at a set of high-level requirements that our DRM server will eventually satisfy.

High-Level Functional blocks of a DRM Server

In this section, we highlight the high level building blocks of a DRM Server.

1. Key Management Infrastructure

A DRM Server makes use of ciphers, which are algorithms that use cryptographic keys to scramble the content. These keys are required to descramble the content.

Since cryptographic keys play such an important role in a DRM Server application, key management is a central building block of a DRM Server. This system deals with the creation and management of cryptographic keys. The following figure outlines what could be a high-level overview of modules present in a key management System.



A brief explanation of each function is in order and is provided here,

1. Key storage or Key Vault

The main job of a key vault is to safely store and provide access to the keys used by the crypto. Engine. This is perhaps a vital piece of the DRM server design.

2. Key Manager

The key manager is an interface that manages the creation, deletion and updates of keys in the key vault. Naturally, it follows that when a key manager retires a key and activates a new key, the data has to be re-encrypted using the newly active primary key.

This is a very sensitive administrative function that must be performed by a cryptographic officer. It follows that the key manager has well-defined access control policies.

3. Crypto Engine

This is a critical piece of the DRM server, as it provides the basic crypto operations, including encryption, decryption, signing and verification. The crypto engine has access to the Key Vault. The providers and the key manager may have access to a crypto engine.

4. Key Manifest

This is a function that acts as the bridge between the keys stored in the key vault and their selection to encrypt the content. It deals with the key families and aliases. This function can also manage the key life cycle.

5. Provider

Provides a level of abstraction between the client and the crypto engine. It verifies a client request for encryption or decryption or other operation and selects the correct key aliases and any other additional parameters to satisfy the request. It passes the results back to the consumer.

6. Consumer

This is the contact point for an application that wishes to make use of the key management system. The consumer is aware of key families as well as receipts of encryption.

2. Key or License Distribution Protocols

When a user wants to use the content he or she purchased, a DRM Server must deliver licenses to the client system. These licenses contain the keys required to use the content on the client system. Key delivery protocols deal with the transfer of the purchase information and content licenses between a client and a DRM server.

The client and server may need to mutually authenticate each other and most of the standards leverage other industry standards to accomplish this function.

3. Content Management Server

If the KMS is part of our DRM Server, then the content management server needs to interact with the KMS to protect the content. The content is usually assigned a unique ID and this Identifier is tied to the Key set used to encrypt the content.

Using Google Analytics to Tune your Site.

A few weeks back, I signed up for google analytics. This is a tool that analyses the web traffic that passes through your website. We will call it GA in short form and hope no one objects. If you wish to make your website profitable, then you have a good reason to read on.

As a newbie to the tool, it took me an 8 minute video with some highlights to get interested in the tool. Then, this was followed up by a small copy procedure that connects my web site to GA, which then starts gathering the data and starts analyzing my website.

EARLY GOALS: When I started out, my goals were simple. Install the tool and wait for the tool to turn in something meaningful. Once, it reports something useful, will consider digging deeper into it.


INFORMATION STARTS TO FLOW:

1. Customer Base - The first Surpise: It took only a week for the tool to smash my view of the customer base for my website. The tool simply told me, I have visitors from 24 more countries than my imagination would allow.

2. Tuning your site's Content - Second Surprise: When you design a web application or a website's information architecture, the only way to know its effectiveness is to deploy and study it.

Now, GA has a report that shows a click picture overlayed on my site's pages. If my interpretation of this report is accurate, it starts to give some clues on the behaviours of the users around the content of your web site. You may be surprised to know some of the content that you thought were right on the money are the ones that are left untouched by the users.

As good as the software is, you cannot rule out bugs etc. or your own misinterpretation of the data presented. It is often a good idea to cross-verify the information with another source, before taking any decision on moving out some or most of the content.

3. Traffic Shaping: GA reported that my site had a suprisingly high number of direct visitors followed by search engine directed traffic. Now, I considered that a bonus.

Tools like GA get you to focus on your strategies, goals and to fine tune your web applications and content. If you can bear with the small learning curve, you can put it to good use.