Hardware-Aware Algorithm Design

Chapter 1: CPU vs GPU

Before we can understand the memory wall, we need to understand what's behind the wall. Let's look at the two processors you'll encounter in ML: the CPU and the GPU. They solve fundamentally different problems.

The CPU: A Few Very Smart Workers

A CPU (Central Processing Unit) is designed to execute a sequence of instructions with minimum latency — the time from "start this task" to "task is done." Think of it as one or two brilliant workers who can each solve complex, branching problems very quickly.

A CPU core has a big control unit that fetches the next instruction and figures out what to do. It has ALU/FPU units (Arithmetic Logic Unit / Floating Point Unit) that do the actual math. And it has large caches that store data close to the processor so it doesn't have to wait for slow main memory.

Most of the transistors in a CPU are dedicated to data caching and flow control — branch prediction, out-of-order execution, speculative execution. The actual compute units are a small fraction of the chip. This makes CPUs brilliant at complex, sequential logic.

The GPU: Thousands of Simple Workers

A GPU (Graphics Processing Unit) takes the opposite approach. Instead of a few smart workers, it has thousands of simple ones. Each worker (called a CUDA core on NVIDIA GPUs) can only do basic arithmetic, but there are so many of them running in parallel that the total throughput — operations per second — is enormous.

GPUs are organized into Streaming Multiprocessors (SMs). An NVIDIA A100 has 108 SMs. Each SM has its own instruction unit, registers, and shared memory. It manages hundreds of threads simultaneously using a model called SIMT (Single Instruction, Multiple Thread): 32 threads are grouped into a warp, and every thread in a warp executes the same instruction at the same time, just on different data.

Why GPUs Dominate Deep Learning

The core building block of deep learning is the matrix multiplication. A matmul of two 4096×4096 matrices requires about 137 billion multiply-add operations. Every single one is independent — you can compute any output element without waiting for any other. This is a perfect fit for the GPU's thousands of parallel workers.

Chapter 2: The Memory Hierarchy

Now that we know GPUs have thousands of cores, the question becomes: how do we feed those cores with data? This is where the memory hierarchy comes in — a cascade of storage levels, each trading capacity for speed.

The Memory Ladder

Think of it like a workshop. Your workbench (registers) holds what you're working on right now — tiny capacity, instant access. The toolbox on the shelf (L1/shared memory) is a step away. The supply closet down the hall (L2 cache) takes a bit longer. And the warehouse across town (HBM/DRAM) has everything you could ever need, but getting something from there takes a real trip.

On an NVIDIA A100 GPU, here are the actual numbers:

The Memory Wall, Quantified

The A100 can do 312 TFLOPS of FP16 compute. But it can only move data from HBM at 2 TB/s. Let's convert to the same units. Each FP16 number is 2 bytes. So 2 TB/s = 1 trillion FP16 numbers per second. But we can process 312 trillion operations per second. That's a ~160:1 ratio. For every byte we read from HBM, we need to do at least 160 floating-point operations, or the compute units sit idle.

This ratio — 160 FLOPs per byte — is the hardware's arithmetic intensity threshold. If your operation does fewer than 160 FLOPs per byte of data it moves, the compute units will be starved. We'll formalize this in Chapter 4.

Chapter 3: Compute-Bound vs Memory-Bound

Now we arrive at the most important concept in hardware-aware design: the classification of every operation into one of two categories. Understanding this distinction is the single most impactful skill you can develop for writing fast ML code.

The Toy Processor

Imagine a simple processor that can do 8 operations per second (compute bandwidth) and move 4 items per second to/from memory (memory bandwidth). Suppose we need to:

1. Load 8 items from memory
2. Compute 1 operation on each item
3. Write 8 results back to memory

Loading 8 items at 4 items/s takes 2 seconds. Computing 8 operations at 8 ops/s takes 1 second. Writing 8 items at 4 items/s takes 2 seconds. If compute overlaps with I/O (which modern GPUs do), the total time at steady state is dominated by memory: the processor can do 8 ops/s but only receives 4 items/s. It does 4 ops per second — 50% compute utilization. The processor is sitting idle half the time, waiting for data. This is memory-bound.

Now Change the Algorithm

Same processor (8 ops/s, 4 items/s), but now our algorithm does 4 operations per item instead of 1:

