4 ms·

Fooling the masses with performance results on parallel computers (2010)

53 points by jsnell 10y ago

mpweiher 10y ago
One of my favorites of these is only showing the speedup..."scales linearly", without comparing to a non-parallel baseline. First time I saw this was with Clik, which reported linear scaling. I was impressed, until I found out that the parallel version was 6x slower on a single CPU than the sequential version. Similar with a SPJ talk on parallel Haskell (can't find it right now). Big claims about this being the One True Way, and then required four cores to match C sequential case. Hmmm. UPDATE: https://www.youtube.com/watch?v=NWSZ4c9yqW8 https://www.youtube.com/watch?v=NWSZ4c9yqW8 around the 1h 10min mark. Four cores to match sequential C (previously had written six, was wrong)
- adrianN 10y ago
  See also "Scalability! But at What COST?" https://www.usenix.org/system/files/conference/hotos15/hotos15-paper-mcsherry.pdf https://www.usenix.org/system/files/conference/hotos15/hotos...
  - mpweiher 10y ago
    Ahh, yes, the Configuration that Outperforms a Single Thread. I think this should be a standard + required measurement.
- ergl 10y ago
  I had a similar realization when I read on STM performance[1], where almost all benchmarks showed considerable slowdowns for the parallel+stm implementations when compared against sequential solutions. [1]: http://queue.acm.org/detail.cfm?id=1454466 http://queue.acm.org/detail.cfm?id=1454466
- inetknght 10y ago
  > This video is not available. > Sorry about that. Oh, Youtube...
- scott_s 10y ago
  Agreed. To my surprise, he kinda argues against this in one of his items (https://blogs.fau.de/hager/archives/6558 https://blogs.fau.de/hager/archives/6558): Always compare the fully parallel accelerator code with a sequential (single-core) CPU version. You can even argue in favor of this, saying that “serial CPU code constitutes a well-defined baseline.” Be sure to rush ahead to the next slide before anyone dares to ask why you don’t use a single GPGPU “core” to make the comparison even more “well-defined.” To be clear, this is about the performance of accelerated codes (such as GPU or FPGA). I had to read that multiple times to come up with the most charitable explanation. What he's really arguing against is framing: it's not valid to claim a 200x performance increase if your baseline is the sequential version on a single core. The graph he shows is actually about a 2.3x performance improvement (comparing GPU with ECC on against CPU with using 12 cores). But as mpweiher points out, I think you absolutely need to include the sequential version in your comparison set: the sequential performance is your "table stakes" baseline. If you can never beat it, then I don't care what your scalability on the device is! It should be there as a sanity check: yes, this approach is better than just using a single thread on the CPU. Where it gets interesting is that whether or not the sequential version wins is often dependent on problem size. In that case, the sequential version needs to be included because even if "large enough" problem sizes benefit from the accelerator, there may be real problem sizes that are not large enough. I think Hager is also coming from the world of HPC, where its okay to focus on particular kernels instead of end-to-end application performance. This is the case in the linked post; the performance graph is for a matrix multiply, not an application which uses matrix multiply for a larger result. And end-to-end application performance often requires factoring in some of the other bullet points (such as device communication) that focusing on kernels side-steps.
- smitherfield 10y ago
  As a bit of a layman with this stuff, I'm wondering if "running the parallel version on a single CPU" means running a parallel algorithm (which is different from a sequential algorithm) on one CPU, or if the sequential and the single-threaded parallel algorithms are equivalent, and it's measuring the difference between e.g. 8 threads per 1 CPU vs. 1 thread per 8 CPUs (in which case, obviously, context switches would account for the performance difference).
  - scott_s 10y ago
    When someone says "running the parallel version on a single CPU" they usually mean running the parallel version with 1 thread on 1 CPU. Comparing that to the sequential (non-parallel) version allows you to measure the baseline overhead cost of parallelization. There are also non-baseline overhead costs of parallelization, which usually come in the form of synchronization overhead between threads or processes.
amelius 10y ago
It should mention: ignoring Amdahl's law, [1]. [1] https://en.wikipedia.org/wiki/Amdahl's_law https://en.wikipedia.org/wiki/Amdahl's_law
- jjoonathan 10y ago
  Alternatively: paying close attention to it and leveraging it for selfish ends.
- Athas 10y ago
  Amdahl's Law is easy to misapply on both sides of the fence. If what you care about is mostly weak scaling (using larger machines to solve larger problems), the Law is not as harsh as it appears at first glance, as in many cases the parallel fraction increases as the workload does.
Athas 10y ago
How come reviewers let this stuff pass in papers? While some of the issues are subtle (inventing more work or mangling the algorithm), some of the graph-based tricks are pretty obvious.
paulmd 10y ago
> Stunt 9: Boast massive speedups with accelerators! > Always compare the fully parallel accelerator code with a sequential (single-core) CPU version. > Be sure to rush ahead to the next slide before anyone dares to ask why you don’t use a single GPGPU “core” to make the comparison even more “well-defined.” > Accelerate only the kernels that are easily portable and report only their performance. Amdahl’s Law and communication overhead will be nothing but smoke and mirrors! I disagree with this one. The baseline for a parallel program is always the best single-threaded program you can write (which usually means with OpenMP/threading removed to reduce overhead). The goal of writing parallel programs is to increase the degree of parallelism that a program exposes, even if the total running time of the program increases (i.e. time spent over all cores, not time-per-core). You know going into it that adding synchronization is going to slow you down - even in standard parallel-CPU programs (OpenMP). Effective GPU parallelization works the same way. For example, you might use counter-based RNGs that are really too slow to be used on CPUs (at least, in the days before AES-NI), but on GPUs math is often "free" because the program is bandwidth limited. Or you might choose to re-compute data in memory rather if possible rather than storing it in memory and costing RAM and bandwidth. You are "wasting cycles" deliberately, to expose a greater degree of parallelism/reduce contention to increase overall program performance. So running the program on a single GPU core is just as stupid as benchmarking an OpenMP program on a single core - again, we literally know going into it that the single-threaded programs are usually most efficient in terms of total cycles expended, that's not really what we're trying to measure here. In the text, the author then pivots to "well GPUs have more cores/memory bandwidth!", which is also rather myopic and dismissive of the actual challenges of GPGPU programming. Exploiting that bandwidth is not easy on a processor with massive latency and <100 bytes of SRAM per core to spread between cache, shared memory, and constant pointers across many threads, not to mention the problems of thread divergence, etc. I do agree that communication overhead needs to be taken into account and total program time is what really counts. This is (IMO) a strong argument for either porting your entire program to run on the GPU, or an absolutely minimal set, so that you minimize communication overhead. The distinction I'm drawing here is the latter is something like GPU-accelerated database searching, where you are not going to store actual rows on the GPU, but just DB indexes that you search and copy target IDs back to the host system. Either way you approach it, your data set needs to live on the GPU as much as possible, which means minimizing the number of times and amount that it gets copied to-and-fro and incurs communication bottlenecks/latency. In turn - this means absolutely brutal minimization of the program state to reduce memory consumption, because fitting a larger problem into the GPU will usually increase total speedups (for a well-written program).
wcrichton 10y ago
This reminds me of my favorite paper: "Scalability! But at what COST?" https://pdfs.semanticscholar.org/6753/959eed800e9fad9e330daae43f81b7a48017.pdf https://pdfs.semanticscholar.org/6753/959eed800e9fad9e330daa...

53 points by jsnell 10y ago

One of my favorites of these is only showing the speedup..."scales linearly", without comparing to a non-parallel baseline. First time I saw this was with Clik, which reported linear scaling. I was impressed, until I found out that the parallel version was 6x slower on a single CPU than the sequential version. Similar with a SPJ talk on parallel Haskell (can't find it right now). Big claims about this being the One True Way, and then required four cores to match C sequential case. Hmmm. UPDATE: https://www.youtube.com/watch?v=NWSZ4c9yqW8 https://www.youtube.com/watch?v=NWSZ4c9yqW8 around the 1h 10min mark. Four cores to match sequential C (previously had written six, was wrong)

adrianN 10y ago
See also "Scalability! But at What COST?" https://www.usenix.org/system/files/conference/hotos15/hotos15-paper-mcsherry.pdf https://www.usenix.org/system/files/conference/hotos15/hotos...
- mpweiher 10y ago
  Ahh, yes, the Configuration that Outperforms a Single Thread. I think this should be a standard + required measurement.
ergl 10y ago
I had a similar realization when I read on STM performance[1], where almost all benchmarks showed considerable slowdowns for the parallel+stm implementations when compared against sequential solutions. [1]: http://queue.acm.org/detail.cfm?id=1454466 http://queue.acm.org/detail.cfm?id=1454466
inetknght 10y ago
> This video is not available. > Sorry about that. Oh, Youtube...
scott_s 10y ago
Agreed. To my surprise, he kinda argues against this in one of his items (https://blogs.fau.de/hager/archives/6558 https://blogs.fau.de/hager/archives/6558): Always compare the fully parallel accelerator code with a sequential (single-core) CPU version. You can even argue in favor of this, saying that “serial CPU code constitutes a well-defined baseline.” Be sure to rush ahead to the next slide before anyone dares to ask why you don’t use a single GPGPU “core” to make the comparison even more “well-defined.” To be clear, this is about the performance of accelerated codes (such as GPU or FPGA). I had to read that multiple times to come up with the most charitable explanation. What he's really arguing against is framing: it's not valid to claim a 200x performance increase if your baseline is the sequential version on a single core. The graph he shows is actually about a 2.3x performance improvement (comparing GPU with ECC on against CPU with using 12 cores). But as mpweiher points out, I think you absolutely need to include the sequential version in your comparison set: the sequential performance is your "table stakes" baseline. If you can never beat it, then I don't care what your scalability on the device is! It should be there as a sanity check: yes, this approach is better than just using a single thread on the CPU. Where it gets interesting is that whether or not the sequential version wins is often dependent on problem size. In that case, the sequential version needs to be included because even if "large enough" problem sizes benefit from the accelerator, there may be real problem sizes that are not large enough. I think Hager is also coming from the world of HPC, where its okay to focus on particular kernels instead of end-to-end application performance. This is the case in the linked post; the performance graph is for a matrix multiply, not an application which uses matrix multiply for a larger result. And end-to-end application performance often requires factoring in some of the other bullet points (such as device communication) that focusing on kernels side-steps.
smitherfield 10y ago
As a bit of a layman with this stuff, I'm wondering if "running the parallel version on a single CPU" means running a parallel algorithm (which is different from a sequential algorithm) on one CPU, or if the sequential and the single-threaded parallel algorithms are equivalent, and it's measuring the difference between e.g. 8 threads per 1 CPU vs. 1 thread per 8 CPUs (in which case, obviously, context switches would account for the performance difference).
- scott_s 10y ago
  When someone says "running the parallel version on a single CPU" they usually mean running the parallel version with 1 thread on 1 CPU. Comparing that to the sequential (non-parallel) version allows you to measure the baseline overhead cost of parallelization. There are also non-baseline overhead costs of parallelization, which usually come in the form of synchronization overhead between threads or processes.

amelius 10y ago

It should mention: ignoring Amdahl's law, [1]. [1] https://en.wikipedia.org/wiki/Amdahl's_law https://en.wikipedia.org/wiki/Amdahl's_law

jjoonathan 10y ago
Alternatively: paying close attention to it and leveraging it for selfish ends.
Athas 10y ago
Amdahl's Law is easy to misapply on both sides of the fence. If what you care about is mostly weak scaling (using larger machines to solve larger problems), the Law is not as harsh as it appears at first glance, as in many cases the parallel fraction increases as the workload does.

Athas 10y ago

How come reviewers let this stuff pass in papers? While some of the issues are subtle (inventing more work or mangling the algorithm), some of the graph-based tricks are pretty obvious.

paulmd 10y ago

> Stunt 9: Boast massive speedups with accelerators! > Always compare the fully parallel accelerator code with a sequential (single-core) CPU version. > Be sure to rush ahead to the next slide before anyone dares to ask why you don’t use a single GPGPU “core” to make the comparison even more “well-defined.” > Accelerate only the kernels that are easily portable and report only their performance. Amdahl’s Law and communication overhead will be nothing but smoke and mirrors! I disagree with this one. The baseline for a parallel program is always the best single-threaded program you can write (which usually means with OpenMP/threading removed to reduce overhead). The goal of writing parallel programs is to increase the degree of parallelism that a program exposes, even if the total running time of the program increases (i.e. time spent over all cores, not time-per-core). You know going into it that adding synchronization is going to slow you down - even in standard parallel-CPU programs (OpenMP). Effective GPU parallelization works the same way. For example, you might use counter-based RNGs that are really too slow to be used on CPUs (at least, in the days before AES-NI), but on GPUs math is often "free" because the program is bandwidth limited. Or you might choose to re-compute data in memory rather if possible rather than storing it in memory and costing RAM and bandwidth. You are "wasting cycles" deliberately, to expose a greater degree of parallelism/reduce contention to increase overall program performance. So running the program on a single GPU core is just as stupid as benchmarking an OpenMP program on a single core - again, we literally know going into it that the single-threaded programs are usually most efficient in terms of total cycles expended, that's not really what we're trying to measure here. In the text, the author then pivots to "well GPUs have more cores/memory bandwidth!", which is also rather myopic and dismissive of the actual challenges of GPGPU programming. Exploiting that bandwidth is not easy on a processor with massive latency and <100 bytes of SRAM per core to spread between cache, shared memory, and constant pointers across many threads, not to mention the problems of thread divergence, etc. I do agree that communication overhead needs to be taken into account and total program time is what really counts. This is (IMO) a strong argument for either porting your entire program to run on the GPU, or an absolutely minimal set, so that you minimize communication overhead. The distinction I'm drawing here is the latter is something like GPU-accelerated database searching, where you are not going to store actual rows on the GPU, but just DB indexes that you search and copy target IDs back to the host system. Either way you approach it, your data set needs to live on the GPU as much as possible, which means minimizing the number of times and amount that it gets copied to-and-fro and incurs communication bottlenecks/latency. In turn - this means absolutely brutal minimization of the program state to reduce memory consumption, because fitting a larger problem into the GPU will usually increase total speedups (for a well-written program).

wcrichton 10y ago

This reminds me of my favorite paper: "Scalability! But at what COST?" https://pdfs.semanticscholar.org/6753/959eed800e9fad9e330daae43f81b7a48017.pdf https://pdfs.semanticscholar.org/6753/959eed800e9fad9e330daa...