6 ms·

A sketch of string unescaping on GPGPU

73 points by panic 8y ago

deleted 8y ago
[deleted]
epberry 8y ago
It's late and I may not be thinking clearly or be well informed enough but... I wonder if this type of thing - implementing algorithms on GPUS that have been the bread and butter of CPUs for generations (parsing regular languages?) - begets a new style of using computer hardware. The sketch shows several clever techniques to get a modest performance gain on the GPU, but what happens when the GPU hardware keeps getting better and the CPU stagnates? I keep thinking back to that Feynman lecture of computers using the analogy of an office filing system. There the final step was a filing clerk so dumb he could only add one to things but he could do it so fast that he was still better than the filing clerk that could reason out all the operations. Can we extend that analogy to have 8 filing clerks all adding one to different wrong indexes and then choosing the right one in the end? (I'll be honest, my understanding of how GPUs work is rudimentary). Perhaps the gains we get from doing the wrong things in parallel actually start to outweigh CPUs doing the right things in sequence (ex branch mispredictions). EDIT: My ramblings aside, kudos to the author for a thought provoking piece.
- gmueckl 8y ago
  Some GPU based methods are faster when they rely on raw parallel processing power, even if it caused a huge amount of work to be discarded. These chips are well suited for regular, embarassingly parallel, dumb work. This starts to drop sharply with increasing branching and the amount of unordered memory accesses, although GPUs get better and better at that. So it can be better right now to do the dumb thing instead of the smart thing. I think that sorting on the GPU is a good example: a parallel quicksort is hard to implement and maps badly to GPU threads. A bitonic sort algorithm is likely to be much faster, although it is a very dumb algorithm.
  - epberry 8y ago
    Interesting, I wasn't familiar with bitonic sorting.
  - Coding_Cat 8y ago
    In general, all algorithms seem to get pushed more and more towards "optimize for memory access" than actually optimizing for computations. GPUs are no exception. Personally, I wonder more what effect widespread HBM (with speeds realistically expressed in TB/s for future iterations) will have on the algorithms we design.
    - gmueckl 8y ago
      Well, GPUs expose the memory hierarchy to the programmer and have atrocious latency when hitting global memory with unordered memory access patterns. Your only chance to make a GPU outperform a CPU is to design your algorithm completely around memory usage. The difference between doing it right and wrong can be several orders of magnitude. Even CPUs show huge performance gains when all the algorithm's data fits in the cache. This can easily be a factor 10 or more when you get it right.
- desertrider12 8y ago
  Doing the "wrong things" in parallel for a net benefit is already a very common theme in all parallel computing, especially in GPUs. All interesting parallel algorithms (more than just a parallel-for over tasks) do more total work than their serial versions, but have shorter critical sections. I found Feynman's lecture and it's a good analogy for the differences between GPUs and CPUs. The GPU has thousands of dumb clerks who are fast at using their scratch paper and doing a few different arithmetic operations, but there's only one boss giving the whole group their instructions. https://youtu.be/EKWGGDXe5MA?t=6m https://youtu.be/EKWGGDXe5MA?t=6m
- jcranmer 8y ago
  GPUs and CPUs have very different design methodologies. GPUs have very high memory latency--so high in fact, that the basic design of a GPU is to schedule enough threads per core so that you can hide the latency of memory requests. On top of this, GPUs impose a requirement that you have to have the control flow be more or less convergent between different threads. You also have a high cost to launch a kernel. Ultimately, GPUs require you to have lots of data in a high data-level parallelism to get any efficiency out of them. Fail to meet any of these requirements, and you can't run on a GPU. A CPU's fundamental design is to try to minimize the latency of any individual instruction, and to try to scavenge any instruction-level parallelism possible. If what you have is a code that is fundamentally serial, with no opportunity for parallelism, a CPU can turn everything else off and ramp up its core frequency to get it done as fast as possible. An example of an unparallelizable code is a binary search: it's a single loop with no instructions outside the critical path, and the inner branches and memory accesses are unpredictable. Another point to make about parallelism: communication bottleneck is the real killer. Your raw FLOPs performance scales more or less linearly with the number of nodes, but topologies mean your communication bandwidth between nodes scales closer to the sqrt (2D mesh) or n^2/3 (3D mesh). It's easy to make a chip with an obscenely high peak FLOP count, but when you try to program it, you find you can't fill the ALUs fast enough, so most of those are idle.

