Virtual memory, input/output and parallelism

This final lesson completes the picture of the machine in three directions. Virtual memory gives every program the illusion of its own large, private address space, with hardware translating each address on every access; it is how operating systems isolate programs from one another. Input and output connect the processor to the world, through device registers, interrupts and direct memory access. Parallel hardware, from vector instructions to multicore chips, is where performance growth has come from since clock rates stalled, as lesson 1 explained. The lesson ends with a capstone that traces one C program through every layer of the course: compilation, execution, pipelining and caching.

The treatment here is from the hardware side. How an operating system chooses which pages to keep in memory, schedules processes and drives devices is the subject of CMPUT-379; how to write parallel programs well is the subject of CMPUT-450 and other courses. What this lesson provides is the mechanism those courses build on.

Why virtual memory

Every program in this course has assumed it owns memory starting at fixed addresses: text at 0x00400000, data at 0x10010000. On a real system dozens of programs run at once, each linked to use the same addresses. Virtual memory makes that possible. Each process uses virtual addresses, and hardware translates each one to a physical address in main memory, using a table the operating system maintains for that process. Two processes can both use virtual address 0x10010000 and reach entirely different physical memory. A process cannot even name another process's memory, which gives protection. Memory can be allocated in scattered pieces while looking contiguous to the program, which simplifies loading. And pages that are not currently needed can live on storage instead of in DRAM, so the total memory used by all programs can exceed physical memory.

Memory is divided into fixed-size pages, 4 KiB in RISC-V and most other systems, with larger pages available for special uses. A virtual address is split into a virtual page number and a page offset; translation replaces the virtual page number with a physical page number and keeps the offset unchanged. The mapping is recorded in a page table: an array of page table entries, each holding a physical page number and permission bits. If a program touches a page whose entry is marked invalid, the hardware raises a page fault, an exception that transfers control to the operating system, which can load the page from storage, allocate a fresh zeroed page, or terminate the program for an illegal access, and then let the program retry the instruction.

Page tables in RISC-V

A single flat page table would be enormous: a 32-bit address space with 4 KiB pages has 2²⁰ pages, needing a 4 MiB table per process even though most programs use a tiny fraction of the space. RISC-V's Sv32 scheme for 32-bit systems uses a two-level tree instead. The 20-bit virtual page number is split into two 10-bit indexes. The first indexes a root table of 1,024 entries, whose base address is held in the satp register; that entry points to a second-level table of 1,024 entries, which holds the final physical page number. Each table is exactly one 4 KiB page. Regions of the address space that are unused need no second-level table at all, so a small program needs only a few pages of tables. 64-bit RISC-V systems use three, four or five levels (Sv39, Sv48 and Sv57).

Each page table entry holds the physical page number and flag bits: V (valid), R, W and X (readable, writable, executable), U (accessible in user mode), G (global), A (accessed) and D (dirty). The permission bits enforce the segment protections of lesson 8, so an attempt to write to the text segment or execute the stack causes a page fault. The A and D bits are set by hardware when a page is used and written, which tells the operating system which pages are in active use and which must be written back to storage before being reused.

PAGE = 4096
def split(va):
    return va >> 22, (va >> 12) & 0x3FF, va & 0xFFF

# A toy two-level page table: root[vpn1] -> second-level table {vpn0: (ppn, flags)}
root = {
    0x001: {0x000: (0x8A2F1, 'R-X'), 0x001: (0x8A2F2, 'R-X')},     # text near 0x00400000
    0x040: {0x010: (0x91C07, 'RW-')},                              # data near 0x10010000
    0x1FF: {0x3FE: (0x7F3A0, 'RW-')},                              # stack near 0x7FFFE000
}

