title: OpenMP integral image slower then sequential
body: <p>I have implemented Summed Area Table (or Integral image) in C++ using OpenMP.</p>
  
  <p>The problem is that the Sequential code is always faster then the Parallel code even changing the number of threads and image sizes.</p>
  
  <p>For example I tried images from (100x100) to (10000x10000) and threads from 1 to 64, but none of the combination is ever faster.</p>
  
  <p>I also tried this code in different machines like:</p>
  
  <ul>
  <li>Mac OSX 1,4 GHz Intel Core i5 dual core</li>
  <li>Mac OSX 2,3 GHz Intel Core i7 quad core</li>
  <li>Ubuntu 16.04 Intel Xeon E5-2620 2,4 GHz 12 cores</li>
  </ul>
  
  <p>The time has been measured with OpenMP function: <code>omp_get_wtime()</code>.</p>
  
  <p>For compiling I use: <code>g++ -fopenmp -Wall main.cpp</code>.</p>
  
  <p>Here is the parallel code:</p>
  
  <pre><code>void transpose(unsigned long *src, unsigned long *dst, const int N, const int M) {
      #pragma omp parallel for
      for(int n = 0; n&lt;N*M; n++) {
          int i = n/N;
          int j = n%N;
          dst[n] = src[M*j + i];
      }
  }
  
  
  unsigned long * integralImageMP(uint8_t*x, int n, int m){
  
      unsigned long * out = new unsigned long[n*m];
      unsigned long * rows = new unsigned long[n*m];
  
      #pragma omp parallel for
      for (int i = 0; i &lt; n; ++i)
      {
          rows[i*m] = x[i*m];
          for (int j = 1; j &lt; m; ++j)
          {
              rows[i*m + j] = x[i*m + j] + rows[i*m + j - 1];
          }
      }
  
      transpose(rows, out, n, m);
  
      #pragma omp parallel for
      for (int i = 0; i &lt; n; ++i)
      {
          rows[i*m] = out[i*m];
          for (int j = 1; j &lt; m; ++j)
          {
              rows[i*m + j] = out[i*m + j] + rows[i*m + j - 1];
          }
      }
  
      transpose(rows, out, m, n);
  
      delete [] rows;
      return out;
  }
  </code></pre>
  
  <p>Here is the sequential code:</p>
  
  <pre><code>unsigned long * integralImage(uint8_t*x, int n, int m){
      unsigned long * out = new unsigned long[n*m];
  
      for (int i = 0; i &lt; n; ++i)
      {
          for (int j = 0; j &lt; m; ++j)
          {
              unsigned long val = x[i*m + j];
              if (i&gt;=1)
              {
                  val += out[(i-1)*m + j];
                  if (j&gt;=1)
                  {
                      val += out[i*m + j - 1] - out[(i-1)*m + j - 1];
                  }
              } else {
                  if (j&gt;=1)
                  {
                      val += out[i*m + j -1];
                  }
              }
              out[i*m + j] = val;
          }
      }
  
      return out;
  }
  </code></pre>
  
  <p>I also tried without the <code>transpose</code> but it was even slower probably because the cache accesses.</p>
  
  <p>An example of calling code:</p>
  
  <pre><code>int main(int argc, char **argv){
      uint8_t* image = //read image from file (gray scale)
      int height = //height of the image
      int width = //width of the image
  
      double start_omp = omp_get_wtime();
  
      unsigned long* integral_image_parallel = integralImageMP(image, height, width); //parallel
  
      double end_omp = omp_get_wtime();
  
      double time_tot = end_omp - start_omp;
  
      std::cout &lt;&lt; time_tot &lt;&lt; std::endl;
  
      start_omp = omp_get_wtime();
  
      unsigned long* integral_image_serial = integralImage(image, height, width); //sequential
  
      end_omp = omp_get_wtime();
  
      time_tot = end_omp - start_omp;
  
      std::cout &lt;&lt; time_tot &lt;&lt; std::endl;
  
      return 0;
  }
  </code></pre>
  
  <p>Each thread is working on a block of rows (maybe an illustration of what each thread is doing can be useful):
  <a href="https://i.stack.imgur.com/UySIJ.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/UySIJ.png" alt="enter image description here"></a>
  Where ColumnSum is done transposing the matrix and repeating RowSum.</p>