跳转到正文
Retep's
返回

[TIL] 优化 Paged Attention

编辑文章

本文由英文原文翻译。代码、公式与技术名称保留原文。

本文介绍如何使用 Nsight Compute 分析和优化 paged attention kernel。

Paged Attention

Attention 的基本想法是从 token 序列推导其潜在状态。把序列看成一维向量列表,训练三个投影矩阵 QQ、KK、VV。每个 token 向量 ee 得到 Q(e)Q(e)、K(e)K(e)。给定 query token eqe_q,对序列中的每个 ee 计算 Q(eq)⋅K(e)scale\dfrac{Q(e_q)\cdot K(e)}{scale},再对所有分数做 Softmax,用对应权重对 V(e)V(e) 加权求和。直观上,就是根据 query 与 key 的匹配程度决定 value 的权重。

Paged attention 的核心是缓存复用。生成序列时,已有 token 的 K(e)K(e)、V(e)V(e) 已经算过,可以复用,避免重复投影。

数据布局

本实验采用分层布局。最上层是 batch,每个 batch 包含逻辑页列表,逻辑页指向物理页。这里简化为连续全局内存中的页索引。每个物理页连续存储 page_size 个 token,每个 token 包含 kv_heads 个长度为 head_dim 的 KV 头。query 输入与输出布局相似:每个 batch 只有一个输入 query,包含 query_heads 个长度为 head_dim 的头向量。

布局示意 布局示意 布局示意

基线

基线故意写得简单。

#include "paged_attention/api.cuh"

#include <cmath>

namespace pa {
namespace {

// Each output element redundantly
// recomputes every Q.K dot product. It is simple, deterministic, and correct,
// making it a useful profiling baseline rather than a performance target.
__global__ void paged_attention_baseline_kernel(Problem p, Inputs in, float *__restrict__ out) {
  int const q_head = blockIdx.x;
  int const batch = blockIdx.y;
  int const d_out = threadIdx.x;
  if (d_out >= p.head_dim)
    return;

  int const kv_head = q_head / p.queries_per_kv();
  int const context = in.context_lengths[batch];
  float running_max = -INFINITY;
  float running_sum = 0.0f;
  float accumulator = 0.0f;

  for (int token = 0; token < context; ++token) {
    // For each token t, get its cached K(t) and V(t)
    // Assuming for this session, token is continously stored in pages
    // e.g. the ith token is stored in i / page_size th page

    int const logical_page = token / p.page_size;
    int const token_in_page = token % p.page_size;
    // block tables maps token index to the physical page
    // each batch(or "stream") can contain max_pages_per_sequence pages
    /*
    stream 1:   p0,  p1,   p2,   #,  #,  #,  #,  #
    stream 2:   p8,  t9,   t10,  #,  #,  #,  #,  #
    stream 3:   t16, t17,  t18,  #,  #,  #,  #,  #

    # for placeholder (blank page), assuming max_pages_per_sequence=8

    */
    int const physical_page = in.block_tables[batch * p.max_pages_per_sequence + logical_page];

    // this assumes pages are stored continously. therefore the start of the page is
    // physical_page * page_size entries away from the base.
    // Each entry has kv_heads * head_dim fp16
    // Finally add the current kv_head we are computing against, which means another kv_head *
    // head_dim fp16 offset
    std::size_t const kv_base =
        ((static_cast<std::size_t>(physical_page) * p.page_size + token_in_page) * p.kv_heads +
         kv_head) *
        p.head_dim;

    // get the query of the current query token
    std::size_t const q_base =
        (static_cast<std::size_t>(batch) * p.query_heads + q_head) * p.head_dim;

    float score = 0.0f;
    for (int d = 0; d < p.head_dim; ++d) {
      // manually perform dot product of query_head * kv_head
      score = fmaf(in.query[q_base + d], in.key_cache[kv_base + d], score);
    }
    score *= in.scale;

    float const new_max = fmaxf(running_max, score);
    float const old_factor = running_max == -INFINITY ? 0.0f : __expf(running_max - new_max);
    float const new_factor = __expf(score - new_max);
    running_sum = running_sum * old_factor + new_factor;
    accumulator = accumulator * old_factor + new_factor * in.value_cache[kv_base + d_out];
    running_max = new_max;
  }
  // softmax across all tokens, store to the output

  std::size_t const out_index =
      (static_cast<std::size_t>(batch) * p.query_heads + q_head) * p.head_dim + d_out;
  out[out_index] = accumulator / running_sum;
}

} // namespace

void launch_baseline(Problem const &p, Inputs const &in, float *out, cudaStream_t stream) {
  dim3 const grid(p.query_heads, p.batch);
  int const threads = p.head_dim <= 64 ? 64 : 128;
  paged_attention_baseline_kernel<<<grid, threads, 0, stream>>>(p, in, out);
}

} // namespace pa

