Richard Cownie (tich@pobox.com) on 8/25/09 wrote:
---------------------------
>JasonB (no@spam.com) on 8/25/09 wrote:
>---------------------------
>
>>As I've said before:
>>
>>1. That cost will be present in the parallel processing case as well,
>
>Sure. But you're talking about the difference between
>the two cases being 1000x. And I'm saying it's probably
>more like 10x or 20x. Because the data has to move around
>in both cases. It probably has to move several extra
>times in my approach. And if the difference turns out to
>be 50x, then I'll need 500uS granules instead of your 10uS
>granules. And that would be just fine for what I'm
>doing (though smaller/quicker is better, obviously).

To clarify the point I'm making, and give some hard numbers, I added in some fake copying before and after a particular routine to simulate transferring data back and forth to different processes.

I chose the routine in question because it was easiest to test with. The output is clearly partitioned -- the multithreaded routine simply allocates a range in the output array to each thread and they can safely dump values into their range without having to worry about interfering with the other threads. The input is less clearly partitioned -- it, too, consists of an array, each element of which (apart from some boundary cases) will only ever be read by a single thread, however some work would be required up-front to work out where those boundaries actually lie.

I didn't do that. I didn't even bother physically sending the data into a different process's memory space or anything like that -- I just allocated memory for each thread, copied the input data into the array with a straight memcpy(), and copied the output data back out of each array afterwards the same way. (No attempt at serialisation or anything like that, just memcpy().)

I tested it with copying all data into each input array beforehand (to simulate the case where you don't know in advance what data is required) as well as a fraction of the data into each input array beforehand (to simulate the case where you know exactly in advance what data is required, and there is no overlap between processes in terms of required data). I ignored other (much smaller) data that is also required by each thread in order to do the computation.

The result was a 14% overhead in the case where 1/4 of the input data was copied for each of the four threads, to 35% overhead in the case where all of the input data was copied into each thread. (So, in terms of space, twice as much physical memory required for the best case and four times as much for the worst case.)

That equates to nearly 3.5 hours in your 24 hour runtime in the perfect case, and nearly 8.4 hours in your 24 hour runtime in the "worst" case. (Not really worse because in reality I was still just copying data around in the same process's memory space, with no communication or synchronisation overheads.)

Of course other operations will have different percentage overheads, but I'm not going to do the work necessary to actually sort it out for a test for exactly the same reason why I'm not going to do the work necessary to use multiprocessing rather than multithreading. This particular case is also unfair both ways -- firstly, it is unfair to your argument because it just happens to have a relatively high rate of data consumption, meaning the processing time per byte copied is lower than average and makes the intial and final copy seem like a bigger deal. But it is also unfair to my argument as well, in that not only did I ignore all overheads other than the actual copy itself, I also chose an operation that just happens to consume all of the input data. There are plenty of other operations that do more work per byte, but most of them don't read all of the input data nor allow you to predict which subset of the input data needs to be copied, so their "work per copied byte" could be either higher or lower.

So ignoring the unfairness of this particular case and all the real-life overheads that are being ignored, does it need to be 1000X faster (i.e. about 20 seconds in a 24 hour runtime)? Perhaps not; but 10X-20X faster would still put it in the ballpark of the Quicksort implementation that you saw fit to replace, and I have no idea how you are going to be able to make a proper serialisation routine 10X-20X faster than a straight memcpy().

>>2. It can be a free lunch if there is enough computation between accesses
>>and the predictors work well enough that the latency is completely hidden.
>
>My view of performance is that programs move data around,
>and that's what costs the time. ALU operations these days
>are mostly free. I'm pretty sure that's the right way
>to analyze the app I work on.

That may be the case for you, but our code is very computationally intensive. Our most bandwidth-intensive operation still scales by a factor of 3.6 on a 3.5 GHz QX9650, and that has the old FSB.

>For some well-tuned
>compute-intensive kernels you can get a working set in
>registers and/or L1 cache and run for a while in compute-
>bound rather than memory-bound mode. But that's not
>the normal case.

In our case the issue is the processing:byte ratio. The data sets are far too large overall to fit in caches but we only read a little bit at a time.

>One thing I didn't mention yet is that copying the data
>can sometimes reveal more parallelism. Compare to
>register renaming.

Sure, I already alluded to this with the potential advantage of not writing results into shared memory, causing cacheline evictions, for example. In our case, however, for the most part, we can partition the data in the output space. It's the input space that's tricky as each output can access quite a large (and sometimes unpredictable) subset of the input data.

>>There's no issue with the data structures in the serial >case.
>
>I can't make sense of that. Choosing a good data
>structure for each algorithm is the main way to optimize
>code (serial or parallel).

On occasion we have had to completely change algorithms for the parallel case in order to realise a performance gain. In cases where the modified algorithm harms single-threaded performance we actually retain both and select the appropriate one based on the number of threads in use. Sometimes turning a serial problem into a parallel one can require quite a bit of imagination and lateral thinking.

>>I would suggest that trying to do anything remotely complicated with programmers
>>that don't have a clue is a bad idea.
>
>And I would agree with you 110%. But it's the normal case,
>as well as being the particular case I have to deal with.

That's fine, provided you don't extrapolate from that particular case to the value and ease of multithreading in general.

It sounds like you're really programming in C with a little bit of C++ thrown in and very little encapsulation. That's perfectly valid, but it isn't very representative of how easy or difficult it is to thread other types of code and therefore whether people only "occasionally" manage to write correct multithreaded code.