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

作者：王其涵; 庞建民; 岳峰; 祝迪; 沈莉; 肖谦

来源：计算机工程, 2022, 1-12.

DOI：10.19678/j.issn.1000-3428.0063954

• 异构众核处理器
• KNN算法
• 并行计算
• 算法优化，分类性能

k-最近邻算法（K-Nearest Neighbor，KNN）是人工智能中最常用的分类算法，其性能的提升对于海量数据的整理分析和大数据分类等具有重要影响。当下新一代神威超级计算机正处于应用发展的初始阶段，结合新一代申威异构众核处理器的结构特性，充分利用庞大的计算资源实现高效的KNN算法是海量数据分析整理的现实需求。本文首先根据SW26010pro处理器的结构特性，采用主从加速编程模型实现基础版本的KNN并行算法，其将计算核心传输到从核上进行，实现了线程级并行。然后分析了影响基础并行算法性能的关键因素并提出了SWKNN算法，该算法不同于基础并行KNN算法的任务划分方式，采用任务重划分策略，避免了冗余计算开销。最后通过数据流水优化、从核间通信优化和二次负载均衡优化等减少了不必要的通信开销，有效缓解了访存压力并进一步提升了算法性能。实验结果表明，与串行算法相比，面向申威架构的基础并行KNN算法在SW26010pro处理器的单核组上可以获得最高48倍的加速，而同等规模下SWKNN较基础并行KNN算法可以获得最高399倍的加速。

• 单位
  中国科学技术大学