(1.衡阳师范学院 计算机科学技术系,湖南 衡阳421008; 2.湖南大学 计算机与通信学院, 长沙 410082)
提出一种利用GPU(图形处理器)和CPU的协同计算模式来提高划分聚类算法enhanced_K-means的计算效率。利用GPU多个子素处理器可以并行计算的特性,将算法中比较耗时的欧氏距离计算与比较、中心点改变后簇中没有发生变化的点集合判断步骤由GPU执行,算法其余步骤由CPU执行,使聚类效率得到显著提高。在配有Pentium 4 3.4 GHz CPU和NVIDIA GeForce7800GT显卡的硬件环境下经过实验测试,证明其运算速度比完全采用CPU计算速度要快。这种改进的划分聚类算法适合在数据流环境下对大量数据进行实时高效聚类操作。
关键词:聚类分析; 图形处理器; 通用计算; 划分聚类
Research of efficiency of partitioning clustering algorithmbased on graphics processing unit
LI Lin1, LI Ken-li 2
(1. Dept. of Computer & Science & Technology, Hengyang Normal University, Hengyang Hunan 421008,China; 2.College of Computer & Communication, Hunan University, Changsha 410082, China)
This paper proposed a mode with CPU+GPU co-processing to improve the efficiency of enhanced_K-means algorithm. By the characterization that the parallel computing could be finished by the multiple fragment processor, the step that the calculation and comparison of Euclidean distance, the judgment on the point aggregation in the clustering that has no difference after the central point was changed, both of which would spent much time, were finished by GPU, while other steps were finished by CPU. Therefore the clustering efficiency was improved greatly. Some experiments conducted in a PC with Pentium 4 3.4GHz AMD 643500+ CPU and NVIDIA GeForce7800GT graphic card demonstrate that the presented algorithm is faster than the previous CPU-based algorithms, thus the improved partitional clustering algorithm is applicable for the clustering data stream that requiring for high speed processing and high quality clustering results. ......