LogoLogo
Continuum WebsiteContinuum ApplicationsContinuum KnowledgeAxolotl Platform
Continuum Knowledge
Continuum Knowledge
  • Continuum
  • Data
    • Datasets
      • Pre Training Data
      • Types of Fine Tuning
      • Self Instruct Paper
      • Self-Alignment with Instruction Backtranslation
      • Systematic Evaluation of Instruction-Tuned Large Language Models on Open Datasets
      • Instruction Tuning
      • Instruction Fine Tuning - Alpagasus
      • Less is More For Alignment
      • Enhanced Supervised Fine Tuning
      • Visualising Data using t-SNE
      • UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction
      • Training and Evaluation Datasets
      • What is perplexity?
  • MODELS
    • Foundation Models
      • The leaderboard
      • Foundation Models
      • LLama 2 - Analysis
      • Analysis of Llama 3
      • Llama 3.1 series
      • Google Gemini 1.5
      • Platypus: Quick, Cheap, and Powerful Refinement of LLMs
      • Mixtral of Experts
      • Mixture-of-Agents (MoA)
      • Phi 1.5
        • Refining the Art of AI Training: A Deep Dive into Phi 1.5's Innovative Approach
      • Phi 2.0
      • Phi-3 Technical Report
  • Training
    • The Fine Tuning Process
      • Why fine tune?
        • Does Fine-Tuning LLMs on New Knowledge Encourage Hallucinations?
        • Explanations in Fine Tuning
      • Tokenization
        • Tokenization Is More Than Compression
        • Tokenization - SentencePiece
        • Tokenization explore
        • Tokenizer Choice For LLM Training: Negligible or Crucial?
        • Getting the most out of your tokenizer for pre-training and domain adaptation
        • TokenMonster
      • Parameter Efficient Fine Tuning
        • P-Tuning
          • The Power of Scale for Parameter-Efficient Prompt Tuning
        • Prefix-Tuning: Optimizing Continuous Prompts for Generation
        • Harnessing the Power of PEFT: A Smarter Approach to Fine-tuning Pre-trained Models
        • What is Low-Rank Adaptation (LoRA) - explained by the inventor
        • Low Rank Adaptation (Lora)
        • Practical Tips for Fine-tuning LMs Using LoRA (Low-Rank Adaptation)
        • QLORA: Efficient Finetuning of Quantized LLMs
        • Bits and Bytes
        • The Magic behind Qlora
        • Practical Guide to LoRA: Tips and Tricks for Effective Model Adaptation
        • The quantization constant
        • QLORA: Efficient Finetuning of Quantized Language Models
        • QLORA and Fine-Tuning of Quantized Language Models (LMs)
        • ReLoRA: High-Rank Training Through Low-Rank Updates
        • SLoRA: Federated Parameter Efficient Fine-Tuning of Language Models
        • GaLora: Memory-Efficient LLM Training by Gradient Low-Rank Projection
      • Hyperparameters
        • Batch Size
        • Padding Tokens
        • Mixed precision training
        • FP8 Formats for Deep Learning
        • Floating Point Numbers
        • Batch Size and Model loss
        • Batch Normalisation
        • Rethinking Learning Rate Tuning in the Era of Language Models
        • Sample Packing
        • Gradient accumulation
        • A process for choosing the learning rate
        • Learning Rate Scheduler
        • Checkpoints
        • A Survey on Efficient Training of Transformers
        • Sequence Length Warmup
        • Understanding Training vs. Evaluation Data Splits
        • Cross-entropy loss
        • Weight Decay
        • Optimiser
        • Caching
      • Training Processes
        • Extending the context window
        • PyTorch Fully Sharded Data Parallel (FSDP)
        • Train Short, Test Long: Attention with Linear Biases Enables Input Length Extrapolation
        • YaRN: Efficient Context Window Extension of Large Language Models
        • Sliding Window Attention
        • LongRoPE
        • Reinforcement Learning
        • An introduction to reinforcement learning
        • Reinforcement Learning from Human Feedback (RLHF)
        • Direct Preference Optimization: Your Language Model is Secretly a Reward Model
  • INFERENCE
    • Why is inference important?
      • Grouped Query Attention
      • Key Value Cache
      • Flash Attention
      • Flash Attention 2
      • StreamingLLM
      • Paged Attention and vLLM
      • TensorRT-LLM
      • Torchscript
      • NVIDIA L40S GPU
      • Triton Inference Server - Introduction
      • Triton Inference Server
      • FiDO: Fusion-in-Decoder optimised for stronger performance and faster inference
      • Is PUE a useful measure of data centre performance?
      • SLORA
  • KNOWLEDGE
    • Vector Databases
      • A Comprehensive Survey on Vector Databases
      • Vector database management systems: Fundamental concepts, use-cases, and current challenges
      • Using the Output Embedding to Improve Language Models
      • Decoding Sentence-BERT
      • ColBERT: Efficient and Effective Passage Search via Contextualized Late Interaction over BERT
      • SimCSE: Simple Contrastive Learning of Sentence Embeddings
      • Questions Are All You Need to Train a Dense Passage Retriever
      • Improving Text Embeddings with Large Language Models
      • Massive Text Embedding Benchmark
      • RocketQAv2: A Joint Training Method for Dense Passage Retrieval and Passage Re-ranking
      • LLM2Vec: Large Language Models Are Secretly Powerful Text Encoders
      • Embedding and Fine-Tuning in Neural Language Models
      • Embedding Model Construction
      • Demystifying Embedding Spaces using Large Language Models
      • Fine-Tuning Llama for Multi-Stage Text Retrieval
      • Large Language Model Based Text Augmentation Enhanced Personality Detection Model
      • One Embedder, Any Task: Instruction-Finetuned Text Embeddings
      • Vector Databases are not the only solution
      • Knowledge Graphs
        • Harnessing Knowledge Graphs to Elevate AI: A Technical Exploration
        • Unifying Large Language Models and Knowledge Graphs: A Roadmap
      • Approximate Nearest Neighbor (ANN)
      • High Dimensional Data
      • Principal Component Analysis (PCA)
      • Vector Similarity Search - HNSW
      • FAISS (Facebook AI Similarity Search)
      • Unsupervised Dense Retrievers
    • Retrieval Augmented Generation
      • Retrieval-Augmented Generation for Large Language Models: A Survey
      • Fine-Tuning or Retrieval?
      • Revolutionising Information Retrieval: The Power of RAG in Language Models
      • A Survey on Retrieval-Augmented Text Generation
      • REALM: Retrieval-Augmented Language Model Pre-Training
      • Retrieve Anything To Augment Large Language Models
      • Generate Rather Than Retrieve: Large Language Models Are Strong Context Generators
      • Active Retrieval Augmented Generation
      • DSPy: LM Assertions: Enhancing Language Model Pipelines with Computational Constraints
      • DSPy: Compiling Declarative Language Model Calls
      • DSPy: In-Context Learning for Extreme Multi-Label Classification
      • Optimizing Instructions and Demonstrations for Multi-Stage Language Model Programs
      • HYDE: Revolutionising Search with Hypothetical Document Embeddings
      • Enhancing Recommender Systems with Large Language Model Reasoning Graphs
      • Retrieval Augmented Generation (RAG) versus fine tuning
      • RAFT: Adapting Language Model to Domain Specific RAG
      • Summarisation Methods and RAG
      • Lessons Learned on LLM RAG Solutions
      • Stanford: Retrieval Augmented Language Models
      • Overview of RAG Approaches with Vector Databases
      • Mastering Chunking in Retrieval-Augmented Generation (RAG) Systems
    • Semantic Routing
    • Resource Description Framework (RDF)
  • AGENTS
    • What is agency?
      • Rephrase and Respond: Let Large Language Models Ask Better Questions for Themselves
      • Types of Agents
      • The risk of AI agency
      • Understanding Personality in Large Language Models: A New Frontier in AI Psychology
      • AI Agents - Reasoning, Planning, and Tool Calling
      • Personality and Brand
      • Agent Interaction via APIs
      • Bridging Minds and Machines: The Legacy of Newell, Shaw, and Simon
      • A Survey on Language Model based Autonomous Agents
      • Large Language Models as Agents
      • AI Reasoning: A Deep Dive into Chain-of-Thought Prompting
      • Enhancing AI Reasoning with Self-Taught Reasoner (STaR)
      • Exploring the Frontier of AI: The "Tree of Thoughts" Framework
      • Toolformer: Revolutionising Language Models with API Integration - An Analysis
      • TaskMatrix.AI: Bridging Foundational AI Models with Specialised Systems for Enhanced Task Completion
      • Unleashing the Power of LLMs in API Integration: The Rise of Gorilla
      • Andrew Ng's presentation on AI agents
      • Making AI accessible with Andrej Karpathy and Stephanie Zhan
  • Regulation and Ethics
    • Regulation and Ethics
      • Privacy
      • Detecting AI Generated content
      • Navigating the IP Maze in AI: The Convergence of Blockchain, Web 3.0, and LLMs
      • Adverse Reactions to generative AI
      • Navigating the Ethical Minefield: The Challenge of Security in Large Language Models
      • Navigating the Uncharted Waters: The Risks of Autonomous AI in Military Decision-Making
  • DISRUPTION
    • Data Architecture
      • What is a data pipeline?
      • What is Reverse ETL?
      • Unstructured Data and Generatve AI
      • Resource Description Framework (RDF)
      • Integrating generative AI with the Semantic Web
    • Search
      • BM25 - Search Engine Ranking Function
      • BERT as a reranking engine
      • BERT and Google
      • Generative Engine Optimisation (GEO)
      • Billion-scale similarity search with GPUs
      • FOLLOWIR: Evaluating and Teaching Information Retrieval Models to Follow Instructions
      • Neural Collaborative Filtering
      • Federated Neural Collaborative Filtering
      • Latent Space versus Embedding Space
      • Improving Text Embeddings with Large Language Models
    • Recommendation Engines
      • On Interpretation and Measurement of Soft Attributes for Recommendation
      • A Survey on Large Language Models for Recommendation
      • Model driven recommendation systems
      • Recommender AI Agent: Integrating Large Language Models for Interactive Recommendations
      • Foundation Models for Recommender Systems
      • Exploring the Impact of Large Language Models on Recommender Systems: An Extensive Review
      • AI driven recommendations - harming autonomy?
    • Logging
      • A Taxonomy of Anomalies in Log Data
      • Deeplog
      • LogBERT: Log Anomaly Detection via BERT
      • Experience Report: Deep Learning-based System Log Analysis for Anomaly Detection
      • Log-based Anomaly Detection with Deep Learning: How Far Are We?
      • Deep Learning for Anomaly Detection in Log Data: A Survey
      • LogGPT
      • Adaptive Semantic Gate Networks (ASGNet) for log-based anomaly diagnosis
  • Infrastructure
    • The modern data centre
      • Enhancing Data Centre Efficiency: Strategies to Improve PUE
      • TCO of NVIDIA GPUs and falling barriers to entry
      • Maximising GPU Utilisation with Kubernetes and NVIDIA GPU Operator
      • Data Centres
      • Liquid Cooling
    • Servers and Chips
      • The NVIDIA H100 GPU
      • NVIDIA H100 NVL
      • Lambda Hyperplane 8-H100
      • NVIDIA DGX Servers
      • NVIDIA DGX-2
      • NVIDIA DGX H-100 System
      • NVLink Switch
      • Tensor Cores
      • NVIDIA Grace Hopper Superchip
      • NVIDIA Grace CPU Superchip
      • NVIDIA GB200 NVL72
      • Hopper versus Blackwell
      • HGX: High-Performance GPU Platforms
      • ARM Chips
      • ARM versus x86
      • RISC versus CISC
      • Introduction to RISC-V
    • Networking and Connectivity
      • Infiniband versus Ethernet
      • NVIDIA Quantum InfiniBand
      • PCIe (Peripheral Component Interconnect Express)
      • NVIDIA ConnectX InfiniBand adapters
      • NVMe (Non-Volatile Memory Express)
      • NVMe over Fabrics (NVMe-oF)
      • NVIDIA Spectrum-X
      • NVIDIA GPUDirect
      • Evaluating Modern GPU Interconnect
      • Scalable Hierarchical Aggregation and Reduction Protocol (SHARP)
      • Next-generation networking in AI environments
      • NVIDIA Collective Communications Library (NCCL)
    • Data and Memory
      • NVIDIA BlueField Data Processing Units (DPUs)
      • Remote Direct Memory Access (RDMA)
      • High Bandwidth Memory (HBM3)
      • Flash Memory
      • Model Requirements
      • Calculating GPU memory for serving LLMs
      • Transformer training costs
      • GPU Performance Optimisation
    • Libraries and Complements
      • NVIDIA Base Command
      • NVIDIA AI Enterprise
      • CUDA - NVIDIA GTC 2024 presentation
      • RAPIDs
      • RAFT
    • Vast Data Platform
      • Vast Datastore
      • Vast Database
      • Vast Data Engine
      • DASE (Disaggregated and Shared Everything)
      • Dremio and VAST Data
    • Storage
      • WEKA: A High-Performance Storage Solution for AI Workloads
      • Introduction to NVIDIA GPUDirect Storage (GDS)
        • GDS cuFile API
      • NVIDIA Magnum IO GPUDirect Storage (GDS)
      • Vectors in Memory
