一种基于截断合并的元素选择方法、设备、介质及产品与流程
本申请实施例涉及人工智能芯片,尤其涉及一种基于截断合并的元素选择方法、设备、介质及产品。
背景技术:
1、topk算子是一类广泛使用的基础操作,其功能是从包含n个元素的输入序列中选取最大(或最小)的k个元素。topk算子是深度学习、信息检索、推荐系统、数据挖掘等领域的核心构建块。例如,在大语言模型的注意力机制中,稀疏注意力需要通过topk选择最相关的键值对;在推荐系统中,需要从海量候选中选取topk个最相关的推荐项。
2、相关技术下,采用完整排序法解决topk问题,具体来说,先对n个元素执行完整排序,获得排序结果;然后从排序结果中选取前k个元素。
3、然而,完整排序法的时间复杂度为o(nlogn),即时间复杂度较高,同时,完整排序法存在大量冗余计算,从而导致计算资源和存储资源浪费。
技术实现思路
1、本申请实施例提供了一种基于截断合并的元素选择方法、设备、介质及产品,用于减少元素选择过程中的冗余计算及资源浪费,提高求解topk问题的效率。
2、一方面,本申请实施例提供了一种基于截断合并的元素选择方法,该方法包括:
3、将n个元素划分为p个元素集,其中,p>1,n>p;
4、对所述p个元素集分别进行元素排序,获得p个元素序列;
5、对所述p个元素序列执行至少一轮截断合并,直到合并为唯一合并序列时停止,并将所述唯一合并序列作为元素选择结果;每轮截断合并包括以下步骤:
6、获取多个合并序列,其中,针对首轮截断合并,所述多个合并序列为所述p个元素序列;针对其他轮截断合并,所述多个合并序列为上一轮截断合并输出的多个合并序列;
7、将所述多个合并序列划分为至少一个序列组;
8、针对每个序列组,从所述序列组的一个合并序列中截取第一片段,以及从所述序列组的另一个合并序列中截取第二片段,并将所述第一片段和所述第二片段合并,获得本轮截断合并输出的包含k个元素的合并序列,其中,k≥1。
9、一方面,本申请实施例提供了一种基于截断合并的元素选择装置,该装置包括:
10、排序模块,用于将n个元素划分为p个元素集,其中,p>1,n>p;对所述p个元素集分别进行元素排序,获得p个元素序列;
11、合并模块,用于对所述p个元素序列执行至少一轮截断合并,直到合并为唯一合并序列时停止,并将所述唯一合并序列作为元素选择结果;每轮截断合并包括以下步骤:
12、获取多个合并序列,其中,针对首轮截断合并,所述多个合并序列为所述p个元素序列;针对其他轮截断合并,所述多个合并序列为上一轮截断合并输出的多个合并序列;
13、将所述多个合并序列划分为至少一个序列组;
14、针对每个序列组,从所述序列组的一个合并序列中截取第一片段,以及从所述序列组的另一个合并序列中截取第二片段,并将所述第一片段和所述第二片段合并,获得本轮截断合并输出的包含k个元素的合并序列,其中,k≥1。
15、可选地,所述合并模块具体用于:
16、确定所述一个合并序列的第一分界点和所述另一个合并序列的第二分界点,所述第一分界点与所述第二分界点之和为k;
17、从所述一个合并序列中截取位于所述第一分界点以及所述第一分界点之前的元素,获得所述第一片段;
18、从所述另一个合并序列中截取位于所述第二分界点以及所述第二分界点之前的元素,获得所述第二片段。
19、可选地,当所述序列组中的每个合并序列为升序序列时,所述第一分界点和所述第二分界点满足以下预设条件:
20、所述一个合并序列中位于所述第一分界点的元素,小于等于所述另一个合并序列中位于所述第二分界点的下一个元素;且,所述一个合并序列中位于所述第一分界点的下一个元素,大于所述另一个合并序列中位于所述第二分界点的元素。
21、可选地,当所述序列组中的每个合并序列为降序序列时,所述第一分界点和所述第二分界点满足以下预设条件:
22、所述一个合并序列中位于所述第一分界点的元素,大于等于所述另一个合并序列中位于所述第二分界点的下一个元素;且,所述一个合并序列中位于所述第一分界点的下一个元素,小于所述另一个合并序列中位于所述第二分界点的元素。
23、可选地,所述合并模块具体用于:
24、对所述一个合并序列执行二分查找操作,获得满足所述预设条件的所述第一分界点和所述第二分界点。
25、可选地,所述排序模块具体用于:
26、通过p个线程块并行对所述p个元素集进行元素排序,获得所述p个元素序列,所述p个元素集中的每个元素集包括t个元素,其中,。
27、可选地,所述合并模块具体用于:
28、将所述第一片段和所述第二片段从全局内存加载到共享内存;
29、从所述共享内存读取所述第一片段和所述第二片段执行合并操作,获得本轮截断合并输出的合并序列。
30、一方面,本申请实施例提供了一种计算机设备,包括存储器、人工智能芯片及存储在存储器上并在人工智能芯片上运行的计算机程序,所述人工智能芯片执行所述计算机程序时实现上述基于截断合并的元素选择方法的步骤。
31、一方面,本申请实施例提供了一种计算机可读存储介质,其存储有可由计算机设备执行的计算机程序,当所述计算机程序在计算机设备上运行时,使得所述计算机设备执行上述基于截断合并的元素选择方法的步骤。
32、一方面,本申请实施例提供了一种计算机程序产品,所述计算机程序产品包括存储在计算机可读存储介质上的计算机程序,所述计算机程序包括程序指令,当所述程序指令被计算机设备执行时,使所述计算机设备执行上述基于截断合并的元素选择方法的步骤。
33、本申请实施例中,将n个元素划分为p个元素集,对p个元素集分别进行元素排序获得p个元素序列,然后对p个元素序列执行至少一轮截断合并,直到合并为唯一合并序列时停止,并将唯一合并序列作为元素选择结果;其中,每轮截断合并包括以下步骤:获取多个合并序列,并将多个合并序列划分为至少一个序列组;从每个序列组中截取包含k个元素的合并序列用于下轮截断合并,这样,在截断合并过程中,除首轮之外的每轮截断合并只需要读取和处理上一轮截断合并输出的包括k个元素的合并序列,而不需要读取和处理完整的n个元素,这样极大降低了元素选择的计算复杂度,减少了大量冗余计算;同时,由于每轮截断合并读写的元素数量大大降低,因此,内存带宽消耗显著降低,在内存带宽受限的人工智能芯片上,带宽节省直接转化为芯片性能提升。
1.一种基于截断合并的元素选择方法,其特征在于,包括:
2.如权利要求1所述的方法,其特征在于,所述从所述序列组的一个合并序列中截取第一片段,以及从所述序列组的另一个合并序列中截取第二片段,包括:
3.如权利要求2所述的方法,其特征在于,还包括:
4.如权利要求2所述的方法,其特征在于,还包括:
5.如权利要求3或4所述的方法,其特征在于,所述确定所述一个合并序列的第一分界点和所述另一个合并序列的第二分界点,包括:
6.如权利要求1所述的方法,其特征在于,所述对所述p个元素集分别进行元素排序,获得p个元素序列,包括:
7.如权利要求1所述的方法,其特征在于,所述将所述第一片段和所述第二片段合并,获得本轮截断合并输出的包含k个元素的合并序列,包括:
8.一种计算机设备,包括存储器、人工智能芯片及存储在存储器上并在人工智能芯片上运行的计算机程序,其特征在于,所述人工智能芯片执行所述计算机程序时实现如权利要求1~7任一项所述方法的步骤。
9.一种计算机可读存储介质,其特征在于,其存储有由计算机设备执行的计算机程序,当所述计算机程序在计算机设备上运行时,使得所述计算机设备执行如权利要求1~7任一项所述方法的步骤。
10.一种计算机程序产品,其特征在于,所述计算机程序产品包括存储在计算机可读存储介质上的计算机程序,所述计算机程序包括程序指令,当所述程序指令被计算机设备执行时,使所述计算机设备执行如权利要求1-7任一项所述方法的步骤。
版权声明:本站专利文献数据主要来源于国家知识产权局等公开渠道,由 技术新讯 进行整理汇编。页面设计及数据汇编的著作权归本站所有。全部内容仅供个人学习、科研评估与技术交流参考,严禁用于任何商业用途(包括但不限于直接生产制造、技术转让、倒卖数据等)。
免责条款:专利技术具有时效性,本站不对资料的绝对准确性、完整性和可实施性提供任何明示或暗示的担保。因参考本站内容造成的直接或间接损失,本站不承担相关法律责任。若您认为本站内容有侵权问题,请及时提供权属证明与我们联系,本站将在核实后依法处理。反馈意见:yyfuon@163.com