Search

CN-121166069-B - Data ordering method, electronic device, storage medium and computer program product

CN121166069BCN 121166069 BCN121166069 BCN 121166069BCN-121166069-B

Abstract

The invention relates to the technical field of artificial intelligence and provides a data sorting method, electronic equipment, a storage medium and a computer program product, wherein the method comprises the steps of carrying out local sorting on data to be processed in parallel through a plurality of processing units of a parallel processor, acquiring partial data from the data to be processed by each processing unit in the plurality of processing units, sorting the acquired partial data by each processing unit, and selecting a preset number of data from the partial data as local target data; and carrying out one or more merging and sorting operations on the local target data acquired by each processing unit according to the data quantity of the data to be processed and the hardware resources of the parallel processor, and selecting a preset quantity of data from the data after merging and sorting as global target data. The method and the device avoid huge calculation cost caused by global ordering of all the data to be processed, and remarkably improve the efficiency and performance of TopK operation.

Inventors

  • Request for anonymity

Assignees

  • 上海壁仞科技股份有限公司

Dates

Publication Date
20260505
Application Date
20251119

Claims (10)

  1. 1. A method of ordering data, comprising: if the preset number is not the power of 2, the preset number is rounded up to be a minimum power of 2 which is greater than or equal to the preset number; The method comprises the steps of carrying out partial sequencing on data to be processed through a plurality of processing units of a parallel processor, wherein each processing unit acquires 2K data from the data to be processed, K is the preset quantity, carrying out ascending sequencing on the first K data in the 2K data, and carrying out descending sequencing on the last K data to obtain a double-tone sequence, and carrying out a comparison exchange stage in a complete double-tone merging network on the double-tone sequence so that the first K data in the double-tone sequence comprise K data with larger values in the whole sequence, and the last K data comprise K data with smaller values; And carrying out one or more merging and sorting operations on the local target data acquired by each processing unit according to the data quantity of the data to be processed and the hardware resources of the parallel processor, and selecting the data with the preset quantity from the data after merging and sorting as global target data.
  2. 2. The data sorting method according to claim 1, wherein the performing one or more merge sort operations on the local target data acquired by each processing unit according to the data amount of the data to be processed and the hardware resource of the parallel processor includes: Carrying out merging and sorting on local target data of each processing unit at a first merging level, and selecting the preset number of data from the data after merging and sorting; and selectively merging and sorting the data selected by the first merging level in a higher merging level according to the data quantity of the data to be processed and the hardware resources of the parallel processor, and selecting the preset quantity of data from the data after merging and sorting until the global target data is acquired.
  3. 3. The data ordering method of claim 2, wherein the merge hierarchy is determined based on the steps of: acquiring the upper limit of the processing data quantity of each level; And determining each level from the local ordering level to a certain level as the merging level when the data amount of the data to be processed is smaller than or equal to the upper limit of the processing data amount of the certain level.
  4. 4. A method of ordering data according to any one of claims 1 to 3, wherein the parallel processor is a graphics processor and the processing unit is a thread; the merge sort operation includes at least one of: merging and sorting local target data of a plurality of threads at a thread bundle level; merging and sorting data obtained by merging a plurality of thread bundles at a thread block level; and merging and sorting the data merged by the plurality of thread blocks at the device level.
  5. 5. The method for sorting data according to claim 1, wherein the step of continuing the sorting operation only on the K data having the larger value to obtain the local target data includes: Ascending sort is carried out on subsequences positioned at odd positions in a target sequence, descending sort is carried out on subsequences positioned at even positions, and the target sequence is a sequence formed by K data with larger values; and recursively executing double-key merging operation on each sub-sequence until the K data in each sub-sequence are arranged in ascending order or descending order, and taking the target sequence after the double-key merging operation as the local target data.
  6. 6. A method of ordering data according to any one of claims 1 to 3, wherein the partial ordering of the data to be processed by the plurality of processing units of the parallel processor in parallel, further comprises: Judging whether the preset quantity is the power of 2 or not; and if the preset number is not the power of 2, rounding the preset number upwards to be a power of 2 value which is greater than or equal to the minimum preset number.
  7. 7. The method of claim 6, wherein selecting the predetermined number of data from the merge-ordered data as global target data comprises: Selecting the rounded preset number of data from the data subjected to merging and sorting as initial target data; And selecting the data with the preset quantity which is ranked in front from the initial target data as the global target data.
  8. 8. An electronic device comprising a memory, a processor and a computer program stored on the memory and running on the processor, characterized in that the processor implements the data sorting method according to any of claims 1 to 7 when executing the computer program.
  9. 9. A non-transitory computer readable storage medium, on which a computer program is stored, characterized in that the computer program, when executed by a processor, implements the data sorting method according to any of claims 1 to 7.
  10. 10. A computer program product comprising a computer program which, when executed by a processor, implements the data sorting method according to any of claims 1 to 7.

