Multi-layer Dataflow: Orchestrate Butterfly Sparsity to Accelerate Attention Computation
Haibin Wu 1 , Wenming Li 1,∗ , Kai Yan 1,∗ , Zhihua Fan 1,∗ , Peiyang Wu 1 , Yuqun Liu 1 , Yanhuan Liu 1 , Ziqing Qiang 1 , Meng Wu 1 , Kunming Zhang 1 , Xiaochun Ye 1 , Dongrui Fan 1 · 2024
Read Multi-layer Dataflow: Orchestrate Butterfly Sparsity to Accelerate Attention Computation by Haibin Wu 1 , Wenming Li 1,∗ , Kai Yan 1,∗ , Zhihua Fan 1,∗ , Peiyang Wu 1 , Yuqun Liu 1 , Yanhuan Liu 1 , Ziqing Qiang 1 , Meng Wu 1 , Kunming Zhang 1 , Xiaochun Ye 1 , Dongrui Fan 1 (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2411-00734.txt.
Description
Abstract Recent neural networks (NNs) with self attention exhibits competitiveness across different AI domains, but the essential attention mechanism brings massive computation and memory demands. To this end, various sparsity patterns are introduced to reduce the quadratic computation complexity, among which the structured butterfly sparsity has been proven efficient in computation reduction while maintaining model accuracy.
Catalog record
| CREATOR | Haibin Wu 1 , Wenming Li 1,∗ , Kai Yan 1,∗ , Zhihua Fan 1,∗ , Peiyang Wu 1 , Yuqun Liu 1 , Yanhuan Liu 1 , Ziqing Qiang 1 , Meng Wu 1 , Kunming Zhang 1 , Xiaochun Ye 1 , Dongrui Fan 1 |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 40 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2411-00734
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Multi-layer Dataflow: Orchestrate Butterfly Sparsity to Accelerate Attention Computation Haibin Wu 1 , Wenming Li 1,∗ , Kai Yan 1,∗ , Zhihua Fan 1,∗ , Peiyang Wu 1 , Yuqun Liu 1 , Yanhuan Liu 1 , Ziqing Qiang 1 , Meng Wu 1 , Kunming Zhang 1 , Xiaochun Ye 1 , Dongrui Fan 1 Abstract Recent neural networks (NNs) with self attention exhibits competitiveness across different AI domains, but the essential attention mechanism brings massive computation and memory demands. To this end, various sparsity patterns are introduced to reduce the quadratic computation complexity, among which the structured butterfly sparsity has been proven efficient in computation reduction while maintaining model accuracy. However, its addressing inefficiency brings utilization degradation and makes parallelism hard to exploit in general block-oriented architecture like GPU. Since the reconfigurable dataflow accelerators have shown the superiority of better data reusability and architectural flexibility towards general NN-based acceleration, we propose a scalable multilayer dataflow method supported with coarse-grained streaming parallelism, to orchestrate the butterfly sparsity computation on dataflow array. The experiments show that compared with Jetson Xavier NX, our design has a speedup of up to 14.34 × 14.34\times ( 9.29 × 9.29\times on average) as well as 12.3 × 12.3\times energy efficiency advancement in attention workloads. In comparison with SOTA butterfly accelerator, our design acquires 1.17 × 1.17\times speedup and 3.36 × 3.36\times energy efficiency improvement, at the same peak performance. I Introduction Prevailing deep learning method, such as Transformer , has dominated various domains in Natural Language Processing (NLP) and Computer Vision (CV) [ 1 ] . Its prominent attention mechanisms [ 2 ] capture comprehensive relationships between tokens and features, through linear mapping implemented by matrix-vector multiplication. However, the computational complexity of attention increases quadratically with the token length, which can extend up to 64K in long sequences, as observed in BERT [ 3 ] , resulting in substantial computation and memory demands. Various speedup methods with diverse sparsity patterns [ 4 , 5 , 6 ] have been introduced in the computation process of {Q,K,V} and softmax(Q(K)^{T})V to alleviate the computation and memory demands. Based on the theoretical evidence provided by recent research [ 7 , 8 ] , structured sparsity does not significantly compromise model accuracy, compared with dynamic sparsity [ 9 , 10 ] . Dynamic sparsity poses challenges in general architecture, like GPU due to the inefficiency associated with randomized addressing . They often require customized hardware to achieve dynamic element compression or rearrangement within matrices [ 11 , matRaptor ] . In contrast, structured sparsity offers predictable addressing regulations that can be efficiently applied through matrix layout optimization during programming or compiling. Among various structured sparsity, butterfly sparsity has been recently proven efficient in enhancing performance of attention workloads while maintaining accuracy across diverse AI tasks [ 8 ] . As shown in Fig. 1 a&1b, one of the butterfly sparsity approach is to simplify the linear weight matrices for Q,K,V by using a set of O(logN) butterfly matrices B_{i} that have the same sparsity rate of 2/N respectively [ 12 , 7 ] . This is a technique we refer to as butterfly pattern matrix-vector multiplication (BPMM) . Another approach, such as FNet [ 13 ] , applies 2D Fast Fourier Transform (2D-FFT) on tokens to heavily decrease the computation amount in attention layers, as illustrated in Fig. 1 c. With these simplifications, the original dense product is replaced with butterfly computation to reduce the complexity and weight size from O(N^{2}) to O(N\log N) . Fig. 1 : Transformer network with butterfly pattern simplification. Fig. 2 : Profiling original dense-based attention and fft-based attention kernels of VIT and BERT on the GPU platform - Jetson Xavier NX. General block-oriented architecture - GPU excels in dense matrix computation, though it lacks energy efficiency, compared to dataflow architectures like TPU [ 14 ] and Plasticine [ 15 ] . In terms of butterfly sparsity, however, the cache-unfriendly addressing results in performance degradation on GPUs. We conducted analyses on NVIDIA - Jetson Xavier NX, by comparing the original dense attention kernels ( to\_qkv and softmax(qk)*v ) and the butterfly attention kernels ( fft-sequence and fft-hidden ) of VIT and BERT. Detailed profiling results are presented in Fig. 2 . Although the data throughput is given in adequate batch parallelism of 128 in GPU, the hit rates , especially for the L1 cache, exhibit significant degradation in the FFT-based kernels compared to the dense q,k,v kernels in both VIT and BERT. Furthermore, their overall performance indicated by duration time fails to exhibit obvious speedup (even a reduced performance for BERT in large scales), despite the theoretical reduction of computational complexity mentioned above with the butterfly sparsity. Aiming for tackling the challenges of accessing inefficiency and parallelism exploitation hardness in structured butterfly sparsity computation, we introduce a scalable multilayer dataflow orchestration method applied on a flexible reconfigurable dataflow architecture, to speed up butterfly computation for attention workloads. Our contributions are as follows: • Algorithm aspects: • i . We propose a multilayer dataflow method to tackle the hardness of orchestrate the data reuse of butterfly sparsity on a reconfigurable dataflow architecture substrate . ii . we equip this dataflow substrate with block-level DFG node scheduling as well as the decoupled function unit design, to exploit effective coarse-grained streaming parallelism . • iii . We introduce a multi-stage division method based on the Cooley-Tukey algorithm to enhance the scalability of our dataflow approach towards butterfly sparsity in various data scales. iv . Moreover, we architect the scratchpad memory with a multi-line design to implement transpose-free SIMD parallelism in large-scale vector sequence for boosting the overall computation performance. • Experiment results demonstrate the superiority of the proposed multilayer dataflow method with outstanding speedup and energy efficiency in attention workloads over the advanced GPU and state-of-the-art accelerators. II Background and Related Work In this session, we begin by discussing the existing variants of sparsity in attention workloads and emphasize the superiority of butterfly sparsity for global relationships capturing. Next, we summarize the shortcomings in recent architectural works towards butterfly sparsity computation. Fig. 3 : Fundamental patterns in existing sparsity variants. II-A Sparsity Variants for Attention Computation The prominent self-attention mechanism effectively facilitates interaction among tokens and features, overcoming the limitations of CNNs and RNNs. But it is plagued by quadratic computation and memory requirements. Recent sparse attention approaches introduce diverse sparsity patterns in attention matrices or linear weighted matrices, as shown in Fig. 3 . One notable implementation is dynamic sparsity, which is determined by the sequence content . Kitaev et al. [ 9 ] proposed Locality Sensitive Hashing (LSH) to infer content-based sparsity. Qu et al . utilized low-rank linear transformations to estimate attention scores [ 10 ] and select the sparse pattern dynamically through top-k selection. However, these content-based methods scale poorly in long sequence and may be application-fixed and awkward when facing with variable sparse density. Static structured sparsity as an alternative method addresses these drawbacks by applying regular sparsity patterns to attention and linear matrices. Common structured approaches often combine several basic patterns shown in Fig. 3 .(a,b,d). For instance, Child et al . [ 16 ] introduced a sparsity model combining