def translate(va, write=False, execute=False):
    vpn1, vpn0, off = split(va)
    second = root.get(vpn1)
    if second is None or vpn0 not in second:
        return f'page fault (no mapping for VPN {vpn1:#05x}:{vpn0:#05x})'
    ppn, flags = second[vpn0]
    need = 'X' if execute else 'W' if write else 'R'
    if need not in flags:
        return f'page fault (access needs {need}, page is {flags})'
    return f'PA {ppn * PAGE + off:#010x}'

for va, w, x in [(0x00400010, False, True), (0x10010A44, True, False), (0x7FFFEFF8, True, False),
                 (0x00400020, True, False), (0x20000000, False, False)]:
    vpn1, vpn0, off = split(va)
    kind = 'execute' if x else 'write' if w else 'read'
    print(f'VA {va:#010x} ({kind:<7}) VPN1={vpn1:#05x} VPN0={vpn0:#05x} off={off:#05x} -> {translate(va, w, x)}')

VA 0x00400010 (execute) VPN1=0x001 VPN0=0x000 off=0x010 -> PA 0x8a2f1010
VA 0x10010a44 (write  ) VPN1=0x040 VPN0=0x010 off=0xa44 -> PA 0x91c07a44
VA 0x7fffeff8 (write  ) VPN1=0x1ff VPN0=0x3fe off=0xff8 -> PA 0x7f3a0ff8
VA 0x00400020 (write  ) VPN1=0x001 VPN0=0x000 off=0x020 -> page fault (access needs W, page is R-X)
VA 0x20000000 (read   ) VPN1=0x080 VPN0=0x000 off=0x000 -> page fault (no mapping for VPN 0x080:0x000)

The fourth access tries to write to a text page, which is mapped readable and executable but not writable, so it faults; the fifth touches an address with no mapping at all. On a real system the operating system would respond to the first by terminating the program with a segmentation fault, and to the second either the same way or, if the address belonged to a region the program had legitimately reserved, by allocating a page.

The TLB

Translation as described would make every memory access cost three: two page table reads and then the access itself. The translation lookaside buffer, or TLB, avoids that. It is a small cache of recent translations, typically 32 to a few thousand entries, often fully associative or highly associative, consulted in parallel with the L1 cache on every access. Because programs have locality and a single 4 KiB page covers 1,024 words, TLB hit rates are very high. On a TLB miss, RISC-V hardware walks the page table itself, as x86-64 and Arm hardware do; some older designs, including MIPS, trapped to the operating system to refill the TLB in software. When the operating system changes a mapping, it must invalidate stale TLB entries, with the RISC-V instruction sfence.vma.

import random
random.seed(229)

def tlb_hit_rate(addresses, entries=16):
    tlb, hits = [], 0                       # fully associative, LRU
    for va in addresses:
        vpn = va >> 12
        if vpn in tlb:
            hits += 1; tlb.remove(vpn)
        elif len(tlb) == entries:
            tlb.pop(0)
        tlb.append(vpn)
    return hits / len(addresses)

seq = [0x10010000 + 4 * i for i in range(20000)]                    # walk an 80 KB array
strided = [0x10010000 + 4096 * (i % 64) for i in range(20000)]      # one word per page, 64 pages
rand = [0x10010000 + 4 * random.randrange(1 << 20) for _ in range(20000)]   # 4 MB at random
for name, trace in [('sequential', seq), ('page stride', strided), ('random', rand)]:
    print(f'{name:>11}: TLB hit rate {100 * tlb_hit_rate(trace):5.1f}%')

 sequential: TLB hit rate  99.9%
page stride: TLB hit rate   0.0%
     random: TLB hit rate   1.6%

Sequential access misses only once per 1,024 accesses, when it crosses into a new page. Touching one word in each of 64 pages in rotation overwhelms a 16-entry TLB completely, and random access over 4 MB is almost as bad. Large pages, 4 MiB megapages in Sv32 and 2 MiB or 1 GiB pages on 64-bit systems, let one TLB entry cover far more memory, which is why databases and scientific programs often request them.

Exceptions, interrupts and privilege

