7 ms·

Prefix Sum on Vulkan

58 points by raphlinus 6y ago

boulos 6y ago
Huh, I missed the discussion in https://news.ycombinator.com/item?id=22902274 https://news.ycombinator.com/item?id=22902274 but while prefix-sum makes for a reasonable microbenchmark, I think it misses my main problem with any of the existing !CUDA attempts: ergonomics. The Vulkan Compute attitude towards device memory deeply confuses me. That is, for both OpenCL and Vulkan Compute, there is no way to say (AFAICT / at least a couple years ago): "I wish to allocate X amount of memory on this device, do not spill to the host; fail if you cannot satisfy". For most programs, it's probably a fine assumption, just like virtual memory for a regular program. But in a world where you're trying to push a system to the limit, you'd still like to say "No, I'm serious". Raph: What's your take on the ergonomics of using Vulkan Compute? I'd hoped to see more on that given your opening of: > Vulkan might be a viable platform, for a sufficiently persistent implementor.
- raphlinus 6y ago
  My take is that ergonomics are pretty bad, there's a significant learning curve. But I'm also hopeful that it's possible to build tools that layer on top of Vulkan - unlike CUDA, which is a highly integrated toolchain and runtime, Vulkan really only targets the lower levels of the stack. I can't speak to your memory allocation question, as I'm personally quite happy with the default behavior.
  - pjmlp 6y ago
    Given that CUDA has a thriving eco-system of programming languages targeting it, I fail to see how it is not possible to build tooling on top of it.
klodolph 6y ago
> Before then, the mechanism for lock-free programming patterns was the volatile qualifier and various nonstandard barrier intrinsics. Ehhhhhh… > The semantics of volatile were never clearly defined… Well, the problem is that volatile was defined, more or less. It means that you get load and store instructions in machine code that correspond to the appearance of loads and stores in the source code. Importantly, this does not imply anything about the memory model on multiprocessor systems. So "volatile" was never supposed to be used for threading. What you can use it for is: - Memory-mapped I/O - Values that are changed in interrupts - Values changed on other threads on x86 if you just don’t give a damn - longjmp/setjmp - Values changed on other threads on Itanium What happens when you don’t use “volatile” is that the compiler will do dead store elimination and optimize out loads. For example, // Global; int x = 0; void wait_for_x(void) { while (x == 0) {} } If `x` is modified by an interrupt, it should be marked `volatile` because otherwise the compiler will helpfully optimize out the test in the loop. What people actually did for lock-free programming in the pre-C++-11 days was to use those non-portable intrinsics or inline assembler. If someone used “volatile”, it was usually out of ignorance.
- raphlinus 6y ago
  Ok, I want to get this right. The major point I'm trying to make is that without the Vulkan memory model, the way to get atomic loads and stores is to add the "volatile" memory qualifier to the buffer interface block. This has basically the same set of problems as using "volatile" in pre-C++11 code. There is definitely precedent for using "volatile" in multithreaded code (though, researching this, I think there may be stronger precedents in C than in C++, see [1], particularly the "In C++11, normally never use volatile for threading, only for MMIO" answer). I agree a good argument can be made that it's incorrect. To be clear, the argument that volatile is incorrect for multithreading is extremely strong from the perspective of standard C and C++, but I think in practice it was considered quite usable. I have a feeling we agree on the substance (a memory model is a dramatic improvement over using volatile), but I can probably improve the wording. [1]: https://stackoverflow.com/questions/4557979/when-to-use-volatile-with-multi-threading https://stackoverflow.com/questions/4557979/when-to-use-vola... ETA: Here's what I consider a great reference for the widespread use of volatile for multithreaded programming. It's from 2001, but by Andrei Alexandrescu, who I think can be considered an authority: https://www.drdobbs.com/cpp/volatile-the-multithreaded-programmers-b/184403766 https://www.drdobbs.com/cpp/volatile-the-multithreaded-progr...
  - raphlinus 6y ago
    Followup: I've changed the language a bit, I hope you agree it's an improvement. https://github.com/raphlinus/raphlinus.github.io/commit/6b92d19492f8052776d84894dda000e5376d1ff1 https://github.com/raphlinus/raphlinus.github.io/commit/6b92...