每个 block 负责一个 batch 和一个 query head,每个线程负责一个输出维度。线程遍历全部 token,计算所有维度的点积以获得分数、最大值和指数和,最后只返回自身维度的输出。由于每线程都遍历全部维度,这里的在线 Softmax 几乎比普通版本做更多工作。性能分析如下:

    Section: GPU Speed Of Light Throughput
    ----------------------- ----------- --------------
    Metric Name             Metric Unit   Metric Value
    ----------------------- ----------- --------------
    DRAM Frequency                  Ghz          13.79
    SM Frequency                    Ghz           2.60
    Elapsed Cycles                cycle    312,174,573
    Memory Throughput                 %          89.78
    DRAM Throughput                   %           2.40
    Duration                         ms         119.98
    L1/TEX Cache Throughput           %          91.72
    L2 Cache Throughput               %           2.23
    SM Active Cycles              cycle 305,463,204.67
    Compute (SM) Throughput           %          89.78
    ----------------------- ----------- --------------

    Section: GPU and Memory Workload Distribution
    -------------------------- ----------- --------------
    Metric Name                Metric Unit   Metric Value
    -------------------------- ----------- --------------
    Average DRAM Active Cycles       cycle     39,683,480
    Total DRAM Elapsed Cycles        cycle  6,617,162,752
    Average L1 Active Cycles         cycle 305,463,204.67
    Total L1 Elapsed Cycles          cycle 11,234,537,952
    Average L2 Active Cycles         cycle 235,037,434.56
    Total L2 Elapsed Cycles          cycle  4,453,487,280
    Average SM Active Cycles         cycle 305,463,204.67
    Total SM Elapsed Cycles          cycle 11,234,537,952
    Average SMSP Active Cycles       cycle 305,463,153.95
    Total SMSP Elapsed Cycles        cycle 44,938,151,808
    -------------------------- ----------- --------------

SM 和 L1 很忙,DRAM 却几乎没被充分利用。乍看像是缓存命中好、occupancy 高,实际上可能只是重复工作。本例重复了 head_dim 次点积,head_dim=128 时就是 128 倍;高 occupancy 无法抵消约两个数量级的冗余分数计算。

V1:协作计算

第一步自然是消除冗余。仍然每个 (batch, query_head) 一个 CTA,但线程合作计算一次 QK 点积,通过共享内存归约各 warp 部分和,再用在线 Softmax 更新不同输出维度。重复点积消失了,代价是每个 token 都要进行 CTA 通信与同步。

#include "paged_attention/api.cuh"
#include <cmath>
namespace pa {

namespace {

__device__ float warp_reduce_sum(float value) {
  // each warp has 32 lanes
  for (int offset = 16; offset > 0; offset /= 2) {
    // 0xfffffff means all lanes participate
    value += __shfl_down_sync(0xffffffff, value, offset);
  }
  return value;
}

__global__ void paged_attention_fused_kernel(Problem p, Inputs in, float *out) {
  int const q_head = blockIdx.x;
  int const batch = blockIdx.y;

  int const d = threadIdx.x;
  int const lane = threadIdx.x & 31;
  int const warp = threadIdx.x >> 5;
  const int num_warps = blockDim.x / 32;

  // each thread computes one dimension, and reduce to become dot product
  if (d >= p.head_dim) {
    return;
  }
  int const kv_head = q_head / p.queries_per_kv();

  const std::size_t q_base =
      ((static_cast<std::size_t>(batch)) * p.query_heads + q_head) * p.head_dim;
  float q = in.query[q_base + d];
  float running_max = -INFINITY;
  float running_sum = 0.0f;
  float accumulator = 0.0f;

  const int num_pages = (in.context_lengths[batch] + p.page_size - 1) / p.page_size;
  for (int logical_page = 0; logical_page < num_pages; ++logical_page) {
    const int physical_page = in.block_tables[batch * p.max_pages_per_sequence + logical_page];
    int valid_tokens = min(p.page_size, in.context_lengths[batch] - logical_page * p.page_size);
    for (int token = 0; token < valid_tokens; ++token) {
      // load K, V
      const std::size_t kv_base =
          ((static_cast<std::size_t>(physical_page)) * p.page_size + token) * p.kv_heads *
              p.head_dim +
          kv_head * p.head_dim;
      // only load d dimension
      float k_d = in.key_cache[kv_base + d];
      float v_d = in.value_cache[kv_base + d];
      float partial_sum = q * k_d;
      float warp_sum = warp_reduce_sum(partial_sum);
      // assume head_dim = 128, we need 4 warps
      __shared__ float warp_sums[4];
      // check if I am the leader warp
      if (lane == 0) {
        warp_sums[warp] = warp_sum;
      }
      __syncthreads();
      // warp 0 reduces all warps
      float block_sum = 0.0f;
      __shared__ float shared_score;
      if (warp == 0) {
        block_sum = lane < num_warps ? warp_sums[lane] : 0.0f;
        block_sum = warp_reduce_sum(block_sum);
        if (lane == 0) {
          shared_score = block_sum * in.scale;
        }
      }
      __syncthreads();
      float const new_max = fmaxf(running_max, shared_score);
      float const old_factor = running_max == -INFINITY ? 0.0f : __expf(running_max - new_max);
      float const increment = __expf(shared_score - new_max);
      // new factor is the incremental
      // prev_sum * old_max / new_max + increment / new_max
      running_sum = running_sum * old_factor + increment;
      // NOTE THAT accumulator is different for each thread
      // because v_d is different
      accumulator = accumulator * old_factor + increment * v_d;
      running_max = new_max;
    }
  }

  std::size_t const out_index = (batch * p.query_heads + q_head) * p.head_dim + d;
  out[out_index] = accumulator / running_sum;
}
} // namespace
void launch_fused_v1(Problem const &p, Inputs const &in, float *out, cudaStream_t stream) {
  // TODO(stage 1): replace this forwarding call with a cooperative CTA kernel.
  // Compute each Q.K once per warp/CTA, use warp reductions, then broadcast the
  // score while lanes update disjoint output dimensions with online softmax.
  dim3 const grid(p.query_heads, p.batch);
  int const threads = p.head_dim <= 64 ? 64 : 128;
  paged_attention_fused_kernel<<<grid, threads, 0, stream>>>(p, in, out);
}
} // namespace pa