Page faults are one kind of exception: an event that diverts the processor from the normal flow of instructions. Exceptions caused by the instruction being executed, such as an illegal instruction, a misaligned access, a page fault or an ecall, are synchronous. Interrupts, caused by events outside the program such as a timer or a network card receiving data, are asynchronous. RISC-V handles both the same way. The processor saves the address of the interrupted instruction in the exception program counter, mepc or sepc, records the cause in mcause or scause, switches to a more privileged mode and jumps to the handler whose address is in mtvec or stvec. The handler, part of the operating system, does its work and executes mret or sret to return.

RISC-V defines privilege modes: machine mode (M), the most privileged, used by firmware; supervisor mode (S), used by an operating system kernel; and user mode (U), used by applications. Instructions that change page tables, disable interrupts or access devices directly are allowed only in privileged modes, and page table entries without the U bit are inaccessible from user mode, so an application cannot interfere with the kernel or with other applications. The ecall instruction used throughout this course is exactly the doorway between modes: in a real system it traps from user mode into the kernel, which reads a7 to decide which service to perform. RARS and this course's simulator implement the services directly instead of running a kernel, but the calling convention is the same idea.

Input and output

Devices are connected to the processor through controllers that expose a small set of registers: a status register indicating whether the device is ready, a control register for commands and a data register for the bytes themselves. RISC-V, like most modern ISAs, uses memory-mapped I/O: device registers appear at physical addresses, and ordinary loads and stores read and write them. Those addresses are marked in the page tables and memory system as uncached, since a device register's value can change at any time and caching it would return stale data. On the widely used QEMU virtual RISC-V machine, for example, a serial port appears at physical address 0x10000000, and writing a byte to it prints a character.

The processor can learn that a device needs attention in two ways. With polling, the program repeatedly reads the status register until the device is ready, which is simple but wastes processor time when devices are slow. With interrupts, the device signals the processor when it is ready, and the processor runs a handler only then, which is efficient for slow or unpredictable devices but has a fixed overhead per event. For large transfers, such as reading a block from a solid-state drive or receiving network packets, direct memory access (DMA) lets the device controller copy data between the device and memory itself, interrupting the processor only when the whole transfer is done. Devices connect through buses and links such as PCI Express, whose current generations deliver tens of gigabytes per second per device.

Parallel hardware

Since the power wall of lesson 1, processors have gained speed mainly through parallelism at several levels. Pipelining and superscalar execution, from lesson 10, exploit instruction-level parallelism within one program automatically. Data-level parallelism applies one operation to many data items: single instruction, multiple data (SIMD) or vector instructions operate on whole registers of values at once. The RISC-V V extension provides vector registers whose length is chosen by the implementation, from 128 bits in small cores to thousands of bits, and code written for it runs unchanged on any vector length. x86-64 has fixed-width SIMD extensions such as SSE, AVX2 and AVX-512, and Arm has NEON and SVE. Compilers can vectorize simple loops automatically, as clang does here for an element-wise addition.

void vadd(int *restrict c, const int *restrict a,
          const int *restrict b, int n) {
    for (int i = 0; i < n; i++)
        c[i] = a[i] + b[i];
}

$ clang --target=riscv32 -march=rv32imv -O2 -S vadd.c -o -
vadd:
    blez    a3, .LBB0_8
    csrr    a6, vlenb
    srli    a5, a6, 1
    bgeu    a3, a5, .LBB0_3
    li      a4, 0
    j       .LBB0_6
.LBB0_3:
    neg     a4, a5
    and     a4, a4, a3
    slli    a6, a6, 1
    vsetvli a7, zero, e32, m2, ta, ma
    mv      a7, a4
    mv      t0, a0
    mv      t1, a2
    mv      t2, a1
