WO2022179023A1 - 一种排序装置及方法 - Google Patents

一种排序装置及方法 Download PDF

Info

Publication number
WO2022179023A1
WO2022179023A1 PCT/CN2021/103111 CN2021103111W WO2022179023A1 WO 2022179023 A1 WO2022179023 A1 WO 2022179023A1 CN 2021103111 W CN2021103111 W CN 2021103111W WO 2022179023 A1 WO2022179023 A1 WO 2022179023A1
Authority
WO
WIPO (PCT)
Prior art keywords
elements
heap
processor
value
fragment
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Ceased
Application number
PCT/CN2021/103111
Other languages
English (en)
French (fr)
Inventor
柯展
张军琛
王建辉
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Huawei Technologies Co Ltd
Original Assignee
Huawei Technologies Co Ltd
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Huawei Technologies Co Ltd filed Critical Huawei Technologies Co Ltd
Priority to EP21927455.2A priority Critical patent/EP4276623A4/en
Publication of WO2022179023A1 publication Critical patent/WO2022179023A1/zh
Priority to US18/454,081 priority patent/US20230393813A1/en
Anticipated expiration legal-status Critical
Ceased legal-status Critical Current

Links

Images

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
    • G06F7/22—Arrangements for sorting or merging computer data on continuous record carriers, e.g. tape, drum, disc
    • G06F7/24—Sorting, i.e. extracting data from one or more carriers, rearranging the data in numerical or other ordered sequence, and rerecording the sorted data on the original carrier or on a different carrier or set of carriers sorting methods in general
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for program control, e.g. control units
    • G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
    • G06F9/46—Multiprogramming arrangements
    • G06F9/50—Allocation of resources, e.g. of the central processing unit [CPU]
    • G06F9/5005—Allocation of resources, e.g. of the central processing unit [CPU] to service a request
    • G06F9/5027—Allocation of resources, e.g. of the central processing unit [CPU] to service a request the resource being a machine, e.g. CPUs, Servers, Terminals
    • G06F9/5038—Allocation of resources, e.g. of the central processing unit [CPU] to service a request the resource being a machine, e.g. CPUs, Servers, Terminals considering the execution order of a plurality of tasks, e.g. taking priority or time dependency constraints into consideration
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for program control, e.g. control units
    • G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
    • G06F9/46—Multiprogramming arrangements
    • G06F9/50—Allocation of resources, e.g. of the central processing unit [CPU]
    • G06F9/5005—Allocation of resources, e.g. of the central processing unit [CPU] to service a request
    • G06F9/5027—Allocation of resources, e.g. of the central processing unit [CPU] to service a request the resource being a machine, e.g. CPUs, Servers, Terminals
    • G06F9/5044—Allocation of resources, e.g. of the central processing unit [CPU] to service a request the resource being a machine, e.g. CPUs, Servers, Terminals considering hardware capabilities
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for program control, e.g. control units
    • G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
    • G06F9/46—Multiprogramming arrangements
    • G06F9/54—Interprogram communication
    • G06F9/544—Buffers; Shared memory; Pipes

