Instruction Level Parallelism and Software Performance
summary
Claims that instruction dependencies, not CPU silicon, limit performance and that loads cost three cycles while adds cost one cycle are demonstrated with concrete loops: a simple A[i]+B[i] loop needs about seven cycles with unlimited resources, a reduction costs ~n3 cycles, and a pointer-chasing linked list falls to ~seven-cycle chains per node. Concrete fixes include interleaving dependency chains, loop unrolling (measured ~15% win for a manual unroll), loop pipelining, and arrayizing trees (pointer vs array example gives ~20–30s vs ~80s). Measurement tools: LVMCA* and Intel top-down microarchitecture analysis.
AI-written summary · about
chapters (20)
- 0:00Instruction level parallelism intro
- 1:25CPU instruction execution
- 3:37Dependency chains limit perf
- 6:24Measuring parallelism in loops
- 8:52Dependency chains in reductions
- 10:59Pointer chasing in linked lists
- 14:32Dependencies vs compiler optimizations
- 16:59Latency vs throughput in CPU
- 19:07Techniques to increase instruction level parallelism
- 24:24Interleaving dependency chains
- 29:43Challenges of interleaving
- 30:45Shortening dependency chains
- 35:00Optimizing binary trees & lists
- 37:07Reducing dependency passes
- 38:12Breaking data structure chains
- 40:40Out-of-order processors & deps
- 44:55Loop unrolling for in-order CPUs
- 46:41Tools for ILP analysis
- 55:33LLVM MCA for performance
- 1:00:54Best practices & future workshops
related talks
01h 04mBranchless Programming in C++
01h 37mAn Overview of Program Optimization Techniques
01h 05mPerformance Optimization in Software Development - Being Friendly to Your Hardware
01h 06mCPU Cache Effects
51mJava vs CPU — round 2
01h 00m“Want fast C++? Know your hardware!"
58mOptimization Tips - Mo' Hustle Mo' Problems
01h 06mPerformance engineering: being friendly to your hardware