Binary Field NVIDIA Instructions

Transcript

So, obviously the goal is to support fast binary arithmetic and on CPU you have lots of really great native instructions. So, the CL mole extension gets you 64-bit careless multiply right there. If you're working in AES field, you can use GNFI to get even nicer like AES focused instructions. Um, but on GPUs up until recently, you don't have a lot of you don't have a lot of great options. So, if you want to do a a careless multiply, you can emulate the multiplication circuit in some way. So, you can kind of directly compute it uh with ALU operations.

We have this instruction uh this PTX instruction called lop3, which is actually very cool instruction. Um, you can encode essentially arbitrary two-input one-output uh logic gates. Kind of any gate you want. Uh for 32-bit inputs and it'll just take a cycle. Um, if you try to use that directly to do careless multiplication, you're going to get really high overhead from all the bit shifting you have to do cuz you want a bit in the middle of the value, you're going to have to do a bunch of shifts and it it tends to be very very expensive compared to just having like PCL moldy Q QDQ or something.

The alternative is to process bit slice batches. So, you take, you know, all the zero bits from a batch of values and run those uh bit sliced inputs through an arithmetic circuit that emulates the multiplication you want. And this is great um but you know, it is a lot of instructions uh in the circuit and also has pretty high register pressure. And what that uh ends up doing is because you have to keep all the intermediates around. What that ends up doing is uh really directly impacting your occupancy on the GPU because you only have so many registers to allocate. And it lowers the number of warps that you can run uh at a time, which means that the GPU is not very fully utilized and is less efficient.

And so, in May uh in CUDA 13.3, we exposed a PTX instruction that is new that is called CL mad. And basically it's almost the same as PCL mole QDQ. And you get to multiply two 64-bit inputs and XOR with an accumulator. And so you can all use it now. You I've seen a lot of code that already uses it and your AI agent can use it even more efficiently. But in this talk I want to talk about some use cases that we prototyped to kind of show off the instruction and also talk about some deeper dive implications on using the instruction.

So yeah, I already talked about I mean you're you're all familiar with careless multiplication. It's basically polynomial multiplication and we have the added input you can have an accumulator polynomial that you're accumulating into. And if you look at kind of the breakdown of like okay, you you put in two 64-bit inputs, you get in a 128-bit input out. The instruction is going to give you be able to give you the high result or the low result. So you either get the lower 64 bits or the upper 64 bits.

If you have a smaller polynomial, say you're doing something in like GF2 to the 32 or smaller, you might really only need one CL mad instruction because everything is just going to fit in the lower 64 bits. In contrast to the nice AS instructions, you don't get a free reduce. So that's something that we have to deal with. But you may not you may not want to commit to one area reducible anyway. It's really easy to use the instruction. So this is the inline PTX for doing a 64 by 64 carryless multiplication with you know both halves.

You can just write it like any other inline assembly where you have a low and a high variant for CL mad. And you can just you just or the inputs together. You get a 128-bit U and 128T out. So the thing that I will foreshadow here is this .U64. That's going to become important in a in a little bit. There is hardware support for this instruction on Ampere and newer GPUs, so anything that uses the SM 80 or or newer has hardware support, and this means that there is silicon in the GPUs already that is a careless multiplier.

So, it's not emulated, there's no like microcode or something. It's just it's using an actual hardware unit that is in it. And um in a sense uh y'all got pretty lucky, I would say, because um it takes a a few years to put something into a GPU, and this has already been in the architecture just not exposed for quite a few years already. So, it's uh it's actually a really nice kind of confluence of events that we're able to just like flip a switch, basically, and turn on something that would be useful. Uh the big take the big uh drawback of CL MAD is that the throughput varies by GPU. So, uh for most of the rest of the talk, I want to give you a sense for what that means and the implications for

it and and how to how to think about it intuitively. Um but before we do that, a couple use cases, um CL MAD is, as you may know, is is really great for accelerating GHash um because it's a bunch of GF(2^128) operations. And using CL MAD, we're able to approach the DRAM bandwidth on both uh uh consumer grade card like the 590 and a a data center card like the V200, um reaching up to yeah, like 6 TBps. And this really reduces the uh cost of doing on-GPU authenticated encryption to the point where GHash really isn't the bottleneck

anymore. The bottleneck is typically how fast you can do actual AES rather than uh GCM or GHash. Um yeah, if you want to do uh uh uh feel operations like G hash, um we've just done a Karatsuba decomposition, so you can use the same instruction. It just takes six of them to do a 128-bit careless multiply, and you just combine the results with some XORs. The performance of CL mad is going to determine, once we get our 256 bits of like unreduced output, what we actually do for the reduction.

So, there are a couple choices for reduction. Um the one I didn't put on the slide is not doing it. So, if you have the register space, and you can just defer reduction, that might be better. But, there are kind of two ways I looked at for doing reduction. Um the one that I was excited about uh was Barrett's Barrett's reduction because you can replace a polynomial division with a bunch of careless multiplications, and we have an instruction to do that, and it only takes like five more. Uh so, I was excited about that um compared to the uh you can reduce with shift and XOR. Um which uh requires like about 30 logic instructions.

