# CS 211 - Lecture 16 ## Computer Architecture ### Efficient Memory Usage Bernhard Firner 2026-03-25 --- ## What is Memory? * We've talked about different types * Program, stack, register, etc * What are these things? * Physical things! --- ## Athlon XP <img style="width: 80%" class="r-stretch" src="figures/AMD_Athlon_XP_Barton_die_by_Birdman86.JPG" /> <br/> <small> Photo by https://commons.wikimedia.org/w/index.php?title=Special:ListFiles&user=Birdman86 </small> --- ## Register Memory * Register memory is per-core, close to the ALUs, but small * This is why it is fast, but also limited * This pattern is replicated over each core, with a tiered memory system feeding data into the cores * L1 is nearest, then L2, then L3, then the very distant RAM or hard disks --- ## AMD Epyc * See the [AMD white paper](https://www.amd.com/content/dam/amd/en/documents/products/epyc/4th-gen-epyc-processor-architecture-white-paper.pdf) * This is what is in some of the iLab machines * L1 is within each core, then L2 and L3 are increasingly distant <div class="col"> <!--<img style="width: 80%" class="r-stretch" src="./figures/AMDEpyc_Core.png" />--> <img style="width: 70%" class="r-stretch" src="./figures/AMDEpyc_Zen4Layout.png" /> </div> --- ## Memory Bottlenecks * Cached memory holds a copy that is fetched when needed and discarded later * It does not hold "everything" needed by a program * A `mov` operation may check the L1 cache and be disappointed * If the cache does not have that address stored, it needs to fetch it from somewhere else * For many workflows, the bottleneck is not processing speed but memory bandwidth and latency --- ## GPUs Vs CPUs * You may wonder how GPUs get so much done if bandwidth and latency are such concerns * GPU (graphical processing units) specialize in doing many operations in parallel * Originally for graphics, more recently for machine learning * Why are they different from CPUs? * And how do they process so much data if the CPU is bandwidth limited? --- ## Early Bandwidth Differences * (before deep learning) * GPUs would take in a relatively small amount of data * mesh information for objects, lighting settings * And would do a lot of internal processing before outputting a result * The pixels to render to the screen --- ## Latency * GPUs have their own output ports supporting large amounts of data going directly to screens * This obviously reduces latency, and allows them to synchronize to an exact framerate * But GPUs weren't cheating latency; they could just do more processing with less input than a CPU * Branching less important for matrix multiplies in the render pipeline, no uncertainty about what to load next --- ## Expanding CPU capabilities * The focus on bandwdith means that CPUs can't compute in the GPU market any time soon * Not true for many other coprocessors * For sound, encryption, etc * Those external chips are still available, but are only used with underpowered microcontrollers * e.g. your talking toaster may use a sound coprocessor --- ## Usurped Capabilities <style> .container { display: flex; } .col {flex: 1;} </style> <div class="container"> <div class="col"> * The CPU has usurped functionality over time * Encryption in your phone CPU, for example </div> <div class="col"> <img style="width: 80%" class="r-stretch" src="./figures/ArmCortexA510-pipeline.png" /> </div> </div> --- ## Future Constraints? * So if the CPU has done more and more, will registers go away in the future? * Could we simply work in memory directly? * Probably not; one is optimized for speed, the other for density * Adding a section to the chip die to handle encryption is okay * The long delay sending it data and getting it back is a small price to pay for the hardware encryption --- ## 2D Space * Add more registers and some of them will get farther away * This means more, and longer, wires to transmit data * Those wires eat more space and take more time * Since clock cycles can only be as fast as the slowest part, eventually you'll slow down the clock rate * GPUs have much more parallelism because they are optimized for different work --- ## Locality * Because of that, the locality of memory will (likely) continue to be a concern * Learning to write memory aware code is the best way to speed up large programs * But we will also need to understand what the code is doing to optimize it * And often that means looking at the assembly --- ## Let's Talk Debugging * So let's briefly talk about a different topic: debugging * We've already used gdb to look at programs * Did you know that you can use it with assembly too? --- ## Loading Assembly Files * Build an assembly file with `gcc -S <filename.c>` * That builds an assembly file named `<filename.s>` * Now compile with the -g flag: * `gcc -g <filename.s>` * Running gdb on that file will allow you to debug in assembly --- ## Example Program ```C #include <stdio.h> #include <stdlib.h> void addSum(long long* buf, int max) { long long sum = 0; for (int i = 1; i < max; ++i) { sum += i; } *buf += sum; } int main(int argc, char** argv) { if (argc < 2) { printf("This program requires a positive number as its second argument.\n"); return 0; } long long buffer = 0; int sum_to = atoi(argv[1]); addSum(&buffer, sum_to); printf("%lli\n", buffer); } ``` --- ## Breakpoints in ASM * You can use line numbers * Or you can set breakpoints by tags * `(gdb) break add_sum.S:addSum` --- ## Looking at Functions * `disassemble <func>` will spit out the assembly for that function * Even gives an indication of the current line <pre> Dump of assembler code for function addSum: 0x0000555555555230 <+0>: endbr64 0x0000555555555234 <+4>: push %r12 => 0x0000555555555236 <+6>: mov %rdi,%r8 0x0000555555555239 <+9>: mov %esi,%r12d 0x000055555555523c <+12>: push %rbp 0x000055555555523d <+13>: lea -0x7(%rsi),%ebp </pre> --- ## Registers * `info registers` ```asm (gdb) info registers rax 0xa 10 rbx 0x7fffffffdde8 140737488346600 rcx 0x7fffffffe1c2 140737488347586 rdx 0x0 0 rsi 0xa 10 rdi 0x7fffffffdcb0 140737488346288 rbp 0x7fffffffdd60 0x7fffffffdd60 rsp 0x7fffffffdca0 0x7fffffffdca0 r8 0x1999999999999999 1844674407370955161 r9 0x0 0 r10 0x7ffff7db1fc0 140737351720896 r11 0x7ffff7db28c0 140737351723200 r12 0x2 2 r13 0x0 0 r14 0x555555557da8 93824992247208 r15 0x7ffff7ffd000 140737354125312 rip 0x555555555236 0x555555555236 <addSum+6> eflags 0x206 [ PF IF ] cs 0x33 51 ss 0x2b 43 ds 0x0 0 es 0x0 0 fs 0x0 0 gs 0x0 0 k0 0x80000000 2147483648 k1 0x8040 32832 k2 0x0 0 k3 0x0 0 k4 0x0 0 k5 0x0 0 k6 0x0 0 k7 0x0 0 fs_base 0x7ffff7fa6740 140737353770816 gs_base 0x0 0 ``` --- ## Print Format * We can query individual registers with print * Use `/d`, `/x`, etc to specify format * d for decimal, x for hex, t for binary, c for char, f for float ```asm (gdb) print/d $rax $1 = 10 (gdb) print/x $rax $2 = 0xa (gdb) print/t $rax $3 = 1010 (gdb) print/c $rax $5 = 10 '\n' ``` --- ## Printing Memory * You can also inspect memory in the program using the `x` (examine) command * `x/<format><length> <location>` * `x/12c $42` to print twelve characters at $42, for example * Type `help x` in gdb for more documentation --- ## Watching a Variable * Let's say you want to keep an eye on rbp: * `display $rbp` * We can even watch the current instruction pointer: * `display $rip` * Now their status will update with every step --- ## Changing a Register * What if we want to change something? ```asm (gdb) set $rax=9 (gdb) print/x $rax $6 = 0x9 ``` --- ## Examining the Stack * When debugging assembly we can also check where things are in memory * `print $rbp - (void*)&total_cpu` * If we see some instructions that we don't understand, this can help * Take a look at how registers changed after the instruction --- ## Checking flags * Printing out the status register gives more information * We can see how a branch will go ```asm (gdb) break *main+4 Breakpoint 1 at 0x10c4: file add_sum.S, line 118. (gdb) run Starting program: examples/add_sum_asm [Thread debugging using libthread_db enabled] Using host libthread_db library "/lib/x86_64-linux-gnu/libthread_db.so.1". Breakpoint 1, main () at add_sum.S:118 118 in add_sum.S (gdb) display/i $rip 1: x/i $rip => 0x5555555550c4 <main+4>: sub $0x18,%rsp (gdb) step 120 in add_sum.S 1: x/i $rip => 0x5555555550c8 <main+8>: mov %fs:0x28,%rax (gdb) print $eflags $2 = [ IF ] (gdb) step 121 in add_sum.S 1: x/i $rip => 0x5555555550d1 <main+17>: mov %rax,0x8(%rsp) (gdb) step 122 in add_sum.S 1: x/i $rip => 0x5555555550d6 <main+22>: xor %eax,%eax (gdb) step 123 in add_sum.S 1: x/i $rip => 0x5555555550d8 <main+24>: cmp $0x1,%edi (gdb) print $eflags $5 = [ PF ZF IF ] (gdb) print $edi $6 = 1 (gdb) set $eflags &= ~(1<<6) (gdb) print $eflags $7 = [ PF IF ] ``` --- ## Common Flags * ZF: Zero flag * SF: Sign flag * CF: Carry flag * OF: Overflow flag * IF: Interrupt enable flag --- ## Checking Stack memory ```asm Breakpoint 1, main () at add_sum.S:118 118 in add_sum.S 1: x/i $rip => 0x5555555550c4 <main+4>: sub $0x18,%rsp (gdb) display/x $rsp 2: /x $rsp = 0x7fffffffdcc8 (gdb) display/x $rbp 3: /x $rbp = 0x7fffffffdd60 (gdb) break addSum Breakpoint 2 at 0x555555555230: file add_sum.S, line 9. (gdb) continue Continuing. Breakpoint 2, addSum () at add_sum.S:9 9 in add_sum.S 1: x/i $rip => 0x555555555230 <addSum>: endbr64 2: /x $rsp = 0x7fffffffdca8 3: /x $rbp = 0x7fffffffdd60 (gdb) step 10 in add_sum.S 1: x/i $rip => 0x555555555234 <addSum+4>: push %r12 2: /x $rsp = 0x7fffffffdca8 3: /x $rbp = 0x7fffffffdd60 (gdb) step 13 in add_sum.S 1: x/i $rip => 0x555555555236 <addSum+6>: mov %rdi,%r8 2: /x $rsp = 0x7fffffffdca0 3: /x $rbp = 0x7fffffffdd60 (gdb) step 14 in add_sum.S 1: x/i $rip => 0x555555555239 <addSum+9>: mov %esi,%r12d 2: /x $rsp = 0x7fffffffdca0 3: /x $rbp = 0x7fffffffdd60 (gdb) step 15 in add_sum.S 1: x/i $rip => 0x55555555523c <addSum+12>: push %rbp 2: /x $rsp = 0x7fffffffdca0 3: /x $rbp = 0x7fffffffdd60 (gdb) step 18 in add_sum.S 1: x/i $rip => 0x55555555523d <addSum+13>: lea -0x7(%rsi),%ebp 2: /x $rsp = 0x7fffffffdc98 3: /x $rbp = 0x7fffffffdd60 (gdb) x/1xw $rsp 0x7fffffffdc98: 0xffffdd60 ``` --- ## Multimedia Registers * Remember those `xmm` registers from the `-O3` optimization? * Those are "multimedia" registers, that hold larger values * Also used for blocks of floating point numbers ```asm (gdb) print $xmm0 $15 = {v8_bfloat16 = {0, 2.342e-38, 0, 0, 0, 0, 0, 0}, v8_half = {0, 1.5199e-05, 0, 0, 0, 0, 0, 0}, v4_float = {2.34180515e-38, 0, 0, 0}, v2_double = {8.256666972292243e-317, 0}, v16_int8 = {0, 0, -1, 0 <repeats 13 times>}, v8_int16 = {0, 255, 0, 0, 0, 0, 0, 0}, v4_int32 = {16711680, 0, 0, 0}, v2_int64 = {16711680, 0}, uint128 = 16711680} ``` -v- ## From Previous Lecture ```asm .file "add_sum7.c" .text .p2align 4 .globl addSum .type addSum, @function addSum: .LFB39: .cfi_startproc endbr64 leal -7(%rsi), %r9d movl %esi, %ecx cmpl $1, %r9d jle .L9 leal -9(%rsi), %eax movl %eax, %r8d shrl $3, %r8d leal 1(%r8), %esi cmpl $23, %eax jbe .L10 pxor %xmm3, %xmm3 movl %esi, %edx pxor %xmm10, %xmm10 xorl %eax, %eax shrl $2, %edx movaps %xmm3, -88(%rsp) movdqa %xmm3, %xmm15 movdqa .LC0(%rip), %xmm11 .p2align 4,,10 .p2align 3 .L4: movdqa %xmm11, %xmm2 movdqa %xmm10, %xmm1 addl $1, %eax movdqa .LC2(%rip), %xmm0 pcmpgtd %xmm2, %xmm1 movdqa %xmm2, %xmm13 movdqa .LC3(%rip), %xmm8 movdqa .LC4(%rip), %xmm7 paddd %xmm2, %xmm0 movdqa %xmm10, %xmm14 movdqa .LC5(%rip), %xmm6 movdqa .LC6(%rip), %xmm5 paddd %xmm2, %xmm8 movdqa %xmm0, %xmm9 paddd %xmm2, %xmm7 movdqa .LC7(%rip), %xmm4 punpckldq %xmm1, %xmm13 movaps %xmm1, -72(%rsp) paddd %xmm2, %xmm6 paddd %xmm2, %xmm5 movdqa %xmm13, %xmm1 movdqa %xmm10, %xmm13 paddd %xmm2, %xmm4 movdqa .LC8(%rip), %xmm3 pcmpgtd %xmm0, %xmm13 pcmpgtd %xmm8, %xmm14 paddq %xmm15, %xmm1 movdqa %xmm10, %xmm15 movdqa %xmm10, %xmm12 paddd %xmm2, %xmm3 pcmpgtd %xmm7, %xmm15 pcmpgtd %xmm4, %xmm12 punpckhdq -72(%rsp), %xmm2 punpckldq %xmm13, %xmm9 movaps %xmm14, -40(%rsp) paddq -88(%rsp), %xmm2 paddd .LC1(%rip), %xmm11 paddq %xmm9, %xmm1 movdqa %xmm8, %xmm9 movaps %xmm13, -56(%rsp) punpckhdq -56(%rsp), %xmm0 punpckldq %xmm14, %xmm9 punpckhdq -40(%rsp), %xmm8 movaps %xmm15, -24(%rsp) paddq %xmm9, %xmm1 movdqa %xmm7, %xmm9 paddq %xmm2, %xmm0 punpckldq %xmm15, %xmm9 punpckhdq -24(%rsp), %xmm7 paddq %xmm8, %xmm0 paddq %xmm9, %xmm1 movdqa %xmm10, %xmm9 movdqa %xmm3, %xmm15 pcmpgtd %xmm6, %xmm9 paddq %xmm7, %xmm0 movdqa %xmm9, %xmm14 movdqa %xmm6, %xmm9 punpckldq %xmm14, %xmm9 punpckhdq %xmm14, %xmm6 paddq %xmm9, %xmm1 movdqa %xmm10, %xmm9 paddq %xmm0, %xmm6 pcmpgtd %xmm5, %xmm9 movdqa %xmm9, %xmm13 movdqa %xmm5, %xmm9 punpckldq %xmm13, %xmm9 punpckhdq %xmm13, %xmm5 paddq %xmm9, %xmm1 movdqa %xmm4, %xmm9 paddq %xmm6, %xmm5 punpckldq %xmm12, %xmm9 punpckhdq %xmm12, %xmm4 paddq %xmm9, %xmm1 movdqa %xmm10, %xmm9 paddq %xmm5, %xmm4 pcmpgtd %xmm3, %xmm9 punpckhdq %xmm9, %xmm3 punpckldq %xmm9, %xmm15 paddq %xmm3, %xmm4 paddq %xmm1, %xmm15 movaps %xmm4, -88(%rsp) cmpl %edx, %eax jne .L4 paddq -88(%rsp), %xmm15 movdqa %xmm15, %xmm0 psrldq $8, %xmm0 paddq %xmm0, %xmm15 movq %xmm15, %rax testb $3, %sil je .L6 andl $-4, %esi leal 1(,%rsi,8), %edx .L3: movslq %edx, %rsi addq %rax, %rsi leal 1(%rdx), %eax cltq addq %rsi, %rax leal 2(%rdx), %esi movslq %esi, %rsi addq %rax, %rsi leal 3(%rdx), %eax cltq addq %rsi, %rax leal 4(%rdx), %esi movslq %esi, %rsi addq %rax, %rsi leal 5(%rdx), %eax cltq addq %rsi, %rax leal 6(%rdx), %esi movslq %esi, %rsi addq %rax, %rsi leal 7(%rdx), %eax cltq addq %rsi, %rax leal 8(%rdx), %esi cmpl %esi, %r9d jle .L6 movslq %esi, %rsi addq %rax, %rsi leal 9(%rdx), %eax cltq addq %rsi, %rax leal 10(%rdx), %esi movslq %esi, %rsi addq %rax, %rsi leal 11(%rdx), %eax cltq addq %rsi, %rax leal 12(%rdx), %esi movslq %esi, %rsi addq %rax, %rsi leal 13(%rdx), %eax cltq addq %rsi, %rax leal 14(%rdx), %esi movslq %esi, %rsi addq %rax, %rsi leal 15(%rdx), %eax cltq addq %rsi, %rax leal 16(%rdx), %esi cmpl %esi, %r9d jle .L6 movslq %esi, %rsi addq %rax, %rsi leal 17(%rdx), %eax cltq addq %rax, %rsi leal 18(%rdx), %eax cltq addq %rsi, %rax leal 19(%rdx), %esi movslq %esi, %rsi addq %rax, %rsi leal 20(%rdx), %eax cltq addq %rsi, %rax leal 21(%rdx), %esi movslq %esi, %rsi addq %rax, %rsi leal 22(%rdx), %eax addl $23, %edx cltq movslq %edx, %rdx addq %rsi, %rax addq %rdx, %rax .L6: leal 9(,%r8,8), %edx .L2: cmpl %edx, %ecx jle .L7 movslq %edx, %rsi addq %rsi, %rax leal 1(%rdx), %esi cmpl %ecx, %esi jge .L7 movslq %esi, %rsi addq %rsi, %rax leal 2(%rdx), %esi cmpl %esi, %ecx jle .L7 movslq %esi, %rsi addq %rsi, %rax leal 3(%rdx), %esi cmpl %ecx, %esi jge .L7 movslq %esi, %rsi addq %rsi, %rax leal 4(%rdx), %esi cmpl %ecx, %esi jge .L7 movslq %esi, %rsi addq %rsi, %rax leal 5(%rdx), %esi cmpl %esi, %ecx jle .L7 movslq %esi, %rsi addq %rsi, %rax leal 6(%rdx), %esi cmpl %esi, %ecx jle .L7 movslq %esi, %rsi addl $7, %edx addq %rsi, %rax movslq %edx, %rsi addq %rax, %rsi cmpl %edx, %ecx cmovg %rsi, %rax .L7: addq %rax, (%rdi) ret .p2align 4,,10 .p2align 3 .L9: movl $1, %edx xorl %eax, %eax jmp .L2 .L10: movl $1, %edx xorl %eax, %eax jmp .L3 .cfi_endproc .LFE39: .size addSum, .-addSum .section .rodata.str1.8,"aMS",@progbits,1 .align 8 .LC9: .string "This program requires a positive number as its second argument." .section .rodata.str1.1,"aMS",@progbits,1 .LC10: .string "%lli\n" .section .text.startup,"ax",@progbits .p2align 4 .globl main .type main, @function main: .LFB40: .cfi_startproc endbr64 subq $24, %rsp .cfi_def_cfa_offset 32 movq %fs:40, %rax movq %rax, 8(%rsp) xorl %eax, %eax cmpl $1, %edi jle .L22 movq 8(%rsi), %rdi movl $10, %edx xorl %esi, %esi movq $0, (%rsp) call strtol@PLT movq %rsp, %rdi movl %eax, %esi call addSum movq (%rsp), %rdx movl $2, %edi xorl %eax, %eax leaq .LC10(%rip), %rsi call __printf_chk@PLT .L19: movq 8(%rsp), %rax subq %fs:40, %rax jne .L23 xorl %eax, %eax addq $24, %rsp .cfi_remember_state .cfi_def_cfa_offset 8 ret .L22: .cfi_restore_state leaq .LC9(%rip), %rdi call puts@PLT jmp .L19 .L23: call __stack_chk_fail@PLT .cfi_endproc .LFE40: .size main, .-main .section .rodata.cst16,"aM",@progbits,16 .align 16 .LC0: .long 1 .long 9 .long 17 .long 25 .align 16 .LC1: .long 32 .long 32 .long 32 .long 32 .align 16 .LC2: .long 1 .long 1 .long 1 .long 1 .align 16 .LC3: .long 2 .long 2 .long 2 .long 2 .align 16 .LC4: .long 3 .long 3 .long 3 .long 3 .align 16 .LC5: .long 4 .long 4 .long 4 .long 4 .align 16 .LC6: .long 5 .long 5 .long 5 .long 5 .align 16 .LC7: .long 6 .long 6 .long 6 .long 6 .align 16 .LC8: .long 7 .long 7 .long 7 .long 7 .ident "GCC: (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.0" .section .note.GNU-stack,"",@progbits .section .note.gnu.property,"a" .align 8 .long 1f - 0f .long 4f - 1f .long 5 0: .string "GNU" 1: .align 8 .long 0xc0000002 .long 3f - 2f 2: .long 0x3 3: .align 8 4: ``` --- ## Why? * More fine-grained debugging * See how your computer works * Will need to know this for the bomb lab, useful when optimizing hw4 * While we're looking at assembly, let's look at one more topic --- ## SIMD * SIMD stands for "single instruction, multiple data" * Also called vector processing, since we operate on a "vector" of values * The multimedia registers allow multiple operations with a single instruction * This obviously can increase program speed quite a bit --- ## Advantages * We increase the amount done with each instruction * Replaces multiple loads, adds, multiplies, xors, etc * Can also eliminate loops * The hardware is optimized for them --- ## Many Versions * The first vector instructions supported were the MMX instructions * Introduced in 1997, MM is for multimedia * This introduced the MM0-MM7 registers * See what your CPU supports, just `cat /proc/cpuinfo` * Try using grep to find mmx, sse, or avx --- ## What For? * These operations are single instructions that operations upon multiple data registers * We saw gcc trying to use these to speed up a loop in lecture 15 * Newer versions support new operations (such as single-instruction multiply add) * Newer versions also support more registers * AVX-512 (from 2016) supports 512-bit wide registers --- ## 2023 Additions * AMX introduced in Intel's Sapphire Rapics microarchitecture * Tile registers are 8192 bits wide (16 rows of 64 bytes) * Made for in-hardware matrix instructions * Even if your matrix is too large, you can break it into blocks * The actual operation will be fully parallel * Delay will be fetching and storing the data * 2048 INT8 or 1024 BF16 ops per cycle --- ## iLab3 CPU flags ``` $ cat /proc/cpuinfo |grep flags flags : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush mmx fxsr sse sse2 ht syscall nx mmxext fxsr_opt pdpe1gb rdtscp lm constant_tsc rep_good nopl nonstop_tsc cpuid extd_apicid aperfmperf rapl pni pclmulqdq monitor ssse3 fma cx16 sse4_1 sse4_2 movbe popcnt aes xsave avx f16c rdrand lahf_lm cmp_legacy svm extapic cr8_legacy abm sse4a misalignsse 3dnowprefetch osvw ibs skinit wdt tce topoext perfctr_core perfctr_nb bpext perfctr_llc mwaitx cpb cat_l3 cdp_l3 hw_pstate ssbd mba ibpb stibp vmmcall fsgsbase bmi1 avx2 smep bmi2 cqm rdt_a rdseed adx smap clflushopt clwb sha_ni xsaveopt xsavec xgetbv1 cqm_llc cqm_occup_llc cqm_mbm_total cqm_mbm_local clzero irperf xsaveerptr rdpru wbnoinvd arat npt lbrv svm_lock nrip_save tsc_scale vmcb_clean flushbyasid decodeassists pausefilter pfthreshold avic v_vmsave_vmload vgif v_spec_ctrl umip rdpid overflow_recov succor smca sev sev_es ``` --- ## Support * iLab1-4 cpus only support up to AVX2 * These are 256-bit vector instructions * My laptop is newer * This is one way that today's inexpensive CPU architectures outperform yesteryear's high-end CPUs --- ## Laptop Flags So many avx options ``` flags : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush mmx fxsr sse sse2 ht syscall nx mmxext fxsr_opt pdpe1gb rdtscp lm constant_tsc rep_good amd_lbr_v2 nopl xtopology nonstop_tsc cpuid extd_apicid aperfmperf rapl pni pclmulqdq monitor ssse3 fma cx16 sse4_1 sse4_2 x2apic movbe popcnt aes xsave avx f16c rdrand lahf_lm cmp_legacy svm extapic cr8_legacy abm sse4a misalignsse 3dnowprefetch osvw ibs skinit wdt tce topoext perfctr_core perfctr_nb bpext perfctr_llc mwaitx cpb cat_l3 cdp_l3 hw_pstate ssbd mba perfmon_v2 ibrs ibpb stibp ibrs_enhanced vmmcall fsgsbase bmi1 avx2 smep bmi2 erms invpcid cqm rdt_a avx512f avx512dq rdseed adx smap avx512ifma clflushopt clwb avx512cd sha_ni avx512bw avx512vl xsaveopt xsavec xgetbv1 xsaves cqm_llc cqm_occup_llc cqm_mbm_total cqm_mbm_local user_shstk avx512_bf16 clzero irperf xsaveerptr rdpru wbnoinvd cppc arat npt lbrv svm_lock nrip_save tsc_scale vmcb_clean flushbyasid decodeassists pausefilter pfthreshold vgif x2avic v_spec_ctrl vnmi avx512vbmi umip pku ospke avx512_vbmi2 gfni vaes vpclmulqdq avx512_vnni avx512_bitalg avx512_vpopcntdq rdpid overflow_recov succor smca fsrm flush_l1d ``` --- ## Compiler Support * Compilers generally add support to use fancy new instructions * And you can hope that they are used when you enable optimizations * But languages move very slowly, so won't reflect hardware capabilities * Luckily, we know some assembly! --- ## Features * We'll stick with the xmm registers so you can test on iLab and most of your own machines * Each is 128-bits * Ints are 32-bits, so these hold 4 * ymm registers are twice as wide, and xmm is the lower half (similar to %eax being the lower half of %rax) * Let's show some summation * We can do 4 simultaneous additions with a single instruction --- ## SIMD Load, Add * Load data from an array, 4 values at a time * Then add, also 4 at a time <div class="col"> <img style="width: 80%" class="r-stretch" src="./figures/movdqu_padd_figure.svg" /> </div> --- ## Paralellism * Compare SIMD to threading * Threading obviously helps fill a superscalar pipeline * While SIMD removes several bottlenecks in the singe instruction, single data architecture * Using both together wins orders of magnitude improvements over naive alternatives --- ## Basic Summing ```c #include <stdio.h> #include <stdlib.h> int sumNumbers(int* numbers, size_t length) { int sum = 0; for (int i = 0; i < length; ++i) { sum += numbers[i]; } return sum; } int main(int argc, char** argv) { int buffer[100000]; for (int i = 0; i < sizeof(buffer)/sizeof(int); ++i) { buffer[i] = i; } printf("%i\n", sumNumbers(buffer, sizeof(buffer)/sizeof(int))); return 0; } ``` --- ## Unrolling * SIMD instructions will be similar to unrolling, so begin there ```C #include <stdio.h> #include <stdlib.h> int sumNumbers(int* numbers, size_t length) { int sum = 0; int i = 0; // Unrolling for (; i < length-4; i+=4) { sum += numbers[i]; sum += numbers[i+1]; sum += numbers[i+2]; sum += numbers[i+3]; } // 3 or fewer leftover numbers for (; i < length; ++i) { sum += numbers[i]; } return sum; } int main(int argc, char** argv) { int buffer[100000]; for (int i = 0; i < sizeof(buffer)/sizeof(int); ++i) { buffer[i] = i; } printf("%i\n", sumNumbers(buffer, sizeof(buffer)/sizeof(int))); return 0; } ``` --- ## Vector Additions * We will be adding with 4 numbers at a time, which is like adding into 4 separate registers ```C #include <stdio.h> #include <stdlib.h> int sumNumbers(int* numbers, size_t length) { int i = 0; // Unrolling // Four different values for addition int x1 = 0; int x2 = 0; int x3 = 0; int x4 = 0; for (; i < length-4; i+=4) { x1 += numbers[i]; x2 += numbers[i+1]; x3 += numbers[i+2]; x4 += numbers[i+3]; } int sum = x1 + x2 + x3 + x4; // 3 or fewer leftover numbers for (; i < length; ++i) { sum += numbers[i]; } return sum; } int main(int argc, char** argv) { int buffer[100000]; for (int i = 0; i < sizeof(buffer)/sizeof(int); ++i) { buffer[i] = i; } printf("%i\n", sumNumbers(buffer, sizeof(buffer)/sizeof(int))); return 0; } ``` --- ## Vector Loading * Now convert everything to use the xmm registers ```C #include <stdio.h> #include <stdlib.h> int sumNumbers(int* numbers, size_t length) { int i = 0; // Unrolling // XOR a register with itself to 0 it __asm__("pxor %%xmm0, %%xmm0" : : :); for (; i < length-4; i+=4) { // move double-word integers into xmm1, then add into xmm0 // The double %% indicates a register, a single % means a user-provided variable. __asm__( "movdqu (%0), %%xmm1\n\t" "paddd %%xmm1, %%xmm0\n\t" : // No outputs : "r" (numbers+i) : ); } // You would think that we would add up the numbers like this: //int sum = x1 + x2 + x3 + x4; // But instead, we'll vectorize this too, adding them in pair // [x1 x2 x3 x4] >> 8 bytes -> [0 0 x1 x2] // [0 0 x1 x2] + [x1 x2 x3 x4] -> [x1 x2 x1+x3 x2+x4] // Shift over and add again, and x1+x2+x3+x4 is in the last position. // Transfer it back to a nonvector register. int sum = 0; __asm__( "movdqa %%xmm0, %%xmm1\n\t" "psrldq $8, %%xmm1\n\t" "paddd %%xmm1, %%xmm0\n\t" "movdqa %%xmm0, %%xmm1\n\t" "psrldq $4, %%xmm1\n\t" "paddd %%xmm1, %%xmm0\n\t" "movd %%xmm0, %0\n\t" : "=r"(sum) : // No inputs : ); // 3 or fewer leftover numbers for (; i < length; ++i) { sum += numbers[i]; } return sum; } int main(int argc, char** argv) { int buffer[100000]; for (int i = 0; i < sizeof(buffer)/sizeof(int); ++i) { buffer[i] = i; } printf("%i\n", sumNumbers(buffer, sizeof(buffer)/sizeof(int))); return 0; } ``` --- ## Simplification * We can transfer out of xmm and then sum ```C #include <stdio.h> #include <stdlib.h> int sumNumbers(int* numbers, size_t length) { int i = 0; // Unrolling // XOR a register with itself to 0 it __asm__("pxor %%xmm0, %%xmm0" : : :); for (; i < length-4; i+=4) { // move double-word integers into xmm1, then add into xmm0 // The double %% indicates a register, a single % means a user-provided variable. __asm__( "movdqu (%0), %%xmm1\n\t" "paddd %%xmm1, %%xmm0\n\t" : // No outputs : "r" (numbers+i) : ); } int sums[4] = {0}; __asm__("movdqa %%xmm0, %0" : "=m" (sums) : :); int sum = sums[0] + sums[1] + sums[2] + sums[3]; // 3 or fewer leftover numbers for (; i < length; ++i) { sum += numbers[i]; } return sum; } int main(int argc, char** argv) { int buffer[100000]; for (int i = 0; i < sizeof(buffer)/sizeof(int); ++i) { buffer[i] = i; } printf("%i\n", sumNumbers(buffer, sizeof(buffer)/sizeof(int))); return 0; } --- ## Advantages * This addition finishes in milliseconds, so while SIMD is fast it isn't a big deal here * But it is a big deal in general * One instruction does 4 ops, so we are now 4x faster * With a 256 bit register, we could be 8x --- ## Other SIMD Instructions * Big list online: [https://www.felixcloutier.com/x86/](https://www.felixcloutier.com/x86/) * Instructions of interest: * Packed compare for equality: [psubd](https://www.felixcloutier.com/x86/psubb:psubw:psubd) * Subtraction, like the paddd instruction we used * Packed compare for equality: [pcmpeqd](https://www.felixcloutier.com/x86/pcmpeqb:pcmpeqw:pcmpeqd) * Compares two xmm (or ymm or avx) registers * Target register positioned are filled with 0 for inequality, -1 for equality --- ## Bandwidth and Memory * With a single instruction we operate on 4 (or more!) registers * What is the speedup limitation? * Bandwidth * We need to actually load the memory to use it * At the extreme, we can optimize our entire system for bandwidth and wide operations * Now we have a GPU --- ## Next Lecture: Memory * It keeps coming up * But how does memory work? * How long does a memory access take? * Why is it just as fast to fetch 4 ints as 1 int? * And how are different kinds of memory optimized? * Speed for registers, density for disks, etc