基于OneAPI的并行化快速选择TopK算法实现
SenXin Wu
Guang Zhou Shi, Guang Dong Sheng
- 0 Collaborators
TopK是指在若干个数的序列中,找出K个最小(或最大)的数。本项目借助OneAPI在CPU多个核心上实现TopK算法的并行计算。本文通过并行快速选择算法寻找K个最小值,实现关键点在于将数序列划分成L块,每块的大小为B,对每块都进行快速选择算法,得出每块的前K小值,然后再对L块的全部前K小值,总计K*L个值,再进行快速选择,找出最终的前K小值,对于不同块而言,可以在不同的CPU核心上并行计算,以提高运算性能。 ...learn more
Project status: Under Development
Overview / Usage
TopK问题是在M个数中找出前K个最小值或最大值的问题。在搜索算法、机器学习、信息检索等相关领域中存在着大量依赖于TopK求解的问题,而如何充分利用单个设备的算力求解TopK,或是利用多个设备、多个处理器高效计算一直是一个复杂的工程问题。通过多线程来并行解算TopK问题,需要仔细编写多线程代码;结合CPU、GPU以及其他专用加速器进行计算时,要求程序员对特定的硬件API有比较深入的认识;当希望利用多台设备进行并行计算时,还需要借助通讯协议使不同设备之间可以数据交换。辅助程序员开发并行程序的框架有很多,例如如MPI、openMP等,但是在异构计算上仍然取不得很好的效果。
本项目采用了英特尔公司开发的OneAPI框架来求解TopK问题。oneAPI是统一的开发工具组合和软件接口,可以让开发人员在CPU、GPU、FPGA、AI加速器等计算架构上实现“高效开发,任意扩展”,并提供了统一的编程框架和编程模型,以简化异构平台的编码复杂程度;
本项目借助OneAPI在CPU多个核心上实现TopK算法的并行计算,并与两个串行的TopK算法进行了对比试验。
Methodology / Approach
本项目使用OneAPI实现在单个设备上的并行计算,后续可以很方便地从CPU并行修改成GPU并行、或者专用FPGA加速器并行;使用MPI实现了跨设备、跨进程地并行计算,相比于串行TopK算法,本项目大幅度提高了TopK问题的解算规模。本项目的根本目的是高效地从M个数中找出前K个最小的数,本项目通过以下三种算法进行对比实验:并行快速选择算法,串行快速选择算法,串行堆排序算法。
快速选择算法定义:快速选择算法由快速排序算法改进而来,通常用于解决TopK问题,它的总体思路与快速排序一致,选择一个元素作为基准来对元素进行划分,将小于和大于基准的元素分别至于基准的左右两侧。但是不同的是,快速选择并不需要和快速排序算法一样,左右两侧都需要递归,快速选择算法是需要递归进入一侧的元素中继续寻找。因此当基准足够随机的时候,期望的复杂度为O(n)。