And the reality is is that the Barrett's reduction is actually way worse than the shift and XOR reduction, and I'll try to explain a little bit why. So, the the underlying reason that CL mad's throughput varies based on the GPU is that it shares a 64-bit data pipe with all of the FP64 computations. So, if you think about a GPU kernel, you're issuing a bunch of instructions. All of your like lop three, shift, add, multiply, all of that is going to the 32-bit like logic data pipe, and we have a ton of uh hardware resources for that, and it's very fast.

But, every time you uh call a CL mad instruction, it goes to the 64-bit data pipe. And the capacity of your you know, of the hardware to do a 64-bit arithmetic is what determines your performance for CL mad. So, the intuition which I alluded to earlier is that data center cards like the B200 will have more FP64 capacity than consumer cards. Um, you can kind of think about it like, you know, data center cards might have more HPC applications that could use higher higher precision floating point and gaming cards don't really do those sort of workloads. So, um, this is a little rough because I know most of you use like 5090s

basically like consumer cards. Um, you still do get a good speed up but it's not as good as if you used a data center card. And uh, if you you look at a 5090 you can see that because if we hammer the 64-bit data type over and over again not only with the carryless multiplies to do the the field multiplication but also to do the reduction, we end up bottlenecking ourselves and and cutting our performance in half. So, it uh, it behooves the workload to uh, try to present a relatively balanced mix of CL mad and logic operations.

Um, so that when you uh, dispatch instructions you can use both pipelines at the same time. Um, uh, sum check was something that we we uh, looked at as a really nice example of what you can do with this instruction uh, mostly because it has a ton of field multiplications in it both in interpolating and composing polynomials. So, we focus on like a composition sum check that doesn't have any crazy optimizations, no univariate skip, and nothing like that. Just just 128-bit field elements. Um, but both in the interpolation and composition and in your folding during the challenge section, you have a ton of CL mad a ton of field multiplications.

And so, uh, compared to like a bit slice circuit on a 5090, as your input size increases you can get I mean, it's pretty stable between 3 1/2 and 4x performance. On a B200, you can do up to 13x faster on some check. And this is this kind of shows the the difference in what the cards are capable of because when you have less 64-bit resources, you end up kind of getting capped anyway by just your ability to to issue CL mad instructions. Um okay, so for the last kind of section, I want to to go a little bit further than that, which is if we know that CL mad uses one data pipe and we

have a lot of logic operations use another data pipe, can we overlap a lot of the proving to kind of uh improve our our overall proving performance. It's and the tool that we're going to use for this is called warp specialization. So, you have a uh uh in a GPU thread block has a lot of different threads and they're they're partitioned into 32 uh a thread warps. Each warp is running at the same time, so they all run the same instruction and are kind of predicated if there's any branching.

Uh and the benefit is that between warps, you have shared memory, very fast bandwidth memory to communicate between warps. So, the idea with warp specialization is to have a bunch of consumer warps that are reading data buffers out of shared memory and computing something and then freeing that that buffer. And at the same time that that consumer warp is doing something, you have a producer warps that are doing some other computation writing into shared memory. And uh this type of optimization is really best suited when there's a repeated kind of repeated stages that are happening one after another where it would be very useful to have very high bandwidth memory movement between the

two of them. Um and the benefit for us is that if we can get the consumer warps to do logic and the producer warps to do SEAL mad, then when we are kind of waiting for SEAL mad to happen, we can have the consumer warps kind of get in there and do some logic and then they can overlap a lot better. So, really good example of where you might use this is in the great dough, which where you have this continuous cycle of we're going to do an NTT to encode something, then we're going to which involves a lot of binary uh or or careless multiplication, then we're going to do a lot of hashing to Merklize something, then we're going to do a lot of uh more

um a lot more careless multiplication in the sum check and then we're just going to keep going around. So, you can try to apply this idea in both cases. Um to get a pipeline where you have some warps encoding things using NTT, some warps doing the hashing, and you try to overlap them as as much as possible. And this helps, although it's not as it's not as satisfying as a hardware-based uh optimization because you don't get that like 4 to to 15x improvement, but um in uh our uh experiments, we were able to basically cut down the the uh end-to-end commitment time by about 15%. And this is off of a relatively well-optimized

baseline where we've fused a bunch of kernels together to to kind of get rid of kernel launch latency and memory transfer. And so, the fusion and and the warp specialization that we can get from uh just using SEAL mad gets you an extra 15% on top. And uh you may be wondering, why is it not more? Because clearly we're not overlapping just 15% of the computation. And um this is something I'll I'll just point out uh as something to think about, which is that the more work you give the GPU, the more power constrained it becomes, and so it lowers the operating frequency to manage thermals.