73 points by panic 8y ago

deleted 8y ago

[deleted]

It's late and I may not be thinking clearly or be well informed enough but... I wonder if this type of thing - implementing algorithms on GPUS that have been the bread and butter of CPUs for generations (parsing regular languages?) - begets a new style of using computer hardware. The sketch shows several clever techniques to get a modest performance gain on the GPU, but what happens when the GPU hardware keeps getting better and the CPU stagnates? I keep thinking back to that Feynman lecture of computers using the analogy of an office filing system. There the final step was a filing clerk so dumb he could only add one to things but he could do it so fast that he was still better than the filing clerk that could reason out all the operations. Can we extend that analogy to have 8 filing clerks all adding one to different wrong indexes and then choosing the right one in the end? (I'll be honest, my understanding of how GPUs work is rudimentary). Perhaps the gains we get from doing the wrong things in parallel actually start to outweigh CPUs doing the right things in sequence (ex branch mispredictions). EDIT: My ramblings aside, kudos to the author for a thought provoking piece.

gmueckl 8y ago
Some GPU based methods are faster when they rely on raw parallel processing power, even if it caused a huge amount of work to be discarded. These chips are well suited for regular, embarassingly parallel, dumb work. This starts to drop sharply with increasing branching and the amount of unordered memory accesses, although GPUs get better and better at that. So it can be better right now to do the dumb thing instead of the smart thing. I think that sorting on the GPU is a good example: a parallel quicksort is hard to implement and maps badly to GPU threads. A bitonic sort algorithm is likely to be much faster, although it is a very dumb algorithm.
- epberry 8y ago
  Interesting, I wasn't familiar with bitonic sorting.
- Coding_Cat 8y ago
  In general, all algorithms seem to get pushed more and more towards "optimize for memory access" than actually optimizing for computations. GPUs are no exception. Personally, I wonder more what effect widespread HBM (with speeds realistically expressed in TB/s for future iterations) will have on the algorithms we design.
  - gmueckl 8y ago
    Well, GPUs expose the memory hierarchy to the programmer and have atrocious latency when hitting global memory with unordered memory access patterns. Your only chance to make a GPU outperform a CPU is to design your algorithm completely around memory usage. The difference between doing it right and wrong can be several orders of magnitude. Even CPUs show huge performance gains when all the algorithm's data fits in the cache. This can easily be a factor 10 or more when you get it right.
desertrider12 8y ago
Doing the "wrong things" in parallel for a net benefit is already a very common theme in all parallel computing, especially in GPUs. All interesting parallel algorithms (more than just a parallel-for over tasks) do more total work than their serial versions, but have shorter critical sections. I found Feynman's lecture and it's a good analogy for the differences between GPUs and CPUs. The GPU has thousands of dumb clerks who are fast at using their scratch paper and doing a few different arithmetic operations, but there's only one boss giving the whole group their instructions. https://youtu.be/EKWGGDXe5MA?t=6m https://youtu.be/EKWGGDXe5MA?t=6m
jcranmer 8y ago
GPUs and CPUs have very different design methodologies. GPUs have very high memory latency--so high in fact, that the basic design of a GPU is to schedule enough threads per core so that you can hide the latency of memory requests. On top of this, GPUs impose a requirement that you have to have the control flow be more or less convergent between different threads. You also have a high cost to launch a kernel. Ultimately, GPUs require you to have lots of data in a high data-level parallelism to get any efficiency out of them. Fail to meet any of these requirements, and you can't run on a GPU. A CPU's fundamental design is to try to minimize the latency of any individual instruction, and to try to scavenge any instruction-level parallelism possible. If what you have is a code that is fundamentally serial, with no opportunity for parallelism, a CPU can turn everything else off and ramp up its core frequency to get it done as fast as possible. An example of an unparallelizable code is a binary search: it's a single loop with no instructions outside the critical path, and the inner branches and memory accesses are unpredictable. Another point to make about parallelism: communication bottleneck is the real killer. Your raw FLOPs performance scales more or less linearly with the number of nodes, but topologies mean your communication bandwidth between nodes scales closer to the sqrt (2D mesh) or n^2/3 (3D mesh). It's easy to make a chip with an obscenely high peak FLOP count, but when you try to program it, you find you can't fill the ALUs fast enough, so most of those are idle.