Jun Liu
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Jun Liu has a total of 39 co-authors. Here are the top co-authors by number of shared publications:
- Guohao Dai
Shanghai Jiao Tong University, Shanghai, China
10 shared publications - Jinhao Li
Shanghai Jiao Tong University, Shanghai, China
6 shared publications - Jiaming Xu
Shanghai Jiao Tong University, Shanghai, China
5 shared publications - Shan Huang
Shanghai Jiao Tong University, Shanghai, China
5 shared publications - Li Ding
Shanghai Jiao Tong University, Shanghai, China
4 shared publications - Yu Wang
Tsinghua University
4 shared publications
Latest Publications
- 1 November 2026
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
- Vol. 45 (11) , 6243-6256
DiffAttn: Sparse Attention Architecture for Video Generation With Spatial Information-Guided Differential Estimation
Recent progress in video generation models (VGMs) has enabled long video generation with strong visual fidelity. VGM architectures have evolved from decomposed 2D attention (e.g., separate spatial/temporal attention) to 3D full attention that jointly processes all frames. However, inference latency remains a major bottleneck due to algorithmic and architectural inefficiencies. Differential methods have become a potential solution by leveraging sparsity to reduce computation. However, existing studies face two challenges: Challenge-1: The existing differential methods fail to identify the weakly connected parts in VGM that can be approximately calculated, leading to many potential redundant computations or severe impacts on generation quality (> 5% loss). Challenge-2: The traditional architecture fails to effectively utilize the unique redundancy distribution (i.e., column-concentrated pattern) in compressed VGMs. To address the above challenges, we propose DiffAttn, a sparse attention architecture for video generation with differential approximation. Building on our prior conference work (ViDA), DiffAttn generalizes differential computing to 3D full attention and strengthens architectural support to exploit the resulting column-concentrated sparsity. It combines three tightly coupled techniques. (1) Spatial information-guided differential estimation method utilizes spatial information to estimate the weakly connected regions in attention computation, which reduces the attention computation by 66.84%. (2) Column-concentrated computing architecture fully leverages the unique column-concentrated sparsity characteristics in the compressed VGMs, which achieves 1.52× speedup over a fully dense architecture. (3) Sparsity-aware inter-layer dataflow dynamically adjusts the workload ratio between the two cores by analyzing layer-wise sparsity and column distribution at runtime, improving the utilization by 36.33%. Experiments on advanced VGMs (e.g., CogVideoX1.5, OpenSora2.0) show that DiffAttn achieves up to 2.62× and 1.89× end-to-end speedup and 3.14×/ and 2.87× energy efficiency improvement over NVIDIA A800 GPU and advanced VGM accelerator, respectively.
- 1 November 2026
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
- Vol. 45 (11) , 6243-6256
DiffAttn: Sparse Attention Architecture for Video Generation With Spatial Information-Guided Differential Estimation
Recent progress in video generation models (VGMs) has enabled long video generation with strong visual fidelity. VGM architectures have evolved from decomposed 2D attention (e.g., separate spatial/temporal attention) to 3D full attention that jointly processes all frames. However, inference latency remains a major bottleneck due to algorithmic and architectural inefficiencies. Differential methods have become a potential solution by leveraging sparsity to reduce computation. However, existing studies face two challenges: Challenge-1: The existing differential methods fail to identify the weakly connected parts in VGM that can be approximately calculated, leading to many potential redundant computations or severe impacts on generation quality (> 5% loss). Challenge-2: The traditional architecture fails to effectively utilize the unique redundancy distribution (i.e., column-concentrated pattern) in compressed VGMs. To address the above challenges, we propose DiffAttn, a sparse attention architecture for video generation with differential approximation. Building on our prior conference work (ViDA), DiffAttn generalizes differential computing to 3D full attention and strengthens architectural support to exploit the resulting column-concentrated sparsity. It combines three tightly coupled techniques. (1) Spatial information-guided differential estimation method utilizes spatial information to estimate the weakly connected regions in attention computation, which reduces the attention computation by 66.84%. (2) Column-concentrated computing architecture fully leverages the unique column-concentrated sparsity characteristics in the compressed VGMs, which achieves 1.52× speedup over a fully dense architecture. (3) Sparsity-aware inter-layer dataflow dynamically adjusts the workload ratio between the two cores by analyzing layer-wise sparsity and column distribution at runtime, improving the utilization by 36.33%. Experiments on advanced VGMs (e.g., CogVideoX1.5, OpenSora2.0) show that DiffAttn achieves up to 2.62× and 1.89× end-to-end speedup and 3.14×/ and 2.87× energy efficiency improvement over NVIDIA A800 GPU and advanced VGM accelerator, respectively.
- Open Access
- 10 November 2025
- Published by Association for Computing Machinery (ACM)
- p. 3866-3876
SG-Filter: Enhancing Similar Text Retrieval via Hierarchical Summarized-Semantic Index and Adaptive Filtering
- 10 November 2025
- Published by Association for Computing Machinery (ACM)
- p. 3866-3876
Open AccessSG-Filter: Enhancing Similar Text Retrieval via Hierarchical Summarized-Semantic Index and Adaptive Filtering
- 22 October 2025
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
- Vol. 45 (6) , 2884-2897
MARCA-v2: Mamba Accelerator With Complementary State-Space Model Sparsity and Reconfigurable Architecture
Large language models (LLMs) with a state-space model (SSM), especially Mamba, have demonstrated remarkable capabilities in various domains. Compared to Transformers, Mamba reduces the quadratic computational complexity and achieves a higher algorithm performance. Current research on Mamba focuses primarily on integrating it with various application scenarios. However, there is limited research on optimizing for Mamba processing. Therefore, we profile the processing carefully and identify three main challenges in Mamba computations: 1) Large memory access overhead of element-wise operations in the SSM. Based on the MARCA architecture, the time proportion of the SSM is still the bottleneck when the sequence length reaches 2048, accounting for 62.52% of the total runtime. In the SSM, the memory access overhead of element-wise operations accounts for 97.17%, leading to consuming 96.56% of the time. 2) Inefficient sparse element-wise (Sp-EW) execution on MARCA architecture. SOTA architectures like MARCA propose a reconfigurable reduction tree to accelerate dense element-wise operations but lack effective sparse support for sparse execution. When 30% of the element-wise operations are skipped, these skipped operations are still mapped to the PE array and trigger redundant execution cycles, incurring$1.43\times $ performance gap with the ideal. 3) Large-area overhead for the nonlinear function unit. Exponential function and SiLU are two main nonlinear functions in the SSM. Previous methods designed a specific unit for acceleration, leading to 38% and 18% area overheads of the PE. In response to these challenges, we propose a new Mamba accelerator with complementary SSM sparsity and reconfigurable architecture, MARCA-v2, based on MARCA, to support fast and energy-efficient Mamba computations. Three novel techniques are as follows: 1) Complementary SSM sparsity with column-wise granularity. We first profile the numerical distributions of activations in the SSM and propose a column-wise complementary static sparsity for SSM computation. To further enable lightweight and hardware-friendly sparse computation, we propose a$\delta $ -bitmap encoding scheme for compressed storage and introduce two abstractions for Sp-EW operations. 2) Lightweight Sp-EW architecture. Based on the hardware-friendly sparsity algorithm and MARCA architecture, we design and integrate a lightweight metadata processing unit (Meta-PU) into the existing pipeline, which decodes the sparsity metadata and dynamically generates control signals to guide PE arrays. The overall architecture can efficiently support both dense and sparse operations, maximizing speed and energy efficiency. 3) Reusable nonlinear function unit based on reconfigurable PE arrays. We decompose the exponential function and SiLU into several element-wise operations. Thus, the reconfigurable PEs are fully reused to execute nonlinear functions with negligible accuracy loss. We conduct extensive experiments on Mamba model families with different sizes. Experimental results show that in the prefill stage, MARCA-v2 achieve 1.77–$10.87\times $ , 1.03–$1.08\times $ , and 4.78–$9.10\times $ speedup, and 8.29–$33.47\times $ /1.03-$1.08\times $ /4.78–$9.10\times $ energy efficiency improvement compared with Mamba–GPU, MARCA, and Spada, respec-tively. In the decode stage, MARCA-v2 achieve 0.88–$7.65\times $ / 1.00–$1.01\times $ /1.19–$1.64\times $ speedup and 3.11–$27.01\times $ /1.00–$1.01\times $ / 1.19–$1.64\times $ energy efficiency improvement compared with Mamba–GPU, MARCA, and Spada, respectively.- 22 October 2025
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
- Vol. 45 (6) , 2884-2897
MARCA-v2: Mamba Accelerator With Complementary State-Space Model Sparsity and Reconfigurable Architecture
Large language models (LLMs) with a state-space model (SSM), especially Mamba, have demonstrated remarkable capabilities in various domains. Compared to Transformers, Mamba reduces the quadratic computational complexity and achieves a higher algorithm performance. Current research on Mamba focuses primarily on integrating it with various application scenarios. However, there is limited research on optimizing for Mamba processing. Therefore, we profile the processing carefully and identify three main challenges in Mamba computations: 1) Large memory access overhead of element-wise operations in the SSM. Based on the MARCA architecture, the time proportion of the SSM is still the bottleneck when the sequence length reaches 2048, accounting for 62.52% of the total runtime. In the SSM, the memory access overhead of element-wise operations accounts for 97.17%, leading to consuming 96.56% of the time. 2) Inefficient sparse element-wise (Sp-EW) execution on MARCA architecture. SOTA architectures like MARCA propose a reconfigurable reduction tree to accelerate dense element-wise operations but lack effective sparse support for sparse execution. When 30% of the element-wise operations are skipped, these skipped operations are still mapped to the PE array and trigger redundant execution cycles, incurring$1.43\times $ performance gap with the ideal. 3) Large-area overhead for the nonlinear function unit. Exponential function and SiLU are two main nonlinear functions in the SSM. Previous methods designed a specific unit for acceleration, leading to 38% and 18% area overheads of the PE. In response to these challenges, we propose a new Mamba accelerator with complementary SSM sparsity and reconfigurable architecture, MARCA-v2, based on MARCA, to support fast and energy-efficient Mamba computations. Three novel techniques are as follows: 1) Complementary SSM sparsity with column-wise granularity. We first profile the numerical distributions of activations in the SSM and propose a column-wise complementary static sparsity for SSM computation. To further enable lightweight and hardware-friendly sparse computation, we propose a$\delta $ -bitmap encoding scheme for compressed storage and introduce two abstractions for Sp-EW operations. 2) Lightweight Sp-EW architecture. Based on the hardware-friendly sparsity algorithm and MARCA architecture, we design and integrate a lightweight metadata processing unit (Meta-PU) into the existing pipeline, which decodes the sparsity metadata and dynamically generates control signals to guide PE arrays. The overall architecture can efficiently support both dense and sparse operations, maximizing speed and energy efficiency. 3) Reusable nonlinear function unit based on reconfigurable PE arrays. We decompose the exponential function and SiLU into several element-wise operations. Thus, the reconfigurable PEs are fully reused to execute nonlinear functions with negligible accuracy loss. We conduct extensive experiments on Mamba model families with different sizes. Experimental results show that in the prefill stage, MARCA-v2 achieve 1.77–$10.87\times $ , 1.03–$1.08\times $ , and 4.78–$9.10\times $ speedup, and 8.29–$33.47\times $ /1.03-$1.08\times $ /4.78–$9.10\times $ energy efficiency improvement compared with Mamba–GPU, MARCA, and Spada, respec-tively. In the decode stage, MARCA-v2 achieve 0.88–$7.65\times $ / 1.00–$1.01\times $ /1.19–$1.64\times $ speedup and 3.11–$27.01\times $ /1.00–$1.01\times $ / 1.19–$1.64\times $ energy efficiency improvement compared with Mamba–GPU, MARCA, and Spada, respectively.- Open Access
- 27 February 2025
- Published by Association for Computing Machinery (ACM)
- p. 2-13
FlightVGM: Efficient Video Generation Model Inference with Online Sparsification and Hybrid Precision on FPGAs
Video Generation Model (VGM), as a representative of multi-modal large models, has revolutionized the productivity of video content creation. VGMs are compute-bound due to adopting the Diffusion Transformer (i.e., DiT) structure. Sparsification is a common method for accelerating compute-intensive models. Still, sparse VGMs cannot fully exploit the effective throughput (i.e., TOPS) of GPUs. FPGAs are good candidates for accelerating sparse deep learning models. However, existing FPGA accelerators still face low throughput ( < 2TOPS) on VGMs due to the significant gap in peak computing performance (PCP) with GPUs ( > 21× ). To achieve a higher throughput than GPUs, FPGA-based acceleration of sparse VGMs still faces the following challenges: large redundancy in activations, low performance of DSPs under hybrid precision, and under-utilization using static compilation for online compression. To tackle these challenges, we propose FlightVGM, the first FPGA accelerator for efficient VGM inference with activation sparsification and hybrid precision. In FlightVGM, our motivation stems from VGMs exhibiting different compression preferences in various dimensions and layers. To exploit the video frames' similarity in the temporal and spatial dimensions, we propose a spatial-temporal online activation sparsification architecture, reducing the computational cost by 3.17×. To provide a good trade-off between the accuracy and efficiency of VGMs, we employ fixed-point precision for linear layers and retain floating-point precision for attention layers. Then, we propose a floating-fixed hybrid precision DSP58 expansion architecture on the AMD V80 FPGA, boosting the PCP by 3.26×. Finally, to make FlightVGM available to various workloads, we propose a dynamic-static combined adaptive scheduling method for low-overhead online sparsification, improving the computation utilization by 2.75×. Implemented on the AMD V80 FPGA, FlightVGM surpasses NVIDIA 3090 GPU by 1.30× in performance and 4.49× in energy efficiency on various sparse VGM workloads.
- 27 February 2025
- Published by Association for Computing Machinery (ACM)
- p. 2-13
Open AccessFlightVGM: Efficient Video Generation Model Inference with Online Sparsification and Hybrid Precision on FPGAs
Video Generation Model (VGM), as a representative of multi-modal large models, has revolutionized the productivity of video content creation. VGMs are compute-bound due to adopting the Diffusion Transformer (i.e., DiT) structure. Sparsification is a common method for accelerating compute-intensive models. Still, sparse VGMs cannot fully exploit the effective throughput (i.e., TOPS) of GPUs. FPGAs are good candidates for accelerating sparse deep learning models. However, existing FPGA accelerators still face low throughput ( < 2TOPS) on VGMs due to the significant gap in peak computing performance (PCP) with GPUs ( > 21× ). To achieve a higher throughput than GPUs, FPGA-based acceleration of sparse VGMs still faces the following challenges: large redundancy in activations, low performance of DSPs under hybrid precision, and under-utilization using static compilation for online compression. To tackle these challenges, we propose FlightVGM, the first FPGA accelerator for efficient VGM inference with activation sparsification and hybrid precision. In FlightVGM, our motivation stems from VGMs exhibiting different compression preferences in various dimensions and layers. To exploit the video frames' similarity in the temporal and spatial dimensions, we propose a spatial-temporal online activation sparsification architecture, reducing the computational cost by 3.17×. To provide a good trade-off between the accuracy and efficiency of VGMs, we employ fixed-point precision for linear layers and retain floating-point precision for attention layers. Then, we propose a floating-fixed hybrid precision DSP58 expansion architecture on the AMD V80 FPGA, boosting the PCP by 3.26×. Finally, to make FlightVGM available to various workloads, we propose a dynamic-static combined adaptive scheduling method for low-overhead online sparsification, improving the computation utilization by 2.75×. Implemented on the AMD V80 FPGA, FlightVGM surpasses NVIDIA 3090 GPU by 1.30× in performance and 4.49× in energy efficiency on various sparse VGM workloads.
- Open Access
- 20 January 2025
- Published by Association for Computing Machinery (ACM)
- p. 148-154
ViDA: Video Diffusion Transformer Acceleration with Differential Approximation and Adaptive Dataflow
Recent advancements in Video Diffusion Transformer (VDiT) models have greatly promoted the development of video generation, as exemplified by Sora of OpenAI. However, there are still two challenges for VDiT: 1) There is still existing large inter-frame redundant computation. Previous works on reducing computation based on inter-frame similarity simply consider the Act-W operators. The remaining Act-Act operators still dominate the execution of VDiT (about 57%). 2) Operational intensity varies greatly, leading to under-utilization. There is a massive gap between the operational intensity of Act-W and Act-Act operators in VDiT with multiple frames. Previous works with the static hardware architecture and dataflow lead to under-utilization (ViDA, a Video Diffusion Transformer Accelerator with Diferential Approximation and Adaptive Dataflow. 1) At the algorithm level, we propose the differential approximation method that exploits similarity for both Act-Act and Act-W operators to reduce redundant computation. 2) At the hardware level, we propose the column-concentrated PE by exploiting the column sparsity pattern in differential computing. 3) At the dataflow level, we propose an intensity adaptive dataflow architecture to balance the execution of operators with significant operational intensity differences. Experiments show that ViDA achieves average 16.44×/2.18× speedup and 18.39×/2.35× area efficiency compared with NVIDIA A100 GPU and SOTA vision accelerator.
- 20 January 2025
- Published by Association for Computing Machinery (ACM)
- p. 148-154
Open AccessViDA: Video Diffusion Transformer Acceleration with Differential Approximation and Adaptive Dataflow
Recent advancements in Video Diffusion Transformer (VDiT) models have greatly promoted the development of video generation, as exemplified by Sora of OpenAI. However, there are still two challenges for VDiT: 1) There is still existing large inter-frame redundant computation. Previous works on reducing computation based on inter-frame similarity simply consider the Act-W operators. The remaining Act-Act operators still dominate the execution of VDiT (about 57%). 2) Operational intensity varies greatly, leading to under-utilization. There is a massive gap between the operational intensity of Act-W and Act-Act operators in VDiT with multiple frames. Previous works with the static hardware architecture and dataflow lead to under-utilization (ViDA, a Video Diffusion Transformer Accelerator with Diferential Approximation and Adaptive Dataflow. 1) At the algorithm level, we propose the differential approximation method that exploits similarity for both Act-Act and Act-W operators to reduce redundant computation. 2) At the hardware level, we propose the column-concentrated PE by exploiting the column sparsity pattern in differential computing. 3) At the dataflow level, we propose an intensity adaptive dataflow architecture to balance the execution of operators with significant operational intensity differences. Experiments show that ViDA achieves average 16.44×/2.18× speedup and 18.39×/2.35× area efficiency compared with NVIDIA A100 GPU and SOTA vision accelerator.
- Open Access
- 20 January 2025
- Published by Association for Computing Machinery (ACM)
- p. 534-540
Accelerator for LLM-Enhanced GNN with Product Quantization and Unified Indexing
To alleviate the vulnerability of graph neural networks (GNNs) on unseen graphs, many works propose to integrate large language models (LLMs) into GNNs, called graph foundation models (GFMs). The LLM-enhanced GNN, a typical integration method of GFMs, has achieved state-of-the-art performance in most graph-related tasks. However, intensive general matrix multiplications (GEMMs) overhead of LLMs poses a significant challenge to end-to-end inference latency. The introduction of LLMs brings 100× more workload than original GNNs, with GEMMs accounting for more than 99%, becoming the bottleneck of end-to-end inference. To tackle the above challenge, we present GFMEngine, an algorithm and hardware co-design accelerator supporting LLM-enhanced GNNs at multiple levels. (1) At the algorithm level, we point out that the computational precision of LLMs has little impact on the end-to-end accuracy, and propose a product-quantization-based (PQ-based) matrix multiplication for LLMs to alleviate the intensive GEMMs in LLMs, reducing more than 70% computation with negligible accuracy loss. (2) At the hardware level, we point out that the implementation of PQ-based matrix multiplication effectively alleviates the intensive GEMMs but results in a substantial increase in dynamic memory access. Coupled with the dynamic memory access inherent in GNNs, we design a unified indexing unit as the hardware support, reducing ~ 30% memory access in end-to-end inference. (3) At the compilation level, we further design an extensible instruction set architecture as the software support, GFM-ISA, for various real-world GFM tasks. We implement GFMEngine with TSMC 28nm process, and extensive experiments show that GFMEngine achieves up to 3.93×, 38.66×, 22.32×, 2.96× speedup and up to 102.52×, 37.82×, 28.37×, 2.56× energy efficiency improvement compared with NVIDIA Tesla A100 and the domain-specific accelerators, SGCN, MEGA, FACT, respectively.
- 20 January 2025
- Published by Association for Computing Machinery (ACM)
- p. 534-540
Open AccessAccelerator for LLM-Enhanced GNN with Product Quantization and Unified Indexing
To alleviate the vulnerability of graph neural networks (GNNs) on unseen graphs, many works propose to integrate large language models (LLMs) into GNNs, called graph foundation models (GFMs). The LLM-enhanced GNN, a typical integration method of GFMs, has achieved state-of-the-art performance in most graph-related tasks. However, intensive general matrix multiplications (GEMMs) overhead of LLMs poses a significant challenge to end-to-end inference latency. The introduction of LLMs brings 100× more workload than original GNNs, with GEMMs accounting for more than 99%, becoming the bottleneck of end-to-end inference. To tackle the above challenge, we present GFMEngine, an algorithm and hardware co-design accelerator supporting LLM-enhanced GNNs at multiple levels. (1) At the algorithm level, we point out that the computational precision of LLMs has little impact on the end-to-end accuracy, and propose a product-quantization-based (PQ-based) matrix multiplication for LLMs to alleviate the intensive GEMMs in LLMs, reducing more than 70% computation with negligible accuracy loss. (2) At the hardware level, we point out that the implementation of PQ-based matrix multiplication effectively alleviates the intensive GEMMs but results in a substantial increase in dynamic memory access. Coupled with the dynamic memory access inherent in GNNs, we design a unified indexing unit as the hardware support, reducing ~ 30% memory access in end-to-end inference. (3) At the compilation level, we further design an extensible instruction set architecture as the software support, GFM-ISA, for various real-world GFM tasks. We implement GFMEngine with TSMC 28nm process, and extensive experiments show that GFMEngine achieves up to 3.93×, 38.66×, 22.32×, 2.96× speedup and up to 102.52×, 37.82×, 28.37×, 2.56× energy efficiency improvement compared with NVIDIA Tesla A100 and the domain-specific accelerators, SGCN, MEGA, FACT, respectively.
- Open Access
- 27 October 2024
- Published by Association for Computing Machinery (ACM)
- p. 1-9
Fast and Efficient 2-bit LLM Inference on GPU: 2/4/16-bit in a Weight Matrix with Asynchronous Dequantization
- 27 October 2024
- Published by Association for Computing Machinery (ACM)
- p. 1-9
Open AccessFast and Efficient 2-bit LLM Inference on GPU: 2/4/16-bit in a Weight Matrix with Asynchronous Dequantization
- Open Access
- 27 October 2024
- Published by Association for Computing Machinery (ACM)
- p. 1-9
MARCA: Mamba Accelerator with Reconfigurable Architecture
- 27 October 2024
- Published by Association for Computing Machinery (ACM)
- p. 1-9
Open AccessMARCA: Mamba Accelerator with Reconfigurable Architecture
- Top Cited PapersOpen Access
- 2 April 2024
- Published by Association for Computing Machinery (ACM)
- p. 223-234
FlightLLM: Efficient Large Language Model Inference with a Complete Mapping Flow on FPGAs
- 2 April 2024
- Published by Association for Computing Machinery (ACM)
- p. 223-234
Top Cited PapersOpen AccessFlightLLM: Efficient Large Language Model Inference with a Complete Mapping Flow on FPGAs
- Open Access
- 28 October 2023
- Published by Association for Computing Machinery (ACM)
- p. 283-296
DF-GAS: a Distributed FPGA-as-a-Service Architecture towards Billion-Scale Graph-based Approximate Nearest Neighbor Search
Embedding retrieval is a crucial task for recommendation systems. Graph-based approximate nearest neighbor search (GANNS) is the most commonly used method for retrieval, and achieves the best performance on billion-scale datasets. Unfortunately, the existing CPU- and GPU-based GANNS systems are difficult to optimize the throughput under the latency constraints on billion-scale datasets, due to the underutilized local memory bandwidth (5-45%) and the expensive remote data access overhead (∼ 85% of the total latency). In this paper, we first introduce a practically ideal GANNS architecture for billion-scale datasets, which facilitates a detailed analysis of the challenges and characteristics of distributed GANNS systems. Then, at the architecture level, we propose DF-GAS, a Distributed FPGA-as-a-Service (FPaaS) architecture for accelerating billion-scale Graph-based Approximate nearest neighbor Search. DF-GAS uses a feature-packing memory access engine and a data prefetching and delayed processing scheme to increase local memory bandwidth by 36-42% and reduce remote data access overhead by 76.2%, respectively. At the system level, we exploit the “full-graph + sub-graph” hybrid parallel search scheme on distributed FPaaS system. It achieves million-level query-per-second with sub-millisecond latency on billion-scale GANNS for the first time. Extensive evaluations on million-scale and billion-scale datasets show that DF-GAS achieves an average of 55.4 ×, 32.2 ×, 5.4 ×, and 4.4 × better latency-bounded throughput than CPUs, GPUs, and two state-of-the-art ANNS architectures, i.e., ANNA [23] and Vstore [27], respectively.
- 28 October 2023
- Published by Association for Computing Machinery (ACM)
- p. 283-296
Open AccessDF-GAS: a Distributed FPGA-as-a-Service Architecture towards Billion-Scale Graph-based Approximate Nearest Neighbor Search
Embedding retrieval is a crucial task for recommendation systems. Graph-based approximate nearest neighbor search (GANNS) is the most commonly used method for retrieval, and achieves the best performance on billion-scale datasets. Unfortunately, the existing CPU- and GPU-based GANNS systems are difficult to optimize the throughput under the latency constraints on billion-scale datasets, due to the underutilized local memory bandwidth (5-45%) and the expensive remote data access overhead (∼ 85% of the total latency). In this paper, we first introduce a practically ideal GANNS architecture for billion-scale datasets, which facilitates a detailed analysis of the challenges and characteristics of distributed GANNS systems. Then, at the architecture level, we propose DF-GAS, a Distributed FPGA-as-a-Service (FPaaS) architecture for accelerating billion-scale Graph-based Approximate nearest neighbor Search. DF-GAS uses a feature-packing memory access engine and a data prefetching and delayed processing scheme to increase local memory bandwidth by 36-42% and reduce remote data access overhead by 76.2%, respectively. At the system level, we exploit the “full-graph + sub-graph” hybrid parallel search scheme on distributed FPaaS system. It achieves million-level query-per-second with sub-millisecond latency on billion-scale GANNS for the first time. Extensive evaluations on million-scale and billion-scale datasets show that DF-GAS achieves an average of 55.4 ×, 32.2 ×, 5.4 ×, and 4.4 × better latency-bounded throughput than CPUs, GPUs, and two state-of-the-art ANNS architectures, i.e., ANNA [23] and Vstore [27], respectively.