goldsborough / k-means

Code accompanying my blog post on k-means in Python, C++ and CUDA

⤴️ ⤴️ k-means

This repository contains code referenced in my blog post Exploring k-means in Python, C++ and CUDA, where I implement k-means in a variety of platforms. In this post I show how CUDA implementations of k-means can outperform scikit-learn and scipy in performance by a factor of 72 and 90, respectively.

The code is not particularly tidy, but gives an idea of how to implement k-means efficiently on a GPU.

Contents

• python/ contains Python code for k-means using scikit-learn, scipy and a roll-it-yourself implementation.
• cpp/ contains C++ implementations of k-means, including one using Eigen.
• cuda/ holds all CUDA implementations.
• data/ has some toy data with 100 and 100k datapoints in five clusters as well as a script to generate more.

Authors

Peter Goldsborough + cat ❤️

k-means's Issues

Bug?

Hi,

There are some code in kmeans cuda fast version might be bug.

k-means/cuda/k-means-fast.cu

Lines 142 to 149 in 3ca19f3

	if (index < k) {
	const int count = max(1, counts[index]);
	means_x[index] = new_sum_x[index] / count;
	means_y[index] = new_sum_y[index] / count;
	new_sum_y[index] = 0;
	new_sum_x[index] = 0;
	counts[index] = 0;
	}

I think new_sum_x[index] should be replaced by shared_data at some index.
Btw, shouldn't counts do the parallel reduction on shared memory?

thanks.