Powered by GitBook
LogoLogo

Continuum - Accelerated Artificial Intelligence

  • Continuum Website
  • Axolotl Platform

Copyright Continuum Labs - 2023

On this page
  • Key Points
  • GPU Architecture
  • Memory Hierarchy
  • Programming GPUs
  • Computation layout for implementing the IVFADC indexing method
  • Non-exhaustive search with PQ codes
  • Key points
  • Multi-GPU parallelism

Was this helpful?

  1. DISRUPTION
  2. Search

Billion-scale similarity search with GPUs

PreviousGenerative Engine Optimisation (GEO)NextFOLLOWIR: Evaluating and Teaching Information Retrieval Models to Follow Instructions

Last updated 11 months ago

Was this helpful?

This famous 2017 paper focuses on improving the performance of similarity search on large-scale datasets using GPUs.

Similarity search is a fundamental operation in many applications, particularly those involving high-dimensional data like images and videos.

The paper proposes several optimisations to better utilise GPU resources and achieve significant speedups compared to prior state-of-the-art methods.

Key Points

Similarity Search

  • The goal is to find the k-nearest neighbours (k−NN)(k-NN) (k−NN)of a query vector xxx within a large collection of vectors [yi][yi] [yi] based on the Euclidean distance.

  • Exact search involves computing the full pairwise distance matrix between the query vectors and the database vectors, which is computationally expensive for large datasets.

