PIM-tree: A Skew-resistant Index for Processing-in-Memory
summary
PIM-tree and PIM-trie are skew-resistant PIM indexes that use push-pull search, top-layer replication and shadow subtrees (eager precaching) to keep search to about log log p rounds and updates amortized constant while using linear space. Implementation uses chunking (B-skiplist, B≈16), a batching/query-trie matching step, and a hierarchical block-hash decomposition; on a 2,000-module prototype (450 MHz, 64MB local) queries use 3–4 memory-round trips and inserts outperform B-trees.
AI-written summary · about
chapters (15)
- 0:00PIM-tree introduction
- 1:07Batch search trees and bottlenecks
- 4:35PIM-tree design and replication
- 7:10Push-pull search for balance
- 10:50Shadow subtree for locality
- 13:46Complexity analysis
- 15:59B-skiplist and chunking
- 17:23Experimental results
- 22:38PIM-trie for string keys
- 24:06Query trie and matching
- 27:05Hierarchical decomposition
- 31:45Precaching in PIM-trie
- 34:41Summary of PIM-trie
- 35:25Common techniques
- 35:48Q&A on PIM parameters
related talks
13mMemPool Flavors: Between Versatility and Specialization in a RISC-V Manycore Cluster
17mLifting to Parity Decision Trees Via Stifling
13mPalleon: A Runtime System for Efficient Video Processing toward Dynamic Class Skew
37m"Algorithms" is Not a Four-Letter Word
35mSQUIP or Why We Need to Study Processors Like Nature
20mText Search on Images with Quantized ColPali
45mTurning Off‑the‑Shelf Tools into a Petabyte‑Scale System
01h 02mFine-Grained Counting Complexity I