.LBB0_4:
    vl2re32.v v8, (t2)
    vl2re32.v v10, (t1)
    vadd.vv v8, v10, v8
    vs2r.v  v8, (t0)
    add     t2, t2, a6
    add     t1, t1, a6
    sub     a7, a7, a5
    add     t0, t0, a6
    bnez    a7, .LBB0_4
    beq     a4, a3, .LBB0_8
.LBB0_6:
    sub     a3, a3, a4
    slli    a4, a4, 2
    add     a0, a0, a4
    add     a2, a2, a4
    add     a1, a1, a4
.LBB0_7:
    lw      a4, 0(a1)
    lw      a5, 0(a2)
    add     a4, a5, a4
    sw      a4, 0(a0)
    addi    a3, a3, -1
    addi    a0, a0, 4
    addi    a2, a2, 4
    addi    a1, a1, 4
    bnez    a3, .LBB0_7
.LBB0_8:
    ret

Find the vector loop in the middle: vl2re32.v loads a group of vector registers from a, a second load fetches b, vadd.vv adds them element by element, and vs2r.v stores the result to c. The csrr reading vlenb at the top asks the hardware how long its vector registers are, so the same machine code processes 8 integers per iteration on a core with 128-bit registers and 32 on one with 512-bit registers. A scalar loop after the vector loop handles any leftover elements. The restrict keywords promise the compiler that the arrays do not overlap, which it needs to know before vectorizing safely.

Thread-level parallelism runs separate instruction streams on separate cores, or on hardware threads that share one core. Cores on one chip share main memory, which raises a new problem: each core has its own L1 and L2 caches, so two cores may hold different copies of the same block. Cache coherence protocols keep the copies consistent. In the common MESI protocol, each cached block is Modified, Exclusive, Shared or Invalid, and a core that wants to write a block first invalidates every other copy, by snooping on a shared bus or by consulting a directory. Coherence makes shared memory behave sensibly, but it has a cost that programmers can see: if two cores repeatedly write different variables that happen to share a cache block, the block bounces between their caches, an effect called false sharing that can make a parallel program slower than a serial one.

Graphics processing units (GPUs) push data-level and thread-level parallelism to the extreme, with thousands of simple cores running the same program on different data, hiding memory latency by switching among many threads rather than with large caches. They were designed for graphics, but their throughput on regular, parallel arithmetic made them the main engine of machine learning. Whatever the hardware, Amdahl's law from lesson 1 still applies: the serial fraction of a program limits the benefit of every one of these forms of parallelism.

Capstone: one program through the whole machine

To close the course, follow one program from source code to cache behavior. The C program below fills an array of 512 integers from a simple pseudo-random generator, sorts it with insertion sort, and prints a summary and a checksum. It was compiled by clang for RV32IM, linked with the course's runtime, and executed on the simulator, which counted instructions by class, measured the deepest stack use, counted load-use pairs and taken branches to estimate a five-stage pipeline's cycles as in lesson 10, and recorded every data access for the cache models of lesson 11.

void print_int(int);
void print_str(const char *);

#define N 512
static int data[N];

static unsigned seed = 2026;
static int next_random(void) {           /* a linear congruential generator */
    seed = seed * 1103515245u + 12345u;
    return (int)((seed >> 16) % 1000);
}

static void insertion_sort(int *a, int n) {
    for (int i = 1; i < n; i++) {
        int key = a[i], j = i - 1;
        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = key;
    }
}

int cmain(void) {
    for (int i = 0; i < N; i++)
        data[i] = next_random();
    insertion_sort(data, N);
    int checksum = 0;
    for (int i = 0; i < N; i++)
        checksum = checksum * 31 + data[i];
    print_str("min "); print_int(data[0]);
    print_str(", median "); print_int(data[N / 2]);
    print_str(", max "); print_int(data[N - 1]);
    print_str(", checksum "); print_int(checksum); print_str("\n");
    return 0;
}

min 2, median 528, max 998, checksum 1575081745
instructions executed: 470633
  ALU 205304, loads 66703, stores 66201, branches 132382 (66684 taken), jumps 33, system 10
