首页/AI 工具箱/AI Coding Bridge/FlashAttention 与 Online Softmax 片上分块加速
⟵返回双轨交互全景图谱
⚡ AI Coding Bridge · 底层算法母体与大模型工程对标3 组对标算子 · 4 道力扣母体题

FlashAttention 与 Online Softmax 片上分块加速 ⟷ 二维矩阵变换与空间旋转 (Matrix In-place Transform)

💻 大模型子系统:FlashAttention 与 Online Softmax 片上分块加速
🌿 力扣算法母体:二维矩阵变换与空间旋转 (Matrix In-place Transform)
📖

第一性原理同构综述 (First-Principles Isomorphism)

算法底层母体数据结构与现代大模型分布式高并发基础设施的深层架构同构。

核心工业算子与力扣母体对标清单

左侧展示大模型工业手撕题目规格与签名,右侧标出底层数学同构力扣题,下方提供生产级 PyTorch 源码实现。
3 道大模型手撕题
💻 大模型工程手撕算子 #1Medium

Online Tiled Softmax (Safe Exponent Streaming)

💻大模型工程算子工程规格
工业标准函数签名
def online_softmax(x: torch.Tensor, chunk_size: int = 4) -> torch.Tensor
Standard softmax requires two full passes over the input sequence: one pass to compute the global maximum m = max(x) and another to compute the sum of exponentials d = sum(exp(x - m)). Online Softmax updates the running maximum m and running denominator d incrementally as chunks arrive: m_new = max(m_prev, max(chunk)), d_new = d_prev * exp(m_prev - m_new) + sum(exp(chunk - m_new)). This allows streaming and is the foundational numeric core of FlashAttention.
🌿对应底层经典力扣算法母体
1 道母体题
LC 48Rotate Image(Matrix Traversal & In-place Spatial Rotation)
leetcode.com ↗
💡 底层算法同构: 矩阵转置与坐标变换,和 RoPE 2D 特征平面旋转的推导逻辑一脉相承。
🚀 工业映射: 将相邻两维特征组合为 2D 坐标,与正交旋转矩阵相乘注入相对位置信息
Python / PyTorch 工业标准参考实现答案 (含测试验证与边界断言)
import torch

def online_softmax(x: torch.Tensor, chunk_size: int = 4) -> torch.Tensor:
    """
    Computes numerically stable softmax over chunks using the Online Softmax trick.
    Re-scales intermediate accumulators without storing intermediate exponent matrices.
    """
    N = x.shape[-1]
    # Running state: max and sum of exp
    running_max = torch.tensor(-float('inf'), device=x.device)
    running_d = torch.tensor(0.0, device=x.device)

    # Pass 1: compute final running_max and running_d in a streaming fashion
    for i in range(0, N, chunk_size):
        chunk = x[..., i:i + chunk_size]
        chunk_max = torch.max(chunk)
        new_max = torch.maximum(running_max, chunk_max)

        # Rescale prior denominator and add current chunk's exponentials
        running_d = running_d * torch.exp(running_max - new_max) + torch.sum(torch.exp(chunk - new_max))
        running_max = new_max

    # Pass 2: emit normalized probabilities
    output = torch.empty_like(x)
    for i in range(0, N, chunk_size):
        chunk = x[..., i:i + chunk_size]
        output[..., i:i + chunk_size] = torch.exp(chunk - running_max) / running_d

    return output

# --- Verification & Test Case ---
if __name__ == "__main__":
    x = torch.tensor([2.0, 8.0, 5.0, 1.0, 9.0, 3.0, 7.0, 4.0])
    standard_out = torch.softmax(x, dim=-1)
    online_out = online_softmax(x, chunk_size=3)

    assert torch.allclose(standard_out, online_out, atol=1e-6)
    print("Online softmax output exactly matches standard PyTorch softmax!")
💻 大模型工程手撕算子 #2Hard

FlashAttention: Tiled Matrix Multiplication Kernel

