CAJ | 학술논문

Kmeans算法是无监督机器学习中一种典型的聚类算法，是对已知数据集进行划分和分组的重要方法，在图像处理、数据挖掘、生物学领域有着广泛的应用。随着实际应用中数据规模的不断变大，对Kmeans算法的性能也提出了更高的要求。在充分考虑不同硬件平台体系架构差异的基础上，系统地研究了Kmeans算法在GPU和APU平台上实现与优化的关键技术：片上全局同步高效实现，冗余计算减少全局同步次数，线程任务重映射，局部内存重用等，实现了Kmeans算法在不同硬件平台上的高性能与性能移植。实验结果表明，优化后的算法在考虑数据传输时间的前提下，在AMD HD7970 GPU上相对于CPU版本取得136.975~170.333倍的加速比，在AMD A10-5800K APU上相对于CPU版本取得22.2365~24.3865倍的加速比，有效验证了优化方法的有效性和平台的可移植性。
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.