title: Matrix multiplication sequential vs parallel performance test
body: <p>I am doing performance tests on an algorithm I wrote for parallel matrix multiplication in Java.
  I get the number of cpu cores from runtime, then divide the calculation loop between the available cores, using a thread pool. I measure the run times of the sequential and parallel version, then display the results in an excel chart.
  There I noticed a strange behavior:
  <img src="https://i.stack.imgur.com/RIyhG.png" alt="enter image description here"></p>
  
  <p>This is a performance test of matrix multiplication of square matrices from size 50 to size 1500. The results are an average calculated from 10 runs. The measurements are indicated by dots on the lines and the lines themselves are smoothed.
  As you can see, the lines of the sequential and parallel functions cross two times. Actually, three times, but the first one is around the matrix sizes 60-80, hence not visible in this chart. That is normal, since threads introduce overhead, so fast functions run better sequentially.</p>
  
  <p>Are the other two intersections normal? I have done multiple measurements in the 500-700 region, this behavior seems prevalent.</p>
  
  <p>Things I think could play part in this: OS thread management, JVM thread management, some thread pool-specific behavior, Intel Hyper Threading (since I have an intel i5-3210M cpu in my machine).
  However, what seems to be behaving irregularly (to me, at least) is actually the sequential algorithm. Notice how, until it hits a size of 650, it barely suffers any time penalty. Then it steepens abruptly at a size of 650.
  In comparison, the parallel curve seems pretty smooth.</p>
  
  <p>I have checked the algorithms a few times, I'm pretty sure they are bug-free. The results of the calculations are correct, that's for sure.
  My functions are measured in a double loop: the outer one repeats the measurements for later averaging and the inner one increases the matrix size every step.
  Inside that, the source matrices are randomized, the sequential function is run and measured, then the parallel one is run and measured.</p>
  
  <p>Is the behavior on the chart normal?</p>
  
  <p>In main:</p>
  
  <pre><code>    // do n measurements
      for (int n = 0; n &lt; measurements; ++n) {
          // display progress
          System.out.println("Progress: " + (float) n / measurements * 100 + "%");
          // single measurement
          for (int i = 0, size_n = size; i &lt; steps; ++i, size_n += increment) {
  
              // allocate memory for matrices: source a, source b, result
              float[][] src_a_seq = new float[size_n][size_n];
              float[][] src_b_seq = new float[size_n][size_n];
              float[][] src_a_par = new float[size_n][size_n];
              float[][] src_b_par = new float[size_n][size_n];
              float[][] res_seq = new float[size_n][size_n];
              float[][] res_par = new float[size_n][size_n];
  
              // fill source matrices with random values
              miscManager.genRandMatrix(src_a_seq, size_n);
              miscManager.genRandMatrix(src_b_seq, size_n);
              miscManager.genRandMatrix(src_a_par, size_n);
              miscManager.genRandMatrix(src_b_par, size_n);
  
              // create time variables
              long before, after, delta_t;
  
              // time measurement, serial multiplication
              before = System.nanoTime();
              serialMultiplier.mul(src_a_seq, src_b_seq, res_seq, size_n);
              after = System.nanoTime();
              delta_t = after - before;
              // add measurement to data
              data[i][0] += delta_t;
  
              // time measurement, parallel multiplication
              before = System.nanoTime();
              parallelMultiplier.mul(src_a_par, src_b_par, res_par, size_n);
              after = System.nanoTime();
              delta_t = after - before;
              // add measurement to data
              data[i][1] += delta_t;
          }
      }
      System.out.println("Progress: 100.0%");
  </code></pre>
  
  <p>serial multiplication:</p>
  
  <pre><code>public void mul(float[][] src_a, float[][] src_b, float[][] res, int size) {
      for (int i = 0; i &lt; size; ++i) {
          for (int j = 0; j &lt; size; ++j) {
              res[i][j] = 0;
              for (int k = 0; k &lt; size; k++) {
                  res[i][j] += src_a[i][k] * src_b[k][j];
              }
          }
      }
  }
  </code></pre>
  
  <p>parallel multiplication:</p>
  
  <pre><code>public void mul(float[][] src_a, float[][] src_b, float[][] res, int size) {
  
      // calculate data required for labor division
      int n = size * size;
      int load = n / cpuCoreCount + 1;
      int remainder = n % cpuCoreCount;
  
      // create thread pool
      ExecutorService taskExecutor = Executors.newFixedThreadPool(cpuCoreCount);
  
      // assign tasks
      int m = 0;
      int i = 0;
      while (i &lt; remainder) {
          taskExecutor.execute(new MultiplierUnit(src_a, src_b, res, size, m, m + load));
          m += load;
          ++i;
      }
      --load;
      while (i &lt; cpuCoreCount) {
          taskExecutor.execute(new MultiplierUnit(src_a, src_b, res, size, m, m + load));
          m += load;
          ++i;
      }
  
      // wait for tasks to finish
      taskExecutor.shutdown();
      try {
        taskExecutor.awaitTermination(Long.MAX_VALUE, TimeUnit.NANOSECONDS);
      } catch (InterruptedException e) {
          System.out.println("error: thread pool interrupted exception");
          System.exit(-1);
      }
  }
  </code></pre>
  
  <p>The values in the data array are later divided by "measurements" to get the average.</p>
  
  <p>MultiplierUnit:</p>
  
  <pre><code>public class MultiplierUnit implements Runnable {
  
      // source a, source b, result
      private final float[][] src_a, src_b, res;
      // matrix dimensions, first entry to execute, last entry to execute
      private final int size, first, last;
  
      public MultiplierUnit(float[][] src_a, float[][] src_b, float[][] res,
              int size, int first, int last) {
          this.src_a = src_a;
          this.src_b = src_b;
          this.res = res;
          this.size = size;
          this.first = first;
          this.last = last;
      }
  
      // parallel multiplication
      @Override
      public void run() {
          // index setup
          int i = first / size;
          int j = first % size;
          int n = first;
  
          // computation
          while (n &lt; last) {
              while (j &lt; size &amp;&amp; n &lt; last) {
                  res[i][j] = 0;
                  for (int k = 0; k &lt; size; k++) {
                      res[i][j] += src_a[i][k] * src_b[k][j];
                  }
                  ++n;
                  ++j;
              }
              j = 0;
              ++i;
          }
      }
  }
  </code></pre>