Towards Enabling Distance-Based Memory Addressing

1 Introduction

• ANNS requires fetching the full dataset for brute-force search, while existing compression- and graph-based indices trade bandwidth efficiency, accuracy, and indexing overhead.High-dimensional search is difficult to accelerate because high recall often requires visiting a large fraction of the vectors.Source: §1 · p. 1
• DAM uses internal memory bandwidth for approximate data-independent brute-force search, then uses the resulting distances to prune the search space in parallel.This makes pruning a post-processing step rather than a pre-filter.Source: §1 · p. 1
• The proposed algorithm generates per-query approximate distances across vector datasets and supports multiple distance metrics through a simple reformulation.The system pairs a lightweight near-array processor with a 1T-1R memory array and uses distances for pruning and bandwidth-efficient reranking.Source: §1 · p. 2
• Near-perfect accuracy accompanies 52.7× throughput and 97× latency improvement over a state-of-the-art compression-based approach on Intel Xeon E5-2680; each DAM chip uses 50% more area but improves energy 4.15× on average.The evaluation is simulation-based and covers a wide variety of real-world embedding datasets.Source: §1 · p. 2

2.1 Similarity Search

• Exact k-nearest-neighbor search in high dimensions requires O(N × D) brute force, while ANNS relaxes exactness to maximize recall under a latency/QPS trade-off.The paper describes ANNS as finding similar objects using a distance metric; recall-k@k measures overlap with the ground-truth neighbors.Source: §2.1 · p. 2
• Product quantization compresses vectors into codeword IDs, and IVF narrows search to nearby clusters; graph methods traverse neighborhood links, with higher recall requiring deeper, bandwidth-intensive search.PQ reduces memory footprint and distance-computation bitwidth, while graph methods incur indexing overhead; Figure 1 illustrates PQ.Source: §2.1.1 · pp. 2–3, Figure 1 · p. 2, §2.1.2 · p. 3

2.2 Memristive Array Structure

• The paper prefers a 1T1R cell over denser 1R crosspoints because its in-situ approach requires isolated column access.Figure 2 depicts the 1T-1R memory cell.Source: §2.2 · p. 3, Figure 2 · p. 3

2.3 Motivation

• Compression-based indices can remain bandwidth-bound and achieve recall-k@k ≤ 0.6 on performant configurations, while graph indices support high recall but incur indexing overhead and bandwidth-inefficient traversal.The paper attributes compression-based recall loss partly to centroid pruning and lack of raw data for reranking.Source: §2.3 · p. 3
• Existing indices struggle with out-of-distribution queries, fresh vectors, and filtered searches; DAM is presented as extending support for these application needs.The paper identifies data-dependent index generation, periodic updates, and pairwise-distance neighborhood information as challenges, and Table 1 summarizes the motivation.Source: §2.3 · p. 3, Table 1 · p. 3

3 Distance-Aware Pruning

• The method performs fast approximate brute-force distance computation across the full dataspace, then prunes as a post-processing step.This reverses the conventional pre-filtering order described for state-of-the-art algorithms.Source: §3 · pp. 3–4

3.1 Runtime Quantization of Data

• Masking the M least significant bits quantizes fixed-point values from 2^N to 2^(N−M) representation levels, each representing 2^M original values.The passage states that this applies to signed and unsigned fixed-point numbers.Source: §3.1 · p. 4

3.2 1-D Pruning Algorithm

• In one dimension, the algorithm generates keys associated with distances, XNOR-matches quantized vectors to those keys, and ranks matches by their quantized distance to the query.The example selects the three vectors closest to the query in quantized space.Source: §3.2 · p. 4

3.3 Multidimensional Distance Generation

• Because dimension-wise aggregation has an irregular tree-like access pattern, the algorithm sums counts of matching dimensions per key multiplied by that key’s distance contribution.The resulting unified quantized distance is computed using comparison/XNOR, counting, and addition.Source: §3 · p. 4, §3.3 · p. 5
• Although the upper bound on possible distances is (2^N−M)^2, valid keys per query are empirically much fewer, and iterations depend on valid per-dimension key values.The passage also notes that this avoids ineffectual comparisons across dimensions.Source: §3.3 · p. 5

