Implementation and Optimization of Parallel KNN Algorithm for Sunway Architecture

doi:10.19678/j.issn.1000-3428.0063954

Abstract

Abstract: The K-Nearest Neighbor（KNN） algorithm is the most typically used classification algorithm in artificial intelligence，and its performance improvement significantly affects the sorting and analysis of massive data and big data classification.The current new generation of Sunway supercomputers is in the initial stage of application development. Exploiting the structural characteristics of the new-generation Sunway heterogeneous many-core processors allows an efficient KNN algorithm to be achieved for massive data analysis and collation.In this study，based on the structural characteristics of the SW26010pro processor，the master-slave acceleration programming model is used to implement the basic version of the KNN parallel algorithm，which transfers the computing core to the slave core for thread-level parallelism.Subsequently，the key factors affecting the performance of the basic parallel algorithm are analyzed，and the SWKNN algorithm is proposed，which is different from the task-division method of the basic parallel KNN algorithm. Finally，unnecessary communication overhead is reduced through data pipelining optimization，intercore communication optimization，and secondary load balancing optimization，which effectively relieves memory access pressure and further improves the algorithm performance.The experimental results show that，compared with the serial KNN algorithm，the basic parallel KNN algorithm for the Sunway architecture can achieve a maximum speedup that is 48 times higher on the single-core group of the SW26010pro processor.At the same scale，the SWKNN can achieve a speedup that is 399 times higher than that of the basic parallel KNN algorithm.

Key words: heterogeneous many-core processors, K-Nearest Neighbor（KNN） algorithm, parallel computing, algorithm optimization, classification performance

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

关键词: 异构众核处理器, K近邻算法, 并行计算, 算法优化, 分类性能

CLC Number:

TP391

WANG Qihan, PANG Jianmin, YUE Feng, ZHU Di, SHEN Li, XIAO Qian. Implementation and Optimization of Parallel KNN Algorithm for Sunway Architecture[J]. Computer Engineering, 2023, 49(5): 286-294.

王其涵, 庞建民, 岳峰, 祝迪, 沈莉, 肖谦. 面向申威架构的KNN并行算法实现与优化[J]. 计算机工程, 2023, 49(5): 286-294.

/ / Recommend / Download Citations

URL: http://www.ecice06.com/EN/10.19678/j.issn.1000-3428.0063954

http://www.ecice06.com/EN/Y2023/V49/I5/286

Figures/Tables 17

References

