Sort【免费下载链接】asc-devkit本项目是CANN 推出的昇腾AI处理器专用的算子程序开发语言原生支持C和C标准规范主要由类库和语言扩展层构成提供多层级API满足多维场景算子开发诉求。项目地址: https://gitcode.com/cann/asc-devkit产品支持情况产品是否支持Ascend 950PR/Ascend 950DT√Atlas A3 训练系列产品 / Atlas A3 推理系列产品√Atlas A2 训练系列产品 / Atlas A2 推理系列产品√Atlas 200I/500 A2 推理产品xAtlas 推理系列产品 AI Core√Atlas 推理系列产品 Vector CorexAtlas 训练系列产品xKirin X90√Kirin 9030√功能说明对应不带模板参数SortConfig的函数原型排序函数按照数值大小进行降序排序。排序后的数据按照如下排布方式进行保存Ascend 950PR/Ascend 950DT采用方式一。Atlas A3 训练系列产品/Atlas A3 推理系列产品采用方式一。Atlas A2 训练系列产品/Atlas A2 推理系列产品采用方式一。Atlas 推理系列产品AI Core采用方式二。Kirin X90采用方式一。Kirin 9030采用方式一。排布方式一一次迭代可以完成32个数的排序排序好的score与其对应的index一起以score, index的结构存储在dst中。不论score为half还是float类型dst中的score, index结构总是占据8Bytes空间。如下所示当score为floatindex为uint32类型时计算结果中index存储在高4Bytesscore存储在低4Bytes。当score为halfindex为uint32类型时计算结果中index存储在高4Bytesscore存储在低2Bytes 中间的2Bytes保留。排布方式二Region Proposal排布输入输出数据均为Region Proposal一次迭代可以完成16个region proposal的排序。每个Region Proposal占用连续8个half/float类型的元素约定其格式[x1, y1, x2, y2, score, label, reserved_0, reserved_1]对于数据类型half每一个Region Proposal占16BytesByte[15:12]是无效数据Byte[11:0]包含6个half类型的元素其中Byte[11:10]定义为labelByte[9:8]定义为scoreByte[7:6]定义为y2Byte[5:4]定义为x2Byte[3:2]定义为y1Byte[1:0]定义为x1。如下图所示总共包含16个Region Proposals。对于数据类型float每一个Region Proposal占32BytesByte[31:24]是无效数据Byte[23:0]包含6个float类型的元素其中Byte[23:20]定义为labelByte[19:16]定义为scoreByte[15:12]定义为y2Byte[11:8]定义为x2Byte[7:4]定义为y1Byte[3:0]定义为x1。如下图所示总共包含16个Region Proposals。对应带模板参数SortConfig的函数原型仅在Ascend 950PR/Ascend 950DT上支持。根据模板参数SortConfig按其中指定的排序算法对输入数据排序排序结果可以指定升序或降序排序。当函数原型带有输出索引dstIndexTensor参数需要输出排序结果数据分别对应的索引若输入带有索引srcIndexTensor参数则输出索引即为原输入的索引若输入不带有索引则对输入数据从0开始生成所需排序数量的索引最终输出索引即为对应输入数据的索引。如下两幅图分别为输入带有索引和输入不带索引的数据排序示意图。图 1输入带有索引srcIndex的排序样例图 2输入不带索引srcIndex的排序样例函数原型不带SortConfigtemplate typename T, bool isFullSort __aicore__ inline void Sort(const LocalTensorT dst, const LocalTensorT concat, const LocalTensoruint32_t index, LocalTensorT tmp, const int32_t repeatTime)带SortConfig仅在Ascend 950PR/Ascend 950DT上支持。接口框架申请临时空间不带srcIndexTensor和dstIndexTensor参数template typename T, bool isReuseSource false, const SortConfig config DEFAULT_SORT_CONFIG __aicore__ inline void Sort(LocalTensorT dstTensor, const LocalTensorT srcTensor, const uint32_t calCount)不带srcIndexTensor参数带有dstIndexTensor参数template typename T, bool isReuseSource false, const SortConfig config DEFAULT_SORT_CONFIG __aicore__ inline void Sort(LocalTensorT dstTensor, LocalTensoruint32_t dstIndexTensor, const LocalTensorT srcTensor, const uint32_t calCount)带有srcIndexTensor和dstIndexTensor参数template typename T, typename U, bool isReuseSource false, const SortConfig config DEFAULT_SORT_CONFIG __aicore__ inline void Sort(const LocalTensorT dstTensor, const LocalTensorU dstIndexTensor, const LocalTensorT srcTensor, const LocalTensorU srcIndexTensor, const uint32_t calCount)通过sharedTmpBuffer入参传入临时空间不带srcIndexTensor和dstIndexTensor参数template typename T, bool isReuseSource false, const SortConfig config DEFAULT_SORT_CONFIG __aicore__ inline void Sort(LocalTensorT dstTensor, const LocalTensorT srcTensor, const LocalTensoruint8_t sharedTmpBuffer, const uint32_t calCount)不带srcIndexTensor参数带有dstIndexTensor参数template typename T, bool isReuseSource false, const SortConfig config DEFAULT_SORT_CONFIG __aicore__ inline void Sort(LocalTensorT dstTensor, LocalTensoruint32_t dstIndexTensor, const LocalTensorT srcTensor, const LocalTensoruint8_t sharedTmpBuffer, const uint32_t calCount)带有srcIndexTensor和dstIndexTensor参数template typename T, typename U, bool isReuseSource false, const SortConfig config DEFAULT_SORT_CONFIG __aicore__ inline void Sort(LocalTensorT dstTensor, LocalTensorU dstIndexTensor, const LocalTensorT srcTensor, const LocalTensorU srcIndexTensor, const LocalTensoruint8_t sharedTmpBuffer, const uint32_t calCount)由于该接口的内部实现中涉及复杂的数学计算需要额外的临时空间来存储计算过程中的中间变量。临时空间支持开发者通过sharedTmpBuffer入参传入和接口框架申请两种方式。通过sharedTmpBuffer入参传入使用该tensor作为临时空间进行处理接口框架不再申请。该方式开发者可以自行管理sharedTmpBuffer内存空间并在接口调用完成后复用该部分内存内存不会反复申请释放灵活性较高内存利用率也较高。接口框架申请临时空间开发者无需申请但是需要预留临时空间的大小。通过sharedTmpBuffer传入的情况开发者需要为tensor申请空间接口框架申请的方式开发者需要预留临时空间。临时空间大小BufferSize的获取方式如下通过GetSortMaxMinTmpSize中提供的接口获取需要预留空间范围的大小。参数说明对应不带SortConfig的函数原型表 1模板参数说明参数名含义T操作数的数据类型。支持的数据类型为half、float。Kirin X90支持的数据类型为half。Kirin 9030支持的数据类型为half。isFullSort是否开启全排序模式。全排序模式指将全部输入降序排序非全排序模式下排序方式请参考表2中的repeatTime说明。表 2参数说明参数名称输入/输出含义dst输出目的操作数shape为[2n]。类型为LocalTensor支持的TPosition为VECIN/VECCALC/VECOUT。LocalTensor的起始地址需要32字节对齐。concat输入源操作数即接口功能说明中的scoreshape为[n]。类型为LocalTensor支持的TPosition为VECIN/VECCALC/VECOUT。LocalTensor的起始地址需要32字节对齐。此源操作数的数据类型需要与目的操作数保持一致。index输入源操作数shape为[n]。类型为LocalTensor支持的TPosition为VECIN/VECCALC/VECOUT。LocalTensor的起始地址需要32字节对齐。此源操作数固定为uint32_t数据类型。tmp输入临时空间。接口内部复杂计算时用于存储中间变量由开发者提供临时空间大小BufferSize的获取方式请参考GetSortTmpSize。数据类型与源操作数保持一致。类型为LocalTensor支持的TPosition为VECIN/VECCALC/VECOUT。LocalTensor的起始地址需要32字节对齐。repeatTime输入重复迭代次数int32_t类型。Ascend 950PR/Ascend 950DT每次迭代完成32个元素的排序下次迭代concat和index各跳过32个elementsdst跳过32*8 Byte空间。取值范围repeatTime∈[0,255]。Atlas A3 训练系列产品 / Atlas A3 推理系列产品每次迭代完成32个元素的排序下次迭代concat和index各跳过32个elementsdst跳过32*8 Byte空间。取值范围repeatTime∈[0,255]。Atlas A2 训练系列产品 / Atlas A2 推理系列产品每次迭代完成32个元素的排序下次迭代concat和index各跳过32个elementsdst跳过32*8 Byte空间。取值范围repeatTime∈[0,255]。Atlas 推理系列产品 AI Core每次迭代完成16个region proposal的排序下次迭代concat和dst各跳过16个region proposal。取值范围repeatTime∈[0,255]。Kirin X90每次迭代完成32个元素的排序下次迭代concat和index各跳过32个elementsdst跳过32*8 Byte空间。取值范围repeatTime∈[0,255]。Kirin 9030每次迭代完成32个元素的排序下次迭代concat和index各跳过32个elementsdst跳过32*8 Byte空间。取值范围repeatTime∈[0,255]。对应带SortConfig的函数原型表 3模板参数说明接口功能T操作数srcTensor和dstTensor的数据类型。RADIX_SORT排序算法支持的数据类型为uint8_t、int8_t、uint16_t、int16_t、uint32_t、int32_t、half、bfloat16_t、float、uint64_t、int64_tMERGE_SORT排序算法支持的数据类型为half、float。U操作数srcIndexTensor和dstIndexTensor的数据类型。RADIX_SORT排序算法支持的数据类型为uint32_t、int32_t、uint64_t、int64_tMERGE_SORT排序算法支持的数据类型为uint32_t。isReuseSource可选参数。是否可以复用输入的Tensor空间。config可选参数。Sort接口的相应配置选择的排序算法排序结果的升降序。数据类型SortConfig定义如下。struct SortConfig { SortType type SortType::RADIX_SORT; // 排序算法 bool isDescend false; // 是否降序排序默认值为false输出结果升序排序 };其中排序算法的数据类型SortType取值如下。enum class SortType { RADIX_SORT, // 使用基排序算法实现 MERGE_SORT // 使用归并排序算法实现 };Sort提供了两种不同的排序算法MERGE_SORT归并排序算法和RADIX_SORT基排序算法。两种算法在执行速度、时间复杂度和算法稳定性上表现不同。MERGE_SORT是一种稳定的排序算法在所有情况下算法的时间复杂度都是O(nlogn)。RADIX_SORT算法的时间复杂度是O(n)在处理大量数据时如果最大数字的位数较少该算法的效率很高可以接近线性时间复杂度。但是如果最大数字的位数很大时间复杂度会接近O(n^2)。config的默认值DEFAULT_SORT_CONFIG取值如下使用基排序RADIX_SORT对排序结果升序排序。constexpr SortConfig DEFAULT_SORT_CONFIG {SortType::RADIX_SORT, false};表 4参数说明参数名称输入/输出含义dstTensor输出值目的操作数shape为[n]。MERGE_SORT算法下输出数据的每个元素需要按8Byte申请空间。类型为LocalTensor支持的TPosition为VECIN/VECCALC/VECOUT。LocalTensor的起始地址需要32字节对齐。dstIndexTensor输出索引目的操作数shape为[n]。当输入不带srcIndexTensor时只支持uint32_t类型。类型为LocalTensor支持的TPosition为VECIN/VECCALC/VECOUT。LocalTensor的起始地址需要32字节对齐。srcTensor输入值源操作数shape为[n]。类型为LocalTensor支持的TPosition为VECIN/VECCALC/VECOUT。LocalTensor的起始地址需要32字节对齐。此源操作数的数据类型需要与值目的操作数保持一致。srcIndexTensor输入索引源操作数shape为[n]。类型为LocalTensor支持的TPosition为VECIN/VECCALC/VECOUT。LocalTensor的起始地址需要32字节对齐。此源操作数的数据类型需要与索引目的操作数保持一致。sharedTmpBuffer输入临时空间。接口内部复杂计算时用于存储中间变量由开发者提供临时空间大小BufferSize的获取方式请参考GetSortMaxMinTmpSize。数据类型为uint8_t。类型为LocalTensor支持的TPosition为VECIN/VECCALC/VECOUT。LocalTensor的起始地址需要32字节对齐。calCount输入需要进行排序的数据元素个数。uint32_t类型。返回值说明无约束说明操作数地址对齐要求请参见通用地址对齐约束。不带SortConfig的接口当存在score[i]与score[j]相同时如果ij则score[j]将首先被选出来排在前面即index的顺序与输入顺序一致。非全排序模式下每次迭代内的数据会进行排序不同迭代间的数据不会进行排序。带SortConfig的接口基排序RadixSort和归并排序MergeSort都为稳定排序即相同值在排序后的先后顺序保持不变。值目的操作数、值源操作数、索引目的操作数、索引源操作数的元素个数相同且calCount参数值不能超过元素个数。不支持源操作数与目的操作数地址重叠。不支持sharedTmpBuffer与源操作数和目的操作数地址重叠。使用MERGE_SORT算法排序时待排序的元素个数必须是32的倍数。若不是32的倍数用户需要手动将数据量补齐到32的倍数。调用示例处理128个half类型数据。该样例适用于Ascend 950PR/Ascend 950DTAtlas A2 训练系列产品/Atlas A2 推理系列产品Atlas A3 训练系列产品/Atlas A3 推理系列产品Kirin X90Kirin 9030// sortedLocal排序结果 // concatLocal待排序数据的预处理结果 // indexLocal索引数据 // sortTmpLocal临时空间 // 待排序元素数量 uint32_t elementCount 128; // 迭代次数每次迭代完成32个元素的排序 uint32_t m_sortRepeatTimes m_elementCount / 32; uint32_t m_extractRepeatTimes m_elementCount / 32; // 预处理 AscendC::Concat(concatLocal, valueLocal, concatTmpLocal, m_concatRepeatTimes); // 执行排序 AscendC::SortT, isFullSort(sortedLocal, concatLocal, indexLocal, sortTmpLocal, m_sortRepeatTimes); AscendC::Extract(dstValueLocal, dstIndexLocal, sortedLocal, m_extractRepeatTimes);示例结果 输入数据srcValueGm: 128个half类型数据 [31 30 29 ... 2 1 0 63 62 61 ... 34 33 32 95 94 93 ... 66 65 64 127 126 125 ... 98 97 96] 输入数据srcIndexGm: [31 30 29 ... 2 1 0 63 62 61 ... 34 33 32 95 94 93 ... 66 65 64 127 126 125 ... 98 97 96] 输出数据dstValueGm: [127 126 125 ... 2 1 0] 输出数据dstIndexGm: [127 126 125 ... 2 1 0]处理64个half类型数据。该样例适用于Atlas 推理系列产品AI Coreuint32_t elementCount 64; uint32_t m_sortRepeatTimes m_elementCount / 16; uint32_t m_extractRepeatTimes m_elementCount / 16; AscendC::Concat(concatLocal, valueLocal, concatTmpLocal, m_concatRepeatTimes); AscendC::SortT, isFullSort(sortedLocal, concatLocal, indexLocal, sortTmpLocal, m_sortRepeatTimes); AscendC::Extract(dstValueLocal, dstIndexLocal, sortedLocal, m_extractRepeatTimes);示例结果 输入数据srcValueGm: 64个half类型数据 [15 14 13 ... 2 1 0 31 30 29 ... 18 17 16 47 46 45 ... 34 33 32 63 62 61 ... 50 49 48] 输入数据srcIndexGm: [15 14 13 ... 2 1 0 31 30 29 ... 18 17 16 47 46 45 ... 34 33 32 63 62 61 ... 50 49 48] 输出数据dstValueGm: [63 62 61 ... 2 1 0] 输出数据dstIndexGm: [63 62 61 ... 2 1 0]带SortConfig处理1024个half类型数据输入索引和输出索引为1024个uint32_t类型数据。该样例适用于Ascend 950PR/Ascend 950DTstatic constexpr AscendC::SortConfig config {AscendC::SortType::RADIX_SORT, false}; SortT, false, config(dstLocal, dstIndexLocal, srcLocal, 1024);示例结果 输入数据srcGm: 1024个half类型数据 [1023 1022 ... 2 1 0] 输入数据srcIndexGm: 1024个uint32_t类型数据 [0 1 2 ... 1022 1023] 输出数据dstGm: [0 1 2 ... 1022 1023] 输出数据dstIndexGm: [1023 1022 ... 2 1 0]【免费下载链接】asc-devkit本项目是CANN 推出的昇腾AI处理器专用的算子程序开发语言原生支持C和C标准规范主要由类库和语言扩展层构成提供多层级API满足多维场景算子开发诉求。项目地址: https://gitcode.com/cann/asc-devkit创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
