When BitCoin mining first started making news, AMD GPUs had a decisive performance advantage over NVIDIA GPUs. CUDA was the more mature and easy-to-program toolchain, but BitCoin miners were willing to go the extra distance if it meant they could “print” their digital currency more quickly.

As it happens, the key instruction difference between AMD and NVIDIA GPUs was that AMD GPUs had a rotate instruction and NVIDIA GPUs did not.

Rotate, of course, is the family of instructions closely related to the shift instructions, where instead of shifting predefined values such as 0’s (for unsigned shifts) or sign bits (for signed or arithmetic shifts), the bits shifted out of one “end” of the number are shifted into the other. If shifting right, for example, the least significant bits are shifted into the most significant end of the word.

How did NVIDIA respond to this competitive pressure?

Did they leave AMD’s challenge unanswered?

No, of course not.

Did they add a rotate instruction?

Also no.

What NVIDIA added in their Kepler (SM 3.0) architecture was a set of funnel shift instructions: instructions that concatenate two (2) registers and shift them as a unit.

One application for funnel shift instructions is to implement memory copies where the source and destination pointers are misaligned with respect to one another. In classic RISC, architectures such as the Alpha would signal an exception if the program attempted a 32-bit read of an address that was not 32-bit aligned (least significant 2 bits set to zero). The modern equivalent to this anachronism: on x86, instructions such as MOVAPS will signal an exception if the effective address is not naturally aligned with respect to the operand size (32- and 64-byte for AVX2 and AVX512, respectively).

On such architectures, memory copies where the source and destination pointers both are aligned are trivial, and if both pointers are “relatively aligned” (misaligned in the same way), the misaligned portion of the copy can be dealt with by small amounts of prologue and epilogue code. But for memory copies where the source and destination pointer are not even relatively aligned, there’s no getting away from misaligned memory accesses of either the source or destination pointer – unless you happen to have a funnel shift in your arsenal. In that case, a memory copy can be formulated entirely in terms of aligned memory transactions, with the shifted operands dealt with in the innermost loop of the copy.

But another, more subtle application for funnel shift is that if the two input operands are the same register, it becomes a rotate.

So NVIDIA was able to close the ISA gap with AMD, not by emulating exactly what AMD had done, but by implementing something else that subsumed the target capability.

Enter LOP3.LUT

It turns out NVIDIA, home to some of the most capable CPU architects in the world, is pretty good at designing such machine instructions: expansive new capabilities in exchange for modest hardware cost. Such instructions work best when the compiler can use them without forcing developers to access them using intrinsic functions.

Another instruction set innovation, not unlike funnel shifts, that NVIDIA deployed in the Maxwell generation: the FPGA-like LOP3.LUT instruction. Like the age-old rasterops (ROPs) used to specify how BitBlt (bit block transfer) operations manipulate pixels, LOP3.LUT implements a general-purpose family of logic operations that can be defined by an 8-bit immediate operand. The usual suspect logic operations AND, OR, XOR, NOT, and variants thereof (e.g. NAND) all are implementable in terms of LOP3.LUT, but so are novel amalgams of other Boolean expressions.

Why is it called LOP3.LUT? Well.. remember when Boolean operations were first introduced to you, and you learned about truth tables? Consider for example the truth tables for A|B and A&B, shown here in code form to work around limitations of Substack:

  A    B    A|B  A&B
  0    0     0    0
  0    1     1    0
  1    0     1    0
  1    1     1    1

With 2 inputs that can have 2 possible values, there are four possible outputs.

Now consider the truth table for a 3-operand logic operation:

  A    B    C   Result
  0    0    0     ?
  0    0    1	  ?
  0    1    0	  ?
  0    1    1	  ?
  1    0    0	  ?
  1    0    1	  ?
  1    1    0	  ?
  1    1    1	  ?

With 3 bits’ input, there are 2³ or 8 bits’ worth of possible outputs, and this output may be specified as an 8-bit immediate to the instruction - filling in the rightmost column of the truth table above. As described here on StackOverflow, the immediate needed for any generalized Boolean function of 3 inputs can be computed by throwing three magical values (0xF0, 0xCC, and 0xAA), derived from the left-hand side of the truth tables, through said function.

So confident is NVIDIA that their compiler can exploit this instruction when developers write complicated logical expressions, that it’s not even available as an intrinsic. (It is, of course, available via inline PTX if necessary.)

Byte Permutes

The first generation of CUDA-capable hardware had some ISA properties that did not make it to the second generation. One such was the ability to address sub-registers: the top and bottom 16-bit halves of the 32-bit registers. For applications like image processing, where 16-bit pixel values often are more than adequate, this hardware capability enabled kernels to be built with a smaller register footprint. But such applications weren’t numerous enough to justify continued support for the hardware feature, especially in light that NVIDIA’s compiler at the time was having difficulty taking advantage of the feature. That prioritization is understandable given that NVIDIA was otherwise occupied, adding major architectural features like caches and critical instructions like fused multiply-add.

Later, as CUDA found application in broader and broader market segments, the need to access subregisters found its way back onto NVIDIA’s priority list. Instead of half-registers, which required opcode space to be allocated for any instructions designed to consume them, NVIDIA instead provided instructions to pick apart 32-bit registers and put them back together in 8-bit chunks: the so-called byte permute instructions, which take two (2) 32-bit registers and return a 32-bit mashup of the inputs, where the 8-bit lanes are selected from the two inputs based on an immediate.

Although available as intrinsics, NVIDIA’s compiler team has done a nice job of exploiting the byte permute instructions when possible. Whenever you write code that OR’s, shifts, and/or masks in 8-bit increments, you’re likely to find some combination of byte permutes (or funnel shifts, or LOP3.LUT!) in the instruction mix.