计算机科学与探索 ›› 2014, Vol. 8 ›› Issue (6): 641-652.DOI: 10.3778/j.issn.1673-9418.1312029

• 高性能计算 • 上一篇    下一篇

面向CPU/MIC异构架构的K-Means向量化算法

谭郁松+,伍复慧,吴庆波,陈  微,孙晓利   

  1. 国防科学技术大学 计算机学院,长沙 410073
  • 出版日期:2014-06-01 发布日期:2014-05-30

Vectorized K-Means Algorithm on Heterogeneous CPU/MIC Architecture

TAN Yusong+, WU Fuhui, WU Qingbo, CHEN Wei, SUN Xiaoli   

  1. School of Computer, National University of Defense Technology, Changsha 410073, China
  • Online:2014-06-01 Published:2014-05-30

摘要: 在大数据背景下,以K-Means为代表的聚类分析对于数据分析和挖掘十分重要。海量高维数据的处理给K-Means算法带来了性能方面的强烈需求。最新提出的众核体系结构MIC(many integrated core)能够为算法加速提供众核间线程级和核内指令级并行,使其成为K-Means算法加速的很好选择。在分析K-Means基本算法特点的基础上,分析了K-Means算法的瓶颈,提出了可利用数据并行的K-Means向量化算法,优化了向量化算法的数据布局方案。最后,基于CPU/MIC的异构架构实现了向量化K-Means算法,并且探索了MIC在非传统HPC(high performance computing)应用领域的优化策略。测试结果表明, K-Means向量化算法具有良好的计算性能和扩展性。

关键词: K-Means, 向量优化, 集成众核(MIC), 异构

Abstract: In the context of big data era, K-Means is an important algorithm of cluster analysis of data mining. The massive high-dimensional data processing brings strong performance demand on K-Means algorithms. The newly proposed MIC (many integrated core) architecture provides both thread-level parallel between cores and instruction-
level parallel in each core, which make MIC good choice for algorithm acceleration. Firstly, this paper describes the basic K-Means algorithm and analyzes its bottleneck. Then it proposes a novel vectorized K-Means algorithm which optimizes vector data layout strategy and gets higher parallel performance. Moreover, it implements the vectorized algorithm on CPU/MIC heterogeneous platform, and explores the MIC optimization strategy in non-traditional HPC (high performance computing) applications. The experimental results prove that the vectorized K-Means algorithm has excellent performance and scalability.

Key words: K-Means, vectorized optimization, many integrated core (MIC), heterogeneous