先用 __shfl_down_sync 做 warp 级归约,再由每个 warp 将部分结果写入共享内存。warp 0 读取并再次归约,得到最终结果并写入共享内存。经过 syncthreads 后,所有线程读取结果,计算各自输出维度。

相同参数下的分析结果:

    Section: GPU Speed Of Light Throughput
    ----------------------- ----------- -------------
    Metric Name             Metric Unit  Metric Value
    ----------------------- ----------- -------------
    DRAM Frequency                  Ghz         13.79
    SM Frequency                    Ghz          2.60
    Elapsed Cycles                cycle    19,510,057
    Memory Throughput                 %         60.59
    DRAM Throughput                   %         37.92
    Duration                         ms          7.50
    L1/TEX Cache Throughput           %         61.40
    Waves Per SM                                 4.74
    L2 Cache Throughput               %         28.18
    SM Active Cycles              cycle 19,237,620.33
    Compute (SM) Throughput           %         60.59
    ----------------------- ----------- -------------


    Section: GPU and Memory Workload Distribution
    -------------------------- ----------- -------------
    Metric Name                Metric Unit  Metric Value
    -------------------------- ----------- -------------
    Average DRAM Active Cycles       cycle    39,235,040
    Total DRAM Elapsed Cycles        cycle   413,871,104
    Average L1 Active Cycles         cycle 19,237,620.33
    Total L1 Elapsed Cycles          cycle   701,828,280
    Average L2 Active Cycles         cycle 16,855,800.56
    Total L2 Elapsed Cycles          cycle   277,861,376
    Average SM Active Cycles         cycle 19,237,620.33
    Total SM Elapsed Cycles          cycle   701,828,280
    Average SMSP Active Cycles       cycle 19,237,596.24
    Total SMSP Elapsed Cycles        cycle 2,807,313,120
    -------------------------- ----------- -------------

耗时和周期数都改善约 16 倍。冗余工作消失后,计算与 L1 百分比下降。DRAM 吞吐从 2.40% 上升到 37.92%,尽管 DRAM 活跃周期仍约 3900 万。这意味着相近的独立 KV 工作集在更短时间内完成。

最忙的计算组件是 LSU 路径,占 60.59%;issue active 为 40.05%。标量 FMA 冗余不再主导,加载、存储和同步的相对成本变大。

V2:向量化

V1 已有明显改善。进一步利用硬件特性时,向量化很关键。常见头维度 128 可以拆成 32 个 float4,恰好对应一个 warp:

  1. 连续地址向量加载、存储减少所需指令。
  2. 全部计算在 warp 内完成,不再需要 block 级同步。
#include "paged_attention/api.cuh"
#include <cmath>
namespace pa {
namespace {
__device__ float warp_reduce_sum(float value) {
  // each warp has 32 lanes
  for (int offset = 16; offset > 0; offset /= 2) {
    // 0xfffffff means all lanes participate
    value += __shfl_down_sync(0xffffffff, value, offset);
  }
  return value;
}

__global__ void paged_attention_vectorized_kernel(Problem p, Inputs in, float *out) {
  int const q_head = blockIdx.x;
  int const batch = blockIdx.y;

  constexpr int vec_width = 4;
  int const chunks = p.head_dim / vec_width;
  int const lane = threadIdx.x & 31;

  // if head_dim = 64, only 16 lanes will be used
  const bool is_valid_lane = lane < chunks;

  int const kv_head = q_head / p.queries_per_kv();

  const std::size_t q_base =
      ((static_cast<std::size_t>(batch)) * p.query_heads + q_head) * p.head_dim;
  // reintepret Q as float4 aligned
  auto const *query4 = reinterpret_cast<float4 const *>(in.query + q_base);
  // load Q aligned
  float4 q = is_valid_lane ? query4[lane] : make_float4(0, 0, 0, 0);
  float running_max = -INFINITY;
  float running_sum = 0.0f;
  float4 accumulator = make_float4(0, 0, 0, 0);

  const int num_pages = (in.context_lengths[batch] + p.page_size - 1) / p.page_size;
  for (int logical_page = 0; logical_page < num_pages; ++logical_page) {
    const int physical_page = in.block_tables[batch * p.max_pages_per_sequence + logical_page];
    int valid_tokens = min(p.page_size, in.context_lengths[batch] - logical_page * p.page_size);
    for (int token = 0; token < valid_tokens; ++token) {
      // load K, V
      const std::size_t kv_base =
          ((static_cast<std::size_t>(physical_page)) * p.page_size + token) * p.kv_heads *
              p.head_dim +
          kv_head * p.head_dim;

      float4 const *key4 = reinterpret_cast<float4 const *>(in.key_cache + kv_base);
      float4 const *value4 = reinterpret_cast<float4 const *>(in.value_cache + kv_base);

      // load d aligned
      float4 k_d = is_valid_lane ? key4[lane] : make_float4(0, 0, 0, 0);
      float4 v_d = is_valid_lane ? value4[lane] : make_float4(0, 0, 0, 0);
      float partial_sum = q.x * k_d.x + q.y * k_d.y + q.z * k_d.z + q.w * k_d.w;
      float shared_score = warp_reduce_sum(partial_sum);
      // need to broad cast to all lanes
      shared_score = __shfl_sync(0xffffffff, shared_score, 0);
      shared_score *= in.scale;
      // assume head_dim = 128, we only need 1 warp
      float const new_max = fmaxf(running_max, shared_score);
      float const old_factor = running_max == -INFINITY ? 0.0f : __expf(running_max - new_max);
      float const increment = __expf(shared_score - new_max);
      // new factor is the incremental
      // prev_sum * old_max / new_max + increment / new_max
      running_sum = running_sum * old_factor + increment;
      accumulator.x = accumulator.x * old_factor + increment * v_d.x;
      accumulator.y = accumulator.y * old_factor + increment * v_d.y;
      accumulator.z = accumulator.z * old_factor + increment * v_d.z;
      accumulator.w = accumulator.w * old_factor + increment * v_d.w;
      running_max = new_max;
    }
  }
  float inverse_sum = 1.0f / running_sum;
  accumulator.x *= inverse_sum;
  accumulator.y *= inverse_sum;
  accumulator.z *= inverse_sum;
  accumulator.w *= inverse_sum;

  std::size_t const out_base = (batch * p.query_heads + q_head) * p.head_dim;
  float4 *out4 = reinterpret_cast<float4 *>(out + out_base);
  if (is_valid_lane) {
    out4[lane] = accumulator;
  }
}

} // namespace

void launch_vectorized_v2(Problem const &p, Inputs const &in, float *out, cudaStream_t stream) {
  // TODO(stage 2): start from fused_v1. Add aligned 16-byte Q/K/V accesses,
  // compare cache layouts, and preserve a scalar tail path if needed.
  dim3 const grid(p.query_heads, p.batch);

  // only need one warp
  int const threads = 32;
  paged_attention_vectorized_kernel<<<grid, threads, 0, stream>>>(p, in, out);
}
} // namespace pa