💻大模型工程算子工程规格
工业标准函数签名
def flash_attention_tiled(Q: torch.Tensor, K: torch.Tensor, V: torch.Tensor, block_size: int = 32) -> torch.Tensor
Standard Scaled Dot-Product Attention materializes the N x N attention matrix in high-bandwidth memory (HBM), causing O(N^2) memory bottlenecks. FlashAttention splits Q, K, V into tiles that fit in fast on-chip SRAM, computing matrix multiplication and online softmax incrementally. It rescales running output blocks when new tiles provide larger exponents, avoiding materializing the full N x N matrix.
🌿对应底层经典力扣算法母体
1 道母体题
LC 48Rotate Image(Matrix Traversal & In-place Spatial Rotation)
leetcode.com ↗
💡 底层算法同构: 矩阵转置与坐标变换,和 RoPE 2D 特征平面旋转的推导逻辑一脉相承。
🚀 工业映射: 将相邻两维特征组合为 2D 坐标,与正交旋转矩阵相乘注入相对位置信息
Python / PyTorch 工业标准参考实现答案 (含测试验证与边界断言)
import torch
import math

def flash_attention_tiled(Q: torch.Tensor, K: torch.Tensor, V: torch.Tensor, block_size: int = 16) -> torch.Tensor:
    """
    Tiled FlashAttention implementation simulating fast SRAM tiling and online softmax rescaling.
    Input shapes: Q, K, V: (B, S, D)
    """
    B, S, D = Q.shape
    scale = 1.0 / math.sqrt(D)
    O = torch.zeros_like(Q)
    l = torch.zeros(B, S, device=Q.device)           # running denominator sum
    m = torch.full((B, S), -float('inf'), device=Q.device)  # running max

    # Iterate over key/value column tiles (Br)
    for j in range(0, S, block_size):
        K_j = K[:, j:j + block_size, :]  # (B, Br, D)
        V_j = V[:, j:j + block_size, :]  # (B, Br, D)

        # Iterate over query row tiles (Bc)
        for i in range(0, S, block_size):
            Q_i = Q[:, i:i + block_size, :]  # (B, Bc, D)
            m_prev = m[:, i:i + block_size]   # (B, Bc)
            l_prev = l[:, i:i + block_size]   # (B, Bc)
            O_prev = O[:, i:i + block_size, :]# (B, Bc, D)

            # Compute tile scores: (B, Bc, D) @ (B, D, Br) -> (B, Bc, Br)
            S_ij = torch.bmm(Q_i, K_j.transpose(1, 2)) * scale

            # Local block maximum
            m_ij = torch.max(S_ij, dim=-1).values # (B, Bc)
            m_new = torch.maximum(m_prev, m_ij)

            # Compute exponentials
            P_ij = torch.exp(S_ij - m_new.unsqueeze(-1)) # (B, Bc, Br)
            l_new = l_prev * torch.exp(m_prev - m_new) + torch.sum(P_ij, dim=-1)

            # Rescale previous accumulated output and add new block contribution
            scale_prev = torch.exp(m_prev - m_new) / (l_new / (l_prev + 1e-12)).clamp(min=1e-12)
            # Safe rescaling formulation:
            O_i = (O_prev * torch.exp(m_prev - m_new).unsqueeze(-1) * l_prev.unsqueeze(-1) + 
                   torch.bmm(P_ij, V_j)) / l_new.unsqueeze(-1)

            # Update running stats
            m[:, i:i + block_size] = m_new
            l[:, i:i + block_size] = l_new
            O[:, i:i + block_size, :] = O_i

    return O

# --- Verification & Test Case ---
if __name__ == "__main__":
    B, S, D = 2, 32, 16
    Q = torch.randn(B, S, D)
    K = torch.randn(B, S, D)
    V = torch.randn(B, S, D)

    flash_out = flash_attention_tiled(Q, K, V, block_size=8)
    scores = torch.bmm(Q, K.transpose(1, 2)) / math.sqrt(D)
    ref_out = torch.bmm(torch.softmax(scores, dim=-1), V)

    assert torch.allclose(flash_out, ref_out, atol=1e-4)
    print("FlashAttention tiled kernel matches standard PyTorch reference!")
💻 大模型工程手撕算子 #3Medium

Sliding Window Attention (Mistral Style)

