Lecture 1: Introduction and Matrix Multiplication

What this lecture covers

This opening lecture answers a basic question: why study performance engineering when correctness, deadlines, and cost usually matter more to programmers? Charles Leiserson frames performance as a currency you spend to buy other properties, like usability or security, and traces how the end of clock-speed scaling around 2004 forced the industry toward multicore chips, making parallel programming unavoidable.

The rest of the lecture is a live case study: starting from a naive matrix multiplication in Python, the class incrementally applies language choice, loop ordering, compiler flags, multicore parallelism, cache-aware tiling, divide-and-conquer recursion, and vector instructions. After watching, you should be able to explain why each optimization works and estimate how far a piece of code is from a machine's peak floating-point performance.

Key ideas

• Performance as currency: performance has no intrinsic value but is spent to buy properties like readability, security, or portability.
• End of Dennard scaling: around 2004, power density stopped clock speeds from increasing further, ending the era of free performance from faster hardware.
• Multicore as the response: unable to raise clock speed, chip makers added more cores per chip, making parallel programming necessary to use new hardware.
• Peak performance: a machine's theoretical maximum flops, computed from clock rate, cores, and floating-point units per core, used as a baseline to judge how far code is from optimal.
• Spatial locality and cache lines: memory is fetched in fixed-size blocks, so access patterns that touch nearby addresses (like row-major traversal) are far cheaper than scattered ones.
• Tiling (blocking): restructuring a computation to work on small sub-blocks that fit in cache drastically cuts the number of memory accesses.
• Divide-and-conquer with a base case: recursive algorithms reduce cache misses further, but need a cutoff size (a base case) to avoid function-call overhead dominating at small sizes.
• Vectorization (SIMD): a single instruction can operate on multiple data words at once, giving further speedup when the compiler or programmer uses vector instructions explicitly.

Walkthrough

Why performance still matters (0:01)

Leiserson opens by noting that programmers usually rank performance below correctness, deadlines, or cost, then argues performance is the "currency" that gets traded for those other properties. He reviews quotes from Donald Knuth, Bill Wulf, and Michael Jackson warning against premature optimization, and shows historical data on Moore's Law and Dennard scaling: until 2004, waiting for faster hardware was often cheaper than optimizing code by hand.

From free speedups to multicore (10:04)

He explains why clock speeds plateaued: rising power density from leakage current, not just dynamic switching power, made further frequency scaling unsafe. Chip vendors responded by adding multiple processing cores per chip instead. This shift means performance is no longer automatic; developers must write parallel code to benefit from new hardware, a trend reflected in rising mentions of "performance" in bug reports and job postings.

Setting up the matrix multiplication case study (15:05)

The class is introduced to the target machine: an 18-core Haswell system with a stated peak of about 836 gigaflops. Using a standard triply nested loop for multiplying two 4096x4096 matrices, the naive Python version takes about 21,000 seconds, reaching roughly 0.00075% of peak. Rewriting the identical algorithm in Java cuts the time to about 46 minutes, and in C to about 19 minutes, because compiled code skips the overhead of interpretation.

Loop order and compiler flags (29:25)

Reordering the three nested loops without changing the math changes the running time by a factor of 18, because different orders access matrix B with different spatial locality: sequential access hits cache lines efficiently, while striding through columns wastes most of each fetched cache line. Choosing the best loop order and then enabling compiler optimization flags (-O2 outperforming -O3 in this case) each buy a further speedup with no algorithmic change.

Parallelizing across cores (36:31)

Using Cilk's parallel loop construct on the outer loop gives close to an 18x speedup on 18 cores, but the lecture notes that parallelizing inner loops instead can actually slow the program down due to scheduling overhead. The rule given is to parallelize outer loops, not inner ones.

Cache tiling and divide-and-conquer (39:34)

Computing the matrix product in tiles rather than full rows cuts total memory accesses roughly 30-fold for this problem size, because a tile's data fits in cache and gets reused. The lecture extends this to multiple cache levels and then shows a recursive divide-and-conquer formulation that tiles automatically at every level of granularity, provided a base-case cutoff (found by experiment to be around 32) is used to avoid excessive function-call overhead at small sizes.

Vectorization and the final result (51:43)

The final stage uses the machine's SIMD vector units, first letting the compiler vectorize automatically with architecture-specific and fast-math flags, then using explicit AVX intrinsics. The cumulative result is about 41% of peak performance and a roughly 50,000x speedup over the original Python code, matching or exceeding Intel's math kernel library on this particular matrix size.

Before you watch

• No prior lectures are required; this is the first lecture of the course.
• Basic familiarity with nested loops, arrays, and matrix multiplication is assumed.
• Knowing that CPUs have caches and multiple cores helps, though the lecture explains these as it goes.

Check your understanding

1. Why did software performance stop improving "for free" around 2004, and how did hardware vendors respond?
2. Why does the order of the three nested loops in matrix multiplication affect running time so much, even though all orders compute the same result?
3. What problem does tiling solve, and why does divide-and-conquer recursion need a base-case cutoff?
4. Why can parallelizing an inner loop be slower than parallelizing an outer loop?
5. What does it mean to say a program is running at some percentage of a machine's peak performance?