Step-5 的 prefill 区域并集:16 行 query 选中同一区域时存几次
16 行 query 都选中了同一个区域,prefill 该存几次?
区域选择给出的是每行 query 的结果。稀疏注意力接下来按组处理最多 16 行,它需要知道三件事:本组要访问哪些区域,每个区域在哪个物理位置,以及哪些行会用它。例如第 0 行选了区域 2 和 7,第 1 行选了 7 和 9,组里只要三条记录。区域 7 的成员掩码是二进制 11,表示两行都选了它。
一个位图,为什么要扫两遍?
旧实现先为每个区域置一位。1024 个区域只占 32 个 32 位字,很省空间,但最多 16 行、每行 513 项的选择结果都来更新这些字。多个线程同时改同一个字的不同位,必须用原子 OR 保住彼此的结果。位图只记下区域出现过,后续还得重新读选择结果,找回物理 ID 和成员信息。
8192-token 的一次输入回放里,旧流程两趟合计 1042 µs。报告记录了约 420 万次原子操作、3100 万条指令,显存带宽只占峰值的 4%–5%。单独把原子操作替换成普通写入做计时,约 140 µs 的工作降到约 35 µs。这样的替换会丢更新,只用于定位竞争来自哪里。
按区域建表,再按 query 行依次更新
第一步改动为每个逻辑区域单设一项。遇到区域 7,就直接在表项 7 记录物理位置和成员信息。随后只需扫描区域表,省掉了重读全部选择结果的一趟。第二步把每组交给一个线程块,按 query 槽位依次处理;同一槽位内部,多个选中区域仍并行处理。按 region 建表的原始提交 · 按槽位更新与就地压缩的实现
沿用上例,处理第 0 行时,区域 7 的成员值从 0 变为 1。线程块同步后,第 1 行读到 1,再与 1 << 1 做 OR,结果为 3。代码的核心就是 old | (1 << q_slot)。相邻槽位之间的屏障使后一次读能看见前一次写。组内共享逻辑到物理的映射,因此重复遇到区域 7 时,写入的物理位置也相同。
最后按编号扫描区域表,用前缀和计算紧凑输出里的下标。区域 2、7、9 分别搬到下标 0、1、2。目标下标始终小于等于源下标,因此可以整块先读、同步、再写回原缓冲;下游只读前 union_counts 项。
什么时候这张表放不下?
按逻辑 ID 直接寻址,要求容量至少等于候选区域总数。假设有 16384 个候选区域,输出只预留了 8208 项,即使最后选中的区域很少,也不能直接访问表项 16383。这时继续走旧的位图双趟路径。原稿记录的同输入回放加速约 3.6 倍,属于区域表能放下时的构建耗时;原记录估计波动约 ±7%–10%。