Introduction

Parallel computing draws a lot of attention these days because of the amazing pace in which multi-core computers has become widely available for industrial and personal use. Developing applications that can take advantage of this computational power requires revision of existing practices and design patterns, since those practices were born in the sequential world and do not solve similar issues.

We all know that writing parallel applications is a difficult and painful mission, not only because of the well-known issues such as deadlocks and race-conditions, but simply because human beings have been always struggling to think in a parallel way. That's why, existing well-designed patterns for parallel programming are so crucial.

As a C# developer, I've started looking for parallel programming resources by using .NET Framework 4, and found an excellent paper by Stephen Toub "Patterns of Parallel Programming". The paper contains an in-depth tour in .NET Framework 4 for parallel programming.

In this post I would like to show one of the examples from the above paper :"Parallel Loops".

Parallel Loops

As you can guess, parallel loops allow running independent actions in parallel. Loops are the most common control structures that enable an application to repeatedly execute some set of instructions. We can use such loops when statements within a loop body have few or no dependencies.

Creating a Manual Parallel For

Let's start with an example of performing a parallel "for" manually:

public static void MyParallelFor(int inclusiveLowerBound, int exclusiveUpperBound, Action body)
{
// Determine the number of iterations to be processed, the number of
// cores to use, and the approximate number of iterations to process
// in each thread.
int size = exclusiveUpperBound - inclusiveLowerBound;
int numProcs = Environment.ProcessorCount;
int range = size / numProcs;
// Use a thread for each partition. Create them all,
// start them all, wait on them all.
var threads = new List(numProcs);
for (int p = 0; p <>
{
int start = p * range + inclusiveLowerBound;
int end = (p == numProcs - 1) ?
exclusiveUpperBound : start + range;
threads.Add(new Thread(() =>
{
for (int i = start; i <>
 body(i);
}));
}
foreach (var thread in threads) thread.Start();
foreach (var thread in threads) thread.Join();
}

The main drawback of this solution is the relative high cost paid for creating and destroying each thread. We can improve it by utilizing a pool of threads:

public static void MyParallelFor(
int inclusiveLowerBound, int exclusiveUpperBound, Action body)
{
// Determine the number of iterations to be processed, the number of
// cores to use, and the approximate number of iterations to process in
// each thread.
int size = exclusiveUpperBound - inclusiveLowerBound;
int numProcs = Environment.ProcessorCount;
int range = size / numProcs;
// Keep track of the number of threads remaining to complete.
int remaining = numProcs;
using (ManualResetEvent mre = new ManualResetEvent(false))
{
// Create each of the threads.
for (int p = 0; p <>
{
int start = p * range + inclusiveLowerBound;
int end = (p == numProcs - 1) ?
exclusiveUpperBound : start + range;
ThreadPool.QueueUserWorkItem(delegate
{
 for (int i = start; i <>
  body(i);
 if (Interlocked.Decrement(ref remaining) == 0)
  mre.Set();
});
}
// Wait for all threads to complete.
mre.WaitOne();
}
}

PARALLEL.FOR

A new "Parallel" class has been added to the .NET Framework 4 library. The class provides methods for performing parallel loops and regions, one of them is "For". In his paper, Stephen gives a very good example of using Parallel.For in order to trace rays of light. The following code snippet demonstrates sequential and parallel variations of this problem:

void RenderSequential(Scene scene, Int32[] rgb)
{
Camera camera = scene.Camera;
for (int y = 0; y <>
{
int stride = y * screenWidth;
for (int x = 0; x <>
{
Color color = TraceRay(
new Ray(camera.Pos, GetPoint(x, y, camera)), scene, 0);
rgb[x + stride] = color.ToInt32();
}
}
}

void RenderParallel(Scene scene, Int32[] rgb)
{
Camera camera = scene.Camera;
Parallel.For(0, screenHeight, y =>
{
int stride = y * screenWidth;
for (int x = 0; x <>
{
Color color = TraceRay(
new Ray(camera.Pos, GetPoint(x, y, camera)), scene, 0);
rgb[x + stride] = color.ToInt32();
}
});
}

We can notice that the only difference between the implementations is replacing of regular for by Parallel.For.

That's it for now.

I'll continue extracting and adding such small articles to give "gustations" of the wonderful stuff from Stephen's book.