Speed Up Matrix Multiplication with OpenMP and Block Method: Can I Do Better?

Question

This is the code I wrote:

#include <omp.h>
void matrix_multi(int c[][TSIZE], int a[][TSIZE], int b[][TSIZE])
{
   int B=8;

  int i, j, k,i1,j1,k1;
#pragma omp parallel for private(i,j,k,i1,j1,k1) schedule(auto) collapse(3)
  for (i=0; i<TSIZE; i+=B)
    for (j=0; j<TSIZE; j+=B)
      for (k=0; k<TSIZE; k+=B)
        for (i1=i;i1<i+B;i1++)
          for (j1=j;j1<j+B;j1++)
            {
              int sum=0;
              for (k1=k;k1<k+B;k1++)
                {
                  sum+=a[i1][k1]*b[k1][j1];
                }
              c[i1][j1]+=sum;
            }

}

My question is: Can I get a better performance with some further manipulation on three inner loops?

Answer 1

Linear algebra is one of the most common operations computers perform. In games and graphics libraries it is THE most common operation. It has been studied and optimized heavily, with entire research groups dedicated to it.

If you care about speed, you should be performing matrix multiplication with a BLAS library. Some of the things that a BLAS library will optimize for:

• minimize cache-misses by performing the matrix multiplication in blocks rather than looping over the entire matrix
• optimize the block size for the cache-size of the computer
• if the computer/CPU has multiple cache levels, use multiple optimized block size levels
• use SIMD instructions if available on the CPU

Note that parallelization is not on the list. This is because in today's computers memory access is slower than the CPU. You will see worse performance with openmp due to the overhead of context switching.

Answer 2

It seems that you are far away from fully optimized. Have you tried loop unroll, loop inversion, etc.?

You could refer to the following link for a step by step optimization on matrix multiplication.

http://wiki.cs.utexas.edu/rvdg/HowToOptimizeGemm/