BlackWaspTM

This web site uses cookies. By using the site you accept the cookie policy.This message is for compliance with the UK ICO law.

Parallel and Asynchronous
.NET 4.0+

Parallel For Loop

The second part of the Parallel Programming in .NET tutorial examines the parallel for loop. This allows the execution of a specific number of loop iterations in parallel, with data decomposition handled automatically by the Task Parallel Library.

Shared State

Parallel loops are ideal when the individual iterations are independent. When the iterations share mutable state, synchronisation is necessary to ensure that errors are not introduced by parallel processes using inconsistent values. This usually requires the introduction of locking mechanisms that slow the performance of the software or changes to algorithms to remove shared state.

The following parallel loop is simple but shows the problem of shared mutable state. Here we have a 'count' variable that we wish to increment one thousand times. With a sequential loop this would happen and the final count value would be 1,000. In the parallel version there is a small pause between the count variable being read and the updated version being stored back into the counter. This gives the opportunity for a parallel iteration to read the inconsistent counter and cause incorrect results.

int count = 0;

Parallel.For(0, 1000, i =>
{
    int temp = count;
    Thread.Sleep(1);
    count = temp + 1;
});

Console.WriteLine(count);   // not 1000

Dependent Iterations

With sequential loops you can assume that all earlier iterations will be completed before the current execution. With parallel loops, as seen in the first example, the order is usually changed. This means that you should not have code within a parallel loop that depends upon another iteration's result.

As an example, consider the following code. This attempts to generate a Fibonacci sequence where each value in the series is the sum of the previous two numbers. However, when the loop runs in parallel, the earlier results are not always available so the later values in the resultant array are incorrect.

int[] fibonnacci = new int[10];
fibonnacci[0] = 0;
fibonnacci[1] = 1;

Parallel.For(2, 10, i =>
{
    fibonnacci[i] = fibonnacci[i - 1] + fibonnacci[i - 2];
    Thread.Sleep(1);
});

for (int i = 0; i < 10; i++)
{
    Console.Write("{0} ", fibonnacci[i]);
}

// Outputs "0 1 1 2 3 5 0 0 0 0 "

Assumption of Parallelism

An uncommon problem, but nonetheless important, is the incorrect assumption that a loop will always execute in parallel. On single core processors parallel loops will generally execute sequentially. Even on multiprocessor systems it is possible for a loop to run in series. If your code requires that a later iteration completes before an earlier one can continue, the loop will be deadlocked.

Calls to Non-Thread-Safe methods

A common mistake in a parallel loop is to call methods that are not thread-safe. If you call your own methods from within a loop, ensure that they are thread-safe. When using standard calls from the .NET framework, you should check the MSDN documentation to ensure that called members are thread-safe. If you do not, it is possible that you will introduce synchronisation bugs.

Calls to Thread-Safe Methods

If the methods that you call from within a loop are thread-safe, you should not generate synchronisation problems through their use. However, if the methods use locking to achieve thread-safety, you may impair the performance of your software as multiple cores become blocked when your parallel loop executes.

NB: An example of a thread-safe method used in this article's examples is Console.WriteLine. This method should not generally be used form within a parallel loop but is useful when understanding the execution of such a loop.

Excessive Parallelism

In most cases parallelism increases the performance of your loops. However, it is possible to overuse parallelism. For example, consider the following code. Here the outer loop has one hundred iterations, as does the inner loop. As both have been constructed using Parallel.For, there is the opportunity for the combined loops to be decomposed into ten thousand individual operations.

int[,] grid = new int[100, 100];

Parallel.For(0, 100, i =>
{
    Parallel.For(0, 100 ,j =>
    {
        grid[i,j] = i+j;
    });
});

On current hardware it is unlikely that there will be enough processor cores to take advantage of this level of parallelism, especially for such a simple repeated operation. Instead, the additional decomposition overhead will lower the performance of the code. It is more appropriate in such cases to use one parallel loop and one sequential loop, as shown below:

int[,] grid = new int[100, 100];

Parallel.For(0, 100, i =>
{
    for (int j = 0; j < 100; j++)
    {
        grid[i, j] = i + j;
    }
});

In the above code only the outer loop is parallel. This results in less overhead than if the outer loop were sequential and the inner loop parallel. As a rule of thumb, when the potential to over-parallelise is present, you should break the task up into several larger tasks, rather than hundreds or thousands of smaller ones.

Thread Affinity

A final problem to consider is thread affinity. When developing software for Windows, some tasks must occur on a specific thread. For example, in Windows Forms and Windows Presentation Foundation (WPF) software, updates to user interface controls must occur on the thread that created the control. If you attempt to make the changes from another thread, exceptions are thrown.

To avoid problems of thread affinity, you should not use parallel loops in these situations. If you are programming a WPF application and wish to use a parallel loop, ensure that it executes on a thread other than the UI thread. The results of the operation can be synchronised later and applied to user interface controls using the UI thread.

15 August 2011