Approximate nearest neighbor search (ANNS) is a fundamental operation in modern vector databases to efficiently retrieve nearby vectors to a given query.On general-purpose computing platforms, ANNS is found not only to be highly memory-bound due to the large amount of high-dimensional vectors to access, but also exhibits very low utilization of the fetched data as many memory accesses and computations are wasted on not-so-nearby vectors.To alleviate these two inefficiencies, we propose a hardware-software co-design that integrates near-data processing architectures with a novel hybrid partial-dimension/bit early termination strategy.Distance calculation and comparison in ANNS are offloaded to the near-data processing units at the memory rank level.As a vector is being gradually fetched from memory, we conservatively estimate a lower bound of its distance to the query using the partially fetched data, e.g., a subset of dimensions and/or partial bits of each element.If this lower bound already exceeds a threshold, we could early terminate to avoid future unnecessary data accesses and computations.In the presence of such irregular early termination execution flow, we further optimize the data layouts within a single memory access and across multiple memory ranks in the system, and handle efficient coordination between the near-data units and the host processor that executes the rest of index traversal and result sorting.With all the above optimizations, our design demonstrates an average 5.26× speedup of using near-data processing, and another 1.52× from enabling hybrid early termination on top of it.

Hybrid main memory systems combine both performance and capacity advantages from heterogeneous memory technologies. With larger capacities, higher associativities, and finer granularities, hybrid memory systems currently exhibit significant metadata storage and lookup overheads for flexibly remapping data blocks between the two memory tiers. To alleviate the inefficiencies of existing designs, we propose Trimma, the combination of a multi-level metadata structure and an efficient metadata cache design. Trimma uses a multi-level metadata table to only track truly necessary address remap entries. The saved memory space is effectively utilized as extra DRAM cache capacity to improve performance. Trimma also uses separate formats to store the entries with non-identity and identity address mappings. This improves the overall remap cache hit rate, further boosting the performance. Trimma is transparent to software and compatible with various types of hybrid memory systems. When evaluated on a representative hybrid memory system with HBM3 and DDR5, Trimma achieves up to 1.68 × and on average 1.33 × speedup benefits, compared to state-of-the-art hybrid memory designs. These results show that Trimma effectively addresses metadata management overheads, especially for future scalable large-scale hybrid memory architectures.

Various near-data processing (NDP) designs have been proposed to alleviate the memory wall challenge for data-intensive applications. Among them, near-DRAM-bank NDP architectures, by incorporating logic near each DRAM bank, promise the highest efficiency and have already been commercially available now. However, due to physical isolation, fast and direct cross-bank communication is impossible in these architectures, limiting their usage to only simple parallel patterns. Applications may also suffer from severe load imbalance if each bank contains data with diverse computation loads. We thus propose NDPBridge, with novel hardware-software co-design to enable cross-bank communication and dynamic load balancing for near-bank NDP systems. We introduce hardware bridges along the DRAM hierarchy to coordinate message transfers among banks. The hardware changes are constrained and do not disrupt the existing DDR links and protocols. We further enable hierarchical and data-transfer-aware load balancing, built upon the above hardware communication path and a task-based programming model. The data transfer overheads are minimized with several novel optimizations to hide latency, avoid congestion, and reduce traffic. Our evaluation shows that NDPBridge significantly outperforms existing NDP designs by $2.23 \times$ to $2.98 \times$ on average.

The data access bottleneck in memory-intensive applications has motivated various architectural innovations in the main memory system, with Near-Data Processing (NDP) and Compute Express Link (CXL) as two recent prominent representations. In this work, we focus on addressing the memory capacity limitation of 3D-stacked NDP systems using CXL-based extended memory, where the DRAM space of the 3D NDP stacks is used as the cache of the CXL-based memory. Nevertheless, this architecture exhibits unique challenges to address the significant interconnect latency and expensive metadata management problems. We propose NDPExt, a hardware-software co-design approach to achieve efficient NDP with extended memory. On the hardware side, NDPExt uses coarse-grained data streams rather than conventional fine-grained cachelines to manage the NDP stacks as a distributed DRAM cache, in order to reduce metadata cost and apply custom optimizations to different data. On the software side, NDPExt periodically derives the optimized cache configuration to allocate the DRAM cache space to each stream based on profiled miss behaviors. The configuration cooptimizes capacity sizing, spatial placement, and data replication. Combining the two techniques allows NDPExt to achieve 1.41× on average and up to 2.43× performance improvements over state-of-the-art cache management solutions.

Integrating hybrid memories with heterogeneous processors could leverage heterogeneity in both compute and memory domains for better system efficiency. To ensure performance isolation, we introduce Hydrogen, a novel hardware architecture to optimize the allocation of hybrid memory resources to heterogeneous CPU-GPU systems. Hydrogen supports efficient capacity and bandwidth partitioning between CPUs and GPUs in both memory tiers. With the key observation that CPUs and GPUs exhibit distinct preferences to memory capacity and bandwidth, Hydrogen enables decoupled capacity and bandwidth allocation between CPUs and GPUs with flexible partitioning ratios. It also throttles overly excessive data migration from GPUs with a token-based mechanism. To effectively explore the large, multi-dimensional design space and support dynamically varying application behaviors, Hydrogen uses epoch-based online search for optimized configurations, and incorporates lightweight reconfiguration with reduced data movements. Combining these novel techniques, Hydrogen significantly outperforms existing designs by $1.16 \times$ on average, and up to $1.31 \times$.

Hybrid memory systems are able to achieve both high performance and large capacity when combining fast commodity DDR memories with larger but slower non-volatile memories in a heterogeneous way. However, it is critical to best utilize the limited fast memory capacity and slow memory bandwidth in such systems to gain the maximum efficiency. In this paper, we propose a novel hybrid memory design, Baryon, that leverages both memory compression and data sub-blocking techniques to improve the utilization of fast memory capacity and slow memory bandwidth, with only moderate metadata overheads and management complexity. Baryon reserves a small fast memory area to efficiently manage and stabilize the irregular and frequently varying data layouts resulted from compression and sub-blocking, and selectively commits only stable blocks to the rest fast memory space. It also adopts a novel dual-format metadata scheme to support flexible address remapping under such complex data layouts with low storage cost. Baryon is completely transparent to software, and works with both cache and flat schemes of hybrid memories. Our evaluation shows Baryon achieves up to 1.68× and on average 1.27× performance improvements over state-of-the-art designs.

Indexing structures are widely used in modern data-processing applications to support high-performance queries, and there are a variety of recent designs specifically optimized for the newly available persistent memory (PM). The primary focus of previous PM indexes is on reducing the expensive PM writes for persisting data. However, we find that in tree-based PM indexes, because of the smaller performance gap between writes and random reads on real PM devices, the read-intensive tree traversal phase dominates the overall latency. This observation calls for further optimizations on existing indexing structures for PM. In this paper, we propose Extendible Radix Tree (ERT), an efficient indexing structure for PM that significantly reduces tree heights to minimize random reads, while still maintaining fast in-node search speed. The key idea is to use extendible hashing for each node in a radix tree. This design allows us to have a relatively large fanout of the radix tree to keep the tree height small, and also to realize constant-time lookups within a node. Using extendible hashing also allows for incremental node modification without excessive writes during inserts and updates. Range queries are efficiently and robustly handled by enforcing partial ordering among the keys in the hash table of each node without introducing more hash collisions. Our experiments on both synthetic and real-world data sets demonstrate that ERT achieves up to 2.65×, 4.41×, and 2.43× speedups for search, insert, and range queries over the respectively state-of-the-art PM index.