Enabling Highly Efficient k-Means Computations on the SW26010 Many-Core Processor of Sunway TaihuLight

作     者：Min Li Chao Yang Qiao Sun Wen-Jing Ma Wen-Long Cao Yu-Long Ao 

作者机构：Institute of SoftwareChinese Academy of SciencesBeijing 100190China University of Chinese Academy of SciencesBeijing 100049China School of Mathematical SciencesPeking UniversityBeijing 100871China Center for Data SciencePeking UniversityBeijing 100871China peng Cheng LaboratoryShenzhen 518052China 

出 版 物：《Journal of Computer Science & Technology》 (计算机科学技术学报（英文版）)

年 卷 期：2019年第34卷第1期

页      面：77-93页

核心收录：

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 0808[工学-电气工程] 08[工学] 0835[工学-软件工程] 0701[理学-数学] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：the National Key Research and Development Plan of China under Grant No.2016YFB0200603 the National Natural Science Foundation of China under Grant No.91530323 the Beijing Natural Science Foundation of China under Grant No.JQ18001 

主　　题：parallel k-means performance optimization SW26010 processor Sunway TaihuLight 

摘      要：With the advent of the big data era,the amounts of sampling data and the dimensions of data features are rapidly *** is highly desired to enable fast and efficient clustering of unlabeled samples based on feature similarities. As a fundamental primitive for data clustering,the k-means operation is receiving increasingly more attentions *** achieve high performance k-means computations on modern multi-core/many-core systems,we propose a matrix-based fused framework that can achieve high performance by conducting computations on a distance matrix and at the same time can improve the memory reuse through the fusion of the distance-matrix computation and the nearest centroids *** implement and optimize the parallel k-means algorithm on the SW26010 many-core processor,which is the major horsepower of Sunway *** particular,we design a task mapping strategy for load-balanced task distribution,a data sharing scheme to reduce the memory footprint and a register blocking strategy to increase the data *** techniques such as instruction reordering and double buffering are further applied to improve the sustained *** on block-size tuning and performance modeling are also *** show by experiments on both randomly generated and real-world datasets that our parallel implementation of k-means on SW26010 can sustain a double-precision performance of over 348.1 Gflops,which is 46.9% of the peak performance and 84%of the theoretical performance upper bound on a single core group,and can achieve a nearly ideal scalability to the whole SW26010 processor of four core *** comparisons with the previous state-of-the-art on both CPU and GPU are also provided to show the superiority of our optimized k-means kernel.