Compressed-Domain Search

  • To improve search efficiency, approximate nearest-neighbor search methods are used, such as the IVFADC (Inverted File with Asymmetric Distance Computation) indexing structure.

  • IVFADC relies on two levels of quantization: a coarse quantizer (q1)(q1)(q1) and a fine quantizer (q2)(q2)(q2) that encodes the residual vector after the first level.

  • The search is performed in two steps: first, the coarse quantizer is used to select a subset of inverted lists (LIVF), and then the fine quantizer is used to compute distances only for the vectors in the selected inverted lists (LIVFADC).

Product Quantizer

  • A product quantizer is used for the fine quantizer (q2)(q2) (q2)to provide a large number of reproduction values without increasing the processing cost.

  • The vector is divided into sub-vectors, each quantized with its own sub-quantizer, typically with 256 reproduction values to fit in one byte.

  • The product quantizer generates b-byte codes, where b is the number of sub-vectors, resulting in a large codebook size (∣C2∣=256b) (|C2| = 256^b)(∣C2∣=256b) while keeping the quantization process computationally cheap.

GPU Optimisation

  • The paper proposes a novel GPU k-selection algorithm that operates in fast register memory and can be fused with other kernels, achieving up to 55% of theoretical peak performance.

  • The authors present an optimised algorithmic layout for exact and approximate k-NN search on GPUs, outperforming previous state-of-the-art methods by a large margin.