Description

Data ordering method, electronic device, storage medium and computer program product Technical Field The present invention relates to the field of artificial intelligence, and in particular, to a data sorting method, an electronic device, a storage medium, and a computer program product. Background The TopK (top K values returned) operator is a common operator in data processing. The traditional TopK operator implementation method generally carries out global sorting on all data to be processed, and then selects the first K data from the sorting results as a final result, but the method carries out global sorting on all data under the condition of huge data volume and relatively smaller K value, and a large number of unnecessary sorting operations are included, so that the calculation efficiency is low, and the calculation resources are wasted. Disclosure of Invention The present invention provides a data sorting method, an electronic device, a storage medium and a computer program product, which are used for solving the defects existing in the related art. The invention provides a data sorting method, which comprises the following steps: The method comprises the steps that a plurality of processing units of a parallel processor are used for carrying out local ordering on data to be processed in parallel, each processing unit in the plurality of processing units obtains partial data from the data to be processed, and each processing unit orders the obtained partial data and selects a preset number of data from the partial data as local target data; And carrying out one or more merging and sorting operations on the local target data acquired by each processing unit according to the data quantity of the data to be processed and the hardware resources of the parallel processor, and selecting the data with the preset quantity from the data after merging and sorting as global target data. According to the data sorting method provided by the invention, the merging and sorting operation is performed on the local target data acquired by each processing unit for one or more times according to the data quantity of the data to be processed and the hardware resource of the parallel processor, and the method comprises the following steps: Carrying out merging and sorting on local target data of each processing unit at a first merging level, and selecting the preset number of data from the data after merging and sorting; and selectively merging and sorting the data selected by the first merging level in a higher merging level according to the data quantity of the data to be processed and the hardware resources of the parallel processor, and selecting the preset quantity of data from the data after merging and sorting until the global target data is acquired. According to the data sorting method provided by the invention, the merging level is determined based on the following steps: acquiring the upper limit of the processing data quantity of each level; And determining each level from the local ordering level to a certain level as the merging level when the data amount of the data to be processed is smaller than or equal to the upper limit of the processing data amount of the certain level. According to the data ordering method provided by the invention, the parallel processor is a graphic processor, and the processing unit is a thread; the merge sort operation includes at least one of: merging and sorting local target data of a plurality of threads at a thread bundle level; merging and sorting data obtained by merging a plurality of thread bundles at a thread block level; and merging and sorting the data merged by the plurality of thread blocks at the device level. According to the data sorting method provided by the invention, each processing unit in the plurality of processing units acquires partial data from the data to be processed, and each processing unit sorts the acquired partial data and selects a preset number of data from the partial data as local target data, and the method comprises the following steps: Each processing unit acquires 2K data from the data to be processed, wherein K is the preset number; the first K data in the 2K data are subjected to ascending sort, and the last K data are subjected to descending sort, so that a double-tone sequence is obtained; Performing double-tone merging operation on the double-tone sequence, and separating K data with larger values from K data with smaller values in the double-tone sequence; And continuing the sorting operation on the K data with larger values only to acquire the local target data. According to the data sorting method provided by the invention, the sorting operation is continued only for the K data with larger values, and the local target data is obtained, which comprises the following steps: Ascending sort is carried out on subsequences positioned at odd positions in a target sequence, descending sort is carried out on subsequences positioned at even