Memory efficient gpu clustering method speeds up large scale k means
GEM-KMeans: Memory-Efficient and Accurate Clustering on Massive Scale with GPU Optimization
Machine LearningHardware ArchitecturePerformance
Summary
Clustering large datasets efficiently and accurately is important but challenging because of heavy memory use. The authors created GEM-KMeans, a new way to do a math step called nonnegative low-rank factorization for k-means clustering that reduces memory needs on GPUs. This method cleverly combines several computations to keep just one main data array in fast GPU memory, cutting down movement and storage. Tests on large real and synthetic datasets show it works well and can be faster than standard GPU-based methods depending on the data.
What this means in practice
- •For data engineers: Run memory-optimized GPU clustering for very large datasets to reduce hardware costs while maintaining accuracy on large-scale data analysis tasks.
- •For cloud platform teams: Improve GPU cluster resource efficiency for shared machine learning services by deploying GEM-KMeans with its reduced memory footprint.
Authors
Peng Xu, Nihar Koganti, Volodymyr Kindratenko, Xiaohui Chen
Abstract
Memory-efficient scaling on clustering problems without sacrificing statistical accuracy is of central interest for large-scale data analysis and machine learning problems. Nonnegative low-rank (NLR) matrix factorization for $K$-means is a scalable clustering method, which connects to semidefinite relaxations with optimal average-case exact recovery guarantees. However, a direct GPU implementation of NLR requires multiple large factor-sized buffers and substantial data movements that are essentially memory-bound. In this paper, we introduce GEM-KMeans, a spectrally normalized yet mathematically equivalent NLR formulation that fuses the gradient update, nonnegative projection, and sufficient statistics for normalization and iterate movement into a matrix-multiplication epilogue. Instead of retaining three massive factor-sized arrays, our IO-aware GPU implementation materializes only one single factor with small tile-reduction arrays as additional storage in the High Bandwidth Memory (HBM). We derive explicit memory costs and spectrally normalized smoothness bounds for optimizing the clustering objective function. Accurate clustering is demonstrated at massive scales on synthetic and real datasets, where performance gains of GEM-KMeans over existing GPU-accelerated Lloyd's algorithms involve data-dependent runtime tradeoffs.