V2 每线程持有四个输出维度,存为 float4。K、V 加载和在线 Softmax 累加器也用 float4。索引改以 chunk 为单位,将指针重解释为 float4。最大值与求和在维度间共享,仍使用标量;只需归约到 lane 0,再用 __shfl_sync 广播给所有 lane。

    Section: GPU Speed Of Light Throughput
    ----------------------- ----------- -------------
    Metric Name             Metric Unit  Metric Value
    ----------------------- ----------- -------------
    DRAM Frequency                  Ghz         13.79
    SM Frequency                    Ghz          2.60
    Elapsed Cycles                cycle    12,869,678
    Memory Throughput                 %         57.42
    DRAM Throughput                   %         57.42
    Duration                         ms          4.95
    L1/TEX Cache Throughput           %         34.10
    Waves Per SM                                 2.37
    L2 Cache Throughput               %         42.14
    SM Active Cycles              cycle 12,578,048.19
    Compute (SM) Throughput           %         17.02
    ----------------------- ----------- -------------


    Section: Launch Statistics
    -------------------------------- --------------- ---------------
    Metric Name                          Metric Unit    Metric Value
    -------------------------------- --------------- ---------------
    Block Size                                                    32
    Cluster Scheduling Policy                           PolicySpread
    Cluster Size                                                   0
    Function Cache Configuration                     CachePreferNone
    Grid Size                                                  2,048
    Preferred Cluster Size                                         0
    Registers Per Thread             register/thread              64
    Shared Memory Configuration Size           Kbyte           32.77
    Driver Shared Memory Per Block       Kbyte/block            1.02
    Dynamic Shared Memory Per Block       byte/block               0
    Static Shared Memory Per Block        byte/block               0
    # SMs                                         SM              36
    Stack Size                                                 1,024
    Threads                                   thread          65,536
    # TPCs                                                        18
    Enabled TPC IDs                                              all
    Uses Green Context                                             0
    Waves Per SM                                                2.37
    Theoretical Occupancy                          %              50
    Achieved Occupancy                             %           37.58
    -------------------------------- --------------- ---------------

虽然 occupancy 从 89.36% 降至 37.58%,kernel 仍更快。单 warp CTA 受驻留 block 数上限限制,每 SM 最多只能达到 48 个可能活跃 warp 中的 24 个。每 lane 活跃状态增多,寄存器从 31 增至 64。但 warp 内归约、更低同步和指令成本抵消了延迟隐藏能力下降。DRAM 利用率达 57.42%,计算仅 17.02%,瓶颈明显转向内存。

V3:共享内存数据复用

内存成为瓶颈后,下一个机会是复用。四个 query head 共用一个 KV head,而 V2 为每个 query head 独立加载同一份 K/V。可以每个 KV head 只暂存一次页,让四个 query warp 消费。