1. Load 4 items from memory
2. Compute 4 ops on each item (16 ops total)
3. Write 4 results back

Loading 4 items: 1 second. Computing 16 ops at 8 ops/s: 2 seconds. Writing 4 items: 1 second. Now compute takes longer than memory. The processor is busy the whole time, and memory has idle moments. This is compute-bound. And now, doubling compute speed to 16 ops/s does help — it cuts the total time.

The Formal Test

For any operation, we can compute two times:

If T_math > T_mem, the operation is compute-bound: compute is the bottleneck. If T_mem > T_math, it's memory-bound: memory is the bottleneck. With overlapped compute and I/O, total time ≈ max(T_math, T_mem).

Chapter 4: Arithmetic Intensity

In the last chapter, we compared T_math and T_mem to decide the bottleneck. There's a more elegant way to express this — a single number that characterizes any operation: the arithmetic intensity.

This measures how much work you do for each byte you move. High arithmetic intensity means you're doing a lot of computation on a small amount of data — the processor stays busy. Low arithmetic intensity means you're constantly shuffling data around with little computation — the processor starves.

The Threshold

We derived the A100's compute-to-memory ratio: ~160 FLOPs/Byte. This is the ridge point — the dividing line between compute-bound and memory-bound:

• If Arithmetic Intensity > 160 FLOPs/Byte → compute-bound (compute is the bottleneck)
• If Arithmetic Intensity < 160 FLOPs/Byte → memory-bound (memory bandwidth is the bottleneck)

Worked Example: Matrix Multiplication

Let's compute the arithmetic intensity of multiplying A [N × K] by B [K × M] to get C [N × M]. We'll count FLOPs and bytes.

FLOPs: Each entry C_ij is a dot product of a row of A and a column of B: K multiplications + K additions = 2K FLOPs. There are N × M entries in C. Total: 2NMK FLOPs.

Bytes: We read A (N×K values), read B (K×M values), and write C (N×M values). In FP16 (2 bytes each): 2(NK + KM + NM) bytes.

Case 1: M = K = 8192, N = 128 (a tall-skinny matrix times a big square one — like a small batch through a large linear layer):

Since 124 < 160, this is memory-bound. The batch is too small to keep the GPU busy.

Case 2: M = K = N = 8192 (three large square matrices):

Since 2,731 >> 160, this is compute-bound. Plenty of work per byte. The GPU is fully utilized.

Common Operations: A Cheat Sheet

Chapter 5: The Roofline Model

We've been asking "is this operation compute-bound or memory-bound?" one operation at a time. The roofline model puts ALL operations on a single diagram and makes the answer visual. It's the most important performance analysis tool in systems engineering.

How It Works

The x-axis is arithmetic intensity (FLOPs/Byte) on a log scale. The y-axis is achievable performance (GFLOPS, also log scale). Two lines form a "roofline":

1. Memory bandwidth ceiling: Performance = Arithmetic Intensity × Memory Bandwidth. This is a diagonal line — the more work you do per byte, the more total FLOPS you can achieve.
2. Compute ceiling: Performance = Peak FLOPS. This is a horizontal line — no matter how high your arithmetic intensity, you can't exceed the hardware's peak compute.

The two lines intersect at the ridge point: the arithmetic intensity where memory bandwidth and compute are perfectly balanced.

Reading the Diagram

Every operation lands somewhere on the roofline. If it's on the diagonal (left of the ridge), it's memory-bound — you improve it by reducing data movement. If it's on the flat ceiling (right of the ridge), it's compute-bound — you improve it by using faster math (Tensor Cores, mixed precision, better algorithms).

Operations that land below the roofline are not reaching their theoretical peak — there's room for optimization. The gap between the roofline and the actual performance tells you how much room you have.

Chapter 6: Tiling & Data Reuse

We've diagnosed the problem: most operations are memory-bound. How do we fix it? The first technique is tiling (also called blocking) — breaking a large operation into small tiles that fit in fast memory (registers/shared memory), so we read from slow HBM once and reuse the data many times.

Naive Matrix Multiply: A Disaster

Consider computing one element of C = A × B. A naive implementation loads one row of A and one column of B, computes the dot product (2K FLOPs), and writes one output. In FP16:

