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

摘要： 在大数据背景下，以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）, 异构