The CUDA Handbook ▸ Chapter 8. Streaming Multiprocessors

8.2 Integer Support

The SMs have the full complement of 32-bit integer operations:

• Addition w/optional negation of an operand for subtraction,

• Multiplication and multiply-add,

• Integer division,

• Logical operations,

• Condition code manipulation,

• Conversion to/from floating point, and

• Miscellaneous operations (e.g. SIMD instructions for narrow integers, population count, find first zero).

CUDA exposes most of this functionality through standard C operators. Nonstandard operations, such as 24-bit multiplication, are exposed through inline PTX assembly or intrinsic functions.

8.2.1 Addition, Subtraction, and Addressing

CUDA GPUs are 32-bit machines. The register file is a bank of 32-bit registers, and the core integer and floating-point instructions take 32-bit operands. A virtue of this design is that the registers are fungible: since Fermi made CUDA hardware a load/store architecture, a given register can hold an address, a signed or unsigned integer, or a floating-point value with equal facility, and the same execution units serve them all. Values wider than 32 bits – double, 64-bit integers, and 64-bit addresses – occupy even-numbered register pairs.

Addition and subtraction are the simplest integer operations. The SASS IADD instruction adds two 32-bit registers, and subtraction is the same operation with one operand negated (as noted in the list above). Maxwell added IADD3, a three-input add that folds a common addressing pattern – a base plus two offsets – into a single instruction. Arithmetic wider than 32 bits is synthesized from 32-bit pieces: a 64-bit add becomes a 32-bit add of the low halves that produces a carry, followed by an add-with-carry of the high halves. (In PTX these are add.cc and addc; the hardware propagates the carry flag between them.)

The tension between a 32-bit machine and a 64-bit address space is most visible when examining the machine code for addressing. Beginning with Fermi, the global address space is 64 bits wide, but the hardware that computes addresses is 32-bit, so every pointer occupies a register pair and every nontrivial address calculation must form the low and high halves separately – frequently several instructions where a CPU would emit one.

8.2.2 Multiplication

Every CUDA-capable GPU has a native 32-bit integer multiplier and an integer multiply-add.

Integer multiplication does not always run at the same throughput as the other integer operations – on several architectures 32-bit multiply issues at a lower rate than 32-bit add – so multiply-heavy integer code can reward profiling, though it needs no special handling in source: the * operator yields the low 32 bits of the product, and the compiler selects the appropriate instruction. Two intrinsics return parts of a product that a plain multiply cannot express: __[u]mulhi() returns the most significant 32 bits of a 32×32-bit product, and __[u]mul64hi() returns the most significant 64 bits of a 64×64-bit product – both useful for fixed-point arithmetic and for building wider multiplies. Table 8-4 summarizes the multiplication intrinsics.

Table 8-4. Multiplication intrinsics

8.2.3 Bit Manipulation

The CUDA compiler implements a number of intrinsics for bit manipulation, as summarized in Table 8-5; on later architectures, many of these intrinsics map to single instructions. When in doubt, disassemble and look at the microcode!

64-bit variants have ‘ll’ (two ells for “long long”) appended to the intrinsic name: __clzll(), __ffsll(), __popcll(), __brevll().

Table 8-5. Bit Manipulation Intrinsics

bfind returns the index of the most significant set bit—the counterpart to __ffs, which returns the least—and has no dedicated intrinsic: it is reached through inline PTX, or computed as 31 - __clz(x) for a nonzero 32-bit input, with a .shiftamt form that returns the left shift needed to normalize the value rather than the raw bit position. __fns is most useful inside a warp: given the ballot mask of participating lanes, it maps a rank produced by a prefix sum back to its lane, the operation at the heart of stream compaction.

8.2.4 Funnel Shift (SM 3.5)

GK110 added a 64-bit "funnel shift" instruction that concatenates two 32-bit values together (the least significant and most significant halves are specified as separate 32-bit inputs, but the hardware operates on an aligned register pair), shifts the resulting 64-bit value left or right, then returns the most significant (for left shift) or least significant (for right shift) 32 bits.

Funnel shift may be accessed with the intrinsics given in Table 8-6. These intrinsics are implemented as inline device functions (using inline PTX assembler) in sm_35_intrinsics.h. By default, the least significant 5 bits of the shift count are masked off; the _lc and _rc intrinsics clamp the shift value to the range 0..32.

Applications for funnel shift include the following:

• Multi-word shift operations.

• Memory copies between misaligned buffers using aligned loads and stores.

• Rotate.

To right-shift data sizes greater than 64 bits, use repeated __funnelshift_r() calls, operating from the least-significant to the most-significant word. The most-significant word of the result is computed using operator>>, which shifts in zero or sign bits as appropriate for the integer type.

To left-shift data sizes greater than 64 bits, use repeated __funnelshift_l() calls, operating from the most-significant to the least-significant word. The least-significant word of the result is computed using operator<<.

Table 8-6. Funnel Shift Intrinsics

8.2.5 Logic Operations

The bitwise operators &, |, ^, and ~ map to the SASS LOP instruction on early hardware. Beginning with Maxwell (SM 5.0), the hardware also provides LOP3, a three-input logic instruction that computes an arbitrary Boolean function of three operands in a single instruction – effectively a tiny lookup table, much like a lookup table (LUT) in an FPGA. The compiler emits it automatically to collapse chains of &/|/^/~ into one operation, so a kernel need never spell it out; but it turns up constantly in disassembly, and reading it requires understanding how the function is encoded.

