Managed Parallel Computing with Parallel Extensions

Full Listing

In my last post I told you about how I like to do talks about my passion. One of the subject I,m interested in at the moment is managed parallel computing, especially with what is coming from Microsoft Research: Parallel Extensions.

Parallel Extension is a new framework that will help us build software that can harvest all the power of a multi-core system without all the complexity of managing thread ourselves. I’m also presenting a lot on this subject, so if you are a member of a local user group I will be pleased to get invited.

What exactly is parallel extension. Like it says, it’s an extension. Actually it’s a replacement of the System.Threading library that add a lot of new types to deal with parallelism. By now, you should be aware of the existence of the thread pool class in the framework. But building multi-threaded application with that requires you to handle all the threads you create yourself. Of course the thread pool will make it easy to create threads, but the first question you have to ask is: how many threads do I need? The answer depend on many things. First, what are you trying to do? Are you just trying to use your idle CPU to some background processing or are your trying to complete an intensive process as fast as possible? How many available core do you have? Is it the only application that need processor power at the moment? The beauty of the Parallel Extensions framework is that it turn those those questions to be almost obsolete.

The power of that framework lives in it task scheduler. Wait! We are talking about Task now! What about thread? Yes, Parallel Extensions adds another layer of abstraction to resolve the problem. Isn’t that always what we do. That Task layer is very convenient. Now we don’t have to bother anymore about thread we just have to break our process into tasks. To put it simply, a task should be the smallest unit of work that can run independent of others.

I know how must you like to see code so here is a little sample for you.

internal class Program
{
    private static void Main(string[] args)
    {
        Tree tree = Tree.Create();
        int sum = tree.Sum();
		Console.WriteLine("Sum is {0}", sum);
    }
}

This is the main code to calculate the sum of a binary tree. Of course we have to implement the Sum method.

    public int Sum()
    {
        int left = SumLeft();
        int right = SumRight();

        return Value + left + right;
    }

The Sum method call two internal function to do the job. It gets the sum of the left part and add it to the sum of the right part. In this sample, we have to wait for the whole calculation of the left part before starting to calculate the right one. This tree can be deep, so SumLeft may take time to process. On a single core system you will have to do it sequentially. But if you have a multi core system you can do at least to calculation at the same time. What if later you move your program to a 16 cores system. With thread you would have to know how may cores are available and then start creating just enough thread to do the processing. Too little, you will waste valuable CPU time, too many you will take too much memory because every managed thread takes 1 Meg of memory. Parallel Extension framework will automatically use all available cores to do the job without interfering with the rest of the system. By default two thread per core will be created with an average priority. Of course you have full control those over those defaults by creating your own TaskManagerPolicy, but we will see that in another post.

Take a look at how to parallelize this task.

public int ParallelSum1()
{
    int left = 0;
    int right = 0;

    Task[] tasks = new Task[]
    {
        Task.Create(x => left = Left.Sum()),
        Task.Create(x => right = Right.Sum())
    };

    Task.WaitAll(tasks);
    return Value + left + right;
}

This is how you could do it with a simple task structure, but this code smells. The problem is that left and right variables are define outside of the scope of the task structure. Let see how to do it better and why.

public int ParallelSum2()
{
    Future<int> futureLeft = Future<int>.Create(() => Left == null ? 0 : Left.Sum());
    Future<int> futureRight = Future<int>.Create(() => Right == null ? 0 : Right.Sum());
    return Value + futureLeft.Value + futureRight.Value;
}

In this snippet futureLeft and futureRight are tasks that will be potentially evaluated on another thread if there is some resource available. If not they will be executed on the current thread when we ask for their Value property. With this method we will use only two cores even though we may have more in the future. But if we try to replace Sum() by ParalaleSum2() on line 3 and 4, it will not work properly. We will end up creating way too many task and it will run slower that the sequential version. Here is a solution to get the scalability we need.

public int ParallelSum3()
{
    Future<int> futureLeft = Future<int>.Create(() => Left == null ? 0 : Left.ParallelSum3());
    int futureRight = Right == null ? 0 : Right.Sum();
    return Value + futureLeft.Value + futureRight;
}

This time we only compute one path of the tree in parallel the other one will be calculated sequentially.

In conclusion even if we have more tools to build our software to do work in parallel, it is not always easy to get it right.

Inspiration comes from Daniel Moth.
http://www.danielmoth.com/Blog/2008/12/introducing-new-task-type.html
http://channel9.msdn.com/pdc2008/TL26/