Abstract

Data movement is fast becoming the dominant cost in computing. Processing-in-Memory (a.k.a., near-data-processing), an idea dating back to 1970, is now emerging as a key technique for reducing costly data movement, by enabling computation to be executed on compute resources embedded in memory modules. While there has been considerable recent work on the architecture/technology side of PIM, there has been very little work addressing the theory/programming side. Open problems include: How should programming and algorithm design on PIM systems differ from traditional parallel or distributed settings? What are the fundamental limitations and trade-offs in using PIM?
This talk highlights our results-to-date addressing these questions. As a driving application kernel, we focus on designing PIM-friendly indexes, i.e., what are PIM-optimized replacements for B-trees, radix trees, and kd-trees? Our indexes address head-on the inherent tension between minimizing communication and achieving load balance in PIM systems, achieving provable guarantees regardless of query or data skew. Experimental results on UPMEM’s 2,560-module PIM system demonstrate that our indexes outperform prior PIM indexes by up to 59x. Finally, we report on our ongoing work designing and implementing a PIM-friendly OLTP database.

Video Recording