Managing High-Bandwidth Memory is a Parallel Scheduling Problem
summary
Argues that minimizing page transfers is the wrong objective: an algorithm that minimizes transfers can be Ω(p) worse for running time. Models HBM with k pages and p disjoint-access threads (assume k > p), shows LRU + FCFS is maximally bad, and gives a priority policy that is O(1)-competitive for makespan. Reduces HBM to a new semi-normal parallel-job scheduling model via chunking, proves a black-box conversion: any α-competitive scheduler yields an α-competitive HBM algorithm, and round-robin gives O(1) for mean completion.
AI-written summary · about
chapters (8)
- 0:00High-bandwidth memory intro
- 2:05HBM vs traditional cache
- 6:54Simplest HBM setup
- 9:27Why FCFS fails
- 13:50Better theoretical model
- 19:44Semi-normal scheduling
- 25:52Open problems
- 33:00Q&A
related talks
14mStrategies for CXL’s success in a world of proprietary Coherent...
49mHVM - A Massively Parallel Architecture
27mAll-Norm Load Balancing in Graph Streams via the Multiplicative Weights Update Method
01h 04mThe challenge of managing parallelism and data-movement for tensor computations on GPUs
40mResilience of 3-Majority Dynamics to Non-Uniform Schedulers
10mA Programming Model for Efficient Inter-Kernel Control-Flow on Memory-Mapped Near-Data(…)
26mLower Bounds on the Running Time for Scheduling and Packing Problems
20mBeyond Worst-Case Budget-Feasible Mechanism Design