My experience with it was: with CSR format, SpMV got about 40x speedup compared to a single CPU core on a RTX 3090, with full core utilization. Rough calculation tells me it's equivalent to 80 GFlops, which is far from the full potential of the card. I thought there was someting wrong with cuSPARSE so I went ahead and wrote a SpMV kernel, based on the code in NVIDIA's past reports. It actually performed slightly better. Fair enough, cuSPARSE has to support all kind of workloads so it might be just that in my case, the handwritten kernel worked better. But still, it would never get to the regime of hundreds of GFlops. After reading various literatures on GPU SpMV implementations getting to the same conclusion, I had to concede that I can't squeeze more GFlops out of it.
Have you checked the roofline performance model as reported by Nsight Compute? A lot of workloads can never reach the hundreds of GFlops because they are bandwidth limited.
I couldn't check it using Nsight Compute. It didn't find the kernel even though I ran it as root. A40 is supposed to be Ampere architecture, with GA102 chip so it should be supported. Maybe the toolkit I'm using is too old (CUDA 11.3).
Everything is on the device during the tight loop, and there is minimal transfer to host, so I don't think it's bandwidth limited in that sense. It could be bandwidth limited on the cache level but I couldn't tell. I wish I could get Compute running.
GPU programming is really a different way of programming, even though the code looks mostly familiar. And if you are used to single threaded, it will give you a massive headache thinking about, how to do everything in parallel, so that everything is not blocking everything.
The raw power is tempting, so much that I evaluate now how to do allmost everything on the GPU, but many things simply are not suitable to do there.
Basically, you want to avoid conditions and loops. Cannot do recursion. Debugging is a pain and non obvious things can make everything very slow, until you roughly understand, what is going on inside.
I found it was worse than that when I started playing with shaders, because my idea of parallelism came from threads, workers, and async functions eg doing several separate tasks at the same time. Parallel on a GPU is more like running lots of the same function each with different parameters at the same time eg running a function to calculate the color of a pixel using its x and y coordinates (and maybe some other uniforms) for every pixel on the screen.
I like to put it like this: a GPU is a really, really fast Map-Reduce hardware processor.
You give it a bunch of data with elements which are all independent of each other, apply the same transformations to to each element, and output a single data structure (a colour attachment or render target, or some compute buffer).
This explains a lot of the shortcomings and design decisions of GPUs. They prioritise throughput over latency; they have a lot of memory but much slower than the cores themselves (~500 – 700 cycle latency compared to ~20 – 40 cycle latency on the CPU); they run 'threads' in synchronised lock-step, called warps; branching on a GPU is particularly expensive—if one shader for one fragment needs to branch, then the entire warp that it's on will have to wait for it, or worse still, calculate that branch, too;
Their 3D graphics legacy still endures: despite the advent of GPGPU, they still have plenty of dedicated hardware for the graphics pipeline, including rasterisers, texture-mapping units, render output processors, etc.
Once people get this idea, then GPU programming is easier to reason about. One execution of a shader deals with one fragment (actually four, but at a high level of abstraction, this is sufficient).
Oddly enough, I did GPU parallelisation first, and then came to CPU parallelisation. I find CPU-level parallelism and concurrency problems like OS inter-process synchronisation, async-await, etc. much harder to reason about, because they generally cannot be reduced to such a simplistic 'one thread for one pixel'. It's also why I like embarrassingly parallel problems, because they're the most easily GPU-able.
true, for reductions you have algorithms like prefix scans, which produce a lot of output you're not necessarily interested in or algorithms which utilize fewer and fewer parts of the chips as the reduction progresses.
I remember how shock I was when the first time I leanred branching (arguably the most basic building block of programming) can severely affect GPU's performance.
*techinically it's even true for CPU in some cases...
> *techinically it's even true for CPU in some cases...
Practically in all cases. It isn't as bad to branch as it is in a GPU. But branch prediction in CPUs is an important factor for performance critical code, and getting it right (e.g. by switching the 'branch/no branch' conditions in assembler or using branch hints such as likely/unlikely in the linux kernel) can make a very noticable difference. I've seen a factor of 2 in some tight loops, and 10% should often be achievable.
And sometimes, by using bitmasks or multiplication by 1/0, one can design branchless code which can enable the use of e.g. more AVX instructions on CPUs, while also avoiding branch miss penalties.
Not really, WebGPU API is around the same level as CUDA or OpenCL.
In fact SYCL (which is used in this article) is slightly higher than WebGPU, because you don't have to manually allocate buffers. If you want something even higher you should look into frameworks like Numba (for CUDA) and Taichi (for Vulkan and WebGPU).
Easier, sure, but not higher level compared to CUDA or OpenCL. You can also (probably) use Taichi.js without installing anything. Which is a high level API.
"You can also (probably) use Taichi.js without installing anything"
Yes you can! (because of WebGPU)
And I never said WebGPU is high level. I said and meant it is simpler to get started with. At least it was quite simple for me. But WebGPU and wgsl by itself are surely not "simple".
It is a pretty different way of programming, and that's part of what makes it so fun. Within constraints, you get a really interactive way to design algorithms which are much more parallel than what is feasible to write for a CPU. Debugging is so much better these days with some support for debuggers and printf (at least on CUDA). Maybe the same facilities aren't available for WebGPU?
Conditions and loops are largely fine as long as you avoid warp divergence and such.
I still don't get the "no good for branching code" point... Since most of the work is split in millions of "threads" which all run in parallel, then why is branching an issue ? Some threads will take a bit longer than the others. Maybe groups of threads will go as slow as the slowest but still, prallelism should make up the bulk of the acceleration. No ?
Most GPU's only have so much compute cores. Even if you have a million threads, you might only have a few hundreds cores to execute them.
If you have heavy branching you might slow down the whole lane (which size can vary from 8 to 64 execution most of the time). Which at this scale still do make a big difference. Although for small branching, masking help avoid too much slowdown.
To expand further the 16k cores aren't real cores. What people would normally consider a core is what Nvidia calls a "streaming multiprocessor" (SM), of which the 4090 has 128. These cores each have 128 "cuda cores", analogous to a SIMD lane - although not quite since "cuda cores" are themselves SIMD.
To simplify: Each 128 SMs can run a different program and each of their 128 "cuda cores" can do ~single-cycle (small) matrix operations.
I'm not sure about the 4090, but most of the GPUs I use have a warp size of 32, and warp divergence affects only up to those 32 threads. If you have a branch and all threads agree, you only walk down one branch.
My mental model is a bit more like you have collections of warps in a block, and all warps in a block get scheduled onto an SM. Different GPU architectures allow for different numbers of warps to be simultaneously active or inactive, and each warp has its own instruction pointer and can be suspended while waiting for things like memory. I found the picture on pg 22 here really helpful: https://images.nvidia.com/aem-dam/en-zz/Solutions/data-cente...
Note that although there's 4 schedulers, on the A100, they don't dispatch every cycle iirc.
The tensor core accelerates mostly matrix operations and is the big block you can see has 4 per SM. Cuda core refers to the thread per SM, which you can see as FP32 or INT32 units, so there are (32*4) per SM on that diagram.
Like you said, tensor core is similar to a special purpose ALU and is at a lower level of abstraction than something with an instruction pointer.
The threads share control units. So if threads sharing the same control unit branch differently, they have to do both branches for all the threads (well, it depends on the GPU architecture). The threads will never finish before the others (again, if they are sharing the same control units). It works out for graphics and well engineered GGPU code because adjacent pixels and vertexes usually are similar enough to have a high chance of having the same branching behavior.
Most GPUs run threads in groups of 16 or more, with one instruction pointer shared by all of the threads in a single group.
So if some threads need to take an IF-branch, and some need to take an ELSE-branch, both paths are executed in sequence, with all threads in the group executing in lock-step, and a per-thread mask disabling the effects of the instructions that aren't needed for each specific thread.
If you do this enough times, with sufficiently complicated branching, you'll quickly negate any efficiency gain you get from the massive parallelism.
GPU threads aren't "threads" as you know them on a CPU. They aren't independent units of execution with their own control flow. Each instruction decoder in the GPU feeds a few hundred execution units, each addressing and fetch unit feeds a few hundred execution units. So if suddenly one of those hundreds of execution units takes a different branch, that control flow will have to be executed in sequence, before or after the control flows that didn't branch. This means that all the other execution units will be flushed, stay idle, and wait while the few instruction decoder and fetch units will process that one different branch. So a branch penalty won't be just a few cycles, as in a CPU, but a few thousand cycles times a few hundred execution units. Plus an additional memory fetch latency because GPU memory also isn't really designed for random access patterns.
Shameless plug for Futhark[0], which you can use to write your computational kernels. The idea is to use functional constructs like map and reduce to express parallel code and let the compiler handle the generation of low-level OpenCL or CUDA.
Disclaimer: I've recently finished a PhD focused on memory optimizations in Futhark.
I used Futhark in the past. It's probably been 5 years or more, so a lot may have changed since then.
It's absolutely a much lower barrier to entry, especially if you are familiar with functional programming. However, it also leaves a lot of performance on the table, and I found it to be hard or cumbersome to integrate with languages other than Python at the time.
And you're still stuck with CUDA (which is single vendor) or OpenCL (which is a pain to set up on most consumer systems, and has very lackluster driver quality for a lot of vendors). I would have liked that by now support for Vulkan compute or OpenGL compute shaders would have been added, but alas.
Regarding the performance, I'd be interested to hear more about your experiences. Because we compile to CUDA or OpenCL in the end, we cannot claim to be faster than what you could (in principle) write in hand. However, most of our benchmarks compare favorably with handwritten reference implementations, and the heavily optimizing compiler is able to write code that is tough to write by hand.
However, we're always looking for instances where we can do better. The goal is to be comparable to CUDA/OpenCL in as many cases as possible.
I'd love to tell you what it did suboptimally in my usecase at the time, but I no longer have the code and it's been so long I don't remember the specifics.
Like I said in my earlier comment, it was so long ago the performance remarks may be outdated and the project may have resolved them.
I would like to give Futhark another try, but I need easy and portable integration in either Go or Rust, and as far as I can tell, that's not the case today? For my current project, I ended up selecting webgpu for my GPU compute needs.
What's your stance on WebGPU - from my understanding it could be perfect thing for Futhark to target, as it would allow for truly portable GPU code both hardware and platform-wise.
We actually have a long-standing issue regarding WebGPU[0]. Long story short, we want to support it, and Athas did some exploratory work a couple of years ago and decided that WebGPU wasn't mature enough yet. We already have a WebAssembly backend, so as soon as it is possible to access WebGPU from WebAssembly it should be relatively straightforward.
I work on Futhark. We hope that WebGPU-through-Emscripten is viable, but I haven't yet had the spare cycles to make sure. I did find some examples that looked promising.
Do you know if there is any work being done to support a Metal backend for Futhark? That would be interesting for local prototyping on macOS. I've found a fork[1], but it doesn't seem to have been updated since February.
That’s a shame. I think since M1, macOS is very slowly starting to become a more popular platform for ML thanks to the unified memory. A mac is probably the cheapest and easiest way to get access to 64GB+ of memory available to a GPU on a local machine.
* Futhark does not expose a scheduling language that gives you precise control over code generation. This is probably the main selling point of Halide.
* Futhark has a much broader focus than Halide, which is mainly oriented towards image processing. Futhark wants to support arbitrary data parallel computation. E.g. see this compiler written in Futhark: https://github.com/Snektron/pareas
Compared to Sycl:
* Futhark is a non-embedded language that is more high level than Sycl. The goals are similar in the sense that both systems to try make (data) parallel programming more accessible. The vision behind Futhark is that the conventional functional programming vocabulary is actually a pretty good fit for parallelism, and that an aggressively optimising compiler can reduce or eliminate the overhead of abstraction. I don't think Sycl is as focused on high levels of abstraction, but rather focuses on being a relatively low-level portable programming interface.
GPU is one part where modern design of Julia truly shines as it allows seamless reusability and composability. I wish the language gets the proper recognition and adoption
I used ILGPU C# library, where I just wrote my kernel as a regular C# function, and the library executed it on the GPU in parallel. Don't need to know nothin' about blocks, warps and them other scary stuff. All thanks to C# excellent reflection support.
Learned that computation should be highly local (working on small isolated pieces of data) and without if's, otherwise won't get any performance benefits.
51 comments
[ 3.8 ms ] story [ 120 ms ] threadOnly when that does not already cover all your needs you have to find or develop other software for handling sparse matrices on GPUs.
Everything is on the device during the tight loop, and there is minimal transfer to host, so I don't think it's bandwidth limited in that sense. It could be bandwidth limited on the cache level but I couldn't tell. I wish I could get Compute running.
A more simple way to get into GPU programming, would be WebGPU.
I can recommend this tutorial as an introduction:
https://surma.dev/things/webgpu/
GPU programming is really a different way of programming, even though the code looks mostly familiar. And if you are used to single threaded, it will give you a massive headache thinking about, how to do everything in parallel, so that everything is not blocking everything.
The raw power is tempting, so much that I evaluate now how to do allmost everything on the GPU, but many things simply are not suitable to do there.
Basically, you want to avoid conditions and loops. Cannot do recursion. Debugging is a pain and non obvious things can make everything very slow, until you roughly understand, what is going on inside.
I found it was worse than that when I started playing with shaders, because my idea of parallelism came from threads, workers, and async functions eg doing several separate tasks at the same time. Parallel on a GPU is more like running lots of the same function each with different parameters at the same time eg running a function to calculate the color of a pixel using its x and y coordinates (and maybe some other uniforms) for every pixel on the screen.
You give it a bunch of data with elements which are all independent of each other, apply the same transformations to to each element, and output a single data structure (a colour attachment or render target, or some compute buffer).
This explains a lot of the shortcomings and design decisions of GPUs. They prioritise throughput over latency; they have a lot of memory but much slower than the cores themselves (~500 – 700 cycle latency compared to ~20 – 40 cycle latency on the CPU); they run 'threads' in synchronised lock-step, called warps; branching on a GPU is particularly expensive—if one shader for one fragment needs to branch, then the entire warp that it's on will have to wait for it, or worse still, calculate that branch, too;
Their 3D graphics legacy still endures: despite the advent of GPGPU, they still have plenty of dedicated hardware for the graphics pipeline, including rasterisers, texture-mapping units, render output processors, etc.
Once people get this idea, then GPU programming is easier to reason about. One execution of a shader deals with one fragment (actually four, but at a high level of abstraction, this is sufficient).
Oddly enough, I did GPU parallelisation first, and then came to CPU parallelisation. I find CPU-level parallelism and concurrency problems like OS inter-process synchronisation, async-await, etc. much harder to reason about, because they generally cannot be reduced to such a simplistic 'one thread for one pixel'. It's also why I like embarrassingly parallel problems, because they're the most easily GPU-able.
*techinically it's even true for CPU in some cases...
Practically in all cases. It isn't as bad to branch as it is in a GPU. But branch prediction in CPUs is an important factor for performance critical code, and getting it right (e.g. by switching the 'branch/no branch' conditions in assembler or using branch hints such as likely/unlikely in the linux kernel) can make a very noticable difference. I've seen a factor of 2 in some tight loops, and 10% should often be achievable.
And sometimes, by using bitmasks or multiplication by 1/0, one can design branchless code which can enable the use of e.g. more AVX instructions on CPUs, while also avoiding branch miss penalties.
https://google.github.io/tour-of-wgsl/
No need to setup, install or config anything. I think that is arguably easier as a quick start.
Otherwise yes, the whole tooling and everything else is not really that mature in WebGPU.
And thanks for Taichi. I did not know of that libary and it sounds interesting! (I will stay with WebGPU for now)
Yes you can! (because of WebGPU)
And I never said WebGPU is high level. I said and meant it is simpler to get started with. At least it was quite simple for me. But WebGPU and wgsl by itself are surely not "simple".
Conditions and loops are largely fine as long as you avoid warp divergence and such.
To simplify: Each 128 SMs can run a different program and each of their 128 "cuda cores" can do ~single-cycle (small) matrix operations.
My mental model is a bit more like you have collections of warps in a block, and all warps in a block get scheduled onto an SM. Different GPU architectures allow for different numbers of warps to be simultaneously active or inactive, and each warp has its own instruction pointer and can be suspended while waiting for things like memory. I found the picture on pg 22 here really helpful: https://images.nvidia.com/aem-dam/en-zz/Solutions/data-cente...
Note that although there's 4 schedulers, on the A100, they don't dispatch every cycle iirc.
Correct me if I'm wrong, but as far as I can tell tensor cores are just accelerators. They can't do general compute: no branch or jump.
Like you said, tensor core is similar to a special purpose ALU and is at a lower level of abstraction than something with an instruction pointer.
So if some threads need to take an IF-branch, and some need to take an ELSE-branch, both paths are executed in sequence, with all threads in the group executing in lock-step, and a per-thread mask disabling the effects of the instructions that aren't needed for each specific thread.
If you do this enough times, with sufficiently complicated branching, you'll quickly negate any efficiency gain you get from the massive parallelism.
Disclaimer: I've recently finished a PhD focused on memory optimizations in Futhark.
[0]: https://futhark-lang.org/
Edit: They do actually mention stuff like Julia and NumPy.
It's absolutely a much lower barrier to entry, especially if you are familiar with functional programming. However, it also leaves a lot of performance on the table, and I found it to be hard or cumbersome to integrate with languages other than Python at the time.
And you're still stuck with CUDA (which is single vendor) or OpenCL (which is a pain to set up on most consumer systems, and has very lackluster driver quality for a lot of vendors). I would have liked that by now support for Vulkan compute or OpenGL compute shaders would have been added, but alas.
Regarding the performance, I'd be interested to hear more about your experiences. Because we compile to CUDA or OpenCL in the end, we cannot claim to be faster than what you could (in principle) write in hand. However, most of our benchmarks compare favorably with handwritten reference implementations, and the heavily optimizing compiler is able to write code that is tough to write by hand.
However, we're always looking for instances where we can do better. The goal is to be comparable to CUDA/OpenCL in as many cases as possible.
Like I said in my earlier comment, it was so long ago the performance remarks may be outdated and the project may have resolved them.
I would like to give Futhark another try, but I need easy and portable integration in either Go or Rust, and as far as I can tell, that's not the case today? For my current project, I ended up selecting webgpu for my GPU compute needs.
[0]: https://github.com/diku-dk/futhark/issues/1403
[1]: https://github.com/MilesLitteral/futhark-metal
* Futhark does not expose a scheduling language that gives you precise control over code generation. This is probably the main selling point of Halide.
* Futhark has a much broader focus than Halide, which is mainly oriented towards image processing. Futhark wants to support arbitrary data parallel computation. E.g. see this compiler written in Futhark: https://github.com/Snektron/pareas
Compared to Sycl:
* Futhark is a non-embedded language that is more high level than Sycl. The goals are similar in the sense that both systems to try make (data) parallel programming more accessible. The vision behind Futhark is that the conventional functional programming vocabulary is actually a pretty good fit for parallelism, and that an aggressively optimising compiler can reduce or eliminate the overhead of abstraction. I don't think Sycl is as focused on high levels of abstraction, but rather focuses on being a relatively low-level portable programming interface.
Learned that computation should be highly local (working on small isolated pieces of data) and without if's, otherwise won't get any performance benefits.