#include "paged_attention/api.cuh"
#include <cmath>
namespace pa {

namespace {
__device__ float warp_reduce_sum(float value) {
  for (int offset = 16; offset > 0; offset /= 2) {
    value += __shfl_down_sync(0xffffffff, value, offset);
  }
  return value;
}
__global__ void paged_attention_gqa_reuse_kernel(Problem p, Inputs in, float *out) {
  const int kv_head = blockIdx.x;
  const int batch = blockIdx.y;
  constexpr int vec_width = 4;
  constexpr int warp_size = 32;
  const int warp = threadIdx.x / warp_size;
  const int lane = threadIdx.x % warp_size;
  // since we are vectorizing, we will use chunks instead of head_dim
  const int chunks = p.head_dim / vec_width;
  bool is_valid_lane = lane < chunks;
  // each CTA contains four warps (handles 4 kv_heads)
  // each CTA handles 1 kv_head and (queries_per_kv) query_heads
  // each warp handles 1 query_head

  // all shared_k and shared_v for one page.
  extern __shared__ float4 shared[];
  float4 *shared_k = shared;
  float4 *shared_v = shared + p.page_size * chunks;
  // every page hosts (page_size * chunks) chunks
  const int query_head = kv_head * p.queries_per_kv() + warp;
  // the query base for the warp (query_head already contains warp info)
  const std::size_t q_base =
      ((static_cast<std::size_t>(batch)) * p.query_heads + query_head) * p.head_dim;
  // each warp is responsible for one query head
  float4 const *global_q = reinterpret_cast<float4 const *>(in.query + q_base);
  // the actual q this thread is responsible for
  const float4 q = is_valid_lane ? global_q[lane] : make_float4(0, 0, 0, 0);

  float running_max = -INFINITY;
  float running_sum = 0.0f;
  float4 accumulator = make_float4(0, 0, 0, 0);

  const int pages = (in.context_lengths[batch] + p.page_size - 1) / p.page_size;
  for (int logical_page = 0; logical_page < pages; ++logical_page) {
    const int physical_page = in.block_tables[batch * p.max_pages_per_sequence + logical_page];
    int valid_tokens = min(p.page_size, in.context_lengths[batch] - logical_page * p.page_size);
    const std::size_t kv_base =
        ((static_cast<std::size_t>(physical_page)) * p.page_size) * p.kv_heads * p.head_dim +
        kv_head * p.head_dim;
    float4 const *global_k4 = reinterpret_cast<float4 const *>(in.key_cache + kv_base);
    float4 const *global_v4 = reinterpret_cast<float4 const *>(in.value_cache + kv_base);

    for (int index = threadIdx.x; index < valid_tokens * chunks; index += blockDim.x) {
      // the step is the block size, so that all threads in the block participate in loading evenly
      int token = index / chunks;
      int chunk = index % chunks;
      shared_k[index] = global_k4[token * p.kv_heads * chunks + chunk];
      shared_v[index] = global_v4[token * p.kv_heads * chunks + chunk];
    }
    __syncthreads();

    for (int token = 0; token < valid_tokens; ++token) {
      // each threads computes a chunk
      float4 k = is_valid_lane ? shared_k[token * chunks + lane] : make_float4(0, 0, 0, 0);
      float4 v = is_valid_lane ? shared_v[token * chunks + lane] : make_float4(0, 0, 0, 0);
      float partial = q.x * k.x + q.y * k.y + q.z * k.z + q.w * k.w;
      float score = warp_reduce_sum(partial);
      score = __shfl_sync(0xffffffff, score, 0);
      score *= in.scale;

      const float new_max = fmaxf(running_max, score);
      const float alpha = running_max == -INFINITY ? 0.0f : __expf(running_max - new_max);
      const float increment = __expf(score - new_max);
      running_sum = running_sum * alpha + increment;
      accumulator.x = accumulator.x * alpha + increment * v.x;
      accumulator.y = accumulator.y * alpha + increment * v.y;
      accumulator.z = accumulator.z * alpha + increment * v.z;
      accumulator.w = accumulator.w * alpha + increment * v.w;
      running_max = new_max;
    }
    __syncthreads();
  }
  accumulator.x /= running_sum;
  accumulator.y /= running_sum;
  accumulator.z /= running_sum;
  accumulator.w /= running_sum;

  const std::size_t out_base = (batch * p.query_heads + query_head) * p.head_dim;
  float4 *out4 = reinterpret_cast<float4 *>(out + out_base);
  if (is_valid_lane) {
    out4[lane] = accumulator;
  }
}

} // namespace
void launch_gqa_reuse_v3(Problem const &p, Inputs const &in, float *out, cudaStream_t stream) {
  // TODO(stage 3): assign a CTA to (batch, kv_head), load a K/V tile once,
  // and process multiple query heads. Measure the reuse/register tradeoff.
  const dim3 grid(p.kv_heads, p.batch);
  const int threads = p.queries_per_kv() * 32; // four warps

  // for each block, allocate one page for k, one page for v
  const int shared_bytes = p.page_size * p.head_dim * 2 * sizeof(float);
  paged_attention_gqa_reuse_kernel<<<grid, threads, shared_bytes, stream>>>(p, in, out);
}
} // namespace pa

本版本由 block 所有线程合作在计算前加载一页。block 的归属从 (batch, query_head) 改成 (batch, kv_head),覆盖四个 query head,每个 warp 负责其中一个:

const int query_head = kv_head * p.queries_per_kv() + warp;

加载均匀分配给 block 全部线程,并确保每次加载唯一:

    for (int index = threadIdx.x; index < valid_tokens * chunks; index += blockDim.x) {
      // the step is the block size, so that all threads in the block participate in loading evenly
      int token = index / chunks;
      int chunk = index % chunks;
      shared_k[index] = global_k4[token * p.kv_heads * chunks + chunk];
      shared_v[index] = global_v4[token * p.kv_heads * chunks + chunk];
    }
    __syncthreads();

