Tree Attention: Topology-aware Decoding for Long-Context Attention on GPU clusters

• URL: http://arxiv.org/abs/2408.04093v3
• Date: Wed, 14 Aug 2024 12:47:31 GMT
• Title: Tree Attention: Topology-aware Decoding for Long-Context Attention on GPU clusters
• Authors: Vasudev Shyam, Jonathan Pilault, Emily Shepperd, Quentin Anthony, Beren Millidge,
• Abstract summary: Self-attention is a significant computational bottleneck due to its complexity in the sequence length. In this work, we derive the scalar energy function whose gradient computes the self-attention block. Our formulation reveals that the reduction across the sequence axis can be efficiently computed in parallel through a tree reduction.
• Score: 10.403248386029407
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Self-attention is the core mathematical operation of modern transformer architectures and is also a significant computational bottleneck due to its quadratic complexity in the sequence length. In this work, we derive the scalar energy function whose gradient computes the self-attention block, thus elucidating the theoretical underpinnings of self-attention, providing a Bayesian interpretation of the operation and linking it closely with energy-based models such as Hopfield Networks. Our formulation reveals that the reduction across the sequence axis can be efficiently computed in parallel through a tree reduction. Our algorithm, for parallelizing attention computation across multiple GPUs enables cross-device decoding to be performed asymptotically faster (up to 8x faster in our experiments) than alternative approaches such as Ring Attention, while also requiring significantly less communication volume and incurring 2x less peak memory. Our code is publicly available here: \url{https://github.com/Zyphra/tree_attention}.

Related papers

• CAGRA: Highly Parallel Graph Construction and Approximate Nearest Neighbor Search for GPUs [4.55224304015001]
  We introduce a novel parallel computing hardware-based proximity graph and search algorithm. By leveraging the high-performance capabilities of modern hardware, our approach achieves remarkable efficiency gains. In large-batch query throughput in the 90% to 95% recall range, our method is 3377x faster than HNSW, and is 3.88.8x faster than the SOTA implementations for GPU.
  arXiv  Detail & Related papers  (2023-08-29T09:10:53Z)
• INR-Arch: A Dataflow Architecture and Compiler for Arbitrary-Order Gradient Computations in Implicit Neural Representation Processing [66.00729477511219]
  Given a function represented as a computation graph, traditional architectures face challenges in efficiently computing its nth-order gradient. We introduce INR-Arch, a framework that transforms the computation graph of an nth-order gradient into a hardware-optimized dataflow architecture. We present results that demonstrate 1.8-4.8x and 1.5-3.6x speedup compared to CPU and GPU baselines respectively.
  arXiv  Detail & Related papers  (2023-08-11T04:24:39Z)
• Instant Neural Graphics Primitives with a Multiresolution Hash Encoding [67.33850633281803]
  We present a versatile new input encoding that permits the use of a smaller network without sacrificing quality. A small neural network is augmented by a multiresolution hash table of trainable feature vectors whose values are optimized through a gradient descent. We achieve a combined speed of several orders of magnitude, enabling training of high-quality neural graphics primitives in a matter of seconds.
  arXiv  Detail & Related papers  (2022-01-16T07:22:47Z)
• AxoNN: An asynchronous, message-driven parallel framework for extreme-scale deep learning [1.5301777464637454]
  AxoNN is a parallel deep learning framework that exploits asynchrony and message-driven execution to schedule neural network operations on each GPU. By using the CPU memory as a scratch space for offloading data periodically during training, AxoNN is able to reduce GPU memory consumption by four times.
  arXiv  Detail & Related papers  (2021-10-25T14:43:36Z)
• VersaGNN: a Versatile accelerator for Graph neural networks [81.1667080640009]
  We propose textitVersaGNN, an ultra-efficient, systolic-array-based versatile hardware accelerator. textitVersaGNN achieves on average 3712$times$ speedup with 1301.25$times$ energy reduction on CPU, and 35.4$times$ speedup with 17.66$times$ energy reduction on GPU.
  arXiv  Detail & Related papers  (2021-05-04T04:10:48Z)
• DistGNN: Scalable Distributed Training for Large-Scale Graph Neural Networks [58.48833325238537]
  Full-batch training on Graph Neural Networks (GNN) to learn the structure of large graphs is a critical problem that needs to scale to hundreds of compute nodes to be feasible. In this paper, we presentGNN that optimize the well-known Deep Graph Library (DGL) for full-batch training on CPU clusters. Our results on four common GNN benchmark datasets show up to 3.7x speed-up using a single CPU socket and up to 97x speed-up using 128 CPU sockets.
  arXiv  Detail & Related papers  (2021-04-14T08:46:35Z)
• GPUTreeShap: Massively Parallel Exact Calculation of SHAP Scores for Tree Ensembles [0.8057006406834467]
  We present a reformulated TreeShap algorithm suitable for massively parallel computation on graphics processing units. We achieve speedups of up to 19x for SHAP values, and speedups of up to 340x for SHAP values, over a state-of-the-art multi-core CPU implementation.
  arXiv  Detail & Related papers  (2020-10-27T00:55:07Z)
• At-Scale Sparse Deep Neural Network Inference with Efficient GPU Implementation [24.824295164938604]
  This paper presents GPU performance optimization and scaling results for inference models of the Sparse Deep Neural Network Challenge 2020. Sparse deep neural networks (SpDNN) have shown promise for reining in the memory footprint of large neural networks. This work presents optimized sparse matrix multiplication kernels fused with the ReLU function.
  arXiv  Detail & Related papers  (2020-07-28T12:09:43Z)
• MPLP++: Fast, Parallel Dual Block-Coordinate Ascent for Dense Graphical Models [96.1052289276254]
  This work introduces a new MAP-solver, based on the popular Dual Block-Coordinate Ascent principle. Surprisingly, by making a small change to the low-performing solver, we derive the new solver MPLP++ that significantly outperforms all existing solvers by a large margin.
  arXiv  Detail & Related papers  (2020-04-16T16:20:53Z)
• Efficient Video Semantic Segmentation with Labels Propagation and Refinement [138.55845680523908]
  This paper tackles the problem of real-time semantic segmentation of high definition videos using a hybrid GPU / CPU approach. We propose an Efficient Video(EVS) pipeline that combines: (i) On the CPU, a very fast optical flow method, that is used to exploit the temporal aspect of the video and propagate semantic information from one frame to the next. On the popular Cityscapes dataset with high resolution frames (2048 x 1024), the proposed operating points range from 80 to 1000 Hz on a single GPU and CPU.
  arXiv  Detail & Related papers  (2019-12-26T11:45:15Z)

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.