Large-scale hierarchical k-means for heterogeneous many-core supercomputers

Lideng Li; Teng Yu; Wenlai Zhao; Haohuan Fu; Chenyu Wang; Li Tan; Guangwen Yang; John Thomson

doi:10.1109/SC.2018.00016

Large-scale hierarchical k-means for heterogeneous many-core supercomputers

Lideng Li
, Teng Yu
, Wenlai Zhao
, Haohuan Fu
, Chenyu Wang
, Li Tan
, Guangwen Yang
, John Thomson

School of Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

This paper presents a novel design and implementation of k-means clustering algorithm targeting the Sunway TaihuLight supercomputer. We introduce a multi-level parallel partition approach that not only partitions by dataflow and centroid, but also by dimension. Our multi-level (nkd) approach unlocks the potential of the hierarchical parallelism in the SW26010 heterogeneous many-core processor and the system architecture of the supercomputer.

Our design is able to process large-scale clustering problems with up to 196,608 dimensions and over 160,000 targeting centroids, while maintaining high performance and high scalability, significantly improving the capability of k-means over previous approaches. The evaluation shows our implementation achieves performance of less than 18 seconds per iteration for a large-scale clustering case with 196,608 data dimensions and 2,000 centroids by applying 4,096 nodes (1,064,496 cores) in parallel, making k-means a more feasible solution for complex scenarios.

