Sawtooth Wavefront Reordering
Yifan Zhu, Yekai Pan, Chen Ding · 2026
Read Sawtooth Wavefront Reordering by Yifan Zhu, Yekai Pan, Chen Ding (2026) 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-2601-16032.txt.
Introduction
Yifan Zhu, Yekai Pan and Chen Ding study how to make attention run fast in large language models. Their 2026 preprint looks at Flash Attention built with CuTile code. Fast attention needs good use of on chip cache. Poor cache use slows each step of the model. The team traced how data moves in cache on an NVIDIA GB10 chip.
From that trace, the authors found the main cause of misses in the L2 cache. They then set out a new order for the work, named sawtooth wavefront order in the title. The new order aims to keep data in cache for more steps. Less time lost to cache misses means faster training and use. The gain counts most for long text runs.
Catalog record
| CREATOR | Yifan Zhu, Yekai Pan, Chen Ding |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 24 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-16032
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Sawtooth Wavefront Reordering Yifan Zhu, Yekai Pan, Chen Ding Abstract . High-performance attention kernels are essential for Large Language Models. This paper presents analysis of CuTile-based Flash Attention memory behavior and a technique to improve its cache performance. In particular, our analysis on the NVIDIA GB10 (Grace Blackwell) identifies the main cause of L2 cache miss. Leveraging this insight, we introduce a new programming technique called Sawtooth Wavefront Reordering that reduces L2 misses. We validate it in both CUDA and CuTile, observing 50% or greater reduction in L2 misses and up to 60% increase in throughput on GB10. Enhanced CuTile FlashAttention on NVIDIA GB10 1. Introduction The Attention mechanism is the computational core of transformer-based generative models ( 14 ; 1 ) . To address its quadratic memory complexity, techniques like Flash Attention ( 2 ) utilize IO-aware tiling to maximize data reuse in on-chip SRAM. Concurrently, programming models such as NVIDIA’s CuTile ( 10 ) facilitate the development of such tiled algorithms by abstracting complex hardware details. While these advancements have democratized high-performance kernel development, the abstraction can obscure the nuanced interactions between thread scheduling and the specific cache hierarchy of modern architectures. Prior work has highlighted the importance of hardware thread scheduling and locality awareness in cache management ( 11 ; 5 ; 6 ) . In this work, we improve the performance of CuTile-based Flash Attention. Our approach begins by using hardware counters and performance models to identify the primary cause of non-compulsory cache misses. We use raw CUDA implementation with specifically designed Thread Block (CTA) scheduling to isolate the effects of memory access from other compiler-induced effects. Our analysis reveals that the L1 cache provides negligible benefit for streaming attention patterns, and that L2 cache behavior follows a deterministic model. We identify a correlation between L2 hit rates and the number of active SMs, suggesting intrinsic data reuse among synchronous wavefronts. Based on these findings, we propose a “Sawtooth” alternating scan pattern that increases L2 cache data reuse. Finally, we port this optimization to the CuTile environment, demonstrating that the insights gained from low-level analysis translate directly to improvements in the high-level programming model. 2. Background 2.1. GPU Memory Hierarchy NVIDIA GPUs are composed of multiple Streaming Multiprocessors (SMs). The CUDA programming model abstracts the parallel execution units as Cooperative Thread Arrays (CTAs), or thread blocks, which are scheduled onto SMs. The memory hierarchy consists of global memory, L2 cache, and the per-SM L1 memory system. The L1 level is often referred to as unified L1/Texture cache (L1Tex) ( 9 ) . Importantly, this L1 memory can be partitioned into L1 cache and shared memory. In high-performance kernels like Fused Multi-Head Attention, developers predominantly rely on Shared Memory rather than the opaque L1 cache. Explicit management allows for deterministic data placement and reuse patterns, essential for the tiling strategies that Flash Attention relies on. NVIDIA GB10 For all our experiments, we use NVIDIA’s latest GB10 processor, which was announced in January 2025 and became available in October 2025. GB10 is a Grace Blackwell chip fabricated on TSMC’s 3nm process node, featuring a unified architecture that combines a Blackwell GPU with 48 streaming multiprocessors and 20 ARM v9.2 CPU cores ( 12 ) . The chip has a 256b bus LPDDR5X 128GB unified memory, with \sim 301GB/s raw bandwidth, and an aggregate bandwidth of \sim 600GB/s. The graphics processor has an L2 cache size of 24MiB. Nsight Compute CLI The Nsight Compute CLI (ncu) ( 8 ) is a command-line tool that provides detailed performance metrics and analysis at the kernel level. The tool offers comprehensive metrics including memory throughput, instruction execution statistics, and occupancy information, making it invaluable for identifying performance bottlenecks and optimizing CUDA kernels. For our experimental purpose, we use the following metrics: lts__t_sectors.sum and lts__t_sector_hit_rate.pct , corresponding to the total number of sectors requested for any operation and the number of cache hit of from these requests respectively. 2.2. Flash Attention and Implmementation Standard scaled dot-product attention computes the output matrix \mathbf{O} as: (1) \mathbf{O}=\text{softmax}\left(\frac{\mathbf{Q}\mathbf{K}^{\top}}{\sqrt{d}}\right)\mathbf{V} where \mathbf{Q},\mathbf{K},\mathbf{V}\in\mathbb{R}^{N\times d} are the query, key, and value matrices. This involves materializing the intermediate attention matrix \mathbf{S}=\mathbf{Q}\mathbf{K}^{\top} and \mathbf{P}=\text{softmax}(\mathbf{S}) , which are of size N\times N . Since N is typically the sequence length, this results in O(N^{2}) memory complexity. FlashAttention ( 2 ) avoids materializing these large intermediate matrices by fusing the computation. It computes the attention output block-by-block. By keeping small tiles of \mathbf{Q},\mathbf{K},\mathbf{V} and intermediate accumulators in the fast on-chip SRAM, it significantly reduces the number of read/write operations to the slow global memory (HBM), practically achieving linear memory complexity with respect to sequence length. We implement and evaluate two Flash Attention kernel variants utilizing WMMA Tensor Core operations. Our study focuses specifically on L2 cache behavior, utilizing a split-Q dataflow where Query tiles remain resident in shared memory while Key and Value tiles are streamed from global memory. Tiling Implementation Given query, key, and value matrices \mathbf{Q},\mathbf{K},\mathbf{V}\in\mathbb{R}^{N\times d} , we employ a tiled approach. Consistent with our implementation code, we enforce square tiling where the block size for the query dimension ( B_{r} ) equals the block size for the key-value dimension ( B_{c} ), denoted as T . For each resident query tile \mathbf{Q}_{i}\in\mathbb{R}^{T\times d} , we stream through blocks of keys and values \{\mathbf{K}_{j},\mathbf{V}_{j}\}_{j=1}^{T_{c}} . The logic follows the standard Flash Attention forward pass: Algorithm 1 Split-Q Fused Multihead Attention with Square Tiling 1: Input: \mathbf{Q},\mathbf{K},\mathbf{V}\in\text{Global Memory} 2: Config: Determine max square tile size T\times T based on SRAM 3: parallel for i=1 to T_{r} do \triangleright Grid-stride loop over Q 4: Load \mathbf{Q}_{i} into Shared Memory (Resident) 5: Initialize \mathbf{O}_{i}=\mathbf{0},\ell_{i}=\mathbf{0},m_{i}=-\infty 6: for j=1 to T_{c} do \triangleright Stream K, V tiles 7: Load \mathbf{K}_{j},\mathbf{V}_{j} into separate Shared Memory buffers 8: Compute \mathbf{S}_{ij}=\mathbf{Q}_{i}\mathbf{K}_{j}^{T} (WMMA) 9: Update Softmax stats m_{i},\ell_{i} (Online Softmax) 10: Compute \mathbf{P}_{ij}=\text{softmax}(\mathbf{S}_{ij}\cdot\text{scale},m_{i},\ell_{i}) 11: Compute \mathbf{O}_{i}\leftarrow\mathbf{O}_{i}+\mathbf{P}_{ij}\mathbf{V}_{j} (WMMA) 12: end for 13: Write \mathbf{O}_{i} to Global Memory 14: end for CTA Scheduling and Work Distribution To manage occupancy and load balancing across the GPU, we employ a persistent CTA (Cooperative Thread Array) pattern with round-robin tile assignment. This gives a deterministic way to study the effect of scheduling on L2 cache. Instead of launching a thread block for every query tile (which could lead to tail effects where some SMs are idle while others finish the last wave), we launch a fixed number of thread blocks. Each thread block (CTA) executes a grid-stride loop, claiming available Query tiles in a round-robin fashion. This ensures that all SMs remain active until the entire workload is near completion. Algorithm 2 Persistent CTA Scheduling (Grid-Stride Loop) 1: Input: Total Query Tiles N_{tiles} , Grid Size G 2: Given: GPU SM Count N_{SM} 3: G\leftarrow\min(N_{tiles},N_{SM}) \triangleright One persistent CTA per SM 4: k\leftarrow\text{blockIdx.x} 5: while k<N_{tiles} do 6: Identify ( Batch,Head,TileIndex ) from linear index k 7: Execute Algorithm 1 for this Query tile 8: k\leftarrow k+G \triangleright Stride by total number of CTAs 9: end while Alternatively, we can employ an approach where CTAs are launched directly based on the work size. In this scheme, the grid size is set exactly to cover the total number of query tiles (potentially split by batch and