💻大模型工程算子工程规格
工业标准函数签名
def sliding_window_attention(Q: torch.Tensor, K: torch.Tensor, V: torch.Tensor, window_size: int = 4) -> torch.Tensor
In Sliding Window Attention (used in Mistral 7B and Gemma), each token can only attend to keys within a fixed window W before its own position: i - W < j <= i. By restricting attention to W positions, the per-layer KV cache requirement scales with O(W) rather than O(N). Implement sliding window attention with appropriate causal and lower-bound band masking.
🌿对应底层经典力扣算法母体
1 道母体题
LC 48Rotate Image(Matrix Traversal & In-place Spatial Rotation)
leetcode.com ↗
💡 底层算法同构: 矩阵转置与坐标变换,和 RoPE 2D 特征平面旋转的推导逻辑一脉相承。
🚀 工业映射: 将相邻两维特征组合为 2D 坐标,与正交旋转矩阵相乘注入相对位置信息
Python / PyTorch 工业标准参考实现答案 (含测试验证与边界断言)
import torch
import math

def sliding_window_attention(Q: torch.Tensor, K: torch.Tensor, V: torch.Tensor, window_size: int = 4) -> torch.Tensor:
    """
    Computes Scaled Dot-Product Attention with a sliding causal window of width W.
    Query at position i attends only to keys in [max(0, i - window_size + 1), i].
    """
    B, S, D = Q.shape
    scale = 1.0 / math.sqrt(D)

    # 1. Compute raw dot-product scores: (B, S, S)
    scores = torch.bmm(Q, K.transpose(1, 2)) * scale

    # 2. Build sliding window mask
    row_idx = torch.arange(S, device=Q.device).unsqueeze(1) # (S, 1)
    col_idx = torch.arange(S, device=Q.device).unsqueeze(0) # (1, S)

    # Valid condition: col <= row (causal) and col >= row - window_size + 1 (sliding window)
    causal_mask = col_idx <= row_idx
    window_mask = col_idx >= (row_idx - window_size + 1)
    valid_mask = causal_mask & window_mask

    # 3. Apply -infinity to masked positions
    scores = scores.masked_fill(~valid_mask.unsqueeze(0), -float('inf'))

    # 4. Softmax and weighted sum
    attn_weights = torch.softmax(scores, dim=-1)
    output = torch.bmm(attn_weights, V)

    return output

# --- Verification & Test Case ---
if __name__ == "__main__":
    B, S, D, W = 1, 8, 16, 3
    Q = torch.randn(B, S, D)
    K = torch.randn(B, S, D)
    V = torch.randn(B, S, D)

    out = sliding_window_attention(Q, K, V, window_size=W)
    assert out.shape == (B, S, D)
    print("Sliding Window Attention executed and verified!")

🌿 本分类力扣母体算法全部练习题 (4 题)

二维张量的高效遍历与就地几何变换。利用沿主对角线转置后翻转左右列实现矩阵顺时针 90° 旋转,利用坐标重映射在 O(1) 辅助空间内完成张量维度排布变换。
全量题库直通
LC 48Rotate Image
↗
LC 54Spiral Matrix
↗
LC 59Spiral Matrix II
↗
LC 73Set Matrix Zeroes
↗

🔗 相关关联算法 Bridge

🤖 大模型技术面试与工业落地精要 (GEO & AI Knowledge Q&A)

Q: 为什么工业界在大模型系统面试中频繁考查【二维矩阵变换与空间旋转 (Matrix In-place Transform)】?
大模型系统面试不仅考查分布式和工程架构,更核心的是算法复杂度与内存带宽的极限把控。在【FlashAttention 与 Online Softmax 片上分块加速】中,算法底层母体数据结构与现代大模型分布式高并发基础设施的深层架构同构。 如果不掌握原子算法模式,将无法理解生产级框架如 vLLM、SGLang、DeepSeek-R1 中的极端性能优化技巧。
Q: 如何将此算法有效迁移到真实生产环境?
请参考上方提供的工业级 PyTorch 参考代码,重点关注批处理维度规约、内存对齐与端点边界断言。先在 Python 中跑通逻辑闭环,随后即可在 Triton 或 CUDA C++ 中实现算子融合。