A cautionary parallel tale: ordering isn’t simple

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!

2 thoughts on “A cautionary parallel tale: ordering isn’t simple”

  1. This is fascinating and will become increasingly relevant in computing. I don’t fully understand all this LINQ stuff quite yet (it is new!), but I will learn–and your post helps a bit.

Comments are closed.