Richard Cownie (tich@pobox.com) on 8/26/09 wrote:
---------------------------
>Well, I'm not really sure that the methodology of taking
>something that you've designed to be parallelized with
>shared memory, and then taking the same decomposition and
>measuring how that would work for a totally different
>scheme, really has the potential to tell you much. Most
>likely you'd partition it differently, and even at a higher
>level.

Actually, this test was meant to represent the highest possible level because I partitioned the data completely and equally with no sharing between processes.

I had 90 MB of input data and 90 MB of output data and four threads.

In one case I copied 90 MB into each array (to simulate the case where you don't know in advance which data needs to be copied) before processing and 22.5 MB back afterwards (i.e. we assume the output can be partitioned perfectly in advance with no sharing), for a total of 450 MB of copying to send the data back and forth.

In the other I copied 22.5 MB into each array (to simulate the case where you know in advance exactly which data needs to be copied, it just happens to be perfectly partitioned with no overlaps, and it just happens to divide equally between the number of processes) before processing and 22.5 MB back afterwards, for a total of 180 MB of copying to send the data back and forth.

I didn't really put them into separate processes, instead assuming that the multiprocessing overheads would be small compared to the cost of the physical memory copy. There was also no serialisation/deserialisation/pointer chasing/table lookup overhead, just a straight memcpy, to establish a lower bound to the overhead of not using shared memory for this operation.

I don't know how fast you can actually send data between processes on Linux vs memcpy or whether you can take advantage of Copy-On-Write to avoid copying large portions of data at all, but then again the thought that Linux could terminate my process due to memory overcommitments (possibly caused by COW) when I could have avoided those overcommitments in the first place scares the crap out of me.

>But having said that, I'm not quite sure what your "14%"
>overhead is referring to. Are you saying the runtime
>of this particular parallel algorithm gets 1.14x bigger
>with the copying added ?

Yes. The time it took that operation to complete was just over a second without the copying, and the copying added about 140 ms in the "minimal copying" case and about 360 ms in the "maximal copying" case.

This is one particular suboperation that I feel represents the best-case scenario for the parallel suboperations in general, of which there will be many (i.e. for each suboperation the data will need to be copied into each process, crunched for anywhere from a few ms to a few seconds, then copied back for the next serial portion).

For some of the other operations that I didn't test the overhead could well be lower because they do more processing per byte (and therefore there may be up to ten seconds, say, of processing to do on that 90 MB of data); however, for some of the other operations that I didn't test the overhead would be much higher because they last a very short period of time, touching only a small part of the input, and it is difficult to partition the input data between them beforehand.

In some cases some of the copying could be eliminated because the output from one parallel step is the input to the next, but in general the serial portion is actually doing something to the output that means fresh copying of new input data out to the worker processes would be required, and if we could predict what that new input data was going to be we wouldn't need the serial step!

So, as I explained, this isn't a very accurate test, but I found it useful as an indicator.

>But then that 1.14x doesn't bear
>any relationship to the 20-hour runtime of my *serial*
>algorithm: it might perhaps, correspond to a 1.14x
>increase in the shorter runtime of a *parallel* algorithm.
>Suppose we get a 5x speedup on 8 threads, so the 20hours
>would shrink to 4 hours, and then go up again to 1.14 x 4
>= 4.56 hours. I'd be pretty happy with that ... But the
>way you're doing it might be multiplying an orange by
>a banana divided by an eggplant, and using the result to
>predict the US deficit in 2029, or something.

That's not the point. We have projects that take more than 24 hours to process in the parallel case, so a 14% increase in runtime caused by changing the parallel algorithm from multithreading to multiprocessing does equate to a meaningful amount of time to the end user if you considered that same amount of time meaningful when it comes to your sort routine.

Of course the overhead will be slightly lower for the operation as a whole because I only measured the overhead for a single parallel operation and ignored the serial sections; however the variation between parallel operations is great enough that I don't think it's meaningful to talk about how much lower the total overhead would be when the serial portions are included -- it's just meant to illustrate that even using the simplest test I could find I was able to show that the overheads had a real impact. If I actually went through and implemented the whole thing with multiprocessing the impact could be anything from a few percent to 50% and I wouldn't be surprised. It would be surprised if it was negligible, and I would be absolutely astonished if it was actually faster and after all my effort I had a less buggy product, given the large amount of rewriting required.

>Bottom line: my approach is quite radically *different*.
>It's aiming at getting a modest parallel speedup with
>some medium-grain parallelism which can be applied with
>some redesign of data structures and serial algorithms,
>but without having to grapple with synchronization/
>locking/repeatability issues. It's a different set of
>tradeoffs, which will involve a different set of decisions.
>And it might well turn out to be crazy, but it doesn't
>seem to be *obviously* crazy.

I'm not saying it's crazy. That might be the best you can do in your case. What I'm saying is that I think your earlier comments on multithreading were overstated and no amount of "YMMV" at the end of the post changes that.

In our case we have two levels of parallelism that make sense -- fine-grained, where we may have many different parallel suboperations interspersed with serial portions, and very course-grained, in the case of our batch processor that treats every single project as a serial operation. The latter approach is useless for speeding up the interactive software, and the former is so fine-grained that the copying overheads alone would be a significant performance penalty, even ignoring the programming effort required to pull out the right bit of the data structures and transfer them to the other processes. We have found that using a few critical sections and the odd event and verifying the code's correctness has proven to be a relatively simple operation in almost all cases, and part of that is because multithreading allows such fine-grained parallelisation that we don't have reams and reams of nested function calls with pointers to pointers to pointers to worry about.

If the overhead was high enough that we had to take a medium-grained approach, then I'm sure multithreading would suddenly look a lot harder to me as well, simply because the higher up you go the more code you have to inspect and the more you have to worry about interactions -- until you get to the point that you're high enough you're naturally working with independent chunks of data again (e.g. separate projects in our batch processor, in our case).

In our case it just happens that our operations have tended to fall into the two extremes naturally regardless of the overheads; some can be partitioned at a very high level, others have to be partitioned at a very low level because of all the serial portions, and very few (I can't actually think of any) can be partitioned at a middle level. So it's lucky for us that multithreading is possible at all, because if it wasn't it would rule out all those operations can can't be partitioned at the highest level due to the overheads of trying to do multiprocessing at very low levels.