Course: MSCS 532 — Algorithms and Data Structures
University of the Cumberlands
Instructor: Dr. Michael Solomon
This project demonstrates cache and memory locality optimization, the single most common microarchitecture fix identified in Azad et al. (2023), which analyzed 1,729 performance commits across 23 open-source HPC projects. Locality optimization appeared in 42 of 186 confirmed performance bugs (21% of all bugs).
The prototype shows that two implementations with identical O(n²) asymptotic complexity can differ significantly in practice due to memory access patterns and cache behavior.
| File | Description |
|---|---|
cache_locality.py |
Python prototype — two locality experiments with benchmarks |
cache_locality_results.png |
Benchmark comparison chart (auto-generated) |
Requirements: Python 3.8+, NumPy, Matplotlib
sudo apt install python3-numpy matplotlib
python3 cache_locality.pyThis runs correctness verification, benchmarks two experiments, prints a results table, and saves cache_locality_results.png.
Compares row-major vs column-major traversal of a 2D Python list. Row-major accesses elements within the same list object sequentially (cache-friendly). Column-major jumps between separate list objects on each inner iteration (cache-unfriendly).
NumPy stores arrays in C-order (row-major) by default. Iterating row-by-row accesses contiguous memory and exploits spatial locality. Iterating column-by-column strides across memory with a step equal to the row width, triggering cache misses at each step once the array exceeds cache capacity.
At a 2,000 x 2,000 NumPy array, column-wise summation is approximately 5x slower than row-wise summation — despite identical O(n²) complexity. The divergence reflects the point at which the array exceeds L1/L2 cache capacity and every column access must fetch from slower memory.
Azad, M. A. K., Iqbal, N., Hassan, F., & Roy, P. (2023). An empirical study of high performance computing (HPC) performance bugs. Proceedings of the 20th IEEE/ACM International Conference on Mining Software Repositories (MSR 2023). https://foyzulhassan.github.io/files/MSR23_HPC.pdf