Optimal Batch-Dynamic kd-trees for Processing-in-Memory with Applications
The kd-tree is a widely used data structure for managing multidimensional data. However, most existing kd-tree designs suffer from the memory wall---bottlenecked by off-chip memory latency and bandwidth limitations. Processing-in-memory (PIM), an emerging architectural paradigm, offers a promising solution to this issue by integrating processors (PIM cores) inside memory modules and offloading computational tasks to these PIM cores. This approach enables low-latency on-chip memory access and provides bandwidth that scales with the number of PIM modules, significantly reducing off-chip memory traffic.
Authors
- Phillip B. Gibbons (ORCID: https://orcid.org/0000-0001-6967-2735)
- Charles McGuffey (ORCID: https://orcid.org/0000-0002-6281-4435)
- Guy E. Blelloch (ORCID: https://orcid.org/0000-0003-0224-9187)
- Laxman Dhulipala (ORCID: https://orcid.org/0000-0003-0685-064X)
- Hongbo Kang (ORCID: https://orcid.org/0009-0009-9672-6490)
- Yan Gu (ORCID: https://orcid.org/0000-0002-4392-4022)
- Yiwei Zhao (ORCID: https://orcid.org/0000-0002-2586-8311)
Institutions
- University of California, Riverside (US)
- Reed College (US)
- University of Maryland, College Park (US)
- Carnegie Mellon University (US)
- Tsinghua University (CN)
Publication Details
- Published
- 2025-07-16
- DOI
- https://doi.org/10.1145/3694906.3743318
- Citations
- 4
- Primary Topic
- Advanced Data Storage Technologies
- Type
- article
- Field-Weighted Citation Impact
- 5.95
Funders
- National Science Foundation
- Western Digital
- Samsung