Sort

Applicability

Function Usage

• Function prototype without the template parameter SortConfig

  Sorts data in descending order by value. The sorted data is saved in the following arrangement mode:

  For the Atlas 350 Accelerator Card, mode 1 is used.

  For the Atlas A3 training product / Atlas A3 inference product , mode 1 is used.

  For the Atlas A2 training product / Atlas A2 inference product , mode 1 is used.

  For the Atlas inference product AI Core, mode 2 is used.

  • Layout mode 1:
    A maximum of 32 scores can be sorted in one iteration. The sorted scores and their corresponding indexes are stored in dst in the (score, index) struct. No matter whether the scores are of the half or float type, the (score, index) structure in dst always occupies 8 bytes. See the following examples:

    • When the score type is float and the index type is uint32, in the computation result, the indexes are stored in the upper 4 bytes and the scores are stored in the lower 4 bytes.

      

    • When the score type is half and the index type is uint32, in the computation result, the indexes are stored in the upper 4 bytes, the scores are stored in the lower 2 bytes, and the middle 2 bytes are reserved.

      

  • Layout mode 2: region proposal
    The input and output data are Region Proposals. 16 Region Proposals are sorted in each iteration. Each Region Proposal consumes eight contiguous elements of the half or float data type. Its format is as follows:

    1	[x1, y1, x2, y2, score, label, reserved_0, reserved_1]

    When a Region Proposal is of the half data type, it occupies 16 bytes. Byte[15:12] is invalid and Byte[11:0] contains six half elements. To be specific, Byte[11:10] is defined as the label, Byte[9:8] is defined as the score, Byte[7:6] is defined as y2, Byte[5:4] is defined as x2, Byte[3:2] is defined as y1, and Byte[1:0] is defined as x1.

    The table in the following figure contains 16 Region Proposals.

    

    When a Region Proposal is of the float data type, it occupies 32 bytes. Byte[31:24] is invalid and Byte[23:0] contains six float elements. To be specific, Byte[23:20] is defined as the label, Byte[19:16] is defined as the score, Byte[15:12] is defined as y2, Byte[11:8] is defined as x2, Byte[7:4] is defined as y1, and Byte[3:0] is defined as x1.

    The table in the following figure contains 16 Region Proposals.

    

• Function prototype with the template parameter SortConfig

  It is supported only on Atlas 350 Accelerator Card.

  Sorts the input data based on the sorting algorithm specified by the template parameter SortConfig. The sorting result can be sorted in ascending or descending order.

  If the function prototype contains the dstIndexTensor parameter, the indexes corresponding to the sorting result data need to be output. If the input has the srcIndexTensor parameter, the output index is the original input index. If the input does not have an index parameter, indexes are generated from 0 for the input data in sequence, and the output indexes are those of the corresponding input data. The following figures show the sorting of input data with index parameter and input data without index parameter.

  Figure 1 Example of input sorting with srcIndex
  
  Figure 2 Example of input sorting without srcIndex
  

Prototype

• Without SortConfig

  1 2	template <typename T, bool isFullSort> __aicore__ inline void Sort(const LocalTensor<T>& dst, const LocalTensor<T>& concat, const LocalTensor<uint32_t>& index, LocalTensor<T>& tmp, const int32_t repeatTime)

Parameters