The function is selected by an 8-bit immediate, immLut. This byte is the truth table: LOP3 computes, for inputs A, B, and C, a result whose value for each of the eight possible input combinations is the corresponding bit of immLut.

The trick to computing immLut for a desired function F(A, B, C) is to evaluate the function itself as a bitwise operation, substituting three specific constants for the inputs⁹:

A = 0xF0
B = 0xCC
C = 0xAA

For example, to compute F = (A | B) & ~C, evaluate the same expression over those constants:

immLut = (0xF0 | 0xCC) & (~0xAA);   // == 0x54

and pass the result as the immediate to the instruction, which in inline PTX reads:

asm( "lop3.b32 %0, %1, %2, %3, 0x54;"
     : "=r"(d) : "r"(a), "r"(b), "r"(c) );

The constants work because their bits, read as columns, enumerate all eight combinations of the three inputs:

A = 0xF0 = 1 1 1 1 0 0 0 0
B = 0xCC = 1 1 0 0 1 1 0 0
C = 0xAA = 1 0 1 0 1 0 1 0

Each bit position is one row of the truth table – reading the columns from the most significant bit, (A, B, C) runs 111, 110, 101, …, 000 – and evaluating the desired expression bitwise across all eight positions at once yields exactly the byte whose bits are F for each row.

The same picture, run in reverse, lets you infer the function from a given immLut: write the byte in binary and read off which input combinations produce a 1. The value 0x54 above is 01010100; the 1 bits sit at positions 6, 4, and 2, which the constants above identify as (A, B, C) = (1,1,0), (1,0,0), and (0,1,0) – precisely the cases where (A | B) is true and C is false.

8.2.6 Integer Dot Products

Pascal (SM 6.1) added two fused integer dot-product-and-accumulate instructions – SASS IDP – aimed squarely at the 8-bit inner loops of quantized deep-learning inference. They predate the Tensor Cores and coexist with them: where a Tensor Core multiplies whole matrices, these operate on a single 32-bit register’s worth of packed bytes, which suits code that is not shaped like a matrix multiply.

__dp4a(a, b, c) treats its two 32-bit inputs as four packed 8-bit integers each, forms the four products, sums them, and adds the 32-bit accumulator c – a four-element 8-bit dot product with 32-bit accumulation in one instruction:

int      __dp4a(int a,      int b,      int c);       // signed
unsigned __dp4a(unsigned a, unsigned b, unsigned c);  // unsigned

__dp2a(a, b, c) is the two-element mixed-width variant: two packed 16-bit values in a against two packed 8-bit values drawn from the low or high half of b, accumulated into c. The half is selected by the intrinsic name – __dp2a_lo() takes the low two bytes of b, __dp2a_hi() the high two – and both come in signed and unsigned forms.

These are close cousins of the SIMD video instructions of Section 8.6.4: all pack narrow integers into 32-bit registers and process every lane at once. What the dot-product instructions add is the reduction and the accumulate, fused into the same instruction. They are single instructions on SM 6.1 and later; on older architectures, the intrinsics still compile, but expand to multi-instruction sequences.

DP4A collapses four multiply-adds into one instruction, but that only helps a kernel whose bottleneck is instruction throughput in the first place. The normalized cross-correlation kernel of Chapter 15 is a cautionary example: dropping DP4A into its byte-reduction inner loop yields no speedup at all, because the kernel is memory-latency-bound at full occupancy and the cheaper arithmetic merely hides in the latency shadow. Only after each thread is given more independent work—two output columns with separate accumulator chains—does the kernel become arithmetic-bound and DP4A contribute roughly a further 2.5× on top of the 2.4× from the added parallelism (Section 15.5). The lesson generalizes: an instruction that lowers arithmetic cost speeds up a kernel in proportion to how arithmetic-bound the code already is, so profiling to find the real limiter comes first.

8.2.7 Dynamic-Programming Instructions (DPX)

Hopper (SM 9.0) introduced the DPX family for dynamic-programming algorithms – Smith-Waterman and Needleman-Wunsch (sequence alignment), Floyd-Warshall (all-pairs shortest paths), and similar recurrences whose inner loops are dominated by chains of min/max and add-then-min/max. Each such chain, several instructions on earlier hardware, collapses to one. The intrinsics come in three shapes:

• Three-input min/max: __vimax3_s32(a, b, c) returns max(a, b, c); __vimin3_s32() the minimum. These fold the two-comparison reduction of three candidate scores into a single instruction.

• Fused add-then-min/max: __viaddmax_s32(a, b, c) returns max(a + b, c), and __viaddmin_s32(a, b, c) returns min(a + b, c). Floyd-Warshall’s relaxation step – “is the path through k shorter?” – is exactly an add followed by a min.

• Min/max with a selection flag: __vibmax_s32(a, b, &pred) returns max(a, b) and sets the boolean pred to indicate which operand was chosen – the traceback bookkeeping that alignment algorithms must keep as they fill the score matrix.

Each is available in signed (_s32), unsigned (_u32), and packed-halfword (_s16x2/_u16x2) forms, the last operating on two 16-bit values at once. A _relu suffix additionally clamps the result at zero, folding the non-negativity step of local alignment into the same instruction: __vimax3_s16x2_relu(a, b, c) computes a per-halfword max(max(a, b, c), 0).

On Hopper and later, these map to single SASS instructions (VIMNMX, and VIADD/VIMNMX fused forms); the intrinsics are portable and compile for earlier architectures as well, but only Hopper and its successors execute them at full DPX rate, where NVIDIA reports roughly a 7x Smith-Waterman speedup over the previous-generation A100.