FlashAttention on a Napkin: A Diagrammatic Approach to Deep Learning IO-Awareness

Vincent Abbott [email protected], Gioele Zardini [email protected] · 2024

Read FlashAttention on a Napkin: A Diagrammatic Approach to Deep Learning IO-Awareness by Vincent Abbott [email protected], Gioele Zardini [email protected] (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-2412-03317.txt.

Introduction

Vincent Abbott and Gioele Zardini explain a famous speed trick for neural networks with diagrams in a 2024 paper. The trick, FlashAttention, made attention about six times faster than the standard library by cutting needless data moves. It took three rounds over three years to develop by hand. Automated compilers have lagged behind such hand-tuned work.

The authors extend a diagram language for neural networks so it also tracks data movement and chip layout. Simple relabeling of diagrams then yields streaming and tiling plans, plus models of the speed gained. The same frame handles number formats and multi-level chip memory. Step-by-step diagrams rebuild known methods such as FlashAttention, turning GPU tuning into a testable science rather than guesswork.

Catalog record

CREATORVincent Abbott [email protected], Gioele Zardini [email protected]
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE86 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-03317

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

FlashAttention on a Napkin: A Diagrammatic Approach to Deep Learning IO-Awareness Vincent Abbott [email protected], Gioele Zardini [email protected] Abstract Optimizing deep learning algorithms currently requires slow, manual derivation, potentially leaving much performance untapped. Methods like FlashAttention have achieved a × 6 \times 6 performance improvement over native PyTorch by avoiding unnecessary data transfers, but required three iterations over three years to be developed. Automated compiled methods have consistently lagged behind. This paper extends Neural Circuit Diagrams for deep learning models to consider resource usage and the distribution of tasks across a GPU hierarchy. We show how diagrams can use simple relabellings to derive high-level streaming and tiling optimization strategies along with performance models. We show how this high-level performance model allows the effects of quantization and multi-level GPU hierarchies to be readily considered. We develop a methodology for representing intermediate-level pseudocode with diagrams, allowing hardware-aware algorithms to be derived step-by-step. Finally, we show how our methodology can be used to better understand existing techniques like FlashAttention. This work uses a theoretical framework to link assumptions about GPU behaviour to claims about performance. We aim to lay the groundwork for a scientific approach to GPU optimization where experiments can address clear hypotheses rather than post-hoc rationalizations. 1 Introduction 1.1 Background To execute an operation, graphical processing units (GPUs) must move data from high-level DRAM to low-level compute cores. GPUs are as limited as much by GB/s of memory bandwidth as TFLOPs of available compute. However, AI models have passed the memory wall —algorithms are increasingly limited by bandwidth/transfer costs ( Ootomo & Yokota, 2023 ; Ivanov et al., 2021 ; Gholami et al., 2024 ) , as compute capability has improved far more quickly \times 3/2 y than DRAM bandwidth \times 1.6/2 y ( Gholami et al., 2024 ) . Furthermore, DRAM already accounts for 46\% of total system power ( Ghose et al., 2018 ) . As memory becomes increasingly inefficient relative to compute, the importance of considering transfer costs— IO-awareness ( Dao et al., 2022 ; Aggarwal & Vitter, 1988 ) —will become even more critical. FlashAttention ( Dao et al., 2022 ; Dao, 2023 ; Shah et al., 2024 ) is an IO-aware approach to attention that overcomes the memory wall. Attention ( Vaswani et al., 2017 ) is central to generative models, including large language models (LLMs) ( Jiang et al., 2024 ; Dubey et al., 2024 ) and image generation algorithms ( Ho et al., 2020 ; Esser et al., 2024 ; Rombach et al., 2022 ; Podell et al., 2023 ) . FlashAttention fuses the steps of attention. It computes all sequential steps on low-level memory, avoiding unnecessary intermediate data transfers. It achieves a \times 6 increase in throughput compared to standard PyTorch, arguably making large contemporary models possible. However, the conditions under which fusion is possible are not generally exploited. Simple cases like element-wise functions can be compiled into matrix multiplications ( Li et al., 2020 ; Paszke et al., 2019 ; Sabne, 2020 ) , but the bespoke techniques of FlashAttention required manual derivation and three iterations over three years to take full advantage of Hopper hardware ( NVIDIA, 2022 ) features. Triton ( Tillet et al., 2019 ) offers some compilation for hardware features but has lagged behind new FlashAttention algorithms ( Dao, 2023 ; Shah et al., 2024 ) . The current best technique for generating IO-aware algorithms that exploit hardware features remains slow, manual derivation. Innovating new optimized algorithms is essential to efficient model deployment. In addition to FlashAttention, methods like grouped query attention ( Ainslie et al., 2023 ) , KV-caching ( Shazeer, 2019 ) , and quantization ( Frantar et al., 2023 ; Gholami et al., 2021 ) all reduce transfer costs while having minimal impact on the function we implement or the quality of model outputs. Much like fusion, the success of these approaches relies on understanding the compositional structure of algorithms so that similar but less costly algorithms can be executed. A systematic approach to innovating optimized algorithms will require a mechanism for understanding the compositional structure of algorithms along with a performance model which compares varying means of executing the same operation. The hardware characteristics of GPUs have a significant impact on performance which varies depending on the target algorithm. When choosing between A100s, H100 SXM5s, or H100 PCIes ( NVIDIA, 2022 , p.39) , we must consider the varying compute, bandwidth, intermediate hierarchies, architecture features, and low-level memory, for which we pay in environmental and economic resources. The application of these features is often non-obvious, FlashAttention-2 ( Dao, 2023 ) was released while the hardware for FlashAttention-3 already existed ( Shah et al., 2024 ) , which achieved \sim 75\% improvement in forward speed. Understanding the impact of GPU features is a necessary component of innovating optimized approaches and making full use of deployed resources. 1.2 Contributions This paper contributes a representational scheme for deep learning algorithms based on Neural Circuit Diagrams that shows the distribution of tasks across a GPU hierarchy and associated resource usages (Section 2 ). This scheme incorporates theorems about the compositional properties of fused algorithms (Appendix A.1 ), allowing for the rapid derivation of high-level sketches of GPU optimized matrix multiplication and attention, along with performance models (Section 3 ). This performance model can consider quantization and multi-level hierarchies (Section 4 ), bolstered by theorems (Appendix A.2 ). With a model corresponding to a Hopper-like architecture, we use a step-by-step process to derive hardware-aware algorithms (Section 5 ). These derivations can consider coalesced memory access, tensor-core operations, and overlapping operations, and reveal the degrees of freedom in the algorithm’s configuration. Our methodology can be used to analyse the bottlenecks of existing methods like FlashAttention (Section 6 ). The main value of this work is providing a potential framework for relating assumptions about GPU behavior to claims about performance. This allows future empirical work to address and improve specific assumptions, thereby iteratively improving the model. This contrasts with the prevailing “tinkering” approach within deep learning that develops post-hoc intuition based on past experiments. Post-hoc intuition is trained on the “test set” of prior successful approaches, weakening generalizability and scientific value. Our diagrammatic scheme allows the rapid application of the framework to algorithms used in practice, distinguishing it from descriptive theory and toy model approaches. Diagrams leverage human visual comprehension and enable complex theorems and underlying implications to be encapsulated with simple notation. 2 Diagramming Deep Learning Algorithms 2.1 Diagramming Functions and Data Types Diagrams have alternating columns of data types and functions. Data type columns are shown in Figure 3 . Arrays such as \mathbb{R}^{a\times b\times c} are represented by a wire for each axis labeled with the size. Data types may be tuples of arrays, such as \mathbb{R}^{a\times b\times c}\times\mathbb{R}^{d\times e\times c} , and are represented by placing a dashed line between constituent arrays. Figure 3: We represent arrays, of forms such as \displaystyle\mathbb{R}^{a\times b\times c} , by labeling stacked wires in a column with \displaystyle a , \displaystyle b , and \displaystyle c . To represent data types that consist of lists of arrays, such as \displaystyle\mathbb{R}^{a\times b\times c}\times\mathbb{R}^{d\times e} , we place a dashed line between them. Functions

Read the complete text