- ncmncm 6y ago
  Many people have written code targeting only MSVC, where volatile is documented to have atomic-like properties, and targeting only x86, where the bus is especially forgiving, albeit at massive costs in extra logic to make it so. So it's not so much ignorance at work as (pathological) tolerance of MS and x86 lock-in. That said, I know a FreeBSD kernel committer who in 2014 was convinced that "volatile" sufficed for thread synchronization on Gcc and any arch. So there is also plenty of ignorance at work. You could say that MS, Intel, and AMD have benefitted from such ignorance through the large amount of de-facto unportable code it engendered.
deleted 6y ago
[deleted]
arianvanp 6y ago
I previously read this: https://cachemiss.xyz/blog/parallel-reduce-and-scan-on-the-GPU https://cachemiss.xyz/blog/parallel-reduce-and-scan-on-the-G... whose implementation seems a lot simpler than what is presented here. What is the main difference here? I've only dabbled a bit in Vulkan. (I wrote a pathtracer that I wanted to speed up using compaction; for which I needed a prefix sum)
- raphlinus 6y ago
  It's a good blog, but only solves a much simpler version of the problem - it only computes prefix sum of a workgroup worth of data. It does not carry the sums forward from workgroup to workgroup, which is the entire point of the decoupled look-back approach. The per-workgroup implementation in that blog is basically similar to mine, though I've put more effort into maxing out the partition size (using as many registers as available).
