Category Archives: Parallelization

C#, LINQ, Parallelization, Wacky Ideas

Visualising the Mandelbrot set with LINQ – yet again

2 Comments

I’ve been thinking about ranges again, particularly after catching a book error just in time, and looking at Marc’s generic complex type. It struck me that my previous attempts were all very well, and demonstrated parallelisation quite neatly, but weren’t very LINQy. In particular, they certainly didn’t use LINQ for the tricky part in the same way that Luke Hoban’s ray tracer does.

The thing is, working out the “value” of a particular point in the Mandelbrot set visualisation is actually quite well suited to LINQ:

  1. Start with a complex value
  2. Apply a transformation to it (square the current value, add the original value from step 1).
  3. Does the result have a modulus > 2? If so, stop.
  4. Have we performed as many iterations as we’re willing to? If so, stop.
  5. Take our new value, and go back to 2.

We only need two “extra” bits of code to implement this: a Complex type, and a way of applying the same transformation repeatedly.

Well, here’s the Complex type – it contains nothing beyond what we need for this demo, but it’ll do. Obviously Marc’s generic implementation is rather more complete.

public struct Complex
{
    readonly double real;
    readonly double imaginary;

    public Complex(double real, double imaginary)
    {
        this.real = real;
        this.imaginary = imaginary;
    }

    public static Complex operator +(Complex c1, Complex c2)
    {
        return new Complex(c1.real + c2.real, c1.imaginary + c2.imaginary);
    }

    public static Complex operator *(Complex c1, Complex c2)
    {
        return new Complex(c1.real*c2.real – c1.imaginary*c2.imaginary,
                           c1.real*c2.imaginary + c2.real*c1.imaginary);
    }

    public double SquareLength
    {
        get { return real * real + imaginary * imaginary; }
    }
}

Simple stuff, assuming you know anything about complex numbers.

The other new piece of code is even simpler. It’s just a generator. It’s a static method which takes an initial value, and a delegate to apply to one value to get the next. It then lazily returns the generated sequece – forever.

public static IEnumerable<T> Generate<T>(T start, Func<T, T> step)
{
    T value = start;
    while (true)
    {
        yield return value;
        value = step(value);
    }
}

Just as an example of use, remember Enumerable.Range which starts at a particular integer, then adds one repeatedly until it’s yielded as many results as you’ve asked for? Well, here’s a possible implementation, given the Generate method:

public static IEnumerable<int> Range(int start, int count)
{
    return Generate(start, x => x + 1).Take(count);
}

These are all the building blocks we require to build our Mandelbrot visualisation. We want a query which will return a sequence of bytes, one per pixel, where each byte represents the colour to use. Anything which goes beyond our maximum number of iterations ends up black (colour 0) and other values will cycle round the colours. I won’t show the drawing code, but the query is now more self-contained:

var query = from row in Enumerable.Range(0, ImageHeight)
            from col in Enumerable.Range(0, ImageWidth)
            // Work out the initial complex value from the row and column
            let c = new Complex((col * SampleWidth) / ImageWidth + OffsetX,
                                (row * SampleHeight) / ImageHeight + OffsetY)
            // Work out the number of iterations
            select Generate(c, x => x * x + c).TakeWhile(x => x.SquareLength < 4)
                                              .Take(MaxIterations)
                                              .Count() into count
            // Map that to an appropriate byte value
            select (byte)(count == MaxIterations ? 0 : (count % 255) + 1);

(The various constants used in the expression are defined elsewhere.) This works, and puts the Mandelbrot logic directly into the query. However, I have to admit that it’s much slower than my earlier versions. Heck, I’m still proud of it though.

As ever, full source code is available for download, should you so wish.

C#, LINQ, Parallelization

A cautionary parallel tale: ordering isn’t simple

2 Comments

A little while ago, I wrote about my silly project to test Parallel LINQ – a Mandelbrot generator. In the last week, two things have happened to make this more of a reality. Firstly, the December CTP of Parallel FX has been released. Secondly, my old laptop died, “forcing” me to get a new laptop, which just happens to have a dual core processor.

So, it should just be a case of running it, right? Well, not quite. First let’s have a look at the query expression again, in its serial form:

 

var query = from row in Enumerable.Range(0, ImageHeight)
            from col in Enumerable.Range(0, ImageWidth)                                             
            select ComputeMandelbrotIndex(row, col);

 

And here’s what should be generated.

That’s the result of running without any parallelism, in other words. Now, I realised from the start that we would need ordering, but my first experiment was just to call AsParallel() to see what would happen:

 

var query = from row in Enumerable.Range(0, ImageHeight).AsParallel()
            from col in Enumerable.Range(0, ImageWidth)                                             
            select ComputeMandelbrotIndex(row, col);

 

