Microsoft Parallel Extension to .Net Framework 3.5 is "a managed programming model for data parallelism, task parallelism, and coordination on parallel hardware unified by a common work scheduler" (MSDN). You can download the December 2007 CTP here. There seems to be a big drive at Microsoft towards parallel computing, also noted in this document, whitepaper from MS on "The Manycore Shift".
I've taken a look at some examples, and performed some rudimentary timing of parallel tasks versus the same tasks sequentially and included my test project in this article for download.
Downloads
Microsoft Parallel Extensions to .Net Framework 3.5, Dec 2007 CTP
My PFX sample/demo project
The Code
The new namespaces introduced in the extensions are:
- System.Linq
- Includes new ParallelEnumerable classes
- System.Linq.Parallel
- Base classes for Linq extensions
- System.Parallel
- System.Parallel.Tasks
- Task, TaskManager, TaskManagerPolicy
- Future factory, Future<> type safe Task
I've focused on the System.Parallel namespace in this article, as the Tasks and Linq namespaces are probably articles on their own.
Jumping straight in, let's look at two examples of for loops, the first implemented in the tried-and-trusted way, the second making using of the Parallel.For static method.
for(int i=0; i < 100; i++)
{
Console.WriteLine(i);
}
The code below looks similar, but notice the use of the static method, and the third parameter which accepts a delegate.
Parallel.For(0, 100, i =>
{
Console.WriteLine(i);
}
);
I've in-lined the code using a lambda expression, but it could just as easily been written as such:
Parallel.For(0, 100, delegate(int i)
{
Console.WriteLine(i);
}
);
To see just how much of a difference the Paraller.For and Parallel.ForEach would make to my code, I set up some simple (contrived) tests to measure. In the first test, I create and List<> (200,000 long) of List<int> (randomly between 50 and 100) long, with values ranging from 0 to 1000. I then coded 8 methods to test various permutations of adding the numbers, both sequentially and in parallel. In the example below, I've made the outer loop execute in parallel, while the inner loop adds up sequentially.
public long ParallelAdditionOuter()
{
long total = 0;
Parallel.For(
0, MaxListLength, i =>
{
int total1 = 0;
for (int j = 0; j < _list[i].Count; j++)
{
total1 += _list[i][j];
}
Interlocked.Add(ref total, total1);
}
);
return (total);
}
You'll notice that I made use of Interlocked.Add when adding the total of my inner list to the grand total - this provides a thread safe atomic operation rather than me writing a locking statement. This is essential, as adding to the variable "total" without locking it could cause unreliable results. I ran the tests in VS2008, and got the following results:
I found it very interesting that the sequential addition was faster than 4 of the 6 parallel methods I'd implemented. I think that its important to note that Parallel Extensions isn't the Silver Bullet (or Go-Faster solution) to poorly written apps and bad designs - clearly, thought needs to be put into what you're going to be doing.
As a second test, I extracted the quick sort example from the Parallel Extension sample code, and implemented a slight variation on their parallel sorting methods. There are now two parallel sorts, one doing the sorting in parallel from beginning to end, the other doing parallel until a "threshold" gets reached, and then switching to sequential. The rest of the implementation is in the sample project.
private void QuicksortSequential<T>(T[] arr, int left, int right) where T : IComparable<T>
{
if (right > left)
{
int pivot = Partition(arr, left, right);
QuicksortSequential(arr, left, pivot - 1);
QuicksortSequential(arr, pivot + 1, right);
}
}
private void QuicksortParallelOptimised<T>(T[] arr, int left, int right) where T : IComparable<T>
{
const int SEQUENTIAL_THRESHOLD = 2048;
if (right > left)
{
if (right - left < SEQUENTIAL_THRESHOLD)
{
QuicksortSequential(arr, left, right);
}
else
{
int pivot = Partition(arr, left, right);
Parallel.Do(
() => QuicksortParallelOptimised(arr, left, pivot - 1),
() => QuicksortParallelOptimised(arr, pivot + 1, right));
}
}
}
Once again, although I sort of expected it, the results showed that the sequential ran faster than one of the parallel implementations.
The third static method in the Parallel namespace is simply Parallel.Do (with many overloads). This is used to execute methods/code asynchronously. I found this useful for calling two methods, which would normally have run sequentially, but are total independent of each other.
Parallel.Do(
( ) =>
{
Thread.Sleep(5000);
Console.WriteLine("Number One is done.");
},
( ) =>
{
Thread.Sleep(6000);
Console.WriteLine("Number Two is done.");
}
);
Had these two sections run sequentially, execution time would have been a little over 11 seconds. This example returns immediately, and the final Console.WriteLine happens in a little over 6 seconds.
In my next article, I'll take a look at the Parallel.Tasks namespace and some examples of the usage.