4 ms·

Followup: I did a very rough prototype on my current Vulkan runner; all the good stuff is in the prefix.comp kernel code. It's not doing the fancy stuff, in par

Followup: I did a very rough prototype on my current Vulkan runner; all the good stuff is in the prefix.comp kernel code. It's not doing the fancy stuff, in particular it doesn't parallelize the lookback code, so that ends up taking a bunch of time. But it does give an example of how to use the Vulkan memory model, for which I've seen very little in the way of published material. If anyone is interested in tuning this and doing a performance comparison, please get in touch. It'd make a good blog post, I think, but already the time I've spent on it is a distraction from the renderer. https://github.com/linebender/piet-gpu/tree/prefix https://github.com/linebender/piet-gpu/tree/prefix

fluffything 7y ago
Thanks, that was super interesting to read. Is subgroupExclusiveAdd a primitive, or is it implemented somewhere? (i've been searching through the git repo without much luck). This has motivated me to learn a bit more about using Vulkan for compute. I hope I get to it tonight and tomorrow - benefits of the pandemic :D
- raphlinus 7y ago
  subgroupExclusiveAdd is part of the subgroup extension, and expected to be implemented in hardware. Best place to read about that is here: https://www.khronos.org/blog/vulkan-subgroup-tutorial https://www.khronos.org/blog/vulkan-subgroup-tutorial
  - fluffything 7y ago
    Which devices do implement this in hardware ? None of the NVIDIA compute devices do, right? Do AMD GPUs implement this ? CPUs from Intel, ARM, RISCV, MIPS, Power support horizontal SIMD add instructions that perform a tree-reduction. I'm skeptical of GPUs being able to actually implement this on hardware. A CPU puts the whole vector in a single 512-bit register, but in a GPU, even for a single half-warp, the operation cannot take 16x64bit registers. The operation would need to be performed on memory, and move the content to the different registers, do warp-local shuffles for the reduction, etc. So we would be talking about a quite big macro-op here. I wouldn't see the point of doing this in hardware, when the compiler or driver could just call a library function that does this for you. But then we are back to the issue that, if you can't write those library functions in pure Vulkan, you are quite limited w.r.t what one can do. There are many prefix-sum like algorithms, like, e.g., a weighted prefix-sum (prefix_sum(x * w)) [0]. In a GPU, you don't want to do the vector multiply first followed by the prefix-sum, but do it all at once. You can probably work around this in Vulkan by doing the vector multiply in shared memory, and then the prefix sum there (while in CUDA you wouldn't need shared memory for that at all), but that won't really work if the reduction is more complicated than just a sum. [0] Convolved prefix sums happen a lot in signal processing with linear-recurrence relations, e.g., in IIR filters, e.g. see [1] https://dl.acm.org/doi/10.1145/3229631.3229649 https://dl.acm.org/doi/10.1145/3229631.3229649 and [2] https://dl.acm.org/doi/10.1145/3296957.3173168 https://dl.acm.org/doi/10.1145/3296957.3173168. The weighted prefix sum example is the simplest possible instance of those.
    - raphlinus 7y ago
      Right, I haven't looked at PTX or Intel Gen ASM, but on AMD this compiles to a lg(n) series of add instructions each with a warp local shuffle (v_add_nc_u32 with a row_shr: modifier). It's not going to shared memory. I've experimented a bit with hand-rolling scans (using subgroupShuffleUp) and get similar but not identical asm (that intrinsic gives you a wave_ror: modifier). So I think you could write this using even lower-level intrinsics and also get good performance. I strongly suspect Intel and NVidia are similar here, but haven't experimented. [1]: http://shader-playground.timjones.io/4d7402168290f8922da5df3f314f87bc http://shader-playground.timjones.io/4d7402168290f8922da5df3...
      - raphlinus 7y ago
        There's actually a lot more to say here, but it really gets into the weeds. To me, the fundamental question is: can you write Vulkan 1.2 compute shaders that exploit most of the performance potential of GPU hardware in a portable way? I believe the answer is yes, but it requires validation. It is, however, not a good approach if the goal is to squeeze out the last 5% or 10% of performance.
        fluffything 7y ago
        That makes sense. Given that one can write good compute shaders with Vulkan, the next obvious question worth answering to me is whether one should do that. If I had to write a new foundational library, e.g., something like CUTLASS or cuFFT for device code, I won't start with code that fully uses a device, but I'd like to be able to do that if I want to. If I need to reach for CUDA to do that, then Vulkan, WebGPU, etc. will need to have great FFI with CUDA C++. Nobody wants to have to "drop up" to a higher-level CUDA C++ API like CUTLASS, but being forced to do so by "dropping down" that API to a C FFI wrapper. It would be like having Rust, but without any unsafe code support except for C FFI, C actually not existing, and having to drop "down" to C++ for everything, and then numbing down the C++ to C FFI for interoperability. You might as well just stick with C++ and spare you the pain. I hope Vulkan and WebGPU get enough extensions so that foundational libraries can be written in those languages.

fluffything 7y ago

Thanks, that was super interesting to read. Is subgroupExclusiveAdd a primitive, or is it implemented somewhere? (i've been searching through the git repo without much luck). This has motivated me to learn a bit more about using Vulkan for compute. I hope I get to it tonight and tomorrow - benefits of the pandemic :D

raphlinus 7y ago
subgroupExclusiveAdd is part of the subgroup extension, and expected to be implemented in hardware. Best place to read about that is here: https://www.khronos.org/blog/vulkan-subgroup-tutorial https://www.khronos.org/blog/vulkan-subgroup-tutorial
- fluffything 7y ago
  Which devices do implement this in hardware ? None of the NVIDIA compute devices do, right? Do AMD GPUs implement this ? CPUs from Intel, ARM, RISCV, MIPS, Power support horizontal SIMD add instructions that perform a tree-reduction. I'm skeptical of GPUs being able to actually implement this on hardware. A CPU puts the whole vector in a single 512-bit register, but in a GPU, even for a single half-warp, the operation cannot take 16x64bit registers. The operation would need to be performed on memory, and move the content to the different registers, do warp-local shuffles for the reduction, etc. So we would be talking about a quite big macro-op here. I wouldn't see the point of doing this in hardware, when the compiler or driver could just call a library function that does this for you. But then we are back to the issue that, if you can't write those library functions in pure Vulkan, you are quite limited w.r.t what one can do. There are many prefix-sum like algorithms, like, e.g., a weighted prefix-sum (prefix_sum(x * w)) [0]. In a GPU, you don't want to do the vector multiply first followed by the prefix-sum, but do it all at once. You can probably work around this in Vulkan by doing the vector multiply in shared memory, and then the prefix sum there (while in CUDA you wouldn't need shared memory for that at all), but that won't really work if the reduction is more complicated than just a sum. [0] Convolved prefix sums happen a lot in signal processing with linear-recurrence relations, e.g., in IIR filters, e.g. see [1] https://dl.acm.org/doi/10.1145/3229631.3229649 https://dl.acm.org/doi/10.1145/3229631.3229649 and [2] https://dl.acm.org/doi/10.1145/3296957.3173168 https://dl.acm.org/doi/10.1145/3296957.3173168. The weighted prefix sum example is the simplest possible instance of those.
  - raphlinus 7y ago
    Right, I haven't looked at PTX or Intel Gen ASM, but on AMD this compiles to a lg(n) series of add instructions each with a warp local shuffle (v_add_nc_u32 with a row_shr: modifier). It's not going to shared memory. I've experimented a bit with hand-rolling scans (using subgroupShuffleUp) and get similar but not identical asm (that intrinsic gives you a wave_ror: modifier). So I think you could write this using even lower-level intrinsics and also get good performance. I strongly suspect Intel and NVidia are similar here, but haven't experimented. [1]: http://shader-playground.timjones.io/4d7402168290f8922da5df3f314f87bc http://shader-playground.timjones.io/4d7402168290f8922da5df3...
    - raphlinus 7y ago
      There's actually a lot more to say here, but it really gets into the weeds. To me, the fundamental question is: can you write Vulkan 1.2 compute shaders that exploit most of the performance potential of GPU hardware in a portable way? I believe the answer is yes, but it requires validation. It is, however, not a good approach if the goal is to squeeze out the last 5% or 10% of performance.
      - fluffything 7y ago
        That makes sense. Given that one can write good compute shaders with Vulkan, the next obvious question worth answering to me is whether one should do that. If I had to write a new foundational library, e.g., something like CUTLASS or cuFFT for device code, I won't start with code that fully uses a device, but I'd like to be able to do that if I want to. If I need to reach for CUDA to do that, then Vulkan, WebGPU, etc. will need to have great FFI with CUDA C++. Nobody wants to have to "drop up" to a higher-level CUDA C++ API like CUTLASS, but being forced to do so by "dropping down" that API to a C FFI wrapper. It would be like having Rust, but without any unsafe code support except for C FFI, C actually not existing, and having to drop "down" to C++ for everything, and then numbing down the C++ to C FFI for interoperability. You might as well just stick with C++ and spare you the pain. I hope Vulkan and WebGPU get enough extensions so that foundational libraries can be written in those languages.