整页加载后,遍历页内 token,从共享内存读取 K/V,其余基本与 V2 相同。

    Section: GPU Speed Of Light Throughput
    ----------------------- ----------- ------------
    Metric Name             Metric Unit Metric Value
    ----------------------- ----------- ------------
    DRAM Frequency                  Ghz        13.79
    SM Frequency                    Ghz         2.60
    Elapsed Cycles                cycle    8,712,909
    Memory Throughput                 %        84.86
    DRAM Throughput                   %        84.86
    Duration                         ms         3.35
    L1/TEX Cache Throughput           %        30.32
    Waves Per SM                                2.84
    L2 Cache Throughput               %        31.54
    SM Active Cycles              cycle 8,193,819.39
    Compute (SM) Throughput           %        28.46
    ----------------------- ----------- ------------


    Section: Launch Statistics
    -------------------------------- --------------- ---------------
    Metric Name                          Metric Unit    Metric Value
    -------------------------------- --------------- ---------------
    Block Size                                                   128
    Cluster Scheduling Policy                           PolicySpread
    Cluster Size                                                   0
    Function Cache Configuration                     CachePreferNone
    Grid Size                                                    512
    Preferred Cluster Size                                         0
    Registers Per Thread             register/thread              39
    Shared Memory Configuration Size           Kbyte          102.40
    Driver Shared Memory Per Block       Kbyte/block            1.02
    Dynamic Shared Memory Per Block      Kbyte/block           16.38
    Static Shared Memory Per Block        byte/block               0
    # SMs                                         SM              36
    Stack Size                                                 1,024
    Threads                                   thread          65,536
    # TPCs                                                        18
    Enabled TPC IDs                                              all
    Uses Green Context                                             0
    Waves Per SM                                                2.84
    Theoretical Occupancy                          %           41.67
    Achieved Occupancy                             %           36.79
    -------------------------------- --------------- ---------------

    Section: GPU and Memory Workload Distribution
    -------------------------- ----------- -------------
    Metric Name                Metric Unit  Metric Value
    -------------------------- ----------- -------------
    Average DRAM Active Cycles       cycle    39,229,512
    Total DRAM Elapsed Cycles        cycle   184,905,728
    Average L1 Active Cycles         cycle  8,193,819.39
    Total L1 Elapsed Cycles          cycle   313,420,716
    Average L2 Active Cycles         cycle  7,569,240.88
    Total L2 Elapsed Cycles          cycle   124,075,968
    Average SM Active Cycles         cycle  8,193,819.39
    Total SM Elapsed Cycles          cycle   313,420,716
    Average SMSP Active Cycles       cycle  8,193,791.33
    Total SMSP Elapsed Cycles        cycle 1,253,682,864
    -------------------------- ----------- -------------

这是报告中最快的完整 kernel。显式复用将 grid 从 2,048 个 query-head CTA 减为 512 个 KV-head CTA,避免逐 query-head 重复的全局/L1 加载指令。由于 K/V 暂存改变活跃值与地址生成需求,寄存器用量也从 64 降到 39。

共享内存将驻留限制为每 SM 约五个 128 线程 CTA,即 20 个 warp,对应 41.67% 理论 occupancy。尽管存在容量代价,复用仍比最大驻留数更有价值。DRAM 吞吐达 84.86%,平均活跃周期几乎不变,表明已经暴露难以进一步削减的工作集,在此负载上确实接近 DRAM 带宽瓶颈。

下一步需要减少字节数或更好隐藏访存延迟,可尝试:

V4:上下文轴并行

V4 尝试沿上下文并行。长上下文中,一个 block 为一个 query head 处理完整序列可能很慢,因此将上下文切成小片,每块处理一片,再启动第二个 kernel 合并。这更偏向可扩展性。