instructions: 470633, load-use stalls: 65673, taken branches and jumps: 66717
5-stage pipeline estimate: 470633 + 4 + 65673 + 2 x 66717 = 669744 cycles, CPI = 1.42
deepest stack use: 16 bytes

void print_int(int);
void print_str(const char *);

#define N 512
static int data[N];

static unsigned seed = 2026;
static int next_random(void) {           /* a linear congruential generator */
    seed = seed * 1103515245u + 12345u;
    return (int)((seed >> 16) % 1000);
}

static void insertion_sort(int *a, int n) {
    for (int i = 1; i < n; i++) {
        int key = a[i], j = i - 1;
        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = key;
    }
}

int cmain(void) {
    for (int i = 0; i < N; i++)
        data[i] = next_random();
    insertion_sort(data, N);
    int checksum = 0;
    for (int i = 0; i < N; i++)
        checksum = checksum * 31 + data[i];
    print_str("min "); print_int(data[0]);
    print_str(", median "); print_int(data[N / 2]);
    print_str(", max "); print_int(data[N - 1]);
    print_str(", checksum "); print_int(checksum); print_str("\n");
    return 0;
}

min 2, median 528, max 998, checksum 1575081745
instructions executed: 470633, data accesses: 132904
512 B, 32-byte blocks, direct-mapped: miss rate 4.3% (5681 misses)
1 KiB, 32-byte blocks, 2-way: miss rate 2.1% (2727 misses)
4 KiB, 64-byte blocks, 4-way: miss rate 0.0% (34 misses)

Read the results layer by layer. Lesson 2 explains the checksum, which deliberately wraps around 32 bits because signed overflow in this checksum is harmless on the machine, even though C does not promise it; a careful program would use unsigned. Lesson 6 explains the instruction mix: insertion sort's inner loop of loads, compares, stores and branches dominates, so loads and stores together make up more than a quarter of all instructions, and branches another quarter. Lesson 7 explains the small stack figure: the compiler inlined the helper functions and kept almost everything in registers, so cmain's single frame is the deepest the stack goes. Lesson 10's estimate shows the pipeline's CPI rising to about 1.4, in roughly equal parts from load-use stalls and taken branches: the inner loop compares each element immediately after loading it, and its backward branch is taken on almost every iteration, exactly the patterns that scheduling and branch prediction exist to attack. And lesson 11 explains the cache results: the 2 KiB array fits comfortably in the 4 KiB cache, so after the first touch almost everything hits, while a 512-byte cache, too small for the array, misses much more.

# Combine the measured counts with lesson 11's cost model (cycle costs are illustrative).
instructions = 470_633          # from the run above
pipe_cycles  = 669_744          # five-stage estimate from the run above
accesses     = 132_904          # data accesses from the cache run
for name, misses in [('512 B direct-mapped', 5_681), ('4 KiB 4-way', 34)]:
    for penalty in (20, 100):
        total = pipe_cycles + misses * penalty
        print(f'{name:<20} miss penalty {penalty:3d}: {total:>9,} cycles, CPI {total / instructions:.2f}')

512 B direct-mapped  miss penalty  20:   783,364 cycles, CPI 1.66
512 B direct-mapped  miss penalty 100: 1,237,844 cycles, CPI 2.63
4 KiB 4-way          miss penalty  20:   670,424 cycles, CPI 1.42
4 KiB 4-way          miss penalty 100:   673,144 cycles, CPI 1.43

With the larger cache, misses add almost nothing; with the tiny cache and a slow next level, they add noticeably to the run time even for this cache-friendly program. Every number in this capstone traces back to a mechanism covered in this course: the representation of the data, the instructions the compiler chose, the calling convention, the pipeline's hazards and the cache's organization. That is the payoff of opening the black box. When a program is slow, or wrong in a way the source code cannot explain, you now know which layer to look at and what tools to use.