TL;DR
This paper introduces PIMLex, a novel learned index designed to overcome the memory bandwidth limitations of traditional computer architectures by leveraging Processing-in-Memory (PIM) technology. PIMLex achieves significant performance improvements by employing a decoupled two-layer structure, a PIM-friendly model design, and a hotness-aware replication mechanism for load balancing.
What Problem Does This Paper Address?
Modern computing systems face a significant bottleneck known as the "memory wall," where the speed of data retrieval from memory lags far behind the processing speed of CPUs. This is particularly problematic for data-intensive applications like learned indexes, which rely heavily on frequent memory accesses for both model computations and data lookups. Existing learned indexes, while outperforming traditional ones, are still constrained by this memory wall. Processing-in-Memory (PIM) technology, which integrates processing units directly into memory devices, offers a promising solution. However, applying learned indexes to PIM architectures presents several challenges:
- Limited PIM Capacity: PIM devices (like UPMEM DIMMs) have significantly smaller capacities (e.g., 8GB) compared to conventional DRAM (e.g., 64GB), while learned indexes can consume substantial memory.
- Model Structure Mismatch: Learned indexes often use complex models involving floating-point operations, which are not efficiently supported by current PIM hardware, leading to performance degradation.
- Load Imbalance: In distributed PIM systems, skewed access patterns can lead to some PIM modules being overloaded while others remain idle, hindering overall performance.
Methods
PIMLex tackles these challenges with a multi-pronged approach:
- Decoupled Two-Layer Structure: PIMLex separates the index into two layers:
- Search Layer (PIM): This layer resides on PIM modules and stores sampled "anchor keys" along with lightweight models trained on these keys. Its primary role is to quickly identify the approximate location of a target key. This significantly reduces the PIM capacity requirement.
-
Data Layer (DRAM): This layer, residing in conventional DRAM, stores the complete dataset (keys and values) and handles actual data retrieval and updates. This design shifts most memory accesses to the PIM modules while minimizing PIM space usage.
-
PIM-Friendly Model Structure: To address the computational limitations of PIM, PIMLex employs two key optimizations:
- Optimized Model Search: Instead of relying solely on hierarchical multi-level models, PIMLex incorporates a global binary search option for upper levels. This reduces computational overhead by increasing memory accesses, which PIM excels at.
- Lookup-Table Based Models: PIMLex uses lookup tables to pre-compute results for high-bit multiplications, effectively eliminating floating-point operations during model predictions. This trades increased memory access for reduced computation.
- Hotness-Aware Replication Mechanism: To combat load imbalance in skewed workloads, PIMLex dynamically creates replicas of search layer partitions across multiple PIM modules. Partitions with higher access frequencies ("hotness") receive more replicas, distributing the load more evenly. This mechanism is designed to be adaptive to changing workload patterns.
Datasets
The paper evaluates PIMLex using five real-world datasets:
- Books (Amazon book sales popularity)
- Osm (OpenStreetMap cell IDs)
- FB (Facebook user IDs)
- Genome (Human chromosome pairs)
- Planet (OpenStreetMap Planet IDs)
These datasets vary in size, with some containing up to 800 million key-value pairs. The workloads include Get-only, Insert-only, and mixed (Get/Insert) operations, often generated using the YCSB benchmark with Zipfian distributions to simulate skewed access patterns.
Key Insights and Ideas
- PIM is a Natural Fit for Learned Indexes: The inherent memory-bound nature of learned indexes makes them prime candidates for PIM acceleration, but careful design is crucial to harness PIM's strengths.
- Decoupling is Key for PIM Capacity: The success of PIMLex hinges on its decoupled architecture, allowing it to leverage PIM's speed without being constrained by its limited capacity. This is a crucial insight for designing PIM-aware data structures.
- "Trading Memory for Computation" is a Winning Strategy on PIM: PIM's strength lies in its massive memory bandwidth, not its raw computational power. PIMLex's model design effectively exploits this by favoring memory accesses over complex calculations.
- Dynamic Load Balancing is Essential for Skewed Workloads: Simply distributing data across PIM modules isn't enough. PIMLex's hotness-aware replication is vital for maintaining performance when certain data partitions are accessed far more frequently than others.
Key Results
- Significant Throughput Gains: PIMLex achieves up to 36.5x higher throughput than a PIM-based learned index baseline (BasicLex) and 2.2x higher throughput than the DRAM-based ALEX index.
- Memory Efficiency: PIMLex demonstrates significant memory efficiency, using very little PIM space due to its decoupled structure. This allows it to handle larger datasets effectively.
- Robustness to Skewed Workloads: The hotness-aware replication mechanism significantly improves performance under skewed workloads, reducing execution time by up to 15x compared to a baseline without load balancing.
- PIM-Friendly Models Outperform Traditional Ones: The PIM-friendly model structure leads to shorter execution times on PIM compared to traditional multi-level models, even outperforming a pure binary search approach in some cases.
Limitations and Future Work
- CPU-PIM Bandwidth: The paper notes that the CPU-PIM bandwidth is significantly slower than CPU-DRAM bandwidth, which impacts performance. Future PIM architectures with enhanced CPU-PIM bandwidth could further boost PIMLex's performance.
- Insert Performance: While PIMLex excels in Get operations, insert performance is limited by DRAM-based data layer writes. The authors suggest that placing the data layer on PIM could improve this, but this is currently constrained by PIM capacity.
- Anchor Interval Trade-off: A larger anchor interval reduces PIM space but can lead to more memory accesses and slightly degraded Get performance. The optimal interval depends on dataset size and access patterns.
- Future PIM Capabilities: The authors anticipate that as future PIM devices offer improved computational capabilities, PIM-based learned indexes will achieve even greater performance. They also suggest that PIMLex's design is adaptable to other PIM architectures beyond UPMEM.
Summary updated