#include "paged_attention/api.cuh"
#include <cmath>
namespace pa {
namespace {
__device__ float warp_reduce_sum(float value) {
  // each warp has 32 lanes
  for (int offset = 16; offset > 0; offset /= 2) {
    // 0xfffffff means all lanes participate
    value += __shfl_down_sync(0xffffffff, value, offset);
  }
  return value;
}

__global__ void paged_attention_split_kernel(Problem p, Inputs in, float *global_partial_max,
                                             float *global_partial_sum,
                                             float *global_partial_output, int num_splits) {
  int const q_head = blockIdx.x;
  int const batch = blockIdx.y;
  int const split = blockIdx.z;

  constexpr int vec_width = 4;
  int const chunks = p.head_dim / vec_width;
  int const lane = threadIdx.x & 31;

  // if head_dim = 64, only 16 lanes will be used
  const bool is_valid_lane = lane < chunks;

  int const kv_head = q_head / p.queries_per_kv();

  const std::size_t q_base =
      ((static_cast<std::size_t>(batch)) * p.query_heads + q_head) * p.head_dim;
  // reintepret Q as float4 aligned
  auto const *query4 = reinterpret_cast<float4 const *>(in.query + q_base);
  // load Q aligned
  float4 q = is_valid_lane ? query4[lane] : make_float4(0, 0, 0, 0);
  float running_max = -INFINITY;
  float running_sum = 0.0f;
  float4 accumulator = make_float4(0, 0, 0, 0);

  const int num_pages = (in.context_lengths[batch] + p.page_size - 1) / p.page_size;
  const int num_pages_per_split = (num_pages + num_splits - 1) / num_splits;

  for (int logical_page = num_pages_per_split * split;
       logical_page < min(num_pages_per_split * (split + 1), num_pages); ++logical_page) {
    const int physical_page = in.block_tables[batch * p.max_pages_per_sequence + logical_page];
    int valid_tokens = min(p.page_size, in.context_lengths[batch] - logical_page * p.page_size);
    for (int token = 0; token < valid_tokens; ++token) {
      // load K, V
      const std::size_t kv_base =
          ((static_cast<std::size_t>(physical_page)) * p.page_size + token) * p.kv_heads *
              p.head_dim +
          kv_head * p.head_dim;

      float4 const *key4 = reinterpret_cast<float4 const *>(in.key_cache + kv_base);
      float4 const *value4 = reinterpret_cast<float4 const *>(in.value_cache + kv_base);

      // load d aligned
      float4 k_d = is_valid_lane ? key4[lane] : make_float4(0, 0, 0, 0);
      float4 v_d = is_valid_lane ? value4[lane] : make_float4(0, 0, 0, 0);
      float partial_sum = q.x * k_d.x + q.y * k_d.y + q.z * k_d.z + q.w * k_d.w;
      float shared_score = warp_reduce_sum(partial_sum);
      // need to broad cast to all lanes
      shared_score = __shfl_sync(0xffffffff, shared_score, 0);
      shared_score *= in.scale;
      // assume head_dim = 128, we only need 1 warp
      float const new_max = fmaxf(running_max, shared_score);
      float const old_factor = running_max == -INFINITY ? 0.0f : __expf(running_max - new_max);
      float const increment = __expf(shared_score - new_max);
      // new factor is the incremental
      // prev_sum * old_max / new_max + increment / new_max
      running_sum = running_sum * old_factor + increment;
      accumulator.x = accumulator.x * old_factor + increment * v_d.x;
      accumulator.y = accumulator.y * old_factor + increment * v_d.y;
      accumulator.z = accumulator.z * old_factor + increment * v_d.z;
      accumulator.w = accumulator.w * old_factor + increment * v_d.w;
      running_max = new_max;
    }
  }
  std::size_t const out_base =
      (batch * p.query_heads * num_splits + p.query_heads * split + q_head) * p.head_dim;
  float *split_partial_max =
      global_partial_max + batch * p.query_heads * num_splits + p.query_heads * split + q_head;
  float *split_partial_sum =
      global_partial_sum + batch * p.query_heads * num_splits + p.query_heads * split + q_head;
  float4 *split_partial_output = reinterpret_cast<float4 *>(global_partial_output + out_base);
  if (lane == 0) {
    // partial max and partial sum are per-cta
    split_partial_max[0] = running_max;
    split_partial_sum[0] = running_sum;
  }
  if (is_valid_lane) {
    split_partial_output[lane] = accumulator;
  }
}
__global__ void paged_attention_merge_kernel(Problem p, Inputs in, float *global_partial_max,
                                             float *global_partial_sum,
                                             float *global_partial_output, int num_splits,
                                             float *out) {
  const int q_head = blockIdx.x;
  const int batch = blockIdx.y;
  constexpr int vec_width = 4;
  const int chunks = p.head_dim / vec_width;
  const int lane = threadIdx.x & 31;
  const bool is_valid_lane = lane < chunks;

  float combined_max = -INFINITY;
  float combined_sum = 0.0f;
  float4 combined_output = make_float4(0, 0, 0, 0);

  for (int split = 0; split < num_splits; ++split) {
    float split_max = 0.0f;
    float split_sum = 0.0f;
    int state_index = batch * p.query_heads * num_splits + p.query_heads * split + q_head;
    if (lane == 0) {
      split_max = global_partial_max[state_index];
      split_sum = global_partial_sum[state_index];
    }
    split_max = __shfl_sync(0xffffffff, split_max, 0);
    split_sum = __shfl_sync(0xffffffff, split_sum, 0);
    float4 *global_partial_output4 = reinterpret_cast<float4 *>(global_partial_output);
    float4 split_output = is_valid_lane ? global_partial_output4[state_index * chunks + lane]
                                        : make_float4(0, 0, 0, 0);

    if (split_sum != 0.0f) {
      // NOTE: if split_sum is 0.0f, it means the split has no element
      // merging it will lead to -INF / -INF error
      const float new_max = fmaxf(combined_max, split_max);
      const float alpha = combined_max == -INFINITY ? 0.0f : __expf(combined_max - new_max);
      // have to use alpha-beta here, because we have no idea of the token level score now
      // so we can not do increment = __expf(score - new_max);
      // have to directly adjust the already calculated split_output
      const float beta = __expf(split_max - new_max);
      combined_sum = alpha * combined_sum + beta * split_sum;
      combined_output.x = combined_output.x * alpha + beta * split_output.x;
      combined_output.y = combined_output.y * alpha + beta * split_output.y;
      combined_output.z = combined_output.z * alpha + beta * split_output.z;
      combined_output.w = combined_output.w * alpha + beta * split_output.w;
      combined_max = new_max;
    }
  }
  combined_output.x /= combined_sum;
  combined_output.y /= combined_sum;
  combined_output.z /= combined_sum;
  combined_output.w /= combined_sum;
  if (is_valid_lane) {
    float4 *out4 = reinterpret_cast<float4 *>(out + (batch * p.query_heads + q_head) * p.head_dim);
    out4[lane] = combined_output;
  }
}

void launch_split_kv_partial(Problem const &p, Inputs const &in, SplitKvWorkspace const &workspace,
                             cudaStream_t stream) {
  const dim3 grid(p.query_heads, p.batch, workspace.num_splits);
  const int threads = 32;

  paged_attention_split_kernel<<<grid, threads, 0, stream>>>(
      p, in, workspace.partial_max, workspace.partial_sum, workspace.partial_output,
      workspace.num_splits);
}
void launch_split_kv_merge(Problem const &p, Inputs const &in, SplitKvWorkspace const &workspace,
                           cudaStream_t stream, float *out) {
  const dim3 grid(p.query_heads, p.batch);
  const int threads = 32;
  paged_attention_merge_kernel<<<grid, threads, 0, stream>>>(
      p, in, workspace.partial_max, workspace.partial_sum, workspace.partial_output,
      workspace.num_splits, out);
}
} // namespace

void launch_split_kv_v4(Problem const &p, Inputs const &in, float *out,
                        SplitKvWorkspace const &workspace, cudaStream_t stream) {
  // TODO(stage 4): split long contexts across CTAs. Store each split's max,
  // sum, and partial output, then combine them with log-sum-exp correction.
  // Add workspace ownership to the public API when implementing this stage.

  launch_split_kv_partial(p, in, workspace, stream);
  // no need to sync between them if they are launched into the same CUDA stream
  launch_split_kv_merge(p, in, workspace, stream, out);
}
} // namespace pa

