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)。

Repository

https://github.com/MichaelTenma/TopK/tree/main