Experiments and Results

  • The proposed approach is evaluated on various similarity search scenarios, including brute-force search, approximate search, and compressed-domain search using product quantization.

  • The implementation achieves significant speedups compared to prior GPU-based methods, enabling the construction of a high-accuracy k-NN graph on 95 million images from the Yfcc100M dataset in 35 minutes and a graph connecting 1 billion vectors in less than 12 hours on 4 Maxwell Titan X GPUs.

GPU Architecture

  • GPUs (Graphics Processing Units) are specialised processors designed for parallel processing and are particularly well-suited for tasks that involve large amounts of data and computations.

  • GPUs consist of thousands of cores (processing units) that can execute instructions simultaneously, enabling massive parallelism.

  • The basic execution unit on a GPU is called a warp, which is a group of 32 threads that execute the same instruction in lockstep.

  • Threads within a warp are referred to as lanes, and each lane has its own registers for storing data.

  • Warps are organised into blocks (or cooperative thread arrays), which can contain up to 32 warps and have access to a shared memory space.

  • Blocks are further organised into a grid, which represents the entire workload of a GPU kernel (a function executed on the GPU).

Memory Hierarchy

  • GPUs have a memory hierarchy similar to CPUs but with some differences.

  • Global memory is the largest and slowest memory on the GPU, accessible by all threads across all blocks. It is used for communication between the CPU and GPU and for storing large datasets.

  • Shared memory is a fast on-chip memory that is shared among threads within a block. It is used for efficient data sharing and communication between threads.

  • Registers are the fastest memory on the GPU and are private to each thread. They are used for storing frequently accessed variables and temporary data.

  • Texture memory and constant memory are read-only caches optimized for specific access patterns.

