Closed
[Requirement|需求建议]: 新增 SortWithIndex 算子在 Atlas A2/A3 上的实现 #4809
流栎Add on 5 days agoClosed at 4 days ago
5 days ago Change title to "[Requirement|需求建议]: 新增 SortWithIndex 算子在 Atlas A2/A3 上的实现", originally titled "[Requirement|需求建议]: ".
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
陈思
5 days ago Comments:
5 days ago Comments:
/assign @zzzsss1234


5 days ago Assign zzzsss1234 as responsible person
4 days ago Close issue
4 days ago changed custom state from 待办的 to 已完成
4 days ago Added label: resolved
一、背景信息 (必填)
新增 SortWithIndex 算子在 Atlas A2/A3 上的实现,用于沿最后一维对输入数值进行升序或降序排序,同时按照相同顺序重排调用者传入的索引。
该算子的输入索引可以来自前序 TopK 算子。它与普通 Sort 输出的“本次排序位置”不同,代表需要随数值一起传递的外部索引。
例如:
在 TopK 排序后处理场景中,原方案通过 Sort 得到排序位置,再通过 GatherElements 重排 TopK 索引。本实现将数值排序和输入索引重排融合,替代原有 Sort + GatherElements 组合。
二、价值/作用 (必填)
性能与 workspace 收益随 shape、数据类型和排序方向变化,具体指标以对应版本的测试报告为准。
三、设计方案 (必填)
3.1 使能方式(涉及哪些框架:如Aclnn直调、Pytorch训练等)
通过 ACLNN 执行器完成算子下发。在 ops-nn 的 aclnnTopK 相关后处理分支中,调用该接口完成 TopK 结果排序及索引重排。
调用关系如下:
本次实现未新增独立的公开 aclnnSortWithIndex 接口,也未新增 PyTorch 原生算子注册;框架侧是否使用该路径,取决于其 ACLNN 接入方式。
3.2 总体设计
将输入张量按最后一维划分为多行:
每行独立排序。比较依据来自 x,index 仅随对应数值移动,不参与大小比较。
3.2.1 算子支持的数据类型
输入 x 与 index 的 shape 必须相同,两个输出的 shape 均与输入一致。
3.2.2 host侧设计
Host 负责输入校验、算法选择、核切分、UB 容量核算及 workspace 申请。
校验数据类型、输入 shape 一致性、排序轴及维度合法性,并计算 R、N。
当前使用以下 tiling key:
当前基数排序起始阈值为:
其中,N 为最后一维长度,R 为前面所有维度的乘积。
当 N 达到对应阈值时,选择 key2(MULTI_BLOCK)基数排序路径。
上述阈值属于性能策略,实际 tile 和核切分还需通过 UB 容量检查。
上述阈值属于性能策略,实际选择还需通过 UB 容量检查。
3. 核切分与负载均衡
3.2.3 kernel侧设计
Kernel 使用 AscendC 实现,通过 tiling key 选择对应执行路径。
支持同一核批量处理多行,以摊薄短行调度及指令开销。
2. 整行 UB 排序:key6
一个核负责完整一行。常规路径将数值排序字段与输入 INT32 索引组织成排序记录:
通过 Sort32 和 MrgSort 在 UB 内完成排序,再直接提取数值及索引输出。特殊值场景使用对应的兼容处理路径。
3. GM 归并:key8
将输入划分为多个 run,即局部有序段:
支持单核处理一行或多核协作处理一行。多核协作时,各核先处理连续输入段;当前跨段最终归并由该行的 lane0 执行。
4. 四路流式归并:key9
一个核独立处理一行,将整行划分为四个 run,分别在 UB 中排序并写入 GM。
随后从四个 run 读取窗口,通过四路归并生成当前可确定的有序前缀,直接输出并更新消费位置,循环至整行完成。该路径无需核间同步。
5. 稳定基数排序:key2
采用 2-bit LSD 基数排序,每轮处理 2 位,共 4 个桶,16 位排序键最多执行 8 轮:
每核负责连续 tile,各核 tile 数尽量均衡。通过输入预取、双缓冲及事件同步协调搬运和计算。
多行组并行时,各组使用独立 workspace;对全局屏障统一安排执行轮次,避免不同行数据范围不同造成同步次数不一致。
3.3 支持硬件
本实现面向:
采用 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;实际还受设备内存及缓冲容量约束。
输入索引作为随行数据传递,不要求是本行内连续的位置编号。