Principled algorithm, data structure and system design for Processing-in-Memory (PIM)”
summary
A design builds semi-balanced trees for Processing-in-Memory that cut worst-case search communication from log n down to log star P by decomposing the tree into log-star groups, adding dual-way caching for bidirectional search, and using probabilistic Steele-style counters to avoid costly updates. A matching lower bound shows the space/communication tradeoff is optimal up to constants, requiring ~n log star P space. Implementation on UPMEM 2048 PIM cores reports higher throughput than shared-memory baselines and large reductions in memory traffic.
AI-written summary · about
chapters (20)
- 0:00PIM introduction and goals
- 1:03PIM model overview
- 2:07PIM tree accelerations limits
- 2:52Log star P decomposition
- 4:39Tree layer replication
- 6:50Log star P groups overhead
- 7:54Log star P results
- 8:37Dual-way caching
- 10:25Decomposition and caching benefits
- 11:07Log star P optimality proof
- 12:31Cell-probe lower bounds
- 13:37Cell-probe model and Q&A
- 16:06Semi-balanced trees for kd-trees
- 17:34Subtree size tracking challenges
- 18:40Approximate subtree counters
- 19:47Algorithm bounds and properties
- 20:29Clustering and Morton trees
- 22:15Morton order trees results
- 23:22PIM augmented trees problems
- 24:29Summary and Q&A
related talks
13mMemPool Flavors: Between Versatility and Specialization in a RISC-V Manycore Cluster
01h 21mPanel+Closing
35mSQUIP or Why We Need to Study Processors Like Nature
58m“SPMD Programming Using C++ and ISPC"
49mGraph Based Processing of Big Images
27mConsistency and Coherence of the NVIDIA Grace-Hopper Superchip
13mPalleon: A Runtime System for Efficient Video Processing toward Dynamic Class Skew
37m"Algorithms" is Not a Four-Letter Word