Closed
[Requirement|需求建议]: 新增 SortWithIndex 算子在 Atlas A2/A3 上的实现 #4809
流栎Add on  5 days agoClosed at  4 days ago
流栎
流栎
5 days ago Create

一、背景信息 (必填)

新增 SortWithIndex 算子在 Atlas A2/A3 上的实现,用于沿最后一维对输入数值进行升序或降序排序,同时按照相同顺序重排调用者传入的索引。
该算子的输入索引可以来自前序 TopK 算子。它与普通 Sort 输出的“本次排序位置”不同,代表需要随数值一起传递的外部索引。
例如:

输入:
x     = [3, 1, 2]
index = [8, 5, 9]

升序输出:
y            = [1, 2, 3]
sorted_index = [5, 9, 8]

在 TopK 排序后处理场景中,原方案通过 Sort 得到排序位置,再通过 GatherElements 重排 TopK 索引。本实现将数值排序和输入索引重排融合,替代原有 Sort + GatherElements 组合。

二、价值/作用 (必填)

  • 减少算子调度开销:将 Sort 与 GatherElements 合并为一次算子执行。
  • 减少中间数据搬运:部分路径在排序记录中直接携带输入索引,归并后直接输出,减少中间位置张量的落盘和后续 Gather。
  • 降低临时空间需求:短行排序完全在 UB 中完成;长行按照实际并行行组申请、复用算法 workspace。
  • 适配不同输入规模:根据行数、排序长度及 UB 容量,选择短行批处理、单核 UB 排序、GM 归并或多核基数排序。
  • 支持 TopK 后处理:保持数值与原输入索引的对应关系,适用于需要返回有序 TopK 数值和索引的场景。
    性能与 workspace 收益随 shape、数据类型和排序方向变化,具体指标以对应版本的测试报告为准。

三、设计方案 (必填)

3.1 使能方式(涉及哪些框架:如Aclnn直调、Pytorch训练等)
l0op::SortWithIndex(
    self, index, axis, descending, stable, executor);

通过 ACLNN 执行器完成算子下发。在 ops-nn 的 aclnnTopK 相关后处理分支中,调用该接口完成 TopK 结果排序及索引重排。
调用关系如下:

aclnnTopKGetWorkspaceSize / aclnnTopK
    ↓
TopK 生成候选数值和对应索引
    ↓
l0op::SortWithIndex
    ↓
Host tiling
    ↓
A2/A3 AscendC Kernel
    ↓
输出排序后的数值及索引

本次实现未新增独立的公开 aclnnSortWithIndex 接口,也未新增 PyTorch 原生算子注册;框架侧是否使用该路径,取决于其 ACLNN 接入方式。

3.2 总体设计

将输入张量按最后一维划分为多行:

N = 最后一维长度
R = 前面所有维度的乘积

输入逻辑上视为 [R,N]

每行独立排序。比较依据来自 x,index 仅随对应数值移动,不参与大小比较。

3.2.1 算子支持的数据类型
参数 含义 支持的数据类型 数据格式
x 待排序数值 FLOAT16、BFLOAT16 ND
index 随数值重排的输入索引 INT32 ND
y 排序后的数值 与 x 相同 ND
sorted_index 重排后的输入索引 INT32 ND

输入 x 与 index 的 shape 必须相同,两个输出的 shape 均与输入一致。

3.2.2 host侧设计

Host 负责输入校验、算法选择、核切分、UB 容量核算及 workspace 申请。

  1. 输入校验
    校验数据类型、输入 shape 一致性、排序轴及维度合法性,并计算 R、N。
  2. 算法选择
    当前使用以下 tiling key:
Key 策略 主要设计
4 MERGE_LOCAL 短行 UB 排序;行数充足时使用多行 batch
6 MERGE_STREAM_UB_SINGLE 一个核负责一行,整行排序在 UB 中完成
8 MERGE_GM 使用有界 UB 排序局部段,通过 GM 保存、归并中间结果
9 MERGE_STREAM_NATIVE 一个核负责一行,固定四段排序后进行流式归并
2 MULTI_BLOCK 动态切分核数和 tile 的稳定基数排序
核心选择逻辑为:
计算 R、N,读取可用核数 Q 和 UB 容量

若 N 达到当前 R 对应的基数排序阈值:
    选择 key2
否则若 N≤2048:
    选择 key4,尝试多行 batch
否则:
    根据每行核预算、N 和 UB 容量
    选择 key6、key8 或 key9

当前基数排序起始阈值为:

行数 R 进入基数排序的起始长度 N
R = 1 32769
2 ≤ R ≤ 8 262144
R ≥ 9 524288

其中,N 为最后一维长度,R 为前面所有维度的乘积。
当 N 达到对应阈值时,选择 key2(MULTI_BLOCK)基数排序路径。

上述阈值属于性能策略,实际 tile 和核切分还需通过 UB 容量检查。

