去重 Multiplicity

地址适用于来自 libtpu-0.0.40-cp314 wheel 的 libtpu.so（build-id 89edbbe81c5b328a958fe628a9f2207d）。其他版本会有差异。

摘要

SparseCore 嵌入查找会为每个样本聚集许多 id，而同一个 id 通常会在一个样本窗口中出现多次；DLRM 的分类特征是一个多重集，不是集合。在 scatter-add 将梯度写回嵌入行之前，流水线会把每个重复 id 折叠为单个唯一行，并记录有多少输入 lane 折叠到该行：即 multiplicity。本页负责这部分算术：DuplicateCount op 与 HLO CSR row-pointers 如何产生每个唯一项的计数，UniqueWithLaneIds 逆置换如何把去重后的结果路由回每个原始 lane，向量内 fetch-and-add 提交顺序（以及为什么去重让它无关紧要），以及 multiplicity 如何绑定到前向 combiner（sum/mean/sqrtn）和反向梯度缩放。

该机制位于两个高度，它们用不同方式产生相同数字。在 TEC（SparseCore 向量引擎）上，DuplicateCount 是单个 VectorExtended 扫描 op（opcode 24/25），它为每个 lane 发出与该 lane 的 id 相同的向量 lane 数量，即向量内 multiplicity。在 HLO 层，SparseDenseMatmulGradOpDecomposer 将梯度应用降低为 Sort → COO→CSR → Cumsum-exclusive → Add-combiner scatter 链，其中 multiplicity 是 CSR row_pointers 中唯一行的 run length，而 count× 累加来自 Add-combiner 将每个重复项求和到一行。两者都归约到同一组 MLIR 去重 op（sc_tpu.unique、sc_tpu.duplicate_count，带或不带 lane ids），这些 op 通过同一个模板化模式 DuplicateCountUniqueOpLowering<OpT> 降低到 HW intrinsic（tpu_dupcnt{i,f} / tpu_uniq{i,f}），返回一个 LLVM struct，再由 lowering 抽取字段。

已经逐字节确认的决定性结构事实是：HW 去重 intrinsic 总是产生三个输出（两个 vector<N×i32> 映射加上输入 dtype 的值）；MLIR op 通过 ReplaceOpWithExtracts 的索引数量选择暴露其中两个或三个（普通形式为 2，WithLaneIds 为 3）。struct 字段顺序是 {i32-vec, i32-vec, input-dtype}，extract 索引数组会把它重新排序回 op-result 约定，即普通形式 {2,1}，WithLaneIds 为 {2,1,0}。暴露出来的第三个结果是 lane→unique-row 逆置换，由 scatter 前紧邻的 PermuteOp 消费。fetch-and-add op 没有 atomic-ordering trait，只有 LLVM alias-scope，因此向量内同地址提交顺序由硅片决定；去重通过用 unique_indices=TRUE 创建 scatter 完全绕开了这个问题，所以一个向量中不会有两个 lane 命中同一地址。

对于重新实现，契约如下：

去重 intrinsic 发出三个结果；op 暴露 2 个或 3 个。 inferReturnTypes 构造 result[0]=input dtype、result[1]=vector<N×i32>，并且仅在 WithLaneIds 中构造 result[2]=vector<N×i32>。lowering 构造三字段 struct {i32-vec, i32-vec, input-dtype}（与 op-result 顺序相反），ReplaceOpWithExtracts 索引数组（{2,1} 或 {2,1,0}）选择哪些 struct 字段成为 op 结果，并把它们重新排序回来。
Multiplicity 是一个计数，用两种一致的方式计算。 TEC：DuplicateCount 扫描 op 的 i32 结果 = 每个 lane 的向量内 id 计数。HLO：csr_row_pointers[i+1] − csr_row_pointers[i] = 唯一行 i 的 run length，由 CumsumExclusive（Pad + ReduceWindow-Add）产生。
count× 累加是 unique_indices=TRUE scatter 的 Add-combiner。 DeduplicateGradientVectorsToApply 使用 CreateAddComputation 作为 update computation，将每个输入的梯度 scatter-ADD 到其唯一行；把所有重复项求和到一行就是 count× 权重。反向路径不会发出显式乘法。
前向 combiner 除数是每个样本的 gains。 sum → 1，mean → 1/valency，sqrtn → 1/sqrt(valency)，其中 valency = 每个样本的 id 计数 = multiplicity；由 EmitValencyLoop 中的 SC ReciprocalF32 / ReciprocalSqrtF32 VectorAlu op 实现。
lane_ids 第三个结果把去重后的结果路由回每个输入 lane。 它是逆置换（输入 lane 域 → 唯一行陪域），由 PermuteOp（→ tpu_sc_permute / llvm.tpu.vperm.sublane）在 VectorStoreIdx / fetch-and-add scatter 前紧邻消费。
向量内提交顺序由硅片决定，且被 unique_indices 变得无关紧要。 fetch-and-add（tpu_vst_msk_idx_ret_add_np）有 AccessGroup + AliasAnalysis trait，且没有 AtomicOrdering；去重 scatter 以 unique_indices=TRUE 创建，因此每个 lane 的顺序永远不会影响结果。


