# Parallelization of element-wise matrix multiplication

I use Armadillo as an interface to OpenBLAS. In my current program, I have a loop, in which I do multiplications of the form

for(long t = t0; t < t1; t+=tStep)
{
stateMatrix %= elementWiseEvolutionMatrix;
}


The operator % is an element-wise multiplication operator. The problem here is that for matrices of side length of 500+ (the ones I have at hand), I can see that there is no parallelization whatsoever. Now I would like to point out that normal matrix multiplication is parallelized. But this kind of element-wise multiplication is not parallelized.

How do I know that? Because I go to htop in my linux system, and I see that only one core is busy, while if I do the same with normal matrix multiplication, I see that all cores go busy.

Now I tried to manually parallelize this with OpenMP, but no luck. I tried:

for(long t = t0; t < t1; t+=tStep)
{
#pragma omp parallel for
for(long i = 0; i < static_cast<long>(stateMatrix.n_rows); i++)
{
stat1eMatrix.row(i) %= elementWiseEvolutionMatrix.row(i);
}
}


But this got all the cores busy, but the program became about a factor of 10 slower.

My question: How can I get the element-wise multiplication to be as fast as possible with parallelization?

Thanks.

EDIT: I would like to point out that I'm more than happy to use another library for the element-wise multiplication, if necessary.

• To speed up your first code, use the -O3 optimization switch in GCC or clang (or the equivalent in MSVC) to enable auto-vectorization. This will make Armadillo use SSE2 instructions. For even more speed, use -O3 -march=native, which will enable AVX instructions. More information is on the Armadillo FAQ page. – mtall Aug 4 '15 at 16:07
• Another observation: Armadillo uses column-major layout, so to get best performance you need to work on columns instead of rows. – mtall Aug 4 '15 at 16:10

There's no element wise multiplication operation in the BLAS library. Your best approach is probably to just implement the operation yourself using (e.g.) OpenMP threading.

Before you do this, you should consider Amdahl's law and whether speeding up this bit of your code is really going to help- chances are that these elementwise multiplications are not where your code is spending most of its time, and as a result you probably won't see much speedup from parallelizing this part of your code.

• Thanks for your response. I'm sure that this part of my code is what makes it slow, because it's THE ONLY part of my code that is being executed in a loop while I measure performance (beside a part that involves only additions, which is way more trivial that multiplications). I've mentioned trying to parallelize this myself with OpenMP and failed. If you have a model that could provide better results, please go ahead, I'd appreciate it. This portion of the code can be fully parallelized because all that matters is element-wise matrix multiplication. Thanks again for trying to help. – The Quantum Physicist May 9 '15 at 23:40
• Btw, I'm more than happy to use another library that could do the element-wise multiplication more efficiently. – The Quantum Physicist May 10 '15 at 0:01
• How large is n_rows? – Brian Borchers May 10 '15 at 0:17
• It's 2^n, where n could go to 15. Right now n=9, meaning that n_rows is 512. – The Quantum Physicist May 10 '15 at 0:23
• and the number of columns? – Brian Borchers May 10 '15 at 0:31

First off, I agree with Brian Borchers comments about profiling to make sure these element-wise multiplications are where your performance issue lies. However, since you are convinced that is your problem, here is another suggestion.

Before trying to exploit multiple CPU, I would make sure that you have an implementation that exploits vectorization. The SSE2 instruction set (available in most modern processors) has an operation to multiply vectors of double precision floating point numbers. Your code may or may not allow your compiler to exploit this instruction.

As far as I know, Armadillo does not have any direct support for SSE2. But since you indicated a willingness to switch libraries, the Eigen library (http://eigen.tuxfamily.org/index.php?title=Main_Page) definitely does generate code using the SSE2 instructions. This could give you a 4x improvement for single precision multiplies and 2x improvement for double precision. If you are fortunate enough to have a CPU that supports the AVX instruction set, the development version of Eigen supports this to provide additional speedup.

• +1 for suggesting Eigen with SSE2. Thanks. – The Quantum Physicist May 10 '15 at 1:06
• Armadillo can use SSE2, SSE3, AVX, etc (ie. SIMD instructions). Just use the -O3 optimization switch in GCC or clang, or the equivalent in MSVC. For even more speed, use -O3 -march=native. More information is on the Armadillo FAQ page. – mtall Aug 4 '15 at 16:05