A Real-Time Adaptive Multi-Stream GPU System for Online Approximate Nearest Neighborhood Search

• URL: http://arxiv.org/abs/2408.02937v2
• Date: Wed, 06 Nov 2024 02:36:02 GMT
• Title: A Real-Time Adaptive Multi-Stream GPU System for Online Approximate Nearest Neighborhood Search
• Authors: Yiping Sun, Yang Shi, Jiaolong Du,
• Abstract summary: We introduce a novel Real-Time Adaptive Multi-Stream GPU ANNS System (RTAMS-GANNS) Our architecture achieves its objectives through three key advancements. The proposed system has also been deployed in real-world industrial search and recommendation systems, serving hundreds of millions of users daily.
• Score: 3.116913746878115
• License:
• Abstract: In recent years, Approximate Nearest Neighbor Search (ANNS) has played a pivotal role in modern search and recommendation systems, especially in emerging LLM applications like Retrieval-Augmented Generation. There is a growing exploration into harnessing the parallel computing capabilities of GPUs to meet the substantial demands of ANNS. However, existing systems primarily focus on offline scenarios, overlooking the distinct requirements of online applications that necessitate real-time insertion of new vectors. This limitation renders such systems inefficient for real-world scenarios. Moreover, previous architectures struggled to effectively support real-time insertion due to their reliance on serial execution streams. In this paper, we introduce a novel Real-Time Adaptive Multi-Stream GPU ANNS System (RTAMS-GANNS). Our architecture achieves its objectives through three key advancements: 1) We initially examined the real-time insertion mechanisms in existing GPU ANNS systems and discovered their reliance on repetitive copying and memory allocation, which significantly hinders real-time effectiveness on GPUs. As a solution, we introduce a dynamic vector insertion algorithm based on memory blocks, which includes in-place rearrangement. 2) To enable real-time vector insertion in parallel, we introduce a multi-stream parallel execution mode, which differs from existing systems that operate serially within a single stream. Our system utilizes a dynamic resource pool, allowing multiple streams to execute concurrently without additional execution blocking. 3) Through extensive experiments and comparisons, our approach effectively handles varying QPS levels across different datasets, reducing latency by up to 40%-80%. The proposed system has also been deployed in real-world industrial search and recommendation systems, serving hundreds of millions of users daily, and has achieved good results.

Related papers

• FusionLLM: A Decentralized LLM Training System on Geo-distributed GPUs with Adaptive Compression [55.992528247880685]
  Decentralized training faces significant challenges regarding system design and efficiency. We present FusionLLM, a decentralized training system designed and implemented for training large deep neural networks (DNNs) We show that our system and method can achieve 1.45 - 9.39x speedup compared to baseline methods while ensuring convergence.
  arXiv  Detail & Related papers  (2024-10-16T16:13:19Z)
• ConServe: Harvesting GPUs for Low-Latency and High-Throughput Large Language Model Serving [15.01982917560918]
  This paper proposes to harvest stranded GPU resources for offline LLM inference tasks. We built ConServe, an LLM serving system that contains an execution engine that preempts running offline tasks. Our evaluation demonstrates that ConServe achieves strong performance isolation when co-serving online and offline tasks.
  arXiv  Detail & Related papers  (2024-10-02T04:12:13Z)
• Performance Tuning for GPU-Embedded Systems: Machine-Learning-based and Analytical Model-driven Tuning Methodologies [0.0]
  The study introduces an analytical model-driven tuning methodology and a Machine Learning (ML)-based tuning methodology. We evaluate the performance of the two tuning methodologies for different parallel prefix implementations of the BPLG library in an NVIDIA Jetson system.
  arXiv  Detail & Related papers  (2023-10-24T22:09:03Z)
• Sparse-DySta: Sparsity-Aware Dynamic and Static Scheduling for Sparse Multi-DNN Workloads [65.47816359465155]
  Running multiple deep neural networks (DNNs) in parallel has become an emerging workload in both edge devices. We propose Dysta, a novel scheduler that utilizes both static sparsity patterns and dynamic sparsity information for the sparse multi-DNN scheduling. Our proposed approach outperforms the state-of-the-art methods with up to 10% decrease in latency constraint violation rate and nearly 4X reduction in average normalized turnaround time.
  arXiv  Detail & Related papers  (2023-10-17T09:25:17Z)
• Spatial-Temporal Graph Enhanced DETR Towards Multi-Frame 3D Object Detection [54.041049052843604]
  We present STEMD, a novel end-to-end framework that enhances the DETR-like paradigm for multi-frame 3D object detection. First, to model the inter-object spatial interaction and complex temporal dependencies, we introduce the spatial-temporal graph attention network. Finally, it poses a challenge for the network to distinguish between the positive query and other highly similar queries that are not the best match.
  arXiv  Detail & Related papers  (2023-07-01T13:53:14Z)
• Fluid Batching: Exit-Aware Preemptive Serving of Early-Exit Neural Networks on Edge NPUs [74.83613252825754]
  "smart ecosystems" are being formed where sensing happens concurrently rather than standalone. This is shifting the on-device inference paradigm towards deploying neural processing units (NPUs) at the edge. We propose a novel early-exit scheduling that allows preemption at run time to account for the dynamicity introduced by the arrival and exiting processes.
  arXiv  Detail & Related papers  (2022-09-27T15:04:01Z)
• An efficient and flexible inference system for serving heterogeneous ensembles of deep neural networks [0.0]
  Ensembles of Deep Neural Networks (DNNs) have achieved qualitative predictions but they are computing and memory intensive. We propose a new software layer to serve with flexibility and efficiency ensembles of DNNs.
  arXiv  Detail & Related papers  (2022-08-30T08:05:43Z)
• GPU-Accelerated Machine Learning in Non-Orthogonal Multiple Access [71.58925117604039]
  Non-orthogonal multiple access (NOMA) is an interesting technology that enables massive connectivity as required in future 5G and 6G networks. We propose a neural network architecture that combines the advantages of both linear and non-linear processing.
  arXiv  Detail & Related papers  (2022-06-13T09:38:23Z)
• Real-Time GPU-Accelerated Machine Learning Based Multiuser Detection for 5G and Beyond [70.81551587109833]
  nonlinear beamforming filters can significantly outperform linear approaches in stationary scenarios with massive connectivity. One of the main challenges comes from the real-time implementation of these algorithms. This paper explores the acceleration of APSM-based algorithms through massive parallelization.
  arXiv  Detail & Related papers  (2022-01-13T15:20:45Z)
• Scaled-Time-Attention Robust Edge Network [2.4417312983418014]
  This paper describes a systematic approach towards building a new family of neural networks based on a delay-loop version of a reservoir neural network. The resulting architecture, called Scaled-Time-Attention Robust Edge (STARE) network, exploits hyper dimensional space and non-multiply-and-add computation. We demonstrate that STARE is applicable to a variety of applications with improved performance and lower implementation complexity.
  arXiv  Detail & Related papers  (2021-07-09T21:24:49Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.