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

张志红

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

; ~: Y5 |% r1 h% B. ^