Sort 族 — Tiling 流程M-way Merge Sort【免费下载链接】cannbot-skillsCANNBot 是面向 CANN 开发的用于提升开发效率的系列智能体本仓库为其提供可复用的 Skills 模块。项目地址: https://gitcode.com/cann/cannbot-skillsSort 族 Top-K 排序算子 Tiling 推导流程。基于 M-way 归并排序的分治策略。1. 决策树给定: N, K, dtype, ubSize, coreNum Step 1: 计算 tileSize sortBytesPerElem sizeof(dtype) sizeof(float) sizeof(uint32) PROPOSAL_SIZE concatTmpPerElem sortTmpPerElem tileSize min(ubSize / sortBytesPerElem, 4096) 对齐到32 Step 2: 比较 N 与 tileSize ├─ N ≤ tileSize │ → Pattern A: 单核排序 │ 直接 Sort API 完成 │ └─ N tileSize └─ 比较 N 与 tileSize × coreNum ├─ N ≤ tileSize × coreNum │ → Pattern B: 多核一级归并 │ 每核≤1个tile, 无需核内多tile归并 │ └─ N tileSize × coreNum → Pattern C: 多核两级归并 每核1个tile, 需两阶段归并2. Pattern C: 四阶段架构Phase 1 — tile排序 (全核并行): 各核将GM数据读入UB → CastArithProgressionConcat → Sort → workspace[0] Phase 2 — 核内多tile归并 (全核并行, 无同步): 各核独立将S_c个有序tile通过M-way归并合并为1个有序数列 循环条件: while listNum ! 1 Phase 3 — 跨核归并 (递减核数, 每轮SyncAll): 将coreNum路逐步归并至≤M路 循环条件: while listNum M Phase 4 — 最终归并输出 (仅Core 0): 将≤M路归并为最终结果 → Extract分离value/index → GM3. Tile 切分公式totalTiles CeilDiv(N, tileSize) frontCoreTiles CeilDiv(totalTiles, coreNum) usedCore CeilDiv(totalTiles, frontCoreTiles) lastCoreTiles totalTiles - (usedCore-1) × frontCoreTiles lastTileSize N - tileSize × (totalTiles-1) elementsPerCore frontCoreTiles × tileSize4. UB 预算 (分Phase)PhaseBuffer数bytes/elemonceMaxElementsPhase 1 (Sort)6~34B (fp16) tileSize 4096Phase 2/3 (Merge)264B(ubSize/64)/32×32Phase 4 (Output)5104B (fp16)(ubSize/BPE)/32×325. 归并轮次Phase 2 归并轮次 ceil(log_M(S_c)) Phase 3 归并轮次 ceil(log_M(coreNum)) - 1 (最后一轮由Phase 4完成) Phase 4 1轮 ≤M-way归并 总SyncAll次数 ceil(log_M(coreNum)) 16. 截断优化 (Top-K)当currentElements × M ≥ K时启用截断:归并输出≥K时, 后续只处理前K个有效元素截断标志truncationFlag跨Phase 2/3持久化首次触发时读入完整数据, 下一轮开始读截断长度7. Workspace 双缓存wsPerCore E_c × 8B × 2 (32B对齐, 双缓存) workspace[0]: 写缓存 workspace[1]: 读缓存 每轮归并后 workSpaceFlag 1 - workSpaceFlag (交替)【免费下载链接】cannbot-skillsCANNBot 是面向 CANN 开发的用于提升开发效率的系列智能体本仓库为其提供可复用的 Skills 模块。项目地址: https://gitcode.com/cann/cannbot-skills创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考