Search papers, labs, and topics across Lattice.
This paper investigates the use of Processing-in-Memory (PIM) systems for accelerating R-tree-based spatial range queries, targeting the memory bandwidth bottleneck in large spatial datasets. They propose a broadcast-based method that constructs the R-tree on the CPU, broadcasts top levels to UPMEM DPUs for filtering, and distributes lower levels for parallel batched queries. Experiments on real and synthetic datasets using a commercial UPMEM PIM system demonstrate significant speedups (up to 3.66x kernel and 2.70x end-to-end) and energy savings (3.4x) compared to CPU-based R-tree search.
Spatial queries on massive datasets can be sped up by 3.6x and consume 3.4x less energy by pushing computation directly into memory using a commercial processing-in-memory system.
The growing volume of data in scientific domains has made spatial query processing increasingly challenging due to high data transfer costs across the memory hierarchy and limited memory bandwidth. To address these bottlenecks and reduce the energy consumed on data movement, this work explores Processing-in-Memory (PIM) systems by executing range queries directly inside memory chips. Unlike prior PIM studies centered on linear scans or hash-based queries, this work is the first to map R-tree range queries onto commercial PIM hardware. The proposed broadcast-based method constructs the R-tree bottom-up on the CPU, broadcasts top levels to UPMEM DPUs (DRAM Processing Units) for global filtering, and distributes lower levels for parallel batched queries in a CPU-DPU system. We evaluate our approach on two real spatial datasets, Sports (999K rectangles) and Lakes (8.4M rectangles), and assess scalability using a synthetic dataset with up to 16M rectangles and 3.9M queries on a commercial UPMEM PIM system with up to 2,540 DPUs. Across all datasets, broadcast-based execution consistently outperforms subtree partitioning by preventing communication from dominating execution. On the Lakes dataset, strong scaling from 512 to 2,540 DPUs reduces kernel time from 64.9 s to 17.6 s, yielding up to 3.66x kernel and 2.70x end-to-end speedup relative to the CPU R-tree search on the same system. The PIM kernel also consumes approximately 3.4x less energy than the corresponding CPU search (e.g., 59.6 kJ vs. 167.0 kJ on Lakes), demonstrating scalable and energy-efficient hierarchical spatial range queries.