[1] DU Q M,LI N,YANG S D,et al.Integrating KNN and gradient boosting decision tree for recommendation[C]//Proceedings of IEEE Advanced Information Technology,Electronic and Automation Control Conference.Washington D.C.,USA:IEEE Press,2021:2042-2049.
[2] 王芳.基于类划分和近邻选取的k近邻算法研究[D].西安:西安理工大学,2020. WANG F.Research on k nearest neighbor algorithm based on class division and neighbor selection[D].Xi'an:Xi'an University of Technology,2020.(in Chinese)
[3] 王进,晏世凯,高延雨,等.基于MPI的ML-kNN算法并行[J].郑州大学学报(理学版),2018,50(3):34-38. WANG J,YAN S K,GAO Y Y,et al.Parallelization of ML-kNN based on MPI[J].Journal of Zhengzhou University(Natural Science Edition),2018,50(3):34-38.(in Chinese)
[4] 高捷,刘沙,黄则强,等.基于国产众核处理器的深度神经网络算子加速库优化[J].计算机科学,2022,49(5):355-362. GAO J,LIU S,HUANG Z Q,et al.Deep neural network operator acceleration library optimization based on domestic many-core processor[J].Computer Science,2022,49(5):355-362.(in Chinese)
[5] 陶小涵,庞建民,高伟,等.基于SW26010处理器的FT程序的性能优化[J].计算机科学,2019,46(4):321-328. TAO X H,PANG J M,GAO W,et al.Performance optimization of FT program based on SW26010 processor[J].Computer Science,2019,46(4):321-328.(in Chinese)
[6] 彭龙,陈俊仕,安虹.基于神威太湖之光的AMBER软件移植与优化[J].计算机工程,2020,46(12):12-20. PENG L,CHEN J S,AN H.Migration and optimization of AMBER software based on Sunway TaihuLight[J].Computer Engineering,2020,46(12):12-20.(in Chinese)
[7] 何亚茹,庞建民,徐金龙,等.基于神威平台的Floyd并行算法的实现和优化[J].计算机科学,2021,48(6):34-40. HE Y R,PANG J M,XU J L,et al.Implementation and optimization of Floyd parallel algorithm based on Sunway platform[J].Computer Science,2021,48(6):34-40.(in Chinese)
[8] 赵瑞祥,郑凯,刘垚,等.基于申威众核处理器的混合并行遗传算法[J].计算机应用,2017,37(9):2518-2523. ZHAO R X,ZHENG K,LIU Y,et al.Hybrid parallel genetic algorithm based on Sunway many-core processors[J].Journal of Computer Applications,2017,37(9):2518-2523.(in Chinese)
[9] COVER T,HART P.Nearest neighbor pattern classification[J].IEEE Transactions on Information Theory,1967,13(1):21-27.
[10] 李航.统计学习方法[M].北京:清华大学出版社,2012. LI H.Statistical learning method[M].Beijing:Tsinghua University Press,2012.(in Chinese)
[11] LI B L,LU Q,YU S W.An adaptive k-nearest neighbor text categorization strategy[J].ACM Transactions on Asian Language Information Processing,2004,3(4):215-226.
[12] 周朴雄.用于WEB文档分类的并行KNN算法[J].计算机工程与应用,2008,44(25):155-156. ZHOU P X.Parallel KNN algorithm for WEB document classification[J].Computer Engineering and Applications,2008,44(25):155-156.(in Chinese)
[13] 王宗跃,马洪超,徐宏根,等.多核CPU的海量点云并行kNN算法[J].测绘科学技术学报,2010,27(1):46-49. WANG Z Y,MA H C,XU H G,et al.k-nearest neighbors algorithm for large scale point clouds data with multi-core CPU[J].Journal of Geomatics Science and Technology,2010,27(1):46-49.(in Chinese)
[14] 贺江,蒲宇亮,李海波,等.一种基于OpenCL的高能效并行KNN算法及其GPU验证[J].电子技术应用,2016,42(2):14-16. HE J,PU Y L,LI H B,et al.A energy efficient parallel KNN algorithm evaluated on GPU using OpenCL[J].Application of Electronic Technique,2016,42(2):14-16.(in Chinese)
[15] MASEK J,BURGET R,KARASEK J,et al.Multi-GPU implementation of k-nearest neighbor algorithm[C]//Proceedings of the 38th International Conference on Telecommunications and Signal Processing.Washington D.C.,USA:IEEE Press,2015:764-767.
[16] BARRIENTOS R J,MILLAGUIR F,SÁNCHEZ J L,et al.GPU-based exhaustive algorithms processing kNN queries[J].The Journal of Supercomputing,2017,73(10):4611-4634.
[17] 高建明.数据挖掘分类与聚类算法并行化研究[D].南京:东南大学,2017. GAO J M.Research on parallelization of data mining classification and clustering algorithm[D].Nanjing:Southeast University,2017.(in Chinese)
[18] 刘端阳,郑江帆,刘志.基于CUDA的KNN算法并行化研究[J].小型微型计算机系统,2019,40(6):1197-1202. LIU D Y,ZHENG J F,LIU Z.Research of parallel KNN algorithm based on CUDA[J].Journal of Chinese Computer Systems,2019,40(6):1197-1202.(in Chinese)
[19] 林增,武铮,安虹,等.PME算法在神威太湖之光上的移植和优化[J].小型微型计算机系统,2021,42(1):9-14. LIN Z,WU Z,AN H,et al.Porting and optimizing PME algorithm on Sunway TaihuLight system[J].Journal of Chinese Computer Systems,2021,42(1):9-14.(in Chinese)
[20] 朱文强,傅游,梁建国,等.Silicon-Crystal应用在SW26010处理器上的移植与优化[J].小型微型计算机系统,2021,42(6):1313-1320. ZHU W Q,FU Y,LIANG J G,et al.Porting and optimizing of Silicon-Crystal application on SW26010 processor[J].Journal of Chinese Computer Systems,2021,42(6):1313-1320.(in Chinese)
[21] FU H H,LIAO J F,YANG J Z,et al.The Sunway TaihuLight supercomputer:system and applications[J].Science China Information Sciences,2016,59(7):1-16.
[22] JOHNSON B A,TATEISHI R,HOAN N T.A hybrid pansharpening approach and multiscale object-based image analysis for mapping diseased pine and oak trees[J]. International Journal of Remote Sensing,2013,34(20):6969-6982.
[23] JOHNSON B A,TATEISHI R,HOAN N T.A hybrid pansharpening approach and multiscale object-based image analysis for mapping diseased pine and oak trees[J].International Journal of Remote Sensing,2013,34(20):6969-6982.
[24] YU T,NWET K T.Comparing SVM and KNN algorithms for Myanmar news sentiment analysis system[C]//Proceedings of the 6th International Conference on Computing and Data Engineering.New York,USA:ACM Press,2020:65-69.
[25] KAUR S,SIKKA G,AWASTHI L K.Sentiment analysis approach based on N-gram and KNN classifier[C]//Proceedings of the 1st International Conference on Secure Cyber Computing and Communication.Washington D.C.,USA:IEEE Press,2018:1-4.
[26] HARPER F M,KONSTAN J A.The MovieLens datasets:history and context[J].ACM Transactions on Interactive Intelligent Systems,2016,5(4):1-19.

Please choose a citation manager

Content to export