去重 op	`sc_tpu.unique` · `…unique_with_lane_ids` · `…duplicate_count` · `…duplicate_count_with_lane_ids`
Lowering 模板	`DuplicateCountUniqueOpLowering<OpT>::matchAndRewrite` — 4 个实例化
HW intrinsic	`llvm.tpu.dupcnt{i,f}` · `llvm.tpu.uniq{i,f}`（3 字段 struct，`NOperands<2>` `OneResult`）
TEC opcode	`DuplicateCount{Integer=24,Float=25}` · `Uniquify{Integer=26,Float=27}` @ word `0x28` bits 16..21
结果类型	`[0]`=input dtype · `[1]`=`vector<N×i32>` · `[2]`=`vector<N×i32>`（WithLaneIds）
HLO decomposer	`SparseDenseMatmulGradOpDecomposer`（`Deduplicate{RowIds,GradientVectors}ToApply`、`CumsumExclusive`、`LocalReduction`）
Fetch-and-add	`tpu_vst_msk_idx_ret_add_np` — `NOperands<4>`、`OneResult`、`AccessGroup`+`AliasAnalysis`，无 AtomicOrdering
去重标志	`xla_tpu_enable_sparse_core_computation_deduplication`（`0x223c5f10`）

注意 — 本页负责 count→multiplicity 算术、WithLaneIds 逆置换以及向量内提交顺序。 bundle 级 Sort/Uniquify/DuplicateCount opcode 在 VectorExtended 中；SSA 发出序列（Unique → IdxAdd → Permute → StoreIdx）在 RankAndPermute 中；fetch-and-add 返回路径和 SourceOne 种子在 VectorLoad Slot 中；每样本 valency loop 在 Emit Valency Loop 中。这里链接它们，不重复。

Dedup Op → Intrinsic → 结果映射

目的

四个 MLIR sc_tpu.* op 表达去重 primitive。unique 和 duplicate_count 只在 result[0] 的含义上不同（唯一值 vs 每位置计数）；…_with_lane_ids 变体会添加第三个结果，即逆置换。四个 op 都通过同一个模板化模式降低到同一个 HW intrinsic，该 intrinsic 总是产生三字段 struct；op 只是选择抽取多少字段。

四个 Op

MLIR op（`sc_tpu.*`）	operands	results	intrinsic（int / float）	extract idx
`unique`	2	2	`uniqi` / `uniqf`	`{0,1}`
`unique_with_lane_ids`	2	3	`uniqi` / `uniqf`	`{0,1,2}`
`duplicate_count`	2	2	`dupcnti` / `dupcntf`	`{0,1}`
`duplicate_count_with_lane_ids`	2	3	`dupcnti` / `dupcntf`	`{0,1,2}`

结果类型由 inferReturnTypes 设置（见 §结果类型）：

text

result[0] = INPUT DATA TYPE   (unique: the unique-value vector;
                               duplicate_count: the per-position count vector)
result[1] = vector<N × i32>   (N = input shape; secondary i32 map)
result[2] = vector<N × i32>   (WithLaneIds only: lane→unique-row INVERSE permutation)

Lowering — 一个模板，三个 Struct 字段

DuplicateCountUniqueOpLowering<OpT>::matchAndRewrite 为每个 op 实例化一次。每个实例读取 op 的 N 个结果类型，对每个执行 convertType，构造这些类型的 LLVMStructType::getLiteral，通过两个类型构造 lambda 发出 HW intrinsic（lambda #1 → integer intrinsic，lambda #2 → float），并用 2 元或 3 元索引数组调用 ReplaceOpWithExtracts：

function DuplicateCountUniqueOpLowering<OpT>::matchAndRewrite(op, rewriter):  // e.g. 0x13599d40
    // read the op's result types (3 reads even for the plain op: add edx,0x3)
    t0 = convertType(op.getNextResultAtOffset(0))     // input dtype
    t1 = convertType(op.getNextResultAtOffset(1))     // vector<N x i32>
    t2 = convertType(op.getNextResultAtOffset(2))     // vector<N x i32>  (built regardless)
    structTy = LLVMStructType::getLiteral({t0,t1,t2}) // 0x17471ae0; header pack 0x600000003
    if  isIntegerElementType:
        v = tpu_dupcnti::create(rewriter, loc, structTy, ...)   // 0x146e23c0 (uniqi 0x149895c0)
    else:
        v = tpu_dupcntf::create(rewriter, loc, structTy, ...)   // 0x146e1bc0 (uniqf 0x14988dc0)
    indices = {0,1}      if plain                     // mov QWORD [rbp-0x60], 0x2
            = {0,1,2}    if WithLaneIds               // mov QWORD [rbp-0x60], 0x3
    ReplaceOpWithExtracts(rewriter, loc, op, structTy, v, indices)   // 0x135b82a0

ReplaceOpWithExtracts（@0x135b82a0）已逐字节确认会遍历索引数组，即 do { ... } while (4*count != offset)，每个 unsigned 索引步进 4 字节；每个索引发出一个 LLVM::ExtractValueOp::create，然后通过 rewriter vtable 调用 replaceOp，用抽取出的 SSA 值替换原 op 的结果：