上述阈值属于性能策略,实际选择还需通过 UB 容量检查。
3. 核切分与负载均衡

  • 短行优先按行并行;batch 模式先均衡分配真实行数,再在各核内部划分批次。
  • GM 归并根据行数选择单核处理完整行,或多核分别处理一行中的连续输入段。
  • 基数排序联合选择 tile 长度、每行核数及并行行组数,并通过成本模型平衡计算、同步和搬运开销。
  • 核内 tile 长度通常按 128 元素对齐,搬运空间按对应 DMA 要求对齐。
  1. Workspace 管理
  • key4、key6 的算法 workspace 为 0。
  • key8、key9、key2 根据中间记录及并行行组数量申请空间。
  • 同一行组处理后续行时复用已有空间,避免按总行数重复申请。
  • 使用算法 GM workspace 时,额外申请平台系统空间,保持系统区与用户算法区隔离:
总 workspace = 系统 workspace + 算法 workspace

3.2.3 kernel侧设计

Kernel 使用 AscendC 实现,通过 tiling key 选择对应执行路径。

  1. 短行归并:key4
搬入数值
    ↓
构造包含数值顺序和原始位置的复合分数
    ↓
Sort32 生成短有序段
    ↓
MrgSort 在 UB 中逐层归并
    ↓
按排序位置 Gather 数值和输入索引
    ↓
搬出结果

支持同一核批量处理多行,以摊薄短行调度及指令开销。
2. 整行 UB 排序:key6
一个核负责完整一行。常规路径将数值排序字段与输入 INT32 索引组织成排序记录:

记录 = 排序字段 + 随行索引

通过 Sort32 和 MrgSort 在 UB 内完成排序,再直接提取数值及索引输出。特殊值场景使用对应的兼容处理路径。
3. GM 归并:key8
将输入划分为多个 run,即局部有序段:

输入段搬入 UB → 局部排序 → 有序记录写入 GM
    ↓
从 GM 分批读取有序窗口,在 UB 中归并
    ↓
非最终层写回另一块 GM 记录区
    ↓
最终层输出数值和索引

支持单核处理一行或多核协作处理一行。多核协作时,各核先处理连续输入段;当前跨段最终归并由该行的 lane0 执行。
4. 四路流式归并:key9
一个核独立处理一行,将整行划分为四个 run,分别在 UB 中排序并写入 GM。
随后从四个 run 读取窗口,通过四路归并生成当前可确定的有序前缀,直接输出并更新消费位置,循环至整行完成。该路径无需核间同步。
5. 稳定基数排序:key2
采用 2-bit LSD 基数排序,每轮处理 2 位,共 4 个桶,16 位排序键最多执行 8 轮:

搬入 tile,构造有序键
    ↓
计算每 tile、每核的桶计数
    ↓
汇总前缀,计算各桶输出位置
    ↓
稳定分桶,搬出数值和对应索引
    ↓
切换输入输出缓冲,处理下一轮

每核负责连续 tile,各核 tile 数尽量均衡。通过输入预取、双缓冲及事件同步协调搬运和计算。
多行组并行时,各组使用独立 workspace;对全局屏障统一安排执行轮次,避免不同行数据范围不同造成同步次数不一致。

3.3 支持硬件

本实现面向:

  • Atlas A2 系列,注册配置为 ascend910b。
  • Atlas A3 系列,注册配置为 ascend910_93。
    采用 arch22 Host 和 Kernel 实现,与 A5 的 arch35 实现分目录维护。

3.4 算子约束限制

数值输入仅支持 FLOAT16、BFLOAT16,输入及输出索引仅支持 INT32。
仅支持 ND 格式的连续稠密输入;非连续输入需要上层先完成连续化处理。
仅支持最后一维排序,不支持直接沿其他维度排序;上层可通过转置适配。
x 与 index 必须具有相同 shape,不支持广播。
当前接口按 rank 1~8 使用;超过 8 维尚未完成完整的接口适配和验证。
不支持 rank=0 的标量及包含零长度维度的输入。
最后一维长度满足 1≤N≤INT32_MAX,前面各维乘积满足 1≤R≤UINT32_MAX;实际还受设备内存及缓冲容量约束。
输入索引作为随行数据传递,不要求是本行内连续的位置编号。

likedislike
流栎流栎
5 days ago Change title to "[Requirement|需求建议]: 新增 SortWithIndex 算子在 Atlas A2/A3 上的实现", originally titled "[Requirement|需求建议]: ".
流栎流栎
5 days ago Modify description of issue
流栎流栎
5 days ago Modify description of issue
流栎流栎
5 days ago Associated pull request
陈思
陈思Collaborators
5 days ago Comments:

/assign @zzzsss1234

likedislike
CANN-robotCANN-robotCollaborators
5 days ago Assign zzzsss1234 as responsible person
CANN-robotCANN-robotCollaborators
4 days ago Close issue
CANN-robotCANN-robotCollaborators
4 days ago changed custom state from 待办的 to 已完成
CANN-robotCANN-robotCollaborators
4 days ago Added label: resolved