How much can matrix multiplication algorithm be parallelized? You all may know that simple Matrix Multiplication algorithm:

for(i = 0; i &lt; n; i++)
   for(j = 0; j &lt; n; j++)
      for(k = 0; k &lt; n; k++)
         C[i,j] += A[i,k] * B[k,j]
      end for
   end for
end for 


When we want to parallelize it, we can, at first, parallelize the outer loop,
which is the most easiest thing to understand, since it is clear that it does not have data dependencies with other loops.

Most tutorial on the web stops here, like we can not parallelize anymore.

But it seems for me that even the second outer loop (the one in the middle):

for(j = 0; j &lt; n; j++)


can be parallelized.

What about the inner loop?

Is thus possible to parallelize all three loops of a matrix multiplication algorithm or must we stop with parallelizing only the first two loops?
Ypu're starting from a completely wrong point. 

The execution time of matrix multiplication does not come from the number of multiplications and additions, it's the number of uncached memory accesses that kill you. Reading a number that's not in any processor cache takes about 100 times longer than a multiplication. 

So the first step is rearranging the order of operations to perform as many operations as possible using only data that is present in the fastest processor cache. That's your first step before you even think about doing things in parallel. 

The next step is adding multiple sums in parallel, still in one thread. Instead of summing up C[i,j] for example you add six sums C[i, j], C[i,j+1], C[i, j+2], C[i+1, j], C[i+1,j+1], C[i+1, j+2] in parallel. This means you are limited by the throughput of operations, not the latency. 

The next step is using SIMD instructions. Your processor quite likely has instructions that perform 2, 4 or 8 floating-point operations just as fast as a single floating-point operation. 

Once you have done all this, especially the first part where the work is divided up into "blocks", you can easily process multiple blocks on multiple threads. What you need to be careful about is that you have enough cache memory to do so.