// xla::tpu::sparse_core::ReplaceOpWithExtracts                          (0x135b82a0)
for (i = 0; i < count; ++i) {                          // count = ArrayRef length (2 or 3)
    extractIndex = indices[i];                         // v20[2] = *(uint*)(a7 + 4*i)
    ev = mlir::LLVM::ExtractValueOp::create(builder);  // one extract per surfaced field
    results.push_back(ev);
}
rewriter.replaceOp(op, ValueRange(results));           // (**v9)(...) vtable call

怪癖 — HW intrinsic 总是发出三路输出；MLIR op 选择两个或三个。 即使是普通 unique / duplicate_count lowering，也会读取三个结果类型并构造三字段 struct（add edx, 0x3；三次 getNextResultAtOffset 读取），然后只抽取 {0,1}。lane_ids 第三字段无论如何都会由硅片计算，普通 op 会丢弃它。重新实现者如果把 intrinsic struct 的大小设为 op 的结果数量（2），就会误解码 WithLaneIds 形式，因为它的第三字段位于普通 op 未读取的同一 struct 偏移处。

Lowering / Intrinsic 地址映射

符号（gfc）	地址	作用
`DuplicateCountUniqueOpLowering<DuplicateCountOp>::matchAndRewrite`	`0x13599d40`	普通计数 lowering（抽取 `{0,1}`）
`…<DuplicateCountWithLaneIdsOp>::matchAndRewrite`	`0x1359a7e0`	计数 + lane_ids（抽取 `{0,1,2}`）
`…<UniqueOp>::matchAndRewrite`	`0x1359b280`	普通 unique lowering（抽取 `{0,1}`）
`…<UniqueWithLaneIdsOp>::matchAndRewrite`	`0x1359bd20`	unique + lane_ids（抽取 `{0,1,2}`）
`ReplaceOpWithExtracts`	`0x135b82a0`	每索引 `ExtractValueOp` + `replaceOp`
`tpu_dupcnti::create` / `tpu_dupcntf::create`	`0x146e23c0` / `0x146e1bc0`	integer / float 计数 intrinsic
`tpu_uniquei::create` / `tpu_uniquef::create`	`0x149895c0` / `0x14988dc0`	integer / float unique intrinsic

注意 — intrinsic op 本身是 NOperands<2>、OneResult、OneTypedResult<Type>。 单个结果是 LLVMStructType literal；将它拆分为 2 个或 3 个 op 结果的是 lowering（不是 intrinsic）。LLVM intrinsic 名称是 llvm.tpu.dupcnti / .dupcntf / .uniquei / .uniquef。duplicate_count 的 result[0] 值语义（每位置广播计数）与 unique（唯一值）从 op 名称读取，而不是从按字段 accessor 读取；字段类型是 = input dtype。