• Function prototype without SortConfig

  Table 1 Template parameters

  Parameter	Description
  T	Operand data type. For the Atlas 350 Accelerator Card, the supported data types are half and float. For the Atlas A3 training product / Atlas A3 inference product , the supported data types are half and float. For the Atlas A2 training product / Atlas A2 inference product , the supported data types are half and float. For the Atlas inference product AI Core, the supported data types are half and float.
  isFullSort	Whether to enable the full sorting mode. In full sorting mode, all inputs are sorted in descending order. For details about non-full sorting mode, see the description of repeatTime in Table 2.

  Table 2 Parameters

  Parameter	Input/Output	Description
  dst	Output	Destination operand, with shape [2n]. The type is LocalTensor, and TPosition can be VECIN, VECCALC, or VECOUT. The start address of LocalTensor must be 32-byte aligned.
  concat	Input	Source operand, that is, score in the API function description, with shape [n]. The type is LocalTensor, and TPosition can be VECIN, VECCALC, or VECOUT. The start address of LocalTensor must be 32-byte aligned. The source operand must have the same data type as the destination operand.
  index	Input	Source operand, with shape [n]. The type is LocalTensor, and TPosition can be VECIN, VECCALC, or VECOUT. The start address of LocalTensor must be 32-byte aligned. This source operand is fixed at the uint32_t data type.
  tmp	Input	Temporary space. This parameter is used to store intermediate variables during complex internal computation of the API. The temporary space is provided by developers. For details about how to obtain the size of the temporary space BufferSize, see GetSortTmpSize. The data type must be the same as that of the source operand. The type is LocalTensor, and TPosition can be VECIN, VECCALC, or VECOUT. The start address of LocalTensor must be 32-byte aligned.
  repeatTime	Input	Number of iteration repeats. The value is of the int32_t type. Atlas 350 Accelerator Card: 32 elements are sorted in each iteration. In the next iteration, 32 elements are skipped in concat and index, and 32 × 8 bytes are skipped in dst. Value range: repeatTime ∈ [0,255] Atlas A3 training product / Atlas A3 inference product : 32 elements are sorted in each iteration. In the next iteration, 32 elements are skipped in concat and index, and 32 × 8 bytes are skipped in dst. Value range: repeatTime ∈ [0,255] Atlas A2 training product / Atlas A2 inference product : 32 elements are sorted in each iteration. In the next iteration, 32 elements are skipped in concat and index, and 32 × 8 bytes are skipped in dst. Value range: repeatTime ∈ [0,255] Atlas inference product AI Core: 16 Region Proposals are sorted in each iteration. In the next iteration, 16 Region Proposals are skipped in concat and dst. Value range: repeatTime ∈ [0,255]