V4 有两个 kernel:一个计算分片部分结果并写到全局内存,另一个读取、合并并输出。分片版本只对 V2 做小改动:不再读全部页,只读当前 block 所负责分片的页:

  const int num_pages = (in.context_lengths[batch] + p.page_size - 1) / p.page_size;
  const int num_pages_per_split = (num_pages + num_splits - 1) / num_splits;

  for (int logical_page = num_pages_per_split * split;
       logical_page < min(num_pages_per_split * (split + 1), num_pages); ++logical_page) {
    const int physical_page = in.block_tables[batch * p.max_pages_per_sequence + logical_page];
    int valid_tokens = min(p.page_size, in.context_lengths[batch] - logical_page * p.page_size);
    for (int token = 0; token < valid_tokens; ++token) {

还需显式分配全局工作区保存部分结果,相关 driver 代码未列出。主要保存:

最大值和指数和是标量,输出是 float4,因为每个维度都有结果。输出暂不除以局部指数和,后续还需要按全局统计量修正。

  std::size_t const out_base =
      (batch * p.query_heads * num_splits + p.query_heads * split + q_head) * p.head_dim;
  float *split_partial_max =
      global_partial_max + batch * p.query_heads * num_splits + p.query_heads * split + q_head;
  float *split_partial_sum =
      global_partial_sum + batch * p.query_heads * num_splits + p.query_heads * split + q_head;
  float4 *split_partial_output = reinterpret_cast<float4 *>(global_partial_output + out_base);
  if (lane == 0) {
    // partial max and partial sum are per-cta
    split_partial_max[0] = running_max;
    split_partial_sum[0] = running_sum;
  }
  if (is_valid_lane) {
    split_partial_output[lane] = accumulator;
  }

合并 kernel 中,每个 block 遍历对应 query head 的全部分片,在分片层面执行在线 Softmax。

分片 kernel:

    Section: GPU Speed Of Light Throughput
    ----------------------- ----------- -------------
    Metric Name             Metric Unit  Metric Value
    ----------------------- ----------- -------------
    DRAM Frequency                  Ghz         13.79
    SM Frequency                    Ghz          2.59
    Elapsed Cycles                cycle    10,178,623
    Memory Throughput                 %         73.41
    DRAM Throughput                   %         73.41
    Duration                         ms          3.92
    L1/TEX Cache Throughput           %         42.05
    Waves Per SM                                18.96
    L2 Cache Throughput               %         52.91
    SM Active Cycles              cycle 10,178,884.22
    Compute (SM) Throughput           %         21.58
    ----------------------- ----------- -------------

合并 kernel:

    ----------------------- ----------- ------------
    Metric Name             Metric Unit Metric Value
    ----------------------- ----------- ------------
    DRAM Frequency                  Ghz        13.79
    SM Frequency                    Ghz         2.57
    Elapsed Cycles                cycle       57,995
    Memory Throughput                 %        85.68
    DRAM Throughput                   %        85.68
    Duration                         us        22.56
    L1/TEX Cache Throughput           %        15.04
    Waves Per SM                                2.37
    L2 Cache Throughput               %        32.28
    SM Active Cycles              cycle    54,381.42
    Compute (SM) Throughput           %        11.52
    ----------------------- ----------- ------------

合并明显受内存带宽限制:假设八个分片,需要读取八份部分输出及标量 Softmax 状态,运算很少。85.68% 的 DRAM 吞吐看起来很高,但绝对耗时只有 22.56 微秒,平均 DRAM 活跃周期仅 27 万,并非此形状的主要瓶颈。相比未切分 V2,两个 kernel 合计更快,因为暴露了更多独立 CTA,缩短各 CTA 的串行 token 循环。实际 occupancy 接近理论上限,工作分布也更均匀。

这里合并成本虽小,总时间仍慢于 GQA 复用版本的 3.35 ms。batch-64 本来已有充足 grid 级并行,而 split-KV 没有在四个 GQA query head 间复用 KV。分片数增长时,工作区和合并读取都线性增长,相对合并成本也会增加。


编辑文章
分享文章:

上一篇
[TIL] IREE Dispatch 的创建过程
下一篇
Composable Kernel Language:用 MLIR 实现基于内存效应的 GPU Kernel 组合