4 DAM Architecture

• The DAM architecture combines a 1T-1R memristor array with in-situ operations and lightweight logic to scale and accumulate dimension-wise distance metrics.The paper motivates the array in part by the compatibility of high-density memristive cells with low-cost peripheral circuits.Source: §4 · p. 5

4.1 DAM Memory Array

• Bitline reads across selected rows produce column-wise data, while a match vector selects dataset rows and peripheral logic supports the required reads.A large resistance range between RH and RL is chosen to avoid sneak currents during bitwise reads.Source: §4.1 · pp. 5–6

4.2 Near-Array Processor

• A mask buffer controls bitline selection and ordering, while each wordline’s NAP processes masked reads and updates row candidacy in the match vector.NAPs include XNOR, stream detection, counting, serial multiplication, and thresholding units; the threshold counter sets candidacy when it saturates.Source: §4.1 · p. 6, §4.2 · p. 6

4.3 Control-flow and Pipelining

• A group controller orchestrates arrays and NAPs through an H-tree, with pipelined stages for configuration, bit-serial reads, accumulation, and thresholding.Stage 4’s match-vector updates signal candidate data availability and overlap execution of the next query’s keys.Source: §4.3 · p. 6, §4.3.1 · p. 7, Figure 6 · p. 7
• Shared key and mask buffers require synchronization across arrays; candidate transfers can overlap accumulation, but Stage 1 or 2 may need to stall for transfer.When accumulation cannot hide the full transfer latency, computation stalls until the transfer completes.Source: §4.3.1 · pp. 7–8

4.4 Memory Organization

• Priority encoding through the H-tree generates candidate addresses in physical order, which the chip controller buffers for candidate fetches.Multiple chips and groups are organized through DIMMs and memory groups; the controller also pauses threshold counters every 32 cycles for transfer and counter updates.Source: §4.4.1 · p. 8, §4.4 · p. 8

4.5 Area overhead Mitigation

• Multiplexing NAPs across consecutive rows mitigates area overhead, but requires NMUX processing steps over all keys and therefore increases latency and reduces throughput.The paper reports that one NAP per row would increase total memory area by almost 6×.Source: §4.5 · p. 8

5 Software Support

• Bitmask M controls quantization precision, while coverage controls overfetch; increasing coverage transfers more vectors and raises latency but provides higher recall guarantees through reranking.Decreasing M increases quantized data width and compute latency while benefiting precision.Source: §5 · p. 8
• Set-first address mapping interleaves vectors across sets because data in different sets cannot be computed in the same iteration.A set is the collection of rows that own a NAP unit in the current computation iteration.Source: §5 · p. 8

5.1 Programming model and API

• The userspace API allocates accelerator memory, sets search parameters, writes CPU-generated Key and Dist structures to chips, and fetches candidate points.The CPU polls DIMMs for availability; candidate transfer sends a datapoint address before its cache line.Source: §5.1 · pp. 8–9

6 Experimental Setup

• DAM is modeled with a lightweight memory simulator based on ESESC, interfaced through QEMU and extended memkind support.The setup includes special memory allocation and writes to configuration address space in DAM DIMMs.Source: §6 · p. 9, Table 3 · p. 9
• Array and peripheral circuitry are modeled with NVSim/NVMExplorer and resistive-memory parameters, while synthesized logic uses Design Compiler with GlobalFoundries at 12nm.CACTI 7.0 evaluates SRAM tables and buffers; match vectors and extra H-tree wiring add 5% area per group.Source: §6 · p. 9
• Baselines run on a 56-core Intel Xeon E5-2680 with 102.4 GBps memory bandwidth, and evaluation covers four billion-scale workloads plus million-scale splits.The four workloads are BIGANN, Microsoft-SPACEV, Facebook-SSNPP, and Yandex-text2Image.Source: §6 · p. 9, Table 2 · p. 9
• The study compares IndexIVFPQ and IndexHNSW with DAM configurations varying compression or graph-search settings, bitmask M, and coverage.Graph-based billion-scale modeling is omitted because its indexing overhead is prohibitive in the given system configuration; recall-100@100 is used throughout.Source: §6 · p. 9
• Yandex-text2Image uses out-of-distribution text queries against image embeddings, while filtered queries can mask dimensions during key generation.The passage also describes index freshness as requiring memory-range initialization and datapoint writes.Source: §6 · p. 9

