Hello,

I'm using K-Means Rex for my own project.

It uses Eigen for the matrix computations.
Hence I downloaded Eigen 3.3.2 to my project.

In the K-Means Algorithm the main thing is calculating the distance between each sample to the centroids.
In K-Means REX it is done using Matrix Multiplication (Yes, lot of overhead and inefficient) as can be seen in the function pairwise_distance.

I compiled the project K-Means REX using Visual Studio 2015.
It's working and pretty fast (Though MATLAB's K-Means is faster).

Yet it seems no Multi Threading is done (I see it using the Resource Monitor in Windows 10).
I compiled it in Release Mode using Visual Studio /openmp flag following the instructions given by Eigen & Multi Threading.

Does Eigen use Multi Threading for Multiplication of Matrices (Large, I made sure they are large)?
If it does, how come it doesn't kick in in my case?

Are there any faster C / C++ K-Means Libraries out there?

Thank You.

For matrix-matrix products Eigen can use multi-threading if you enable OpenMP on your compiler. Search for the option in the project config.

Hi @ggael,

As you can see in my post above, I did turned on the OpenMP flag (/openmp in Visual Studio) to begin with as I read Eigen documentation.

Nothing happened.

Could you define "large" in your context. If it's only slightly larger than 16 then no multithreading occur. Also line 154, write Dist.noalias() = ... to avoid a temporary (not related to multithreading)

For instance X can be 1e5 x 20 and mu can be something like 20 x 20.

So D =120 > 16..

Moreover, since there is a "Broadcasting" there (The row k of Mu is subtracted from each row of X) and then very large matrix is sugared element wise and then summed I'd expect this to be parallelized.
Shouldn't Eigen parallelize it?

Regarding line 154, do you mean:

Dist = -2*(X.matrix() * Mu.transpose().matrix()); -> Dist.noalias() = -2*(X.matrix() * Mu.transpose().matrix());

By the way, could I add parallelization for the 'for' loop at 150?

Thank You.

I've improved the heuristic to compute the adequate number of multithreading threads in both the devel and 3.3 branch [1]. Feel free to give it a try now, or wait for 3.3.3.

[1] https://bitbucket.org/eigen/eigen/commits/4d09e90f07c8/

Hi,

I will give it a try.
Does Multi Threading work on Broadcasting Operations?

Eigen is great!

Royi wrote:Does Multi Threading work on Broadcasting Operations?

nope. but its cost is marginal compared to a matrix-matrix product (10000*120*20 vs 10000*20)