Cache-Optimize a Graph-Analytics Kernel for a Social Platform
Overview
What this challenge is about.
Receive the existing kernel (C++ + OpenMP, around 1,200 lines), the 1.8B-edge graph (CSR format, around 14GB), and target hardware (dual-socket AMD EPYC 9354, 384GB DDR5, 256MB L3 per socket). Profile the current kernel with perf c2c + likwid to confirm bandwidth-bound vs. latency-bound behavior. Apply 3 stacked optimizations: (1) vertex reordering using Gorder or RCM to maximize locality, (2) cache-blocking the traversal with a block size tuned to L3, (3) software prefetching at appropriate look-ahead distance. Benchmark each optimization individually + cumulatively. Validate result equivalence against the baseline on 100 sampled queries. Deliver the optimized kernel, the reordered graph artifact, a benchmark report, a per-optimization speedup waterfall, and a 5-page write-up for the recsys team.
The Brief
What you'll do, and what you'll demonstrate.
Re-design a friend-of-friend graph kernel for cache locality (reordering + blocking + prefetching) and prove 6-10x speedup with result equivalence.
Earning criteria — what you'll demonstrate
- Distinguish bandwidth-bound vs. latency-bound kernels with perf + likwid
- Apply vertex reordering (Gorder, RCM) to graph workloads
- Tune cache-blocking and software prefetching for a real CPU
- Validate optimization equivalence honestly on sampled queries
Program Fit
Where this fits in your program.
Sharpens the same skills your degree expects you to demonstrate.
Skills
Skills you'll demonstrate.
Each one shows up on your verified credential.
Careers
Roles this prepares you for.
Real titles. Real skill bridges. Pick the one closest to your trajectory.
Career mappings coming soon.