Original language	English
Title of host publication	Proceedings of the International Conference for High Performance Computing, Networking, Storage, and Analysis (SC '18)
Place of Publication	Piscataway
Publisher	IEEE Press
Chapter	13
Pages	160-170
Number of pages	11
ISBN (Electronic)	9781538683842
DOIs	https://doi.org/10.1109/SC.2018.00016
Publication status	Published - 11 Nov 2018
Event	The International Conference for High Performance Computing, Networking, Storage, and Analysis - Dallas, United States Duration: 11 Nov 2018 → 16 Nov 2018 https://sc18.supercomputing.org/

Conference

Conference	The International Conference for High Performance Computing, Networking, Storage, and Analysis
Abbreviated title	SC18
Country/Territory	United States
City	Dallas
Period	11/11/18 → 16/11/18
Internet address	https://sc18.supercomputing.org/

Keywords

Supercomputer
Multi/many-core Processors
Clustering
Parallel computing

Access to Document

10.1109/SC.2018.00016

Thomson_2018_LargeScaleKMeans_AAM
Copyright © 2018 IEEE Press. This work has been made available online in accordance with the publisher's policies. This is the author created accepted version manuscript following peer review and as such may differ slightly from the final published version. The final published version of this work is available at https://dl.acm.org/citation.cfm?id=3291674
Accepted author manuscript, 904 KB

https://dl.acm.org/citation.cfm?id=3291674

Handle.net

Persistent link

ABC: Adaptive Brokerage for the Cloud: ABC: Adaptive Brokerage for the Cloud
Barker, A. (PI) & Thomson, J. (CoI)
EPSRC
1/04/18 → 30/09/22
Project: Standard
TeamPlay: H2020 ICT-5 Teamplay
Brown, C. (PI)
Joint Research Centre European Commission
1/01/18 → 31/12/20
Project: Standard
Discovery: Pattern Discovery and Program: Discovery: Pattern Discovery and Program Shaping for Manycore Systems
Thomson, J. (PI), Hammond, K. (CoI) & Sarkar, S. (CoI)
EPSRC
1/07/17 → 31/12/20
Project: Standard

Heterogeneity-aware scheduling and data partitioning for system performance acceleration
Yu, T. (Author), Thomson, J. D. (Supervisor), 29 Jul 2020
Student thesis: Doctoral Thesis (PhD)

Cite this

@inproceedings{dd552c75e08e471f9367a8f909aa25fb,

title = "Large-scale hierarchical k-means for heterogeneous many-core supercomputers",

abstract = "This paper presents a novel design and implementation of k-means clustering algorithm targeting the Sunway TaihuLight supercomputer. We introduce a multi-level parallel partition approach that not only partitions by dataflow and centroid, but also by dimension. Our multi-level (nkd) approach unlocks the potential of the hierarchical parallelism in the SW26010 heterogeneous many-core processor and the system architecture of the supercomputer. Our design is able to process large-scale clustering problems with up to 196,608 dimensions and over 160,000 targeting centroids, while maintaining high performance and high scalability, significantly improving the capability of k-means over previous approaches. The evaluation shows our implementation achieves performance of less than 18 seconds per iteration for a large-scale clustering case with 196,608 data dimensions and 2,000 centroids by applying 4,096 nodes (1,064,496 cores) in parallel, making k-means a more feasible solution for complex scenarios. ",

keywords = "Supercomputer, Multi/many-core Processors, Clustering, Parallel computing",

author = "Lideng Li and Teng Yu and Wenlai Zhao and Haohuan Fu and Chenyu Wang and Li Tan and Guangwen Yang and John Thomson",

note = "Funding: J.Thomson and T.Yu are supported by the EPSRC grants ”Discovery” EP/P020631/1, ”ABC: Adaptive Brokerage for the Cloud” EP/R010528/1, and EU Horizon 2020 grant Team-Play: ”Time, Energy and security Analysis for Multi/Many-core heterogenous PLAtforms” (ICT-779882, https://teamplay- h2020.eu); The International Conference for High Performance Computing, Networking, Storage, and Analysis, SC18 ; Conference date: 11-11-2018 Through 16-11-2018",

year = "2018",

month = nov,

day = "11",

doi = "10.1109/SC.2018.00016",

language = "English",

pages = "160--170",

booktitle = "Proceedings of the International Conference for High Performance Computing, Networking, Storage, and Analysis (SC '18)",

publisher = "IEEE Press",

url = "https://sc18.supercomputing.org/",

}

Li, L, Yu, T, Zhao, W, Fu, H, Wang, C, Tan, L, Yang, G & Thomson, J 2018, Large-scale hierarchical k-means for heterogeneous many-core supercomputers. in Proceedings of the International Conference for High Performance Computing, Networking, Storage, and Analysis (SC '18). IEEE Press, Piscataway, pp. 160-170, The International Conference for High Performance Computing, Networking, Storage, and Analysis, Dallas, Texas, United States, 11/11/18. https://doi.org/10.1109/SC.2018.00016

Large-scale hierarchical k-means for heterogeneous many-core supercomputers. / Li, Lideng; Yu, Teng; Zhao, Wenlai et al.
Proceedings of the International Conference for High Performance Computing, Networking, Storage, and Analysis (SC '18). Piscataway: IEEE Press, 2018. p. 160-170.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Large-scale hierarchical k-means for heterogeneous many-core supercomputers

AU - Li, Lideng

AU - Yu, Teng

AU - Zhao, Wenlai

AU - Fu, Haohuan

AU - Wang, Chenyu

AU - Tan, Li

AU - Yang, Guangwen

AU - Thomson, John

N1 - Funding: J.Thomson and T.Yu are supported by the EPSRC grants ”Discovery” EP/P020631/1, ”ABC: Adaptive Brokerage for the Cloud” EP/R010528/1, and EU Horizon 2020 grant Team-Play: ”Time, Energy and security Analysis for Multi/Many-core heterogenous PLAtforms” (ICT-779882, https://teamplay- h2020.eu)

PY - 2018/11/11

Y1 - 2018/11/11

N2 - This paper presents a novel design and implementation of k-means clustering algorithm targeting the Sunway TaihuLight supercomputer. We introduce a multi-level parallel partition approach that not only partitions by dataflow and centroid, but also by dimension. Our multi-level (nkd) approach unlocks the potential of the hierarchical parallelism in the SW26010 heterogeneous many-core processor and the system architecture of the supercomputer. Our design is able to process large-scale clustering problems with up to 196,608 dimensions and over 160,000 targeting centroids, while maintaining high performance and high scalability, significantly improving the capability of k-means over previous approaches. The evaluation shows our implementation achieves performance of less than 18 seconds per iteration for a large-scale clustering case with 196,608 data dimensions and 2,000 centroids by applying 4,096 nodes (1,064,496 cores) in parallel, making k-means a more feasible solution for complex scenarios.

AB - This paper presents a novel design and implementation of k-means clustering algorithm targeting the Sunway TaihuLight supercomputer. We introduce a multi-level parallel partition approach that not only partitions by dataflow and centroid, but also by dimension. Our multi-level (nkd) approach unlocks the potential of the hierarchical parallelism in the SW26010 heterogeneous many-core processor and the system architecture of the supercomputer. Our design is able to process large-scale clustering problems with up to 196,608 dimensions and over 160,000 targeting centroids, while maintaining high performance and high scalability, significantly improving the capability of k-means over previous approaches. The evaluation shows our implementation achieves performance of less than 18 seconds per iteration for a large-scale clustering case with 196,608 data dimensions and 2,000 centroids by applying 4,096 nodes (1,064,496 cores) in parallel, making k-means a more feasible solution for complex scenarios.

KW - Supercomputer

KW - Multi/many-core Processors

KW - Clustering

KW - Parallel computing

U2 - 10.1109/SC.2018.00016

DO - 10.1109/SC.2018.00016

M3 - Conference contribution

SP - 160

EP - 170

BT - Proceedings of the International Conference for High Performance Computing, Networking, Storage, and Analysis (SC '18)

PB - IEEE Press

CY - Piscataway

T2 - The International Conference for High Performance Computing, Networking, Storage, and Analysis

Y2 - 11 November 2018 through 16 November 2018

ER -

Large-scale hierarchical k-means for heterogeneous many-core supercomputers

Abstract

Conference

Keywords

Access to Document

Handle.net

Fingerprint

Projects

ABC: Adaptive Brokerage for the Cloud: ABC: Adaptive Brokerage for the Cloud

TeamPlay: H2020 ICT-5 Teamplay

Discovery: Pattern Discovery and Program: Discovery: Pattern Discovery and Program Shaping for Manycore Systems

Student theses

Heterogeneity-aware scheduling and data partitioning for system performance acceleration

Cite this