• Function prototype with SortConfig

  Table 3 Template parameters

  Parameter	Function
  T	Data types of the operands srcTensor and dstTensor. For the Atlas 350 Accelerator Card, the RADIX_SORT algorithm supports the uint8_t, int8_t, uint16_t, int16_t, uint32_t, int32_t, half, bfloat16_t, float, uint64_t, and int64_t data types, and the MERGE_SORT algorithm supports the half and float data types.
  U	Data type of the operands srcIndexTensor and dstIndexTensor. For the Atlas 350 Accelerator Card, the RADIX_SORT algorithm supports the uint32_t, int32_t, uint64_t, and int64_t data types, and the MERGE_SORT algorithm supports the uint32_t data type.
  isReuseSource	This parameter is optional. Whether the input tensor space can be reused.
  config	This parameter is optional. Sort API configuration: includes the selected sorting algorithm and ascending or descending order of the sorting result. The data type SortConfig is defined as follows: 1 2 3 4 struct SortConfig { SortType type = SortType::RADIX_SORT; // Sorting algorithm bool isDescend = false; // Whether to sort the output results in descending order. The default value is false, indicating that the output results are sorted in ascending order. }; The values of SortType are as follows: 1 2 3 4 enum class SortType { RADIX_SORT, // Implemented using the RADIX_SORT algorithm. MERGE_SORT // Implemented using the MERGE_SORT algorithm. }; The Sort API provides two sorting algorithms: MERGE_SORT and RADIX_SORT. The two algorithms have different performance in terms of execution speed, time complexity, and algorithm stability. MERGE_SORT is a stable sorting algorithm with a time complexity of O(nlogn) in all cases. The time complexity of the RADIX_SORT algorithm is O(n). When processing a large amount of data, if the maximum number of digits is small, the algorithm is highly efficient and can approach linear time complexity. However, if the maximum number of digits is large, the time complexity approaches O(n^2). The default value of config is DEFAULT_SORT_CONFIG, which uses the RADIX_SORT algorithm to sort the sorting results in ascending order. 1 constexpr SortConfig DEFAULT_SORT_CONFIG = {SortType::RADIX_SORT, false};

  Table 4 Parameters

  Parameter	Input/Output	Description
  dstTensor	Output	Value destination operand, with shape [n]. In the MERGE_SORT algorithm, space must be allocated for each element of the output data based on 8 bytes. The type is LocalTensor, and TPosition can be VECIN, VECCALC, or VECOUT. The start address of LocalTensor must be 32-byte aligned.
  dstIndexTensor	Output	Index destination operand, with shape [n]. If the input does not contain srcIndexTensor, only the uint32_t type is supported. The type is LocalTensor, and TPosition can be VECIN, VECCALC, or VECOUT. The start address of LocalTensor must be 32-byte aligned.
  srcTensor	Input	Value source operand, with shape [n]. The type is LocalTensor, and TPosition can be VECIN, VECCALC, or VECOUT. The start address of LocalTensor must be 32-byte aligned. The source operand must have the same data type as the value destination operand.
  srcIndexTensor	Input	Index source operand, with shape [n]. The type is LocalTensor, and TPosition can be VECIN, VECCALC, or VECOUT. The start address of LocalTensor must be 32-byte aligned. The source operand must have the same data type as the index destination operand.
  sharedTmpBuffer	Input	Temporary space. This parameter is used to store intermediate variables during complex internal computation of the API. The temporary space is provided by developers. For details about how to obtain the size of the temporary space BufferSize, see GetSortMaxMinTmpSize. The data type is uint8_t. The type is LocalTensor, and TPosition can be VECIN, VECCALC, or VECOUT. The start address of LocalTensor must be 32-byte aligned.
  calCount	Input	Number of data elements to be sorted. The type is uint32_t.

Returns

None

Constraints

• When score[i] is the same as score[j], if i > j, score[j] is selected first. That is, the index sequence is the same as the input sequence.
• In non-full sorting mode, data within each iteration is sorted, but data across different iterations is not sorted.
• For details about the operand address alignment requirements, see General Address Alignment Restrictions.
• APIs with SortConfig:
  • It is supported only by the Atlas 350 Accelerator Card.
  • Both RadixSort and MergeSort are stable sorting algorithms, meaning that the relative order of elements with equal values remains unchanged after sorting.
  • The number of elements in the value destination operand, value source operand, index destination operand, and index source operand must be the same, and the value of calCount cannot exceed the number of elements.
  • The source operand address must not overlap the destination operand address.
  • The address of sharedTmpBuffer cannot overlap that of the source or destination operand.
  • For details about the operand address alignment requirements, see General Address Alignment Restrictions.
  • When the MERGE_SORT algorithm is used for sorting, the number of elements to be sorted must be a multiple of 32. If the number is not a multiple of 32, you need to manually pad the data to a multiple of 32.

Examples

To obtain an operator sample project, click sort operator sample.

• Processing 128 pieces of half-type data

  This example applies to:

  Atlas 350 Accelerator Card

  Atlas A2 training product / Atlas A2 inference product

  Atlas A3 training product / Atlas A3 inference product

  1 2 3 4 5 6 7 8 9 10 11 12 13 14

  // sortedLocal: sorting result // concatLocal: preprocessing result of the data to be sorted // indexLocal: index data // sortTmpLocal: temporary space // Number of elements to be sorted uint32_t elementCount = 128; // Number of iterations. 32 elements are sorted in each iteration. uint32_t m_sortRepeatTimes = m_elementCount / 32; uint32_t m_extractRepeatTimes = m_elementCount / 32; // Preprocess AscendC::Concat(concatLocal, valueLocal, concatTmpLocal, m_concatRepeatTimes); // Sort AscendC::Sort<T, isFullSort>(sortedLocal, concatLocal, indexLocal, sortTmpLocal, m_sortRepeatTimes); AscendC::Extract(dstValueLocal, dstIndexLocal, sortedLocal, m_extractRepeatTimes);

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

  Result example: Input data (srcValueGm): 128 pieces of half-type data [31 30 29 ... 2 1 0 63 62 61 ... 34 33 32 95 94 93 ... 66 65 64 127 126 125 ... 98 97 96] Input (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] Output (dstValueGm): [127 126 125 ... 2 1 0] Output (dstIndexGm): [127 126 125 ... 2 1 0]

• Processing 64 pieces of half-type data

  This example applies to:

  Atlas inference product AI Core

  1 2 3 4 5 6

  uint32_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::Sort<T, isFullSort>(sortedLocal, concatLocal, indexLocal, sortTmpLocal, m_sortRepeatTimes); AscendC::Extract(dstValueLocal, dstIndexLocal, sortedLocal, m_extractRepeatTimes);

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

  Result example: Input data (srcValueGm): 64 pieces of half-type data [15 14 13 ... 2 1 0 31 30 29 ... 18 17 16 47 46 45 ... 34 33 32 63 62 61 ... 50 49 48] Input (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] Output (dstValueGm): [63 62 61 ... 2 1 0] Output (dstIndexGm): [63 62 61 ... 2 1 0]