Efficient Approximations for Cache-conscious Data Placement
summary
Shows a linear-time 1+ε approximation for minimizing cache misses in direct-mapped caches under a sparsity assumption on the access graph, reducing placement to k-coloring a sparsified hypergraph and solving via a bottom-up tree DP. Runtime is linear in number of items and accesses but exponential in k, the cache size; formal hardness results still hold for general instances. Experiments report improvement over heuristics in 84–88% of small-cache cases.
AI-written summary · about
chapters (11)
- 0:00Introduction
- 0:49Cache-conscious placement problem
- 3:03Placement map and optimal
- 4:31Hardness results and gap
- 5:35Sparsity-based approximation
- 8:25Cache miss assumptions
- 10:34One plus epsilon proof
- 12:00Hypergraph coloring and DP
- 14:05Conclusion and limits
- 15:09Q&A multi-threaded
- 15:49Q&A real-world
related talks
47mHardness Amplification and the Approximate Degree of Constant-Depth Circuits
20mFast and Optimal Extraction for Sparse Equality Graphs
18mRapid: Region-Based Pointer Disambiguation
01h 12mLightning Talks by Simons Institute Fellows
20mExploiting Sparsity and Redundancy
25mAUTOMAP: Inferring Rank-Polymorphic Function Applications with Integer Linear Programming
17mA Better Approximation for Interleaved Dyck Reachability
14mFast Linear Programming through Transprecision Computing on Small and Sparse Data