摘要
Kmeans算法是无监督机器学习中一种典型的聚类算法,是对已知数据集进行划分和分组的重要方法,在图像处理、数据挖掘、生物学领域有着广泛的应用。随着实际应用中数据规模的不断变大,对Kmeans算法的性能也提出了更高的要求。在充分考虑不同硬件平台体系架构差异的基础上,系统地研究了Kmeans算法在GPU和APU平台上实现与优化的关键技术:片上全局同步高效实现,冗余计算减少全局同步次数,线程任务重映射,局部内存重用等,实现了Kmeans算法在不同硬件平台上的高性能与性能移植。实验结果表明,优化后的算法在考虑数据传输时间的前提下,在AMD HD7970 GPU上相对于CPU版本取得136.975~170.333倍的加速比,在AMD A10-5800K APU上相对于CPU版本取得22.2365~24.3865倍的加速比,有效验证了优化方法的有效性和平台的可移植性。
As a typical clustering algorithm and an important method to data decomposition and packet processing, Kmeans algorithm is widely used in image processing, machine learning and biology, etc. Due to the constant expan-sion on data set, Kmeans is facing more and more demand on its performance. Having taken into full account the difference between hardware platforms and architectures, this paper conducts a systematic research on achieving Kmeans algorithm efficiently running on GPU and APU platforms based on OpenCL. And with the help of several optimization methods, such as the implementation of iterative algorithm with multiple global synchronization in GPU, the reduction on global synchronization by redundant computation, the redistribution on thread task, the reuseof local memory, etc, Kmeans algorithm achieves high efficient implementation on different hardware architectures and the optimization methods suitable for iterative algorithm are summed up. The experimental results show that the optimized algorithm gets 136.975~170.333 times speedup on AMD HD7970 GPU than the CPU version (with con-sidering the data transfer time) and gets 22.2365~24.3865 times speedup on AMD A10-5800K APU than the CPU version, which effectively verifies the validity and the cross-platform ability of the optimization methods proposed in this paper.
出处
《计算机科学与探索》
CSCD
2014年第10期1162-1176,共15页
Journal of Frontiers of Computer Science and Technology
基金
国家自然科学基金 Nos.61133005
61272136
国家高技术研究发展计划(863计划) No.2012AA010903
ISCAS-AMD联合Fusion软件中心资助项目~~
关键词
并行计算
迭代算法
跨平台
OpenCL
Kmeans
OpenCL
parallel computing
Kmeans
iterative algorithm
cross-platform