Saturday, December 4, 2010

Parallel Loops with .NET Framework 4

Introduction

Parallel computing draws a lot of attention at these days, because of amazing pace in which multi-core computers become widely available for industrial and personal use.
Developing applications that can take advantage of this computitional power, requires revision of the existing practices and design patterns, since those practices were born in the sequential world and do not solve similar
We all know that writting paraller applications is difficult and painful mission, not only because of 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 of well-designed patterns for parallel programming is so crucial.

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

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

Parallel Loops

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

Creating Manual Parallel For

Let's start with the example of performing 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 relative high cost paid for creating and destroying each thread.
We can improve it by utilizing pools 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

The 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. Following code snippets demonstrate the 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 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 a "gustations" of the wonderful stuff from Stephen's book.

Mark.

1 comment:

  1. how would one do the following using Parallel

    for (var index = lengthOfString - 1; index >= 0; index--){
    DoSomething();
    }

    ReplyDelete