ohiovr 6y ago
16309
bronxbomber92 6y ago
A couple of small comments. 1. The single pass prefix sum the author implements is not legal Vulkan code. The algorithm requires spinning on conditions to be satisfied by concurrently running threads. This is allowed to deadlock in Vulkan and is mentioned explicitly in the "Limited Forward Progress Guarantees" section of the Vulkan Memory Model blog post linked to by the author. The only GPUs on which is it technically safe to run this algorithm are the Volta and newer NVIDIA architectures. 2. The mask argument of the CUDA shuffle intrinsics is there, not because it is a more powerful abstraction, but because compiler technology of today is unable to prevent illegal code motion of shuffle intrinsics. There are threads on the LLVM mailing list that discuss this in some detail. 3. I am happy to see this topic written about. Portability of compute algorithms and where APIs differ or lack is not well understood and CUDA tends to dominate the discussions. Regarding subgroup portability - I do wonder if asking developers to write their code for specific subgroup sizes and allowing them to request subgroup sizes is the correct long term abstraction. In Metal you can get a long way writing code that uses subgroup ('simdgroup' in Metal speak) functionality without actually making any assumptions about the subgroup size. It is a balance - there will always be performance to be had if you hard code such assumptions, but the more we can close the gap, the less it makes sense to do so.
- raphlinus 6y ago
  Thanks, especially the second paragraph. I'll probably update the post based on that (I've made several updates already). On 1, I'm wondering if there's some confusion, especially as I don't see what difference Volta makes here. I accept that the Vulkan spec makes no guarantees about thread scheduling fairness, and that one could write an adversarial but spec-compliant implementation which schedules the atomic bump of the first workgroup to claim the first partition, then context switches to the second workgroup and attempts to run it to completion, which will deadlock. But I think it is reasonable to make the assumption, for an extremely wide range of hardware, that when the atomic bump is scheduled, the code to compute the partition aggregate will make forward progress at least to the point where it writes that aggregate, which is all that is required for completion. Note that this all of this is about a workgroup depending on the progress of another workgroup. Obviously if invocations within a workgroup were depending on the progress of other invocations within the same workgroup, that would be a problem, but of course there are control barriers for that. I don't see how it is any more technically safe to run this on Volta than any other hardware. If there is a document that guarantees stronger forward progress than mandated by the spec, I'm unaware of it. From my reading of the spec, there is no way to write a one-pass prefix sum that is technically guaranteed deadlock-free. I'd argue that this is a defect of the spec, as there's a gap between useful guarantees that can safely be made by all real hardware and what the spec provides. I'll allow that fixing this defect is not easy. Until then, I think a good strategy is to ignore the defect. On 3, while I hope to avoid code duplication, so far our track record has been pretty rough. For piet-metal, I tried writing the kernel in subgroup size adaptive way, but had problems with size 64 subgroups, as that requires dealing with 64 bit ballot values, and I never got that to work (I don't have 64 bit hardware in front of me, so had to iterate by asking other people to test). Also, for Brian's work on 32x32 boolean matrix transpose, we tried a hybrid approach using both subgroups and thread local storage, and performance was really disappointing. But, armed with this experience, perhaps we can do better going forward.

58 points by raphlinus 6y ago

Huh, I missed the discussion in https://news.ycombinator.com/item?id=22902274 https://news.ycombinator.com/item?id=22902274 but while prefix-sum makes for a reasonable microbenchmark, I think it misses my main problem with any of the existing !CUDA attempts: ergonomics. The Vulkan Compute attitude towards device memory deeply confuses me. That is, for both OpenCL and Vulkan Compute, there is no way to say (AFAICT / at least a couple years ago): "I wish to allocate X amount of memory on this device, do not spill to the host; fail if you cannot satisfy". For most programs, it's probably a fine assumption, just like virtual memory for a regular program. But in a world where you're trying to push a system to the limit, you'd still like to say "No, I'm serious". Raph: What's your take on the ergonomics of using Vulkan Compute? I'd hoped to see more on that given your opening of: > Vulkan might be a viable platform, for a sufficiently persistent implementor.

raphlinus 6y ago
My take is that ergonomics are pretty bad, there's a significant learning curve. But I'm also hopeful that it's possible to build tools that layer on top of Vulkan - unlike CUDA, which is a highly integrated toolchain and runtime, Vulkan really only targets the lower levels of the stack. I can't speak to your memory allocation question, as I'm personally quite happy with the default behavior.
- pjmlp 6y ago
  Given that CUDA has a thriving eco-system of programming languages targeting it, I fail to see how it is not possible to build tooling on top of it.

klodolph 6y ago

> Before then, the mechanism for lock-free programming patterns was the volatile qualifier and various nonstandard barrier intrinsics. Ehhhhhh… > The semantics of volatile were never clearly defined… Well, the problem is that volatile was defined, more or less. It means that you get load and store instructions in machine code that correspond to the appearance of loads and stores in the source code. Importantly, this does not imply anything about the memory model on multiprocessor systems. So "volatile" was never supposed to be used for threading. What you can use it for is: - Memory-mapped I/O - Values that are changed in interrupts - Values changed on other threads on x86 if you just don’t give a damn - longjmp/setjmp - Values changed on other threads on Itanium What happens when you don’t use “volatile” is that the compiler will do dead store elimination and optimize out loads. For example, // Global; int x = 0; void wait_for_x(void) { while (x == 0) {} } If `x` is modified by an interrupt, it should be marked `volatile` because otherwise the compiler will helpfully optimize out the test in the loop. What people actually did for lock-free programming in the pre-C++-11 days was to use those non-portable intrinsics or inline assembler. If someone used “volatile”, it was usually out of ignorance.

raphlinus 6y ago
Ok, I want to get this right. The major point I'm trying to make is that without the Vulkan memory model, the way to get atomic loads and stores is to add the "volatile" memory qualifier to the buffer interface block. This has basically the same set of problems as using "volatile" in pre-C++11 code. There is definitely precedent for using "volatile" in multithreaded code (though, researching this, I think there may be stronger precedents in C than in C++, see [1], particularly the "In C++11, normally never use volatile for threading, only for MMIO" answer). I agree a good argument can be made that it's incorrect. To be clear, the argument that volatile is incorrect for multithreading is extremely strong from the perspective of standard C and C++, but I think in practice it was considered quite usable. I have a feeling we agree on the substance (a memory model is a dramatic improvement over using volatile), but I can probably improve the wording. [1]: https://stackoverflow.com/questions/4557979/when-to-use-volatile-with-multi-threading https://stackoverflow.com/questions/4557979/when-to-use-vola... ETA: Here's what I consider a great reference for the widespread use of volatile for multithreaded programming. It's from 2001, but by Andrei Alexandrescu, who I think can be considered an authority: https://www.drdobbs.com/cpp/volatile-the-multithreaded-programmers-b/184403766 https://www.drdobbs.com/cpp/volatile-the-multithreaded-progr...
- raphlinus 6y ago
  Followup: I've changed the language a bit, I hope you agree it's an improvement. https://github.com/raphlinus/raphlinus.github.io/commit/6b92d19492f8052776d84894dda000e5376d1ff1 https://github.com/raphlinus/raphlinus.github.io/commit/6b92...
ncmncm 6y ago
Many people have written code targeting only MSVC, where volatile is documented to have atomic-like properties, and targeting only x86, where the bus is especially forgiving, albeit at massive costs in extra logic to make it so. So it's not so much ignorance at work as (pathological) tolerance of MS and x86 lock-in. That said, I know a FreeBSD kernel committer who in 2014 was convinced that "volatile" sufficed for thread synchronization on Gcc and any arch. So there is also plenty of ignorance at work. You could say that MS, Intel, and AMD have benefitted from such ignorance through the large amount of de-facto unportable code it engendered.

deleted 6y ago

[deleted]

arianvanp 6y ago

I previously read this: https://cachemiss.xyz/blog/parallel-reduce-and-scan-on-the-GPU https://cachemiss.xyz/blog/parallel-reduce-and-scan-on-the-G... whose implementation seems a lot simpler than what is presented here. What is the main difference here? I've only dabbled a bit in Vulkan. (I wrote a pathtracer that I wanted to speed up using compaction; for which I needed a prefix sum)

raphlinus 6y ago
It's a good blog, but only solves a much simpler version of the problem - it only computes prefix sum of a workgroup worth of data. It does not carry the sums forward from workgroup to workgroup, which is the entire point of the decoupled look-back approach. The per-workgroup implementation in that blog is basically similar to mine, though I've put more effort into maxing out the partition size (using as many registers as available).

ohiovr 6y ago

16309

bronxbomber92 6y ago

A couple of small comments. 1. The single pass prefix sum the author implements is not legal Vulkan code. The algorithm requires spinning on conditions to be satisfied by concurrently running threads. This is allowed to deadlock in Vulkan and is mentioned explicitly in the "Limited Forward Progress Guarantees" section of the Vulkan Memory Model blog post linked to by the author. The only GPUs on which is it technically safe to run this algorithm are the Volta and newer NVIDIA architectures. 2. The mask argument of the CUDA shuffle intrinsics is there, not because it is a more powerful abstraction, but because compiler technology of today is unable to prevent illegal code motion of shuffle intrinsics. There are threads on the LLVM mailing list that discuss this in some detail. 3. I am happy to see this topic written about. Portability of compute algorithms and where APIs differ or lack is not well understood and CUDA tends to dominate the discussions. Regarding subgroup portability - I do wonder if asking developers to write their code for specific subgroup sizes and allowing them to request subgroup sizes is the correct long term abstraction. In Metal you can get a long way writing code that uses subgroup ('simdgroup' in Metal speak) functionality without actually making any assumptions about the subgroup size. It is a balance - there will always be performance to be had if you hard code such assumptions, but the more we can close the gap, the less it makes sense to do so.

raphlinus 6y ago
Thanks, especially the second paragraph. I'll probably update the post based on that (I've made several updates already). On 1, I'm wondering if there's some confusion, especially as I don't see what difference Volta makes here. I accept that the Vulkan spec makes no guarantees about thread scheduling fairness, and that one could write an adversarial but spec-compliant implementation which schedules the atomic bump of the first workgroup to claim the first partition, then context switches to the second workgroup and attempts to run it to completion, which will deadlock. But I think it is reasonable to make the assumption, for an extremely wide range of hardware, that when the atomic bump is scheduled, the code to compute the partition aggregate will make forward progress at least to the point where it writes that aggregate, which is all that is required for completion. Note that this all of this is about a workgroup depending on the progress of another workgroup. Obviously if invocations within a workgroup were depending on the progress of other invocations within the same workgroup, that would be a problem, but of course there are control barriers for that. I don't see how it is any more technically safe to run this on Volta than any other hardware. If there is a document that guarantees stronger forward progress than mandated by the spec, I'm unaware of it. From my reading of the spec, there is no way to write a one-pass prefix sum that is technically guaranteed deadlock-free. I'd argue that this is a defect of the spec, as there's a gap between useful guarantees that can safely be made by all real hardware and what the spec provides. I'll allow that fixing this defect is not easy. Until then, I think a good strategy is to ignore the defect. On 3, while I hope to avoid code duplication, so far our track record has been pretty rough. For piet-metal, I tried writing the kernel in subgroup size adaptive way, but had problems with size 64 subgroups, as that requires dealing with 64 bit ballot values, and I never got that to work (I don't have 64 bit hardware in front of me, so had to iterate by asking other people to test). Also, for Brian's work on 32x32 boolean matrix transpose, we tried a hybrid approach using both subgroups and thread local storage, and performance was really disappointing. But, armed with this experience, perhaps we can do better going forward.