Definitions

  • a sorting apparatus may be a functional module provided in a server or other equipment.
  • the functional module is, for example, a chip, or may also be a functional module in other forms.
  • the sorting means may include a hardware sorting unit and a processor. a hardware sorting unit, which can determine the fragmentation granularity of the multiple elements to be sorted, and determine the end value of each fragment in some or all of the M fragments obtained according to the fragmentation granularity, Each fragment includes N elements, where N is an integer greater than or equal to 2, and the end value is the maximum value or the minimum value.
  • the processor may determine K elements in the plurality of elements according to the end value of each slice in the partial or all slices, and the K elements are the maximum value or the highest value among the plurality of elements. The smallest element, K is a positive integer.
  • the hardware sorting unit is configured to determine the fragmentation granularity of multiple elements to be sorted by: reading a configuration file, where the configuration file includes information on the fragmentation granularity; Or, receiving an instruction from the processor, the instruction indicating the fragmentation granularity.
  • the hardware ordering unit determines the sharding granularity.
  • the fragmentation granularity can be determined by reading the configuration file, or the fragmentation granularity can also be determined by receiving an instruction, which is more flexible.
  • the terminal value is the maximum value
  • the K elements are the element with the largest value among the plurality of elements.
  • the method further includes: in the case that the end value of the first fragment is less than or equal to the top element of the binary heap, the processor does not put the first fragment into the binary heap, the The first slice is one of the partial or all slices.
  • a data can correspond to a feature vector. If you want to retrieve or cluster a data, you can calculate the feature distance between the feature vector of the data and each feature vector in the vector library to obtain multiple feature distances, and then use Multiple feature distances are sorted to obtain K feature distances with the largest value or the smallest value, so that the meaning or category of the data can be further determined according to the K feature distances.
  • the sequence can be constructed as a binary heap, which can be referred to FIG. 4A.
  • Each node in the binary heap can be numbered by layer, for example, node 7 at the top of the heap is numbered 0, node 3 at the second layer is numbered 1, node 8 at the second layer is numbered 2, and node 8 at the third layer is numbered 2.
  • Node 5 is numbered 3, node 1 of the third layer is numbered 4, and node 2 of the third layer is numbered 5. If you want to get an ascending sequence, use a large top heap, and if you want to get a descending sequence, use a small top heap. Next, take the sequence obtained in ascending order as an example to introduce the sorting process of the large top heap.
  • the fragmentation granularity is related to the number of comparisons performed by the processor 502 . If the shard granularity is large, if the processor 502 determines not to put a shard into the binary heap, because the shard granularity is large, the shard includes more elements, so the processing can be reduced to a greater extent The number of elements that the processor 502 needs to compare can improve the efficiency of the processor 502 and save power consumption. However, if the granularity of the shard is too large, a shard will contain many elements.

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • General Engineering & Computer Science (AREA)
  • Software Systems (AREA)
  • Physics & Mathematics (AREA)
  • General Physics & Mathematics (AREA)
  • Computer Hardware Design (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
  • Management, Administration, Business Operations System, And Electronic Commerce (AREA)

Abstract

本申请涉及一种排序装置及方法。排序装置包括硬件排序单元和处理器，硬件排序单元，用于确定待排序的多个元素的分片粒度，以及，确定根据所述分片粒度所获得的M个分片中的部分或全部分片中的每个分片的端值。处理器，用于根据所述部分或全部分片中的每个分片的端值，确定所述多个元素中的K个元素，所述K个元素为所述多个元素中取值最大或最小的元素。硬件排序单元分担了处理器的部分任务，处理器无需参与整个排序过程，相较于由处理器单独执行排序的方式来说效率较高。

Description

一种排序装置及方法
本申请要求在2021年02月25日提交中国国家知识产权局、申请号为202110209778.3、申请名称为“一种排序方法及装置”的中国专利申请的优先权，以及于2021年3月25日提交中国专利局、申请号为202110321985.8、申请名称为“一种排序装置及方法”的中国专利申请的优先权，其全部内容通过引用结合在本申请中。
技术领域
本申请涉及通信技术领域，尤其涉及一种排序装置及方法。
背景技术
随着科技不断发展，信息量不断暴增。为了在海量数据中查找有效信息，对数据的特征进行检索或聚类的需求越来越迫切。对数据的特征进行检索，能够确定该特征的含义，对数据的特征进行聚类，能够确定该数据的类别。对特征进行检索或聚类等过程，一般包含特征距离的计算过程和前(Top)K特征距离的排序过程。特征距离的计算，主要是计算待查询的特征向量与向量库中的特征向量之间的特征距离，TopK特征距离的排序，是指通过排序，确定计算得到的特征距离中的前K个特征距离，根据前K个特征距离可以确定待查询的特征向量的含义或类型等。
其中，对于TopK特征距离的排序过程，目前一般是采用中央处理器(central processing unit，CPU)等通用处理器完成，或者通过多核处理器采用多核并行的方式完成。如果由通用处理器完成，则由于通用处理器只能串行处理，且通用处理器除了执行排序任务外还可能执行其他多种任务，因此排序过程的效率较低；而如果由多核处理器并行完成，则功耗较高。可见，TopK特征距离的排序过程已经成为了检索或聚类等过程的瓶颈。
发明内容
本申请实施例提供一种排序装置及方法，用于提高排序效率，且降低功耗。
第一方面，提供一种排序装置，该排序装置可以是设置在服务器或其他设备中的功能模块，该功能模块例如为芯片，或者也可以是其他形式的功能模块。该排序装置可包括硬件排序单元和处理器。硬件排序单元，可确定待排序的多个元素的分片粒度，以及，确定根据所述分片粒度所获得的M个分片中的部分或全部分片中的每个分片的端值，其中每个分片包括N个元素，N为大于或等于2的整数，所述端值为最大值或最小值。处理器，可根据所述部分或全部分片中的每个分片的端值，确定所述多个元素中的K个元素，所述K个元素为所述多个元素中取值最大或最小的元素，K为正整数。
本申请实施例提供的排序装置可包括硬件排序单元和处理器，硬件排序单元可以获得M个分片，分别获得各个分片的端值，处理器再根据分片的端值来确定K个元素。相当于由硬 件排序单元分担了处理器的部分任务，处理器无需参与整个排序过程，相较于由处理器单独执行排序的方式来说效率较高。而且本申请实施例也无需通过多核处理器来完成，能够降低设备的功耗。
在一种可选的实施方式中，所述硬件排序单元用于通过如下方式确定待排序的多个元素的分片粒度：读取配置文件，所述配置文件包括所述分片粒度的信息；或，接收来自所述处理器的指令，所述指令用于指示所述分片粒度。硬件排序单元要确定分片粒度，可以有多种方式。例如可通过读取配置文件来确定分片粒度，或者也可通过接收指令来确定分片粒度，较为灵活。
在一种可选的实施方式中，所述端值为最大值，所述K个元素为所述多个元素中取值最大的元素。所述处理器，还用于在第一分片的端值大于二叉堆的堆顶元素的情况下，确定所述第一分片包括的部分或全部元素中的每个元素是否大于所述堆顶元素，其中，如果一个元素大于所述堆顶元素，则将所述一个元素放入所述二叉堆，如果一个元素小于或等于所述堆顶元素，则不将所述一个元素放入所述二叉堆，所述第一分片为所述部分或全部分片中的一个。如果第一分片的端值大于该二叉堆的堆顶元素，表明第一分片中可能有元素符合“要选择K个取值最大的元素”这一目标，因此，处理器可将第一分片所包括的部分或全部元素中的每个元素与该二叉堆的堆顶元素比较，以确定这些元素是否能放入二叉堆。例如，如果第一分片中的元素A大于与元素A比较的堆顶元素，则处理器可将元素A放入该二叉堆，而如果第一分片中的元素A小于或等于与元素A比较的堆顶元素，因为要获得的是K个取值最大的元素，而如果元素A小于或等于小顶堆的堆顶元素，表明元素A不能满足要获得K个取值最大的元素这一要求，因此处理器可不将元素A放入该二叉堆，而继续比较第一分片中的下一个元素。
在一种可选的实施方式中，所述端值为最大值，所述K个元素为所述多个元素中取值最大的元素。所述处理器，还用于在第一分片的端值小于或等于二叉堆的堆顶元素的情况下，不将所述第一分片放入所述二叉堆，所述第一分片为所述部分或全部分片中的一个。因为要获得的是K个取值最大的元素，而如果第一分片的最大值都比二叉堆的堆顶元素要小，或者等于二叉堆的堆顶元素，表明第一分片中没有元素能够满足要获得K个取值最大的元素这一要求，因此处理器不必再考虑第一分片。通过这种方式，处理器可以减少参与比较的元素的数量，从而能够提高处理效率，也能节省处理器的功耗。
在一种可选的实施方式中，所述端值为最小值，所述K个元素为所述多个元素中取值最小的元素。所述处理器，还用于在第一分片的端值小于二叉堆的堆顶元素的情况下，确定所述第一分片包括的部分或全部元素中的每个元素是否小于所述堆顶元素，其中，如果一个元素小于所述堆顶元素，则将所述一个元素放入所述二叉堆，如果一个元素大于或等于所述堆顶元素，则不将所述一个元素放入所述二叉堆，所述第一分片为所述部分或全部分片中的一个。如果第一分片的端值小于该二叉堆的堆顶元素，表明第一分片中可能有元素符合“要选择K个取值最小的元素”这一目标，因此，处理器可将第一分片所包括的部分或全部元素中的每个元素与该二叉堆的堆顶元素比较，以确定这些元素是否能放入二叉堆。例如，如果第一分片中的元素A小于与元素A比较的堆顶元素，则处理器可将元素A放入该二叉堆，而如果第一分片中的元素A大于或等于与元素A比较的堆顶元素，因为要获得的是K个取值最小的元素，而如果元素A大于或等于小顶堆的堆顶元素，表明元素A不能满足要获得K个取值最小的元素这一要求，因此处理器可不将元素A放入该二叉堆，而继续比较第一分片中的下 一个元素。
在一种可选的实施方式中，所述端值为最小值，所述K个元素为所述多个元素中取值最小的元素。所述处理器，还用于在第一分片的端值大于或等于二叉堆的堆顶元素的情况下，不将所述第一分片放入所述二叉堆，所述第一分片为所述部分或全部分片中的一个。因为要获得的是K个取值最小的元素，而如果第一分片的最小值都比二叉堆的堆顶元素要大，或者等于二叉堆的堆顶元素，表明第一分片中没有元素能够满足要获得K个取值最小的元素这一要求，因此处理器不必再考虑第一分片。通过这种方式，处理器可以减少参与比较的元素的数量，从而能够提高处理效率，也能节省处理器的功耗。
在一种可选的实施方式中，所述处理器，还用于按照二叉堆方式将所述K个元素进行排序。处理器可再对该二叉堆包括的K个元素进行排序，也就是说，可以再对该二叉堆进行调整，使得该二叉堆满足规则，在调整完毕后处理器可得到升序序列或降序序列，例如处理器可以输出所得到的序列。或者，因为目的就是要得到Top K个最小值或最大值，而该二叉堆包括的就是Top K个最小值或最大值，因此处理器可以无需再对该二叉堆包括的K个元素进行排序，而是输出该二叉堆包括的K个元素即可。
在一种可选的实施方式中，所述硬件排序单元为AI处理芯片，或，所述硬件排序单元包括AI处理芯片中的一个或多个功能模块。除此之外，硬件排序单元也可以通过其他方式实现。
第二方面，提供一种排序方法，该排序方法可通过第一方面所述的排序装置来执行。该方法可包括：排序装置中的硬件排序单元确定待排序的多个元素的分片粒度，其中每个分片包括N个元素，N为大于或等于2的整数；所述硬件排序单元确定根据所述分片粒度所获得的M个分片中的部分或全部分片中的每个分片的端值，所述端值为最大值或最小值；所述排序装置中的处理器根据所述部分或全部分片中的每个分片的端值，确定所述多个元素中的K个元素，所述K个元素为所述多个元素中取值最大或最小的元素，K为正整数。
在一种可选的实施方式中，所述硬件排序单元确定待排序的多个元素的分片粒度，包括：所述硬件排序单元读取配置文件，所述配置文件包括所述分片粒度的信息；或，所述硬件排序单元接收来自所述处理器的指令，所述指令用于指示所述分片粒度。
在一种可选的实施方式中，所述端值为最大值，所述K个元素为所述多个元素中取值最大的元素。所述方法还包括：在第一分片的端值大于二叉堆的堆顶元素的情况下，所述处理器确定所述第一分片包括的部分或全部元素中的每个元素是否大于所述堆顶元素，其中，如果一个元素大于所述堆顶元素，则将所述一个元素放入所述二叉堆，如果一个元素小于或等于所述堆顶元素，则不将所述一个元素放入所述二叉堆，所述第一分片为所述部分或全部分片中的一个。
在一种可选的实施方式中，所述端值为最大值，所述K个元素为所述多个元素中取值最大的元素。所述方法还包括：在第一分片的端值小于或等于二叉堆的堆顶元素的情况下，所述处理器不将所述第一分片放入所述二叉堆，所述第一分片为所述部分或全部分片中的一个。
在一种可选的实施方式中，所述端值为最小值，所述K个元素为所述多个元素中取值最小的元素。所述方法还包括：在第一分片的端值小于二叉堆的堆顶元素的情况下，所述处理器确定所述第一分片包括的部分或全部元素中的每个元素是否小于所述堆顶元素，其中，如果一个元素小于所述堆顶元素，则将所述一个元素放入所述二叉堆，如果一个元素大于或等 于所述堆顶元素，则不将所述一个元素放入所述二叉堆，所述第一分片为所述部分或全部分片中的一个。
在一种可选的实施方式中，所述端值为最小值，所述K个元素为所述多个元素中取值最小的元素。所述方法还包括：在第一分片的端值大于或等于二叉堆的堆顶元素的情况下，所述处理器不将所述第一分片放入所述二叉堆，所述第一分片为所述部分或全部分片中的一个。
在一种可选的实施方式中，所述方法还包括：所述处理器按照二叉堆方式将所述K个元素进行排序。
在一种可选的实施方式中，所述硬件排序单元为AI处理芯片，或，所述硬件排序单元包括AI处理芯片中的一个或多个功能模块。
关于第二方面或各种可选的实施方式所带来的技术效果，可参考对于第一方面或相应的实施方式的技术效果的介绍。
附图说明
图1为多处理单元的示意图；
图2为双调排序的示意图；
图3为通用处理器的示意图；
图4A～图4E为通过大顶堆进行排序的示意图；
图5为本申请实施例提供的一种排序装置的结构示意图；
图6为本申请实施例提供的一种排序方法的流程图。
具体实施方式
为了使本申请实施例的目的、技术方案和优点更加清楚，下面将结合附图对本申请实施例作进一步地详细描述。
首先介绍本申请实施例涉及的技术术语。
特征距离，例如两个特征向量之间的欧式距离就认为是这两个特征向量之间的特征距离。例如一个特征向量为(q 1，q 2，……，q n)，另一个特征向量为(p 1，p 2，……，p n)，则这两个特征向量之间的欧式距离可通过如下方式计算：
Figure PCTCN2021103111-appb-000001
对公式1化简可得：
Figure PCTCN2021103111-appb-000002
其中，||x||表示x的范数。
一个数据可以对应一个特征向量，如果要对一个数据进行检索或聚类，则可以计算该数据的特征向量与向量库中的每个特征向量之间的特征距离，得到多个特征距离，再将多个特征距离进行排序，得到取值最大或取值最小的K个特征距离，从而根据K个特征距离可以进一步确定该数据的含义或类别等。
下面介绍本申请实施例涉及的技术特征。
目前的排序算法有多种。在图形处理器(graphics processing unit，GPU)或现场可 编程门阵列(field－programmable gate array，FPGA)等加速芯片上，一般采用多核排序算法，例如可参考图1，为多个处理单元的示意图，多个处理单元就表示多核，图1中外面的框，表示该多个处理单元所在的设备。多核排序算法就是利用多核(或者说，多个处理单元)并行计算的方式来实现排序。一种多核排序算法例如为双调排序，双调排序算法使得对数据的比较顺序与数据无关，可以充分利用多核的优势，下面介绍双调排序算法。
初始时可构建一个双调序列，该双调序列的长度例如为N，前
Figure PCTCN2021103111-appb-000003
个元素为升序排列，后
Figure PCTCN2021103111-appb-000004
个元素为降序排列。将前
Figure PCTCN2021103111-appb-000005
个元素与后
Figure PCTCN2021103111-appb-000006
个元素进行比较，比较方式为，将前
Figure PCTCN2021103111-appb-000007
个元素中的第i个元素与后
Figure PCTCN2021103111-appb-000008
个元素中的第i个元素比较，如果前
Figure PCTCN2021103111-appb-000009
个元素中的第i个元素小于或等于后
Figure PCTCN2021103111-appb-000010
个元素中的第i个元素，则不作处理，而如果前
Figure PCTCN2021103111-appb-000011
个元素中的第i个元素大于后
Figure PCTCN2021103111-appb-000012
个元素中的第i个元素，则将前
Figure PCTCN2021103111-appb-000013
个元素中的第i个元素与后
Figure PCTCN2021103111-appb-000014
个元素中的第i个元素互换位置。在将前
Figure PCTCN2021103111-appb-000015
个元素与后
Figure PCTCN2021103111-appb-000016
个元素比较完毕后，将前
Figure PCTCN2021103111-appb-000017
个元素从中间拆分为两部分，每个部分包括
Figure PCTCN2021103111-appb-000018
个元素，以及，将后
Figure PCTCN2021103111-appb-000019
个元素从中间拆分为两部分，每个部分也包括
Figure PCTCN2021103111-appb-000020
个元素，将前
Figure PCTCN2021103111-appb-000021
个元素拆分得到的两个部分进行比较，比较方式与上述方式相同，以及，将后
Figure PCTCN2021103111-appb-000022
个元素拆分得到的两个部分进行比较，比较方式与上述方式相同。在比较完毕后，再将包括
Figure PCTCN2021103111-appb-000023
个元素的4个部分中的每个部分从中间再拆分为两个部分，以此类推，直到拆分得到的每个部分包括两个元素时，拆分过程结束，得到最终的排序结果，最终的排序结果为升序。如果想得到降序的结果，则将元素进行比较时互换位置的依据改为：如果前面的元素大于或等于后面的元素，则不作处理，而如果前面的元素小于后面的元素，则二者互换位置，其他过程都与升序的排列过程相同。
可参考图2，为双调排序算法的一种示意图。参与排序的序列中可能包括多个元素，图2只表示了其中的部分元素，因此图2的虚线框就表示未画出的元素。图2中的第1行表示初始时的双调序列，该双调序列包括两个部分，图2中的“9”和“0”之间就是这两部分的分界点，“9”属于第一部分，“0”属于第二部分。第1行下面的线条，就表示将第一部分的元素与第二部分的元素进行比较，其中的一条线所指向的两个元素，就是相比较的两个元素，例如“9”和“0”就是一对相比较的元素，“8”和“3”是另一对相比较的元素。在比较完毕后，将第一部分再划分为两个部分，以及将第二部分也划分为两个部分，再将第一部分包括的两个部分进行比较，以及将第二部分包括的两个部分比较，可参考图2的第2行，第2行下面的线条也就表示相互比较的两个元素，以此类推。图2的第5行，就表示最终排序后的序列。
而在CPU或一些专用集成电路(application-specific integrated circuit，ASIC)设备上，由于计算核心较少，使用多核排序算法的优势较小，因此一般会使用二叉堆排序算法。二叉堆是一种非线性结构，可以将二叉堆看做一个数组，或者看做一个完全二叉树，通俗来讲，二叉堆就是利用完全二叉树的结构维护的一维数据。二叉堆可分为大顶堆和小顶堆， 大顶堆中每个节点的取值都大于或等于该节点的左右子节点的取值，小顶堆中每个节点的取值都小于或等于该节点的左右子节点的取值。可参考图3，为通用处理器的示意图，图3中外面的框，表示该通用处理器所在的设备。与图1相比可以看到，图3少了很多处理单元。下面简单介绍二叉堆排序算法的排序过程，在下面的介绍过程中，以大顶堆为例。
二叉堆排序的基本思想为，将待排序的序列构造为一个大顶堆，此时，整个序列的最大值就是堆顶的根节点的取值。将堆顶的根节点的取值与堆末尾的节点的取值进行交换，此时堆末尾的节点就为最大值。再将剩余的n-1个元素重新构造为一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列。为了便于理解，下面通过一个具体的示例来介绍大顶堆的排序过程。
例如有一个待排序的序列，该序列为{7,3,8,5,1,2}，该序列此时是无序的。可将该序列构造为一个二叉堆，该二叉堆可参考图4A。可将该二叉堆中的各个节点按层进行编号，例如堆顶的节点7，编号为0，第二层的节点3编号为1，第二层的节点8编号为2，第三层的节点5编号为3，第三层的节点1编号为4，第三层的节点2编号为5。如果要得到升序的序列，就采用大顶堆，如果要得到降序的序列，就使用小顶堆。接下来以得到升序的序列为例，介绍大顶堆的排序过程。
先找到二叉堆的最后一个非叶子节点，例如二叉堆的最后一个非叶子节点的编号通过如下方式确定：
Figure PCTCN2021103111-appb-000024
序列{7,3,8,5,1,2}的长度为6，那么图4A所示的二叉堆的最后一个非叶子节点的编号就是2，在图4A所示的二叉堆中，编号为2的节点的取值为8。接着将编号为2的节点的取值与该节点左右的子节点的取值进行比较，如果该节点的取值小于该节点的子节点的取值，则将该节点的取值与该节点的子节点的取值进行交换。这样操作的目的是将该节点和该节点的子节点中最大的取值放到该节点。对于图4A中编号为2的节点，取值为8，该节点只有左边的子节点(即，编号为5的节点)，该子节点的取值为2，不需要交换取值。
接着，继续找到该二叉堆的下一个非叶子节点，寻找方式例如为将当前的编号减1，得到的就是下一个非叶子节点的编号。在图4A所示的二叉堆中，编号为1的节点的取值为3，该节点的取值小于该节点的左边的子节点(即，编号为3的节点)的取值，则将该节点的取值与该节点的左边的子节点的取值进行交换，交换后编号为1的节点的取值为5，编号为3的节点的取值为3。交换后编号为1的节点的取值大于该节点的右边的子节点(即，编号为4的节点)的取值，不需要交换。可参考图4B，为经过这步处理后的二叉堆的示意图。
下一步，继续找到下一个非叶子节点，寻找方式与上述方式相同。下一个非叶子节点为编号为0的节点，该节点的取值为7，大于该节点的左边的子节点(即，编号为1的节点)的取值，不需要交换。而该节点的取值小于该节点的右边的子节点(即，编号为2的节点)的取值，则将该节点的取值与该节点的右边的子节点的取值进行交换，交换后，编号为0的节点的取值为8，编号为2的节点的取值为7。可参考图4C，为经过这步处理后的二叉堆的示意图。
接着，将堆顶的根节点(编号为0的节点)与堆中的最后一个节点(编号为5的节点)的取值交换(可理解为，将最大元素"沉"到数组末端)，交换后编号为0的节点的取值为2， 编号为5的取值为8。可参考图4D，为经过这步处理后的二叉堆的示意图。此时该堆中的最大元素就实现了归位。之后，对除了编号为5的节点外的剩余的5个节点，继续重复上述排序操作。由于排序过程都是类似的，因此不再多赘述。在排序结束后可得到升序的序列，该升序的序列为{1,2,3,5,7,8}，对应的二叉堆可参考图4E。
根据前述介绍可知，对于TopK元素的排序过程，目前一般是采用CPU等通用处理器完成，或者通过多核处理器采用多核并行的方式完成。如果由通用处理器完成，则需要占用通用处理器的资源，且由于通用处理器除了执行排序任务外还可能执行其他多种任务，因此排序过程的效率较低；而如果由多核处理器并行完成，则功耗较高。可见，TopK特征距离的排序过程已经成为了检索或聚类等过程的瓶颈。
鉴于此，提供本申请实施例的技术方案。本申请实施例提供的排序装置可包括硬件排序单元和处理器，硬件排序单元可以获得M个分片，分别获得各个分片的端值，处理器再根据分片的端值来确定K个元素。相当于由硬件排序单元分担了处理器的部分任务，处理器无需参与整个排序过程，相较于由处理器单独执行排序的方式来说效率较高。而且本申请实施例也无需通过多核处理器来完成，能够降低设备的功耗。
下面结合附图介绍本申请实施例提供的技术方案。
本申请实施例提供一种排序装置，该排序装置可以是设置在服务器或其他设备中的功能模块，该功能模块例如为芯片，或者也可以是其他形式的功能模块。可参考图5，为本申请实施例提供的排序装置的一种结构示意图。该排序装置可包括至少一个硬件排序单元501和处理器502。其中，名称并不构成对于特征的限制，例如硬件排序单元也可以有其他名称，例如称为排序单元等。
硬件排序单元501例如为人工智能(artificial intelligence，AI)处理芯片，或者，硬件排序单元例如为AI处理芯片中的一个或多个功能模块，或者，硬件排序单元501也可以有其他的实现方式。该排序装置可包括至少一个硬件排序单元501，如果包括多个硬件排序单元501，那么待排序的元素可分别输入多个硬件排序单元501，每个硬件排序单元501需要处理的分片有所减少，且多个硬件排序单元501可以并行处理，能够提高处理效率。而如果该排序装置包括一个硬件排序单元501，则能够简化该排序装置的结构。在本申请实施例的介绍过程中，以该排序装置包括一个硬件排序单元501为例，如果该排序装置包括多个硬件排序单元501，则每个硬件排序单元501的处理过程都与该排序装置包括一个硬件排序单元501时该硬件排序单元501的处理过程是类似的。
在本申请实施例中，处理器502例如为GPU、嵌入式神经网络处理器(neural-network process units，NPU)、通用处理器、数字信号处理器、专用集成电路、现场可编程门阵列或者其他可编程逻辑器件、分立门或者晶体管逻辑器件、分立硬件组件，或者也可以是这些器件内的功能模块，可以实现或者执行本申请实施例中的公开的各方法、步骤及逻辑框图。通用处理器可以是CPU、微处理器或者任何常规的处理器等。结合本申请实施例所公开的方法的步骤可以直接体现为硬件处理器执行完成，或者用处理器中的硬件及软件模块组合执行完成。
硬件排序单元501与处理器502要交换数据，可通过共享内存的方式来实现。例如处理器502可申请内存，在申请成功后处理器502可将该内存地址发送给硬件排序单元501。硬件排序单元501如果有待传输给处理器502的数据，则可以存储在该内存中，处理器502通过读取该内存就能获得来自硬件排序单元501的数据。该内存可以属于处理器502，或者该 内存也可以是位于处理器502外部的存储空间。
在本申请实施例中，硬件排序单元501可以确定分片粒度，分片粒度用于指示一个分片最多能够包括的元素数量。例如分片粒度为N，表明一个分片最多包括N个元素，N为大于或等于2的整数。硬件排序单元501确定分片粒度后，可根据该分片粒度获得M个分片，并获得M个分片中的部分或全部分配中每个分片的端值。硬件排序单元501将获得的端值发送给处理器502(例如可通过共享内存的方式发送，或者可以通过其他方式发送)，处理器再根据这些端值确定待排序的元素中的K个取值最大的元素或K个取值最小的元素，K为正整数。可以理解为，硬件排序单元501可以执行排序过程中的部分操作，处理器502再执行排序过程中的剩余操作，从而通过硬件排序单元501和处理器502的合作能够获得Top K个元素。这样一来，硬件排序单元501分担了处理器502的部分任务，处理器502无需参与整个排序过程，相较于由处理器502单独执行排序的方式来说效率较高。而且本申请实施例也无需通过多核处理器来完成，能够降低设备的功耗。另外，硬件排序单元501例如为AI处理芯片，或为AI处理芯片中的一个或多个功能模块，也就是说，本申请实施例并不用额外增加新的硬件模块来作为硬件排序单元501，而是可以用设备中相应的芯片等模块来实现硬件排序单元501的功能，由此能够简化设备的结构。
硬件排序单元501确定分片粒度，可以有多种方式，下面举例介绍。
例如，硬件排序单元501可以读取配置文件，该配置文件可以配置在硬件排序单元501中，该配置文件可指示分片粒度，则硬件排序单元501通过读取配置文件就能确定分片粒度。又例如，处理器502可以确定分片粒度，且处理器502可向硬件排序单元发送指令，该指令可指示分片粒度，硬件排序单元501接收该指令后，就能确定分片粒度。再例如，待排序的元素对应于该排序装置所在的设备中的第一应用(APP)，也就是说，第一应用对应多个元素，这多个元素需要排序，则第一应用可以向硬件排序单元501发送指令，该指令可指示分片粒度，硬件排序单元501接收该指令后，就能确定分片粒度。例如分片粒度与业务相关，例如，如果该业务涉及的待排序的元素较多，则分片粒度可以较大。例如第一应用为购物APP，购物APP对应的多个元素为与物品A类似的多个物品的信息，对这多个物品的信息进行排序是为了确定与物品A最为类似的K个物品。分片粒度可由该购物APP确定，且该购物APP可将分片粒度的信息发送给硬件排序单元501。或者，除了如上方式之外，硬件排序单元501还可以通过其他方式来确定分片粒度，本申请实施例不做限制。
如果有待排序的元素，则待排序的元素会进入硬件排序单元501。硬件排序单元501确定分片粒度后，可以根据分片粒度获得M个分片，M个分片中的每个分片可包括一个或多个元素，M为正整数。例如，待排序的元素可能是逐渐输入到硬件排序单元501，那么每到来一个元素，硬件排序单元501就将该元素放入一个分片。如果一个分片包括的元素数量已达到了分片粒度指示的数量，则如果再有下一个元素到来，硬件排序单元501就会将下一个元素放入下一个分片，而不会再放入该分片。以此类推，硬件排序单元501可将待排序的元素放入M个分片中。其中，对于M个分片中的最后一个分片，该分片包括的元素的数量可能等于N，也可能小于N；而对于M个分片中除了最后一个分片外的其他分片，其中的一个分片包括的元素的数量可能等于N。N为分片粒度，或者说，N为分片粒度所指示的数量。例如，分片粒度为5，待排序的元素共38个，则硬件排序单元501可得到8个分片，这8个分片中的前7个分片中的每个分片可包括5个元素，这8个分片中的最后一个分片可包括3个元素。又例如，分片粒度为5，待排序的元素共40个，则硬件排序单元501可得到8个分片，这8 个分片中的每个分片都包括5个元素。
在获得M个分片后，硬件排序单元501可获得M个分片中的部分或全部分片中的每个分片的端值，从而硬件排序单元501共可获得一个或多个端值。其中，一个分片的端值可以是指该分片所包括的元素的最大值，或者是指该分片所包括的元素的最小值。究竟硬件排序单元501获得的是分片的最大值还是最小值，取决于排序需求。例如，如果需要获得的是Top K个最大值，那么硬件排序单元501获得的就是分片的最大值，而如果需要获得的是Top K个最小值，那么硬件排序单元501获得的就是分片的最小值。硬件排序单元501要获得一个分片的端值，例如将该分片所包括的各个元素进行比较，以通过比较的方式找到该分片的端值。又例如，硬件排序单元501也可以将该分片所包括的元素进行排序，以获得该分片的端值。硬件排序单元501对一个分片包括的元素进行排序，例如可采用二叉堆的排序方法，或者也可采用其他排序方法，本申请实施例不做限制。或者，硬件排序单元501也可以通过其他方式来获得分片的端值。在获得M个分片中的部分或全部分片中的每个分片的端值后，硬件排序单元501可将获得的端值发送给处理器502。例如，硬件排序单元501将获得的端值放入共享内存，处理器502通过读取该共享内存就可以获得这些端值。
其中，硬件排序单元501获得M个分片的时间可能不同，硬件排序单元501可以在获得M个分片后再确定M个分片中的部分或全部分片中的每个分片的端值，或者，硬件排序单元501每获得一个分片，就可以确定该分片的端值。如果硬件排序单元501是一并获得M个分片中的部分或全部分片中的每个分片的端值，则硬件排序单元501可将获得的一个或多个端值一并发送给处理器502。或者，如果硬件排序单元501每获得一个分片，就可以确定该分片的端值，则硬件排序单元501可以每获得一个端值，就将该端值发送给处理器502，从而处理器502可以与硬件排序单元501并行处理，以提高处理效率；或者，硬件排序单元501也可以在获得全部端值后，再将获得的端值发送给处理器502，从而减少硬件排序单元501与处理器501的交互次数。
处理器502在获得来自硬件排序单元501的一个或多个端值后，可根据这一个或多个端值来确定待排序的多个元素中的K个元素，这K个元素就是待排序的多个元素中的Top K个元素，也就是说，这K个元素可以是待排序的多个元素中取值最大的K个元素，或者是待排序的多个元素中取值最小的K个元素。下面介绍处理器502获得K个元素的方式。因为K个元素可能是待排序的多个元素中取值最大的K个元素，也可能是待排序的多个元素中取值最小的K个元素，因此下面对这两种情况分别介绍。
1、K个元素可能是待排序的多个元素中取值最大的K个元素。在这种情况下，硬件排序单元501所获得的端值也是分片的最大值。
要获得Top K个取值最大的元素，可借助于小顶堆来实现。例如处理器502可先根据预设的元素构造小顶堆。该小顶堆的堆顶元素(可理解为前述二叉堆示例中的堆顶根节点)的取值是整个堆的最小值，该小顶堆所包括的元素的数量可以等于K。
例如处理器502获得了M个分片中的第一分片的端值，则处理器502可将第一分片的端值与处理器502当前维护的小顶堆的堆顶元素进行比较，如果第一分片的端值大于该小顶堆的堆顶元素，则处理器502可分别确定第一分片所包括的部分或全部元素中的每个元素是否大于该小顶堆的堆顶元素，也就是说，处理器502可将第一分片所包括的部分或全部元素中的每个元素与该小顶堆的堆顶元素比较，如果第一分片中的元素A大于与元素A比较的堆顶元素，则将元素A放入该小顶堆，而如果第一分片中的元素A小于或等于与元素A比较的堆 顶元素，因为要获得的是K个取值最大的元素，而如果元素A小于或等于小顶堆的堆顶元素，表明元素A不能满足要获得K个取值最大的元素这一要求，因此处理器502可不将元素A放入该小顶堆，而继续比较第一分片中的下一个元素。在比较时，处理器502可将第一分片的端值放到最后与该小顶堆的堆顶元素比较。本申请实施例所述的将元素进行比较，可理解为将元素的取值进行比较，或者元素本身就是数值，则就是将元素本身进行比较。
例如处理器502当前维护的是小顶堆A，处理器502在获得第一分片的端值后，将第一分片的端值与小顶堆A的堆顶元素比较。如果第一分片的端值大于小顶堆A的堆顶元素，则处理器502确定第一分片所包括的元素A是否大于小顶堆A的堆顶元素。如果元素A小于或等于小顶堆A的堆顶元素，则处理器502不将元素A放入小顶堆A，而是继续比较第一分片所包括的其他元素；而如果元素A大于小顶堆A的堆顶元素，则处理器502用元素A替换小顶堆A的堆顶元素，相当于元素A变为新的堆顶元素，原堆顶元素被挤出堆，此时的小顶堆A也相当于发生了变更，例如将变更后的小顶堆A称为小顶堆B。在得到小顶堆B后，处理器502可将小顶堆B进行调整，使得小顶堆B满足小顶堆的规则，小顶堆的规则为，小顶堆中每个节点的取值都小于或等于该节点的左右子节点的取值，该调整过程可参考前文对于二叉堆排序过程的介绍。在小顶堆B满足小顶堆的规则后，小顶堆B的堆顶元素可能还是元素A，也可能不再是元素A。处理器502再确定第一分片所包括的元素B是否大于小顶堆B的堆顶元素，以此类推，比较过程都是类似的。在将第一分片所包括的部分或全部元素都比较完毕后，处理器502得到的小顶堆例如称为小顶堆C。
而如果第一分片的端值小于或等于小顶堆A的堆顶元素，则处理器502不将第一分片放入小顶堆A，或者说，处理器502不再将第一分片所包括的元素与小顶堆A的堆顶元素进行比较。因为要获得的是K个取值最大的元素，而如果第一分片的最大值都比小顶堆A的堆顶元素要小，或者等于小顶堆A的堆顶元素，表明第一分片中没有元素能够满足要获得K个取值最大的元素这一要求，因此处理器502不必再考虑第一分片。通过这种方式，处理器502可以减少参与比较的元素的数量，从而能够提高处理效率，也能节省处理器502的功耗。
如果处理器502获得了小顶堆C，则处理器502再将M个分片中的第二分片的端值与小顶堆C的堆顶元素比较；或者，如果处理器502未将第一分片放入小顶堆A，则处理器502此时维护的还是小顶堆A，则处理器502将M个分片中的第二分片的端值与小顶堆A的堆顶元素比较。具体的比较过程可参考将第一分片与小顶堆A进行比较的方式，不多赘述。
在处理器502将M个分片中的部分或全部分片都比较完毕后，就能够获得最终的小顶堆，该小顶堆所包括的就是待排序的多个元素中取值最大的K个元素，即，Top K个最大值。也就是说，通过上述过程，就获得了Top K个最大值。处理器502可再对该小顶堆包括的K个元素进行排序，也就是说，可以再对该小顶堆进行调整，使得该小顶堆满足小顶堆的规则，在调整完毕后处理器502可得到降序序列，例如处理器502可以输出所得到的序列。或者，因为目的就是要得到Top K个最大值，而该小顶堆包括的就是Top K个最大值，因此处理器502可以无需再对该小顶堆包括的K个元素进行排序，而是输出该小顶堆包括的K个元素即可。
2、K个元素可能是待排序的多个元素中取值最小的K个元素。在这种情况下，硬件排序单元501所获得的端值也是分片的最小值。
要获得Top K个取值最小的元素，可借助于大顶堆来实现。例如处理器502可先根据预设的元素构造大顶堆。该大顶堆的堆顶元素的取值是整个堆的最大值，该大顶堆所包括的元 素的数量可以等于K。
例如处理器502获得了M个分片中的第一分片的端值，则处理器502可将第一分片的端值与处理器502当前维护的大顶堆的堆顶元素进行比较，如果第一分片的端值小于该大顶堆的堆顶元素，则处理器502可分别确定第一分片所包括的部分或全部元素中的每个元素是否小于该大顶堆的堆顶元素，也就是说，处理器502可将第一分片所包括的部分或全部元素中的每个元素与该大顶堆的堆顶元素比较，如果第一分片中的元素A小于与元素A比较的堆顶元素，则将元素A放入该大顶堆，而如果第一分片中的元素A大于或等于与元素A比较的堆顶元素，则不将元素A放入该大顶堆，而继续比较第一分片中的下一个元素。在比较时，处理器502可将第一分片的端值放到最后与该大顶堆的堆顶元素比较。
例如处理器502当前维护的是大顶堆A，处理器502在获得第一分片的端值后，将第一分片的端值与大顶堆A的堆顶元素比较。如果第一分片的端值小于大顶堆A的堆顶元素，则处理器502确定第一分片所包括的元素A是否小于大顶堆A的堆顶元素。如果元素A大于或等于大顶堆A的堆顶元素，则处理器502不将元素A放入大顶堆A，而是继续比较第一分片所包括的其他元素；而如果元素A小于大顶堆A的堆顶元素，则处理器502用元素A替换大顶堆A的堆顶元素，相当于元素A变为新的堆顶元素，原堆顶元素被挤出堆，此时的大顶堆A也相当于发生了变更，例如将变更后的大顶堆A称为大顶堆B。在得到大顶堆B后，处理器502可将大顶堆B进行调整，使得大顶堆B满足大顶堆的规则，大顶堆的规则为，大顶堆中每个节点的取值都大于或等于该节点的左右子节点的取值，该调整过程可参考前文对于二叉堆排序过程的介绍。在大顶堆B满足大顶堆的规则后，大顶堆B的堆顶元素可能还是元素A，也可能不再是元素A。处理器502再确定第一分片所包括的元素B是否小于大顶堆B的堆顶元素，以此类推，比较过程都是类似的。在将第一分片所包括的部分或全部元素都比较完毕后，处理器502得到的大顶堆例如称为大顶堆C。
而如果第一分片的端值大于或等于大顶堆A的堆顶元素，则处理器502不将第一分片放入大顶堆A，或者说，处理器502不再将第一分片所包括的元素与大顶堆A的堆顶元素进行比较。因为要获得的是K个取值最小的元素，而如果第一分片的最小值都比大顶堆A的堆顶元素要大，或者等于大顶堆A的堆顶元素，表明第一分片中没有元素能够满足要获得K个取值最小的元素这一要求，因此处理器502不必再考虑第一分片。通过这种方式，处理器502可以减少参与比较的元素的数量，从而能够提高处理效率，也能节省处理器502的功耗。
如果处理器502获得了大顶堆C，则处理器502再将M个分片中的第二分片的端值与大顶堆C的堆顶元素比较；或者，如果处理器502未将第一分片放入大顶堆A，则处理器502此时维护的还是大顶堆A，则处理器502将M个分片中的第二分片的端值与大顶堆A的堆顶元素比较。具体的比较过程可参考将第一分片与大顶堆A进行比较的方式，不多赘述。
在处理器502将M个分片中的部分或全部分片都比较完毕后，就能够获得最终的大顶堆，该大顶堆所包括的就是待排序的多个元素中取值最小的K个元素，即，Top K个最小值。也就是说，通过上述过程，就获得了Top K个最小值。处理器502可再对该大顶堆包括的K个元素进行排序，也就是说，可以再对该大顶堆进行调整，使得该大顶堆满足大顶堆的规则，在调整完毕后处理器502可得到升序序列，例如处理器502可以输出所得到的序列。或者，因为目的就是要得到Top K个最小值，而该大顶堆包括的就是Top K个最小值，因此处理器502可以无需再对该大顶堆包括的K个元素进行排序，而是输出该大顶堆包括的K个元素即可。
可见，分片粒度与处理器502的比较次数有关。如果分片粒度较大，则处理器502如果确定不将一个分片放入二叉堆，则由于分片粒度较大，该分片包括的元素较多，因此可以在较大程度上减少处理器502需要比较的元素的数量，能够提高处理器502的效率，节省功耗。但如果分片粒度过大，则一个分片所包括的元素会很多，如果处理器502确定一个分片的端值符合放入二叉堆的要求，则处理器502需要将该分片里的每个元素与堆顶元素比较，而因为分片粒度过大，该分片里可能包括了很多并不符合放入二叉堆的要求的元素，但处理器502也需要这些元素都进行比较，增加了处理器502的工作量。如果分片粒度过小，则处理器502需要比较的元素的数量会增多，又不符合减轻处理器502的负担的需求。因此，无论是通过配置文件指示分片粒度，还是由上层应用来指示分片粒度，或者通过其他方式指示分片粒度，分片粒度都需要综合衡量，例如可根据待排序的元素的总数量和/或根据其他因素来确定分片粒度，以选取较为合适的数值作为分片粒度。
接下来请参考图6，介绍本申请实施例提供的一种排序方法，该排序方法例如可通过图5所示的排序装置实现。
S601、硬件排序单元501确定分片粒度。
S602、硬件排序单元501根据分片粒度获得M个分片，M个分片中的一个或多个分片中的每个分片包括N个元素。其中，S602为可选的步骤，在图6中用虚线表示。
S603、硬件排序单元确定M个分片中的部分或全部分片中每个分片的端值，所述端值为最大值或最小值。
S604、处理器502根据所述部分或全部分片中每个分片的端值，确定待排序的多个元素中的K个元素，K个元素为取值最大或最小的元素。
关于图6所示的实施例所涉及的各个步骤的细节，例如硬件排序单元501如何确定分片粒度，如何获得M个分片，如何确定分片的端值，如何将端值发送给处理器502，以及处理器502如何确定K个元素等过程，均可参考图5所示的实施例的介绍。
本申请实施例通过硬件排序单元501分担排序过程中的部分操作，可以减轻处理器502的负担，提高处理器502的处理效率。而且硬件排序单元501例如为AI处理芯片，或为AI处理芯片中的一个或多个功能模块，硬件排序单元501的处理时延较短，处理效率较高，由此能够进一步提高排序的效率。
本申请实施例提供了一种芯片系统，该芯片系统包括处理器，处理器可实现前述的处理器502和硬件排序单元501的功能。可选的，该芯片系统还可以包括存储器。该芯片系统可实现前述方法中排序装置的功能。该芯片系统可以由芯片构成，也可以包含芯片和其他分立器件。
本领域普通技术人员可以意识到，结合本文中所公开的实施例描述的各示例的单元及步骤，能够以电子硬件、或者计算机软件和电子硬件的结合来实现。这些功能究竟以硬件还是软件方式来执行，取决于技术方案的特定应用和设计约束条件。专业技术人员可以对每个特定的应用来使用不同方法来实现所描述的功能，但是这种实现不应认为超出本申请的范围。
在本申请所提供的几个实施例中，应该理解到，所揭露的系统、装置和方法，可以通过其它的方式实现。例如，以上所描述的装置实施例仅仅是示意性的，例如，所述单元的划分，仅仅为一种逻辑功能划分，作为分离部件说明的单元可以是或者也可以不是物理上分开的，作为单元显示的部件可以是或者也可以不是物理单元，即可以位于一个地方，或者也可以分布到多个网络单元上。可以根据实际的需要选择其中的部分或者全部单元来实现本实施例方 案的目的。
所述功能如果以软件功能单元的形式实现并作为独立的产品销售或使用时，可以存储在一个计算机可读取存储介质中。基于这样的理解，本申请的技术方案本质上或者说对现有技术做出贡献的部分或者该技术方案的部分可以以软件产品的形式体现出来，该计算机软件产品存储在一个存储介质中，包括若干指令用以使得一台计算机设备(可以是个人计算机，服务器，或者网络设备等)执行本申请各个实施例所述方法的全部或部分步骤。而前述的计算机可读存储介质，可以是计算机能够存取的任何可用介质。以此为例但不限于：计算机可读介质可以包括随机存取存储器(random access memory，RAM)、只读存储器(read-only memory，ROM)、可编程只读存储器(programmable ROM，PROM)、可擦除可编程只读存储器(erasable PROM，EPROM)、电可擦可编程只读存储器(electrically erasable programmable read only memory，EEPROM)、紧凑型光盘只读存储器(compact disc read-only memory，CD-ROM)、通用串行总线闪存盘(universal serial bus flash disk)、移动硬盘、或其他光盘存储、磁盘存储介质或者其他磁存储设备、或者能够用于携带或存储具有指令或数据结构形式的期望的程序代码并能够由计算机存取的任何其他介质。另外，通过示例性但不是限制性说明，许多形式的RAM可用，例如静态随机存取存储器(static RAM，SRAM)、动态随机存取存储器(dynamic RAM，DRAM)、同步动态随机存取存储器(synchronous DRAM，SDRAM)、双倍数据速率同步动态随机存取存储器(double data rate SDRAM，DDR SDRAM)、增强型同步动态随机存取存储器(enhanced SDRAM，ESDRAM)、同步连接动态随机存取存储器(synchlink DRAM，SLDRAM)或直接内存总线随机存取存储器(direct rambus RAM，DR RAM)。
以上所述，仅为本申请的具体实施方式，但本申请实施例的保护范围并不局限于此，任何熟悉本技术领域的技术人员在本申请实施例揭露的技术范围内，可轻易想到变化或替换，都应涵盖在本申请实施例的保护范围之内。因此，本申请实施例的保护范围应所述以权利要求的保护范围为准。

Claims (17)

  1. 一种排序装置，其特征在于，包括：
    硬件排序单元，用于确定待排序的多个元素的分片粒度，以及，确定根据所述分片粒度所获得的M个分片中的部分或全部分片中的每个分片的端值，其中每个分片包括N个元素，N为大于或等于2的整数，所述端值为最大值或最小值；
    处理器，用于根据所述部分或全部分片中的每个分片的端值，确定所述多个元素中的K个元素，所述K个元素为所述多个元素中取值最大或最小的元素，K为正整数。
  2. 根据权利要求1所述的装置，其特征在于，所述硬件排序单元用于通过如下方式确定待排序的多个元素的分片粒度：
    读取配置文件，所述配置文件包括所述分片粒度的信息；或，
    接收来自所述处理器的指令，所述指令用于指示所述分片粒度。
  3. 根据权利要求1或2所述的装置，其特征在于，所述端值为最大值，所述K个元素为所述多个元素中取值最大的元素；
    所述处理器，还用于在第一分片的端值大于二叉堆的堆顶元素的情况下，确定所述第一分片包括的部分或全部元素中的每个元素是否大于所述堆顶元素，其中，如果一个元素大于所述堆顶元素，则将所述一个元素放入所述二叉堆，如果一个元素小于或等于所述堆顶元素，则不将所述一个元素放入所述二叉堆，所述第一分片为所述部分或全部分片中的一个。
  4. 根据权利要求1～3任一项所述的装置，其特征在于，所述端值为最大值，所述K个元素为所述多个元素中取值最大的元素；
    所述处理器，还用于在第一分片的端值小于或等于二叉堆的堆顶元素的情况下，不将所述第一分片放入所述二叉堆，所述第一分片为所述部分或全部分片中的一个。
  5. 根据权利要求1～4任一项所述的装置，其特征在于，所述端值为最小值，所述K个元素为所述多个元素中取值最小的元素；
    所述处理器，还用于在第一分片的端值小于二叉堆的堆顶元素的情况下，确定所述第一分片包括的部分或全部元素中的每个元素是否小于所述堆顶元素，其中，如果一个元素小于所述堆顶元素，则将所述一个元素放入所述二叉堆，如果一个元素大于或等于所述堆顶元素，则不将所述一个元素放入所述二叉堆，所述第一分片为所述部分或全部分片中的一个。
  6. 根据权利要求1～5任一项所述的装置，其特征在于，所述端值为最小值，所述K个元素为所述多个元素中取值最小的元素；
    所述处理器，还用于在第一分片的端值大于或等于二叉堆的堆顶元素的情况下，不将所述第一分片放入所述二叉堆，所述第一分片为所述部分或全部分片中的一个。
  7. 根据权利要求1～6任一项所述的装置，其特征在于，
    所述处理器，还用于按照二叉堆方式将所述K个元素进行排序。
  8. 根据权利要求1～7任一项所述的装置，其特征在于，所述硬件排序单元为AI处理芯片，或，所述硬件排序单元包括AI处理芯片中的一个或多个功能模块。
  9. 一种排序方法，其特征在于，应用于排序装置，所述方法包括：
    所述排序装置中的硬件排序单元确定待排序的多个元素的分片粒度，其中每个分片包括N个元素，N为大于或等于2的整数；
    所述硬件排序单元确定根据所述分片粒度所获得的M个分片中的部分或全部分片中的每 个分片的端值，所述端值为最大值或最小值；
    所述排序装置中的处理器根据所述部分或全部分片中的每个分片的端值，确定所述多个元素中的K个元素，所述K个元素为所述多个元素中取值最大或最小的元素，K为正整数。
  10. 根据权利要求9所述的方法，其特征在于，所述硬件排序单元确定待排序的多个元素的分片粒度，包括：
    所述硬件排序单元读取配置文件，所述配置文件包括所述分片粒度的信息；或，
    所述硬件排序单元接收来自所述处理器的指令，所述指令用于指示所述分片粒度。
  11. 根据权利要求9或10所述的方法，其特征在于，所述端值为最大值，所述K个元素为所述多个元素中取值最大的元素，所述方法还包括：
    在第一分片的端值大于二叉堆的堆顶元素的情况下，所述处理器确定所述第一分片包括的部分或全部元素中的每个元素是否大于所述堆顶元素，其中，如果一个元素大于所述堆顶元素，则将所述一个元素放入所述二叉堆，如果一个元素小于或等于所述堆顶元素，则不将所述一个元素放入所述二叉堆，所述第一分片为所述部分或全部分片中的一个。
  12. 根据权利要求9～11任一项所述的方法，其特征在于，所述端值为最大值，所述K个元素为所述多个元素中取值最大的元素，所述方法还包括：
    在第一分片的端值小于或等于二叉堆的堆顶元素的情况下，所述处理器不将所述第一分片放入所述二叉堆，所述第一分片为所述部分或全部分片中的一个。
  13. 根据权利要求9～12任一项所述的方法，其特征在于，所述端值为最小值，所述K个元素为所述多个元素中取值最小的元素，所述方法还包括：
    在第一分片的端值小于二叉堆的堆顶元素的情况下，所述处理器确定所述第一分片包括的部分或全部元素中的每个元素是否小于所述堆顶元素，其中，如果一个元素小于所述堆顶元素，则将所述一个元素放入所述二叉堆，如果一个元素大于或等于所述堆顶元素，则不将所述一个元素放入所述二叉堆，所述第一分片为所述部分或全部分片中的一个。
  14. 根据权利要9～13任一项所述的方法，其特征在于，所述端值为最小值，所述K个元素为所述多个元素中取值最小的元素，所述方法还包括：
    在第一分片的端值大于或等于二叉堆的堆顶元素的情况下，所述处理器不将所述第一分片放入所述二叉堆，所述第一分片为所述部分或全部分片中的一个。
  15. 根据权利要求9～14任一项所述的方法，其特征在于，所述方法还包括：
    所述处理器按照二叉堆方式将所述K个元素进行排序。
  16. 根据权利要求9～15任一项所述的方法，其特征在于，所述硬件排序单元为AI处理芯片，或，所述硬件排序单元包括AI处理芯片中的一个或多个功能模块。
  17. 一种计算机可读存储介质，其特征在于，所述计算机可读存储介质用于存储计算机程序，当所述计算机程序在计算机上运行时，使得所述计算机执行如权利要求9～16中任一项所述的方法。
PCT/CN2021/103111 2021-02-25 2021-06-29 一种排序装置及方法 Ceased WO2022179023A1 (zh)

Priority Applications (2)

Application Number Priority Date Filing Date Title
EP21927455.2A EP4276623A4 (en) 2021-02-25 2021-06-29 SORTING DEVICE AND METHOD
US18/454,081 US20230393813A1 (en) 2021-02-25 2023-08-23 Sorting apparatus and method

Applications Claiming Priority (4)

Application Number Priority Date Filing Date Title
CN202110209778.3 2021-02-25
CN202110209778 2021-02-25
CN202110321985.8A CN114968547A (zh) 2021-02-25 2021-03-25 一种排序装置及方法
CN202110321985.8 2021-03-25

Related Child Applications (1)

Application Number Title Priority Date Filing Date
US18/454,081 Continuation US20230393813A1 (en) 2021-02-25 2023-08-23 Sorting apparatus and method

Publications (1)

Publication Number Publication Date
WO2022179023A1 true WO2022179023A1 (zh) 2022-09-01

Family

ID=82973013

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/CN2021/103111 Ceased WO2022179023A1 (zh) 2021-02-25 2021-06-29 一种排序装置及方法

Country Status (4)

Country Link
US (1) US20230393813A1 (zh)
EP (1) EP4276623A4 (zh)
CN (2) CN114968547A (zh)
WO (1) WO2022179023A1 (zh)

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20220334762A1 (en) * 2021-04-14 2022-10-20 Montage Technology Co., Ltd. Device and method for picking up top k values

Families Citing this family (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN117992010A (zh) * 2022-10-28 2024-05-07 华为技术有限公司 信号处理方法、装置、设备、介质及芯片
CN118642680B (zh) * 2024-08-16 2024-11-01 泰山学院 一种基于fpga的堆排序系统及方法

Citations (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN103440246A (zh) * 2013-07-19 2013-12-11 百度在线网络技术（北京）有限公司 用于MapReduce的中间结果数据排序方法及系统
CN108228663A (zh) * 2016-12-21 2018-06-29 杭州海康威视数字技术股份有限公司 一种分页检索方法及装置
US20190347071A1 (en) * 2016-11-14 2019-11-14 Google Llc Sorting for data-parallel computing devices
CN112085644A (zh) * 2019-06-12 2020-12-15 上海赜睿信息科技有限公司 多列数据排序方法、装置、可读存储介质和电子设备
CN112395623A (zh) * 2019-08-19 2021-02-23 华控清交信息科技(北京)有限公司 一种数据处理方法、装置和电子设备

Family Cites Families (15)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP3152466B2 (ja) * 1991-04-04 2001-04-03 三菱電機株式会社 ソーティング装置およびソーティング方法
CN103095448B (zh) * 2013-01-22 2015-08-26 广西宝恒电子科技有限公司 一种数字化信号的处理方法
US10482389B2 (en) * 2014-12-04 2019-11-19 Sap Se Parallel development and deployment for machine learning models
US10108555B2 (en) * 2016-05-26 2018-10-23 Macronix International Co., Ltd. Memory system and memory management method thereof
US11797838B2 (en) * 2018-03-13 2023-10-24 Pinterest, Inc. Efficient convolutional network for recommender systems
JP7089179B2 (ja) * 2018-08-30 2022-06-22 富士通株式会社 画像認識装置、画像認識方法および画像認識プログラム
CN109254221A (zh) * 2018-11-26 2019-01-22 南方电网科学研究院有限责任公司 一种智能变电站的数据处理方法
US12566962B2 (en) * 2019-01-04 2026-03-03 Microsoft Technology Licensing, Llc Dithered quantization of parameters during training with a machine learning tool
US11615319B2 (en) * 2019-07-15 2023-03-28 Meta Platforms Technologies, Llc System and method for shift-based information mixing across channels for shufflenet-like neural networks
CN111767023A (zh) * 2019-07-17 2020-10-13 北京京东尚科信息技术有限公司 数据排序方法和数据排序系统
US11573793B2 (en) * 2020-03-18 2023-02-07 Oracle International Corporation Lazy push strategies for vectorized D-Heaps
US11954093B2 (en) * 2020-06-04 2024-04-09 Alibaba Group Holding Limited Performing a top-k function using a binary heap tree
CN111913955A (zh) * 2020-06-22 2020-11-10 中科驭数（北京）科技有限公司 数据的排序处理装置、方法和存储介质
CN111914125B (zh) * 2020-07-16 2024-10-15 北京爱芯科技有限公司 数据处理方法及装置、存储介质及电子设备
CN112202692A (zh) * 2020-09-30 2021-01-08 北京百度网讯科技有限公司 数据分发方法、装置、设备以及存储介质

Patent Citations (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN103440246A (zh) * 2013-07-19 2013-12-11 百度在线网络技术（北京）有限公司 用于MapReduce的中间结果数据排序方法及系统
US20190347071A1 (en) * 2016-11-14 2019-11-14 Google Llc Sorting for data-parallel computing devices
CN108228663A (zh) * 2016-12-21 2018-06-29 杭州海康威视数字技术股份有限公司 一种分页检索方法及装置
CN112085644A (zh) * 2019-06-12 2020-12-15 上海赜睿信息科技有限公司 多列数据排序方法、装置、可读存储介质和电子设备
CN112395623A (zh) * 2019-08-19 2021-02-23 华控清交信息科技(北京)有限公司 一种数据处理方法、装置和电子设备

Non-Patent Citations (1)

* Cited by examiner, † Cited by third party
Title
See also references of EP4276623A4

Cited By (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20220334762A1 (en) * 2021-04-14 2022-10-20 Montage Technology Co., Ltd. Device and method for picking up top k values
US11842070B2 (en) * 2021-04-14 2023-12-12 Montage Technology Co., Ltd. Device and method for picking up top k values

Also Published As

Publication number Publication date
EP4276623A1 (en) 2023-11-15
CN114968547A (zh) 2022-08-30
CN115599541A (zh) 2023-01-13
US20230393813A1 (en) 2023-12-07
EP4276623A4 (en) 2024-06-05

Similar Documents

Publication Publication Date Title
US12608608B2 (en) Aggregated embeddings for a corpus graph
US20230393813A1 (en) Sorting apparatus and method
CN111913955A (zh) 数据的排序处理装置、方法和存储介质
CN111801665B (zh) 用于大数据应用的分层局部敏感哈希(lsh)分区索引
EP3766021A1 (en) Cluster compression for compressing weights in neural networks
CN103177414B (zh) 一种基于结构的图节点相似度并行计算方法
CN111858651A (zh) 一种数据处理方法以及数据处理装置
CN114692079A (zh) 一种gpu批量矩阵乘法加速器及其处理方法
US20240169463A1 (en) Mixture-of-experts layer with dynamic gating
CN105956666A (zh) 一种机器学习方法及系统
CN114358252A (zh) 目标神经网络模型中的操作执行方法及装置、存储介质
CN102902713A (zh) 一种基于图形处理单元的非确定有限自动机的匹配方法及装置
CN114297046A (zh) 基于日志的事件获取方法、装置、设备及介质
CN110209895A (zh) 向量检索方法、装置和设备
US20240160894A1 (en) Mixture-of-experts layer with switchable parallel modes
CN114297260B (zh) 分布式rdf数据查询方法、装置和计算机设备
WO2015094721A2 (en) Apparatuses and methods for writing masked data to a buffer
CN109815475B (zh) 文本匹配方法、装置、计算设备及系统
CN111914125B (zh) 数据处理方法及装置、存储介质及电子设备
US20230401034A1 (en) Methods, Systems, and Circuits for Coordinated Optimization in In-Memory Sorting
US20240160906A1 (en) Collective communication phases at mixture-of-experts layer
CN112100446B (zh) 搜索方法、可读存储介质和电子设备
JP7830849B2 (ja) 情報処理プログラム、情報処理方法及び情報処理装置
CN106790620B (zh) 一种分布式大数据处理方法
US20250371331A1 (en) Implementing n:m sparsity in a digital compute-in-memory accelerator

Legal Events

Date Code Title Description
121 Ep: the epo has been informed by wipo that ep was designated in this application

Ref document number: 21927455

Country of ref document: EP

Kind code of ref document: A1

ENP Entry into the national phase

Ref document number: 2021927455

Country of ref document: EP

Effective date: 20230808

NENP Non-entry into the national phase

Ref country code: DE

WWE Wipo information: entry into national phase

Ref document number: 11202305895X

Country of ref document: SG

WWW Wipo information: withdrawn in national office

Ref document number: 2021927455

Country of ref document: EP