Programming GPUs

  • CUDA (Compute Unified Device Architecture) is a popular programming model developed by NVIDIA for programming their GPUs.

  • CUDA allows developers to write code in languages like C, C++, or Fortran and provides extensions to define GPU kernels and manage GPU memory.

  • OpenCL (Open Computing Language) is an open standard for parallel programming across different devices, including GPUs, CPUs, and FPGAs.

  • When programming GPUs, you typically define kernels, which are functions that are executed in parallel on the GPU threads.

  • Kernels are launched with a specific grid and block configuration, determining the number of threads and their organisation.

  • Inside a kernel, you can access thread and block IDs to identify the specific thread and its position within the grid.

  • You can transfer data between the CPU (host) and GPU (device) using memory management functions provided by CUDA or OpenCL.

  • Synchronisation primitives, such as barriers and atomic operations, are used to coordinate the execution and data sharing between threads.

Example: Vector Addition on GPU

__global__ void vectorAdd(int *a, int *b, int *c, int size) {
    int tid = blockIdx.x * blockDim.x + threadIdx.x;
    if (tid < size) {
        c[tid] = a[tid] + b[tid];
    }
}

int main() {
    int size = 1024;
    int *a, *b, *c;
    cudaMallocManaged(&a, size * sizeof(int));
    cudaMallocManaged(&b, size * sizeof(int));
    cudaMallocManaged(&c, size * sizeof(int));

    // Initialize input vectors
    for (int i = 0; i < size; i++) {
        a[i] = i;
        b[i] = i * 2;
    }

    int blockSize = 256;
    int numBlocks = (size + blockSize - 1) / blockSize;
    vectorAdd<<<numBlocks, blockSize>>>(a, b, c, size);

    cudaDeviceSynchronize();

    // Print the result
    for (int i = 0; i < size; i++) {
        printf("%d ", c[i]);
    }

    cudaFree(a);
    cudaFree(b);
    cudaFree(c);
    return 0;
}