An arithmetic intensity of 0.5. On an A100 with a ridge point of 160, we'd achieve less than 0.3% of peak compute. Catastrophic.

1D Tiling: Reuse Across a Row

What if one thread computes a tile of T_c outputs in the same row of C? It loads 1 row of A and T_c columns of B, and reuses the row of A across all T_c dot products.

For T_c = 2: AI ≈ 4K / (3K+2) ≈ 1.33. Better, but still far from 160.

2D Tiling: The Real Win

Now each thread computes a T_r × T_c tile of C. It loads T_r rows of A and T_c columns of B, reusing both across the tile.

For T_r = T_c = 128, K = 4096: AI = 128 × 128 × 4096 / (128×4096 + 128×4096 + 128×128) ≈ 63.5. Now we're getting somewhere. With larger tiles we can push past the ridge point.

Tiling in Practice

In real GPU programs (CUDA), tiling maps directly to the hardware. A thread block is assigned a tile of the output matrix. The block cooperatively loads its tile of A and B into shared memory (the fast, per-SM cache), then each thread computes its portion from shared memory. This is exactly what NVIDIA's cuBLAS library does under the hood.

Modern Tensor Cores on the A100 compute 4×4 or 8×8 tiles in a single clock cycle, making tiling a hardware-level primitive. When you call torch.matmul, cuBLAS is tiling for you. But for fused operations (Chapter 7), you need to tile manually — which is what FlashAttention does.

Chapter 7: Operator Fusion

Tiling helps us reuse data within a single operation. Operator fusion goes further: it combines multiple operations into a single kernel, so intermediate results never touch slow HBM.

The Problem with Separate Kernels

In a standard PyTorch transformer layer, a sequence of operations might look like this: matmul → bias add → GELU → dropout. Without fusion, each operation is a separate GPU kernel. Each kernel reads its input from HBM, computes, and writes its output back to HBM. The next kernel reads that output from HBM.

The unfused version does 4 separate round-trips to HBM. Bias add, GELU, and dropout are all memory-bound (AI < 1). Their compute time is negligible — they're pure overhead from the memory transfers. Fusing them into the matmul kernel eliminates 3 out of 4 HBM accesses. The intermediate values live in fast registers and shared memory, never touching HBM.

FlashAttention: Fusion's Greatest Hit

The standard attention computation is: Q×K¹ → scale → mask → softmax → dropout → ×V. Without fusion, each step reads/writes full [seq_len × seq_len] matrices to HBM. For a sequence length of 2048, that's 2048² × 2 bytes = 8 MB per intermediate matrix, several times.

FlashAttention fuses the entire attention computation into a single kernel. It tiles the Q, K, V matrices into blocks that fit in shared memory (SRAM), computes attention tile-by-tile, and accumulates the output without ever materializing the full attention matrix in HBM. The result: 2–4× speedup and dramatically less memory usage.

When to Fuse?

Fusion helps most when the operations being fused are memory-bound. Fusing two compute-bound operations doesn't help much — they're already utilizing the hardware well. The sweet spot is fusing a chain of memory-bound operations (bias add, activation, norm, dropout) with a compute-bound one (matmul), so the memory-bound ops ride along "for free."

python
# PyTorch without fusion: 4 separate HBM round-trips
x = torch.matmul(input, weight)     # write to HBM
x = x + bias                        # read + write HBM
x = torch.nn.functional.gelu(x)     # read + write HBM
x = torch.nn.functional.dropout(x)  # read + write HBM

# With torch.compile or a custom kernel: 1 HBM round-trip
# All intermediate results stay in registers
x = fused_matmul_bias_gelu_dropout(input, weight, bias)

Chapter 8: Connections

Let's pull it all together. This lesson covered the fundamental hardware-software interface for ML systems: why hardware matters, how CPUs and GPUs differ, the memory hierarchy, arithmetic intensity, the roofline model, tiling, and operator fusion. These concepts are the foundation of every performance optimization in modern deep learning.

The Principles, Summarized

Real-World Impact

Where to Go From Here

• CS 229s Lecture 5: FlashAttention deep dive — how tiling and fusion combine to make attention hardware-efficient
• CS 229s Lecture 4: Profiling tools — how to measure arithmetic intensity and identify bottlenecks in real code
• Transformer lesson — the architecture whose performance these techniques optimize