And so, you get this weird thing where you get a little bit of benefit and then if you stress it too much it'll just cut the operating frequency down and then you'll lose optimization. So it's a very tricky process but you can get definitely a noticeable boost out of this kind of optimization. Okay. So yeah, having native binary arithmetic in GPUs helps us in two ways. First, anywhere you use a field multiplication we can help improve that performance. And two, if you kind of consider the varying hardware resources you can adapt your execution pipeline to better overlap and and use kind of different resources at the right times.

Now before I take any questions I will plug this some fine folks on the product side who are working on a QPQC library which will basically have an expanding collection of GPU accelerated crypto math libraries. So right now they have a lot of hashing so I think SHA-2, 3, and Shake and Merkle trees. They have some NTT libraries and some big integer stuff and there's more coming down the pipeline in that library. So if you want some you know, some NVIDIA supported software kind of underlying improving stacks I think this would be totally the place to go and I'm happy to put you in touch with those guys.

Um but yeah, other than that happy to take some questions. >> Hi, thank you for the talk. Um I have two questions. One, you mentioned tiles so are you using cute layout algebra to try to do tiles? >> Oh, um >> And the other question is you mentioned producer consumers so I think NVIDIA has programmable dependent launches and work stealing but work stealing only works at the CTA levels and here you want to do warp level. So, how do you do that?

>> Sorry. Um so, the first question is it I just wrote tile here. It doesn't really mean anything. So, I'm not using like cute or or anything. It's just um And sorry, the second question is how you do >> Uh So, you have producer and consumer warps. And work stealing in uh CUDA works at CTA level. Uh and you want it to do warp level specialization. So, how would you do this? >> Yeah, okay. So, how you do this is actually it's much more gross, but also much easier to implement, which is you have um you you each of your warps are running the same kernel, but based on their identifier, you are telling it to do something

different. And it's using memory synchronization like instructions to >> Okay, so atomics. And you pull on the atomics until it's ready. >> Exactly. Exactly. Yeah. Mhm. >> It's not a technical question, but something that is still really interesting to me. How does Nvidia allocate resources to cryptography with everything else that's going on? >> Uh great question. I mean, the the answer is uh they're they can't allocate that that many resources. Um so, but that's why we have that's why we have a research division is to look into kind of cutting-edge uh cryptography.

And I would this kind of goes back to some of the discussion earlier, but the reason we have support for this instruction uh yes, this instruction, SEAL mad is a combination of different reasons. So, it is useful for for uh proving. It's also useful for normal encryption. It's also useful for like error correcting codes. And so, we So, like all the NTTs we're doing to to do uh error error correction, uh you know, we might do that for something completely different. So, um, yeah. So, there's you need to find that intersection of like where there are enough, uh, there are enough users who might need it

in different areas of the company. It It helps a lot in terms of, uh, deciding like what to support. Yeah. >> Um, do you have any intention of cuz SEAL might, you know, sort of just through luck happen to already be supported. Do you have any intention of adding something even more specialized for like cryptographic, um, workloads, you know, in a few years from now or something? >> Yeah. Yeah. I mean, uh, yeah, if it's useful, if it's broadly useful enough, then yes. Um, but it this was this is kind of a special situation cuz we can just be like, you can just use it now and all of the GPUs you bought in the last 6 years have it.

Um, the next like new capabilities might take a couple of years. It's a It's a combination of are there enough people who might use exactly the same thing from, you know, across across the industry, across different industries, and are how sure can we be that it will provide a significant impact in like 2 years? >> How do you measure that? Like it's not just a vibe check of >> It's not a vibe check, but but yeah, it's like, uh, you know, it's it's, um, it's the same thing as like writing a position paper and trying to trying to motivate why you should do something.

Yeah. >> Okay. >> Yeah, there there's no like, uh, there's no statistical analysis we can do about it, unfortunately. Yeah. That would make things a lot easier. >> Great, thanks. >> How often does it happen that new instructions get added to CUDA? >> I think it's it's all the time. So, in 13.3, there's this wasn't the only instruction added. Um, and it yeah, the process is just it depends on who needs it and and what it's needed for. Yeah. >> Great. Any more questions? >> I'm I'm wondering if if these are on your hardware already, what's stopping you

from just using them before they're released? >> So, there's Yeah, that that's a good question. Um, I guess internally we could use them before they're released if we want to, but it's not really the way that in video works because we want to support we're not running our own workloads most of the time, other people are running workloads. So, it it's a question of you know, if we release CLM, someone has to make sure that that goes into every new architecture and that every version of the CUDA compiler has support for it and all old CUDA programs will run on new hardware if they have that instruction on them. So, it's it's less of uh it's less of that there's no like

there's no like hiding instructions. It's more about what is a reasonable uh maintenance load, basically. Also, don't quote me on that. I I don't really do that part of the the the stack, but that's what I would figure. Yeah. My my non-expert opinion. Yeah. >> Great. With that, thank you so much, Jean-Luc. >> Thanks. >> [applause]