In this example, we define a GPU kernel called vectorAdd that performs element-wise addition of two vectors a and b and stores the result in vector c.

Each thread is responsible for adding one element based on its thread ID.

In the main function, we allocate memory on the GPU using cudaMallocManaged, initialise the input vectors, and launch the kernel with a specific grid and block configuration.

Finally, we synchronise the device to ensure all computations are complete and print the result.

This is just a simple example, but GPUs can be used for a wide range of applications, including image and video processing, machine learning, scientific simulations, and more.

By leveraging the massive parallelism and high memory bandwidth of GPUs, you can accelerate computationally intensive tasks and achieve significant performance gains compared to CPUs.

Computation layout for implementing the IVFADC indexing method

IVFADC is an approximate nearest neighbor search method that combines the inverted file index with asymmetric distance computation (ADC) based on product quantization.

The key aspects of the implementation are the distance computations and their integration with the k-selection process.

Exact search

  • Exhaustive search, also known as exact brute-force search, is used for small datasets or as a component of other indexing methods.

  • In the context of IVFADC, exact search is used for the coarse quantizer (q1).(q1).(q1).

Distance computation

  • The distance computation for exact search boils down to a matrix multiplication.

  • Optimised GEMM (General Matrix Multiplication) routines from the cuBLAS library are used to calculate the −2<xj,yi>-2<x_j, y_i>−2<xj​,yi​> term for L2 distance.

  • The GEMM operation results in a partial distance matrix DDD.

Fused k-selection kernel

  • To complete the distance calculation, a fused k-selection kernel is employed.

  • The fused kernel adds the ∣∣yi∣∣2||y_i||^2∣∣yi​∣∣2 term to each entry of the partial distance matrix DDD and immediately submits the value to k-selection in registers.

  • The ∣∣xj∣∣2||x_j||^2 ∣∣xj​∣∣2term is not required before k-selection and can be omitted.

  • Kernel fusion allows for only 2 passes over D (GEMM write and k-select read), reducing memory access compared to implementations that may require 3 or more passes.

Tiling and memory management

  • For realistic problem sizes, the distance matrix DDD may not fit in GPU memory.

  • To handle this, the problem is tiled over the batch of queries, with tq≤nqt_q ≤ n_qtq​≤nq​ queries being run in a single tile.

  • Each tile represents an independent problem, but two tiles are run in parallel on different streams to better utilise the GPU.

  • The effective memory requirement for DD D becomes O(2×tq)O(2 × t_q)O(2×tq​).

  • The computation can also be tiled over the database size (n)(n) (n)if necessary.

Data transfer and overlap

  • For very large input coming from the CPU, pinned memory buffering is used to overlap CPU-to-GPU data transfer with GPU computation.

  • This helps to hide the latency of data transfer and improve overall performance.

The efficient implementation of IVFADC on GPUs relies on several key optimisations:

  1. Using optimised GEMM routines from cuBLAS for the distance computation matrix multiplication.

  2. Fusing the k-selection kernel with the final distance calculation to reduce memory access and passes over the distance matrix.

  3. Tiling the problem over the batch of queries and database size to handle large datasets that exceed GPU memory capacity.

  4. Running multiple tiles in parallel on different streams to maximize GPU utilisation.

  5. Overlapping CPU-to-GPU data transfer with computation using pinned memory buffering.

By carefully designing the computation layout and leveraging GPU-specific optimizations, the IVFADC method can be implemented efficiently on GPUs, outperforming other GPU-compliant approximate nearest neighbor search strategies.