7.1 Area Analysis

• Throughput rises with area overhead, then largely plateaus between N_Mux=8 and N_Mux=16 as the bottleneck shifts from compute to external bandwidth; evaluations use N_Mux=16 for peak-power limits.Figure 8 plots average throughput against added circuitry as a fraction of chip area.Source: Figure 8 · p. 10, §7.1 · p. 10

7.2 Million-Scale Evaluations

• Address mapping that minimizes iterations and reduced bandwidth requirements account for much of DAM's QPS improvement over PQ; re-ranking supports high recall.On TTI, DAM achieves almost perfect recall for out-of-distribution queries, while HNSW plateaus around 0.8 recall.Source: §7.2 · p. 10
• On million-scale datasets, HNSW has lower tail latency at low recall, but its latency converges toward DAM's as its working set exceeds processor-cache size.Increasing Cov causes only a minimal tail-latency increase across most configurations; aliasing raises DAM-5 latency on MSSPACEV relative to DAM-4.Source: §7.2 · p. 10

7.3 Billion-Scale Evaluations

• DAM maintains very high recall across billion-scale datasets and M/Cov settings while visiting at most 10^-3% of the dataset per query.PQ baselines saturate at lower recall as scale increases, which the authors attribute to PQ's difficulty capturing the data distribution.Source: §7.3 · p. 10

7.2 Million-Scale Evaluations

• Across four datasets, DAM achieves throughput improvements of 8.2x/100x/9x/2x and latency improvements of 972x/985x/85x/100x over the best PQ baseline configuration, respectively.Source: §7.2 · p. 10

7.3 Billion-Scale Evaluations

• 13.3x/76.2x/4.8x/1.3x throughput and 937x/603x/3.8x/1.9x latency improvement over the best PQ baseline across four billion-scale datasets, with near-perfect recall.The comparison covers throughput and tail latency on 1B indices.Source: Figure 10 · p. 11, §7.3 · p. 11
• At billion scale, increasing coverage sharply reduces QPS for SSNPP and TTI with DAM-5 because of aliasing at lower precision; MSSPACEV does not show this effect.The authors attribute the MSSPACEV pattern to poor DAM-3 Cov=1 performance obscuring later throughput changes.Source: §7.3 · p. 11

7.4 Energy and Power Analysis

• 28.5×, 8.57×, 67.4×, and 2.21× energy improvement over the most optimal configuration on BIGANN, MS-SPACEV, SSNPP, and TTI, respectively.For N_Mux=16, each group controller with its NAP, wiring, and buffers has 382 uW peak power; the proposed 8Gb chip peaks at about 0.488W.Source: §7.4 · pp. 11–12

Similarity Search Algorithms

• Graph-based software indices can incur memory overhead and scale out to disks, while compression-based product quantization lacks re-ranking support.The paper also notes that LSH and tree approaches perform poorly at scale.Source: §8 · p. 12

Hardware Acceleration of ANNS

• Prior ANNS accelerators have limits: ANNA struggles to scale to high recall under tighter guarantees, PQ-based FPGA accelerators do not scale to billion-scale data, and Tigris targets 3D point clouds.TPU-KNN is another cited accelerator approach.Source: §8 · p. 12

Processing-In-Memory

• Some RRAM PIM approaches require many memory writes, whereas this paper's bit-serial processing model requires no writes during computation.Source: §8 · p. 12

• DAM accesses data according to its approximate proximity to a query, with search-space pruning performed as a post-processing step within memory.Source: §9 · p. 12
• DAM achieves high recall irrespective of dataset characteristics.Source: §9 · p. 12
• The paper reports significant performance and energy improvements over state-of-the-art software baselines.Source: §9 · p. 12