多核CPU环境下的并行KNN算法设计  

Design of parallel KNN algorithm in multi-core CPU environment

作　　者：潘峰[1,2] 苏浩辀 段艳 闵云霄 Pan Feng;Su Haozhou;Duan Yan;Ming Yunxiao(Key Laboratory of Pattern Recognition and Intelligent System,Guizhou Minzu University,Guiyang,Guizhou 550025,China;Network Security and Big Data Application Training Center,Guizhou Minzu University)

机构地区：[1]贵州民族大学模式识别与智能系统重点实验室,贵州贵阳550025 [2]贵州民族大学网络安全与大数据应用训练中心

出　　处：《计算机时代》2023年第7期34-37,共4页Computer Era

基　　金：贵州省教育厅自然科学研究项目(黔教技[2022]047号,黔教技[2022]015号)。

摘　　要：针对KNN算法计算比较耗时的问题,提出将计算任务分解为多个子任务,每个子任务分配给一个线程完成,通过多个线程的并行执行完成工作。将训练集读入一个二维数组,二维数组的每一行只分配给一个线程使用;每个新数据被同时广播给多个线程,每个线程计算该新数据在自己训练集中的最近邻,并将最近邻反馈给主程序;主程序收集每个线程返回的最近邻,以最近邻中的最佳近邻的类别作为新数据的类别。实验证明该并行设计方案充分利用计算资源,加快了计算速度。In view of the time consuming problem of KNN algorithm,the computation task is decomposed into multiple subtasks,and each subtask is assigned to a thread to complete the work through the parallel execution of multiple threads.Firstly,the training set is read into a two-dimensional array,each row of which is allocated to only one thread.Secondly,each new data is broadcasted to multiple threads simultaneously,and each thread calculates the nearest neighbor of the new data in its own training set and feeds it back to the main program.Finally,the main program collects the nearest neighbors returned by each thread and uses the category of best nearest neighbors as the category of new data.Experimental results show that this parallel design scheme makes full use of computing resources and speeds up the computing.

关 键 词：并行KNN算法 多线程 二维数组 最佳近邻 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]