The combination of optimized distance computations and tight integration with the k-selection process enables high-performance similarity search on large-scale datasets.

Non-exhaustive search with PQ codes

The key idea behind using product quantization (PQ) codes for non-exhaustive search is to compute the distance between a query vector and a set of reproduction values using lookup tables.

This approach significantly reduces the computational cost compared to explicit distance calculations.

Key points

PQ lookup tables

  • When the query vector x and the coarse quantizer reproduction value q1(y)q1(y) q1(y)are known, all distances to the PQ reproduction values can be precomputed and stored in lookup tables T1,...,TbT1, ..., TbT1,...,Tb.

  • Each lookup table is of size 256, corresponding to the number of reproduction values for each sub-quantizer.

  • Computing the distance between xxx and q(y)q(y)q(y) consists of bb b lookups and additions

IVFADC lookup tables

  • When scanning the elements of an inverted list ILILIL, where q1(y)q1(y) q1(y)is constant, the lookup table method can be applied.

  • The distance computation is further optimised by decomposing it into three terms

  • Term 1 is independent of the query and can be precomputed and stored in a table of size ∣C1∣×256×b.|C1| × 256 × b.∣C1∣×256×b.

  • Term 2 is the distance to q1′sq1'sq1′s reproduction value and is a by-product of the first-level quantizer q1q1q1.

  • Term 3 can be computed independently of the inverted list, with a cost of d×256d × 256d×256 multiply-adds.

GPU implementation

  • The inverted lists are stored as two separate arrays for PQPQPQ codes and associated IDs.

  • A kernel is responsible for scanning the τ closest inverted lists for each query and calculating the per-vector pair distances using the lookup tables TiTiTi.

  • The lookup tables are stored in shared memory to enable fast access.

  • Multi-pass kernels are used to process the nq×τnq × τnq×τ pairs of queries and inverted lists independently, with tiling to reduce memory consumption.

  • A two-pass k-selection is introduced to reduce the number of partial results written back to global memory.

The use of product quantization codes and lookup tables enables efficient non-exhaustive search on GPUs.

By precomputing distances and storing them in lookup tables, the computational cost of distance calculations is greatly reduced.

The GPU implementation leverages the massive parallelism and fast shared memory to scan inverted lists and perform k-selection efficiently.

Multi-GPU parallelism

To further scale the similarity search system, the authors propose two strategies for multi-GPU parallelism:

Replication

  • If an index instance fits in the memory of a single GPU, it can be replicated across RRR different GPUs.

  • Each replica handles a fraction nq/Rnq/Rnq/R of the queries, and the results are joined back together on a single GPU or in CPU memory.

  • Replication provides near-linear speedup, except for potential efficiency loss with small nq.

Sharding

  • If an index instance does not fit in the memory of a single GPU, it can be sharded across SSS different GPUs.

  • For adding vectors, each shard receives n/Sn/Sn/Sof the vectors.

  • For querying, each shard handles the full query set nqnqnq, and the partial results are joined on a single GPU or in CPU memory, requiring an additional round of k-selection.

  • Sharding provides a speedup compared to replication, but is usually less than pure replication due to fixed overhead and the cost of subsequent k-selection.

Replication and sharding can be used together, with SS Sshards and each shard having RRR replicas, for a total of S×RS × RS×R GPUs. These strategies can also be applied to distribute an index across multiple machines.

In summary, the paper presents a comprehensive approach to efficient similarity search on GPUs, covering both exact and approximate search methods.

The key contributions include the WarpSelect algorithm for fast k-selection, the optimised computation layout for IVFADC indexing, and the multi-GPU parallelism strategies.

The experimental results demonstrate significant speedups compared to state-of-the-art GPU implementations and showcase the effectiveness of the proposed methods on large-scale datasets.

The open-source implementation provided by the authors enables researchers and practitioners to benefit from these advances in similarity search on GPUs.

LogoBillion-scale similarity search with GPUsarXiv.org
Billion-scale similarity search with GPUs
Page cover image