结果类型 {#the-result-types}

目的

inferReturnTypes 是每个 op 有多少结果以及结果类型是什么的唯一事实来源。重新实现者必须复现此函数，才能把去重 op 接入类型检查的 IR。二结果与三结果形式在结构上逐字节相同，只多一次 push。

WithLaneIds 构造（3 个结果）

UniqueWithLaneIdsOp::inferReturnTypes（@0x145a0040）取得 op 的 ValueRange operands，从 operand 0 读取输入数据类型（& ~7 用于剥离指针 tag bits），从最后一个 operand 取得 shape，构造 signless i32 VectorType::get(shape, i32)，并 push 三个结果类型：输入类型一次，vector<N×i32> 两次：

// mlir::sparse_core::UniqueWithLaneIdsOp::inferReturnTypes                  (0x145a0040)
inputTy = dereference_iterator(operands, 0)              // v11 → result[0]
shape   = VectorType::getShape(operands[last] & ~7)      // 0x1d895080
i32     = IntegerType::get(ctx, 32, /*signless*/0)       // 0x1d8c60c0
vecI32  = VectorType::get(shape, i32)                    // 0x1d894100
results.push_back(inputTy & ~7)                          // result[0] = input data type
results.push_back(vecI32)                                // result[1] = vector<N x i32>
results.push_back(vecI32)                                // result[2] = vector<N x i32>  (lane→unique map)
return 1

已逐字节确认对 SmallVectorImpl<Type>（a11）的三次 grow_pod 保护存储：v17（输入类型）一次，v16（vector<N×i32> 值）两次。DuplicateCountWithLaneIdsOp::inferReturnTypes（@0x1459ff00）结构完全相同（三次 push）。

普通构造（2 个结果）

UniqueOp::inferReturnTypes（@0x1459fe00）和 DuplicateCountOp::inferReturnTypes（@0x1459fd00）push 两个类型：输入类型，然后一次 vector<N×i32>：

// mlir::sparse_core::UniqueOp::inferReturnTypes                            (0x1459fe00)
inputTy = dereference_iterator(operands, 0) & ~7         // v13
results.push_back(inputTy)                               // result[0] = input data type
shape   = VectorType::getShape(operands[last] & ~7)
vecI32  = VectorType::get(shape, IntegerType::get(ctx,32,0))
results.push_back(vecI32)                                // result[1] = vector<N x i32>
return 1

inferReturnTypes	地址	Push 的结果
`UniqueWithLaneIdsOp`	`0x145a0040`	input · vec<i32> · vec<i32>（3）
`DuplicateCountWithLaneIdsOp`	`0x1459ff00`	input · vec<i32> · vec<i32>（3）
`UniqueOp`	`0x1459fe00`	input · vec<i32>（2）
`DuplicateCountOp`	`0x1459fd00`	input · vec<i32>（2）

陷阱 — result[1] 和 result[2] 是同一类型 vector<N×i32>，但语义不同。 它们由一次共享的 VectorType::get 调用构造并 push 两次，因此仅靠类型检查无法区分。result[2] 是 lane_ids 逆置换（由 PermuteOp 消费）；result[1] 是次级 i32 映射（前向置换 / segment-start / count-index）。[1] 与 [2] 的职责拆分来自 op 名称后缀和 PermuteOp 消费者约定，而不是来自不同的按字段 accessor。

Multiplicity 算术 — 两个层级

目的

“这个唯一 id 出现了多少次”的计数在两个粒度上产生，流水线将它们作为并行机制保留：TEC 向量内 primitive（每个 tile、一次一个向量）和 HLO CSR row-pointers（跨 tile、完整 minibatch 窗口）。两者都产生 i32 计数；本页记录两者并标出尚未追踪的交接点。

TEC 向量内 — `DuplicateCount` 扫描 Op

在 TEC 上，DuplicateCount 是一元 VectorExtended（EUP scan-family）op。DuplicateCountInteger 是 opcode 24（@0x1eca7b20，word 0x28 bits 16..21 >> 16 的 cmp 0x180000）；DuplicateCountFloat 是 25。它作为 EmitVectorResultUnop<…DuplicateCountInteger>（@0x13aaf660）发出：一个输入 VREG（GetVregno）、一个 GetVectorMask、一个用于认领空闲 V 读端口的 FindAndEmitToUnusedPort，并通过 VectorResult XRF→VRF 路径排出计数结果；这与它共享槽位的 scan ops 使用同一排出模型。

// EmitVectorResultUnop<…DuplicateCountInteger>                            (0x13aaf660)
in    = GetVregno(input)                  // the id vector
mask  = GetVectorMask(...)
port  = FindAndEmitToUnusedPort(...)      // one free V read port
emit  DuplicateCountInteger(in, mask) → VectorResult (XRF)
// per lane: result[lane] = #{ j : id[j] == id[lane] }  — the in-vector multiplicity

该 op 为每个 lane 给出该 lane 的值在向量中的 multiplicity。这个 i32 计数就是 combiner 用作 mean 除数（前向）或梯度缩放器（反向）的值。

HLO 分解 — CSR Row-Pointers 和 Add-Combiner

minibatch 梯度应用由 SparseDenseMatmulGradOpDecomposer 降低。这里的 multiplicity 是 CSR row_pointers 中唯一 id 的 run length，而 count× 累加是 unique_indices=TRUE scatter 的 Add-combiner：

text

SparseDenseMatmulGradOpDecomposer — backward dedup-reduce
  Sort (sample,id) pairs           SortVectorsAndGainsBySampleIds  0x1367c5a0
    → COO → CSR                     CooToSparseMatrixFormat         0x13412480
        csr_row_pointers[i+1] − csr_row_pointers[i] = multiplicity of unique row i
    → exclusive prefix sum          CumsumExclusive = Pad + ReduceWindow(Add)  0x134b3ec0
        = each input's destination unique-row index (the multiplicity INDEX)
    → DeduplicateRowIdsToApply      0x134b4560  Scatter(unique=TRUE)+Overwrite+MaxValue+Ternary
        collapses duplicate ids onto the unique slot
    → DeduplicateGradientVectorsToApply  0x134b4e40
        Scatter(update=AddComputation, unique=TRUE) + LiteralUtil::Zero
        scatter-ADDs each input gradient into its unique row → count× accumulation
    → LocalReduction                0x134b01e0  ReduceWindow + Scatter(Add) + Gather/Compare/Ternary
        windowed sum over the run of duplicate rows of one unique id

已逐字节确认 DeduplicateGradientVectorsToApply（@0x134b4e40）会：创建两个 HLO parameter（cumsum_exclusive、gradient_vectors）；通过 LiteralUtil::Zero + CreateBroadcast（accumulated_gradients_zero_init）将累加器零初始化；使用 CreateAddComputation 构造 scatter 的 update computation；并发出 CreateScatter(operand, scatter_indices, updates, AddComputation, dim_numbers, indices_are_sorted=0, unique_indices=…)。尾部 scatter bool 参数已逐字节确认：push 0x0 = indices_are_sorted=false，push 0x1 = unique_indices=true。

怪癖 — 反向路径上没有显式 × count。 count× 权重隐式存在于 Add-combiner 中：count 个重复 id 中的每一个都贡献一次梯度，scatter 的 AddComputation 将它们全部求和到单个唯一行，因此折叠后的行正好累加 count × 每输入梯度。重新实现者如果在反向路径寻找按 multiplicity 的 MulOp，将找不到；这个乘法就是 Add-combiner 对重复 run 的折叠。

前向 Combiner — `gains` 除数

前向归约是按每个 id 的 gain 缩放的 segmented sum。combiner 是三者之一，已从 backend-config attr 字符串 "sum" / "mean" / "sqrtn" 逐字节确认：

Combiner	`gains`	实现方式
`sum`	`1`	（无缩放）
`mean`	`1 / valency`	`ReciprocalF32`（`EmitExtendedVectorVxUnop` `0x13a1dc00`）
`sqrtn`	`1 / sqrt(valency)`	`ReciprocalSqrtF32`（`0x13a1de00`）

valency = 每样本 id 计数 = multiplicity。gains 在 SparseDenseMatmulDotCombinerEmitter::EmitValencyLoop（@0x1332cee0）内部按样本应用；SortVectorsAndGainsBySampleIds（@0x1367c5a0）在 segmented reduce 前按 sample id 对聚集的行和它们的 gains 排序。承载这些内容的 config 字段是 gains、csr_row_pointers、has_reciprocal、has_reciprocal_sqrt、divisor、max_valency、feature_length、valency。Bf16 reciprocal 变体（0x13a1dd00 / 0x13a1df00）存在于半精度路径。

注意 — TEC 向量内 DuplicateCount 与 HLO CSR multiplicity 是否曾被组合尚未按位追踪。 两者都会产生计数，但每 tile 的向量内 primitive 与跨 minibatch 的 CSR row-pointer 计数是并行机制；哪个在何种粒度上喂给哪个 scatter 尚未解析。custom-combiner gains 算术（SparseDenseMatmulCustomCombinerOpDecomposer 0x1366cf80）定义了 sum/mean/sqrtn 之外的 gains，未追踪。

Uniquify 逆置换

目的

去重 loop 对每个唯一行计算一次，但嵌入 op 必须为每个输入 lane 产生一个结果。…_with_lane_ids op 的第三个结果就是闭合这个 loop 的映射：对于每个原始输入 lane，它给出折叠到的唯一行，即 PermuteOp 用来把每唯一项结果扇出回每个输入位置的逆置换。

映射及其类型

result[2]（"lane_ids"）是 vector<N×i32>，与输入形状相同（由上面 inferReturnTypes 中同一个 VectorType::get(inputShape, i32) 构造）。它是逆置换：域 = 输入 lane 索引，陪域 = 唯一行索引。读取 lane k 会给出输入 id k 映射到的唯一代表。

消费者 — Scatter 前的 `PermuteOp`

RankAndPermuteComputeFunction（@0x134039c0）中的发出序列，即 SC radix-sort emitter，已逐字节确认：

text

UniqueOp                  create @0x134042a9   (sc_tpu.unique)
UniqueWithLaneIdsOp       create @0x13404303   (sc_tpu.unique_with_lane_ids → lane_ids = result[2])
VectorLoadStoreIdxAddOp   create @0x1340456c   (rank / fetch-and-add over the unique window)
PermuteOp                 create @0x13404771   (data, lane_ids) → fan result back to input lanes
VectorStoreIdxOp          create @0x134049cb   (write the permutation index vector)

PermuteOp 是 NOperands<2>、OneResult（create @0x145f3920；lowering @0x135a1640 → tpu_sc_permute / llvm.tpu.vperm.sublane）。它接受 (data, lane_ids) 并应用置换，在 VectorStoreIdx / fetch-and-add scatter 写入结果前，立即把每唯一行结果路由回原始输入 lane 位置。第二个调用者是 (anon)::TransferOperandSlices（@0x13d202e0），位于 ElementScatterContext 内；这是使用 lane-id 映射来路由切片的 scatter 消费者。

注意 — 普通 unique op 没有 lane_ids，并跳过 PermuteOp。 emitter 通过目标能力查询选择 UniqueWithLaneIds（3 个结果）或 Unique（2 个结果）；在普通路径中，lane_id Value 为空，PermuteOp 步骤完全省略（见 RankAndPermute）。总是发出 PermuteOp 的重新实现会在无 lane-ids 路径上因空 operand 而出错。tpu_sc_permute 的 HW datapath（sublane-permute 网络宽度 / 周期）由硅片决定。

向量内 Fetch-and-Add 提交顺序

目的

当一个向量的两个 lane scatter-add 到同一地址时，它们的 read-modify-add 提交顺序决定了原始（未去重）scatter 的结果。本节记录 IR 指定了什么、没有指定什么，以及为什么去重路径不受影响。

无 Atomic Ordering — 只有 Alias Scope

fetch-and-add op tpu_vst_msk_idx_ret_add_np 携带如下 trait 包，已从其 getHasTraitFn 模板实例化（@0x14a6ac60）逐字节确认：

text

ZeroRegions · OneResult · OneTypedResult<Type> · ZeroSuccessors · NOperands<4u>
            · OpInvariants · BytecodeOpInterface::Trait
            · LLVM::AccessGroupOpInterface::Trait · LLVM::AliasAnalysisOpInterface::Trait

这里没有 AtomicOrdering trait，也没有 MemoryEffectsOpInterface ordering attribute。唯一的内存接口是 AccessGroup 和 AliasAnalysis，即给调度器使用的 LLVM alias-scope metadata，而不是 atomic ordering。普通 scatter-add tpu_vst_msk_idx_add 是 NOperands<4>、ZeroResult（无返回）。fetch-and-add 返回加之前的值（它通过 load-Dest mux 读取；见 VectorLoad Slot）；其 LLVM intrinsic 是 llvm.tpu.vst.msk.idx.ret.add.{np,e4m3,e5m2}（无 .cb 形式）。

VectorLoadStoreIdxAddOpLowering::matchAndRewrite（@0x135c3ba0）计算 strided element pointer（MemRefDescriptor::stride + LLVM::MulOp + LLVM::AddOp = base + index*stride），构造索引向量（ShuffleVectorOp / InsertElementOp），读取 mask（getBoolVectorAttr），并发出一个 tpu_vst_msk_idx_ret_add_np::create。lowering 中没有 loop、没有 atomic 构造、没有逐 lane 序列化；它是单个 HW 向量 op。

text

intra-vector same-address fetch-and-adds within ONE vector:
   IR says nothing about order  →  it is silicon  (a read-modify-add HAZARD)
cross-vector order:
   sequential program order of the scatter instructions (each is one ordered HW op)

硬件会检测同地址冲突：SC telemetry counter "Address match conflict count"（位于 .rodata string pool 中 "Stream wait count" 附近）和 conflict-stall 字符串（"must wait more that 16 cycles due to conflicting accesses by Vector Store instructions"）表明 HW 会用 stall cycles 序列化冲突的同地址访问；combine 是有序 read-modify-add，不是自由并行 reduce。

陷阱 — 对原始 scatter，向量内提交顺序在这里未定义。 一个向量内并发同地址 fetch-and-add 的精确逐 lane 优先级（low-lane-first / high-lane-wins / tree-combine）不在 C++ 中；它由硅片决定。这只对禁用去重的 scatter（由 xla_tpu_enable_sparse_core_computation_deduplication @0x223c5f10 控制）重要；对去重路径它无关紧要。

为什么去重让它无关紧要

DeduplicateRowIdsToApply（@0x134b4560）和 DeduplicateGradientVectorsToApply（@0x134b4e40）都使用 unique_indices=TRUE 创建其 HLO Scatter（逐字节确认：push 0x1 = 参数 unique_indices；push 0x0 = 参数 indices_are_sorted）。经过 Uniquify 后，每个唯一行只被触碰一次，因此一个向量中不会有两个 lane 对同一地址 fetch-and-add；逐 lane 提交顺序永远不会影响结果。AliasScopeAssignment / MemrefAliasScopeAnnotationPass（@0x135d2060）会把 LLVM !alias.scope / !noalias metadata 附加到去重后的 scatter op（AliasAnalysisOpInterface trait），为调度器编码 non-aliasing。去重就是正确性机制；硅片向量内顺序只在原始路径可达。

完整 Dedup-Reduce 流水线

DuplicateCount 和 Uniquify 位于 SparseCore 嵌入 dedup-reduce datapath 的中段。完整组合如下（其他阶段由链接页面负责）：

text

SparseCore embedding dedup-reduce — 8 stages
 1. GATHER   Stream IndirectStream         id list → HBM[base+id*stride] → TILE_SPMEM   (stream-gather-scatter)
 2. SORT     SortVectorsAndGainsBySampleIds → HLO Sort; TEC VectorExtended SortInteger 20/21
 3. COO→CSR  CooToSparseMatrixFormat        csr_row_pointers = run lengths = multiplicity
 4. UNIQUIFY UniqueWithLaneIds (op 26/27)   collapse duplicates + lane→unique inverse perm (result[2])
 5. COUNT    DuplicateCount (op 24/25)      per-unique multiplicity i32                  ◄── THIS PAGE
 6. REDUCE   forward: SegmentedAddScan sum × gains{1, 1/valency, 1/√valency}             ◄── THIS PAGE
             backward: scatter-ADD gradient into each unique row ONCE (unique_indices=TRUE,
                       Add-combiner = count× accumulation)                               ◄── THIS PAGE
 7. PERMUTE  PermuteOp + lane_ids → tpu_sc_permute   route per-unique result → input lanes  ◄── THIS PAGE
 8. SCATTER  VectorLoadStoreIdxAdd fetch-and-add / VectorStoreIdx; pre-add return;
             no atomic ordering; conflict-free by unique_indices + alias-scope           (vectorload-slot)

阶段 4–7（本页）折叠重复项、计数 multiplicity、将它折入 combiner，并把结果路由回来。实现阶段 2–7 的 radix-sort SSA 发出由 RankAndPermute 负责；应用 gains 的每样本 valency loop 由 Emit Valency Loop 负责；bundle 级 opcode 20/21/24/25/26/27 由 VectorExtended 负责。

分代对照表

去重 op 集和 HLO decomposer 在各代之间稳定：SparseDenseMatmulGradOpDecomposer 以 jellyfish::Target 参数化，因此覆盖所有 SC 代；每代 VectorExtended opcode 字段位置也稳定（vfc/glc/gfc 均为 word 0x28 bits 16..21 的 6-bit 字段）。

Quantity	VF（vfc, v5e）	GL（glc, v5p）	GF（gfc, v6e）
`DuplicateCount{Integer,Float}` VEX op	yes	yes	yes
`Uniquify{Integer,Float}` VEX op	yes	yes	yes
`DuplicateCountInteger` opcode	24（`0x180000`）	24	24
`UniquifyInteger` opcode	26（`0x1a0000`）	26	26
`tpu_dupcnt{i,f}` / `tpu_uniq{i,f}` intrinsic	yes	yes	yes
`sc_tpu.*_with_lane_ids`（3 结果）	yes	yes	yes
`lane_ids` 第三个结果 = `vector<N×i32>`	yes	yes	yes
`tpu_vst_msk_idx_ret_add_np`（fetch-and-add）	yes	yes	yes
fetch-and-add 上的 AtomicOrdering	NO	NO	NO
去重 Scatter `unique_indices=TRUE`	yes	yes	yes

每代 TEC opcode 的 Matches() 锚点：gfc DuplicateCountInteger @0x1eca7b20 / UniquifyInteger @0x1eca7b60；vfc @0x1e9ae0c0 / @0x1e9ae100；glc @0x1eb2d320 / @0x1eb2d360。

函数映射

符号（gfc）	地址	作用
`DuplicateCountUniqueOpLowering<DuplicateCountOp>::matchAndRewrite`	`0x13599d40`	普通计数 lowering，抽取 `{0,1}`
`…<DuplicateCountWithLaneIdsOp>::matchAndRewrite`	`0x1359a7e0`	计数 + lane_ids，抽取 `{0,1,2}`
`…<UniqueOp>::matchAndRewrite`	`0x1359b280`	普通 unique lowering
`…<UniqueWithLaneIdsOp>::matchAndRewrite`	`0x1359bd20`	unique + lane_ids
`ReplaceOpWithExtracts`	`0x135b82a0`	每索引 `ExtractValueOp` + `replaceOp`
`UniqueWithLaneIdsOp::inferReturnTypes`	`0x145a0040`	3 个结果（input · vec<i32> · vec<i32>）
`DuplicateCountWithLaneIdsOp::inferReturnTypes`	`0x1459ff00`	3 个结果（结构相同）
`UniqueOp::inferReturnTypes`	`0x1459fe00`	2 个结果（input · vec<i32>）
`DuplicateCountOp::inferReturnTypes`	`0x1459fd00`	2 个结果
`EmitVectorResultUnop<…DuplicateCountInteger>`	`0x13aaf660`	TEC 向量内计数 emitter（op 24）
`DeduplicateGradientVectorsToApply`	`0x134b4e40`	Add-combiner scatter，`unique_indices=TRUE`
`DeduplicateRowIdsToApply`	`0x134b4560`	Overwrite scatter，折叠 ids
`CumsumExclusive`	`0x134b3ec0`	`Pad` + `ReduceWindow(Add)` → CSR 行索引
`LocalReduction`	`0x134b01e0`	对重复 run 的窗口求和
`CooToSparseMatrixFormat`	`0x13412480`	COO → CSR；row-pointer run lengths
`SortVectorsAndGainsBySampleIds`	`0x1367c5a0`	按 sample id 排序 rows + gains
`EmitValencyLoop`	`0x1332cee0`	每样本 gains 应用
`ReciprocalF32` / `ReciprocalSqrtF32` emitters	`0x13a1dc00` / `0x13a1de00`	`mean` / `sqrtn` gain
`PermuteOp::create` / lowering	`0x145f3920` / `0x135a1640`	应用 lane_ids 逆置换
`tpu_vst_msk_idx_ret_add_np` trait fn	`0x14a6ac60`	fetch-and-add traits（无 AtomicOrdering）
`VectorLoadStoreIdxAddOpLowering::matchAndRewrite`	`0x135c3ba0`	一个 HW op，无序列化
`MemrefAliasScopeAnnotationPass::runOnOperation`	`0x135d2060`	去重 scatters 上的 `!noalias`

注意事项

精确复现 inferReturnTypes。 构造 result[0]=input dtype、result[1..]=vector<N×i32>（WithLaneIds 中两次）。两个 i32 向量共享类型；只有 op 名称后缀能把 lane_ids 映射（result[2]）与次级映射（result[1]）区分开。
将 intrinsic struct 大小设为三字段，而不是 op 的结果数量。 HW intrinsic 总是返回 {value, vec<i32>, vec<i32>}；lowering 通过 ReplaceOpWithExtracts 索引数组暴露 2 个或 3 个结果。2 字段 struct 会误解码 WithLaneIds 形式。
反向 count× 是 Add-combiner，不是乘法。 用 unique_indices=TRUE 和 CreateAddComputation 发出梯度 scatter；count× 累加来自重复项求和。不要在反向路径上添加 × multiplicity op。
前向除数是 gains，按样本应用。 sum → 1、mean → 1/valency、sqrtn → 1/sqrt(valency)，通过 EmitValencyLoop 中的 SC reciprocal op 实现；valency 就是 multiplicity。
在普通 unique 路径跳过 PermuteOp。 lane_ids 只存在于 …_with_lane_ids op；普通路径直接存储 rank，不发出 PermuteOp。
向量内顺序由硅片决定；去重让它无关紧要。 fetch-and-add 没有 atomic-ordering trait；依赖 unique_indices=TRUE + alias-scope，而不是确定性的逐 lane 提交顺序。
未映射。 原始（禁用去重）向量内提交优先级；result[1] 与 result[2] 的职责拆分（[2]=lane_ids，[1] 次级映射）；duplicate_count 的 result[0] 值语义（计数广播）；custom-combiner gains 算术；TEC 向量内与 HLO-CSR multiplicity 的交接；tpu_sc_permute HW datapath。

名称	关系
`DuplicateCountUniqueOpLowering<OpT>`（`0x13599d40`+）	将全部四个去重 op 降低到 3 字段 intrinsic 的同一个模板
`ReplaceOpWithExtracts`（`0x135b82a0`）	通过索引数组长度选择暴露 2 个还是 3 个结果
`SparseDenseMatmulGradOpDecomposer`（`Deduplicate*` `0x134b4560`/`0x134b4e40`）	HLO multiplicity 分解（CSR + Add-combiner scatter）
`SparseDenseMatmulDotCombinerEmitter::EmitValencyLoop`（`0x1332cee0`）	应用 `sum`/`mean`/`sqrtn` gains（前向乘数）
`tpu_vst_msk_idx_ret_add_np`（trait fn `0x14a6ac60`）	去重所喂给的 fetch-and-add；无 atomic ordering，仅 alias-scope
`RankAndPermuteComputeFunction`（`0x134039c0`）	SSA 发出序列（Unique → IdxAdd → Permute → StoreIdx）

交叉引用

RankAndPermute and the Radix-Sort Ordering — 创建本文所记录的 Unique / Permute / scatter op 的 SSA 发出序列
VectorExtended (VEX) — bundle 级 Sort/Uniquify/DuplicateCount opcode（20/21/24/25/26/27）和 scan-emitter 模型
VectorLoad Slot — fetch-and-add 返回路径（通过 load-Dest mux 的 pre-add）和 SourceOne scan 种子
Emit Valency Loop — 消费 multiplicity 并应用 gains 的每样本 valency loop
Sample Combiner Emitter — 驱动 sort → dedup → gather → reduce datapath 的嵌入 combiner
SparseCore Overview — dedup-reduce 在 SC 引擎类中的位置
Binary: extracted/libtpu-0.0.40-cp314-cp314-manylinux_2_31_x86_64/libtpu/libtpu.so（build-id 89edbbe81c5b328a958fe628a9f2207d）
索引条目: Part IX — SparseCore & BarnaCore / SparseCore datapath (embeddings) — 返回索引

去重 Multiplicity ​

摘要 ​

Dedup Op → Intrinsic → 结果映射 ​

目的 ​

四个 Op ​

Lowering — 一个模板，三个 Struct 字段 ​

Lowering / Intrinsic 地址映射 ​

结果类型 {#the-result-types} ​

目的 ​

WithLaneIds 构造（3 个结果） ​

普通构造（2 个结果） ​

Multiplicity 算术 — 两个层级 ​

目的 ​

TEC 向量内 — DuplicateCount 扫描 Op ​

HLO 分解 — CSR Row-Pointers 和 Add-Combiner ​

前向 Combiner — gains 除数 ​

Uniquify 逆置换 ​

目的 ​

映射及其类型 ​

消费者 — Scatter 前的 PermuteOp ​

向量内 Fetch-and-Add 提交顺序 ​

目的 ​

无 Atomic Ordering — 只有 Alias Scope ​

为什么去重让它无关紧要 ​

完整 Dedup-Reduce 流水线 ​

分代对照表 ​

函数映射 ​

注意事项 ​

相关组件 ​

交叉引用 ​

去重 Multiplicity

摘要

Dedup Op → Intrinsic → 结果映射

目的

四个 Op

Lowering — 一个模板，三个 Struct 字段

Lowering / Intrinsic 地址映射

结果类型 {#the-result-types}

目的

WithLaneIds 构造（3 个结果）

普通构造（2 个结果）

Multiplicity 算术 — 两个层级

目的

TEC 向量内 — `DuplicateCount` 扫描 Op

HLO 分解 — CSR Row-Pointers 和 Add-Combiner

前向 Combiner — `gains` 除数

Uniquify 逆置换

目的

映射及其类型

消费者 — Scatter 前的 `PermuteOp`

向量内 Fetch-and-Add 提交顺序

目的

无 Atomic Ordering — 只有 Alias Scope

为什么去重让它无关紧要

完整 Dedup-Reduce 流水线

分代对照表

函数映射

注意事项

相关组件

交叉引用