title: Matrix multiplication, KIJ order, Parallel version slower than non-parallel
body: <p>I have a school task about paralel programming and I'm having a lot of problems with it.
  My task is to create a parallel version of given matrix multiplication code and test its performence (and yes, it has to be in KIJ order):</p>
  <pre><code>void multiply_matrices_KIJ()
  {
      for (int k = 0; k &lt; SIZE; k++)
          for (int i = 0; i &lt; SIZE; i++)
              for (int j = 0; j &lt; SIZE; j++)
                  matrix_r[i][j] += matrix_a[i][k] * matrix_b[k][j];
  }
  </code></pre>
  <p>This is what I came up with so far:</p>
  <pre><code>void multiply_matrices_KIJ()
  {
      for (int k = 0; k &lt; SIZE; k++)
  #pragma omp parallel
      {
  #pragma omp for schedule(static, 16)
          for (int i = 0; i &lt; SIZE; i++)
              for (int j = 0; j &lt; SIZE; j++)
                  matrix_r[i][j] += matrix_a[i][k] * matrix_b[k][j];
      }
  }
  </code></pre>
  <p>And that's where i found something confusing to me. This parallel version of the code is running around 50% slower than non-parallel one. The difference in speed varies only a little bit based on the matrix size (tested SIZE = 128, 256, 512, 1024, 2048, and various schedule versions - dynamic, static, w/o it at all etc. so far).</p>
  <p>Can someone help me understand what am I doing wrong? Is it maybe because I'm using the KIJ order and it won't get any faster using openMP?</p>
  <h1>EDIT:</h1>
  <p>I'm working on a Windows 7 PC, using Visual Studio 2015 Community edition, compiling in Release x86 mode (x64 doesn't help either). My CPU is: Intel Core i5-2520M CPU @ 2,50GHZ (yes, yes it's a laptop, but I'm getting same results on my home I7 PC)</p>
  <p>I'm using global arrays:</p>
  <pre><code>float matrix_a[SIZE][SIZE];    
  float matrix_b[SIZE][SIZE];    
  float matrix_r[SIZE][SIZE];
  </code></pre>
  <p>I'm assigning random (float) values to matrix a and b, matrix r is filled with 0s.</p>
  <p>I've tested the code with various matrix sizes so far (128, 256, 512, 1024, 2048 etc.). For some of them it is intended NOT to fit in cache.
  My current version of code looks like this:</p>
  <pre><code>void multiply_matrices_KIJ()
  {
  #pragma omp parallel 
      {
      for (int k = 0; k &lt; SIZE; k++) {
  #pragma omp for schedule(dynamic, 16) nowait
          for (int i = 0; i &lt; SIZE; i++) {
              for (int j = 0; j &lt; SIZE; j++) {
                  matrix_r[i][j] += matrix_a[i][k] * matrix_b[k][j];
              }
          }
      }
      }
  }
  </code></pre>
  <p>And just to be clear, I know that with different ordering of loops I could get better results but that is the thing - I HAVE TO use KIJ order. My task is to do the KIJ for loops in parallel and check the performence increase. My problem is that I expect(ed) at least a little faster execution (than the one im getting now which it between 5-10% faster at most) even though it's the I loop that is in parallel (can't do that with K loop because I will get incorrect result since it's matrix_r[i][j]).</p>
  <p>These are the results I'm getting when using the code shown above (I'm doing calculations hundreds of times and getting the average time):</p>
  <h2>SIZE = 128</h2>
  <ul>
  <li>Serial version : 0,000608s</li>
  <li>Parallel I, schedule(dynamic, 16): 0,000683s</li>
  <li>Parallel I, schedule(static, 16): 0,000647s</li>
  <li>Parallel J, no schedule:    0,001978s    (this is    where I exected
  way    slower execution)</li>
  </ul>
  <h2>SIZE = 256</h2>
  <ul>
  <li>Serial version: 0,005787s</li>
  <li>Parallel I, schedule(dynamic, 16): 0,005125s</li>
  <li>Parallel I, schedule(static, 16): 0,004938s</li>
  <li>Parallel J, no schedule:    0,013916s</li>
  </ul>
  <h2>SIZE = 1024</h2>
  <ul>
  <li>Serial version: 0,930250s</li>
  <li>Parallel I, schedule(dynamic, 16): 0,865750s</li>
  <li>Parallel I, schedule(static, 16): 0,823750s</li>
  <li>Parallel J, no schedule: 1,137000s</li>
  </ul>