As expected, that didn’t produce quite the result we wanted:

Well, that’s okay. I wanted to prove that ordering was necessary, and indeed that’s fairly obvious from the result. There are horizontal blocks, returned out of order. Easily fixable, right? After all, I posted what I thought would be the solution with the original post. We just need to give the appropriate option as a method parameter:

 

var query = from row in Enumerable.Range(0, ImageHeight).AsParallel(ParallelQueryOptions.PreserveOrdering)
            from col in Enumerable.Range(0, ImageWidth)                                             
            select ComputeMandelbrotIndex(row, col);

 

Not so fast. It certainly changed things, but not quite as hoped:

I haven’t yet analysed quite why we now have the rows in order but the columns out of order. However, I haven’t quite managed to fix it with the code in its original form. I have managed to fix it by reducing it from two (implicit) loops to one:

 

var query = from row in Enumerable.Range(0, ImageHeight).AsParallel(ParallelQueryOptions.PreserveOrdering)                                             
            select ComputeMandelbrotRow(row);

byte[] data = new byte[ImageHeight * ImageWidth];

int rowStart = 0;
foreach (byte[] row in query)
{
    Array.Copy(row, 0, data, rowStart, ImageWidth);
    rowStart += ImageWidth;
}

 

Instead of getting all the results in one go (with a call to ToArray()) we now have to reassemble all the data into a block. Still, it achieves the desired result. I should point out that PFX has better ways of doing this, Parallel.For being an obvious starting point from the little I know of it. At some point I’ll get round to reading about them, but at the moment life’s too short. I should also say that I don’t expect that any of the pictures indicate a bug in Parallel LINQ, merely my understanding of it.

Update: Explanation and a workaround

Having asked about this on the Connect forum for PFX, Igor Ostrovsky has explained that this is by design – currently only outer ordering is preserved when requested. The issue is still open, however – it’s possible that it will change before release.

In the meantime, Nicholas Palladinos has come up with an alternative solution which I rather like. I’ve refactored it a bit, but the basic idea is to turn the two sequences into one before parallelisation:

 

var points = from row in Enumerable.Range(0, ImageHeight)
             from col in Enumerable.Range(0, ImageWidth)
             select new { row, col };

var query = from point in points.AsParallel(ParallelQueryOptions.PreserveOrdering)                                              
            select ComputeMandelbrotIndex(point.row, point.col);

 

That works really well – in fact, more than twice as fast as the serial version, on my 2-core box!

Books, C#, General, LINQ, Parallelization

LINQ to Silliness: Generating a Mandelbrot with parallel potential

Leave a comment

I’ve been writing about LINQ recently, and in particular I’ve written a small amount about Parallel LINQ. (Don’t get excited – it’s only about a page, just to mention it as a sort of “meta-provider” for LINQ.) I was wondering what to use to demonstrate it – what general task can we perform which could take a lot of CPU?

Well, I used to be quite into fractals, and I’ve written Mandelbrot set generators in various languages. I hadn’t done it in C# before now, however. Calculating the colour of each pixel is completely independent of all the other pixels – it’s an “embarrassingly parallelizable” task. So, a great task for PLINQ. Here’s the “normal LINQ” code:

 

var query = from row in Enumerable.Range(0, ImageHeight)
            from col in Enumerable.Range(0, ImageWidth)
            select ComputeMandelbrotIndex(row, col);

byte[] data = query.ToArray();

Changing this into a parallel query is really simple – although we do need to preserve the ordering of the results: 

var query = from row in Enumerable.Range(0, ImageHeight).AsParallel(QueryOptions.PreserveOrdering)
            from col in Enumerable.Range(0, ImageWidth)
            select ComputeMandelbrotIndex(row, col);

byte[] data = query.ToArray();

Without being able to actually use PLINQ yet, I can’t tell how awful the order preservation is – Joe warns that it’s costly, but we’ll see. This is on a pretty giant sequence of data, of course… An alternative would be to parallelize a row at a time, but that loses some of the purity of the solution. This is a very, very silly way of parallelizing the task, but it’s got a certain quirky appeal.

Of course, there’s then the code for ComputeMandelBrotIndex and displaying a bitmap from it – the full code is available for download (it’s a single C# file – just compile and run). Enjoy.

Update!

This blog post has been picked up by Nick Palladinos, who has written his own Parallel LINQ provider (much kudos for that – unfortunately for me the blog is in Greek, which I don’t understand). Apparently on a dual core processor the parallelised version of the Mandelbrot generator is indeed about twice as fast – it works! Unfortunately I can’t tell as my laptop only has a single core… it’s very exciting though :)