面向申威架构的KNN并行算法的实现和优化

作者:王其涵; 庞建民; 岳峰; 祝迪; 沈莉; 肖谦
更新时间:

K-最近邻算法(K-Nearest Neighbor,KNN)是人工智能中最常用的分类算法。其业绩的提升对海量数据的分类分析和大数据分类有重要影响。目前,新一代神威超级计算机正处于应用开发的初级阶段。结合新一代申威异构众核处理器的结构特点,充分利用巨大的计算资源,实现高效的KNN算法,是海量数据分析整理的现实需求。首先,根据SW26010pro处理器的结构特点,本文采用主从加速编程模型实现了KNN并行算法的基本版本,将计算核心转移到从核心,实现了线程级并行。然后,分析了影响基本并行算法性能的关键因素,提出了SWKNN算法算法。该算法不同于基本并行KNN算法的任务划分模式。为了避免冗余的计算开销,采用了任务重划分策略。最后,通过数据管道优化、核间通信优化和二次负载平衡优化,减少了不必要的通信开销,有效缓解了内存访问压力,进一步提高了算法的性能。实验结果表明,与串行算法相比,申威体系结构的基本并行KNN算法在SW26010pro处理器的单核群上可以实现48倍的最大加速度,而SWKNN算法在相同规模上可以实现399倍的最大加速度。