title: no speedup using openmp + SIMD
body: <p>I am new to Openmp and now trying to use Openmp + SIMD intrinsics to speedup my program, but the result is far from expectation. </p>
  
  <p>In order to simplify the case without losing much essential information, I wrote a simplier toy example:</p>
  
  <pre><code>#include &lt;omp.h&gt;
  #include &lt;stdlib.h&gt;
  #include &lt;iostream&gt;
  #include &lt;vector&gt;
  #include &lt;sys/time.h&gt;
  
  #include "immintrin.h" // for SIMD intrinsics
  
  int main() {
      int64_t size = 160000000;
      std::vector&lt;int&gt; src(size);
  
      // generating random src data
      for (int i = 0; i &lt; size; ++i)
          src[i] = (rand() / (float)RAND_MAX) * size;
  
      // to store the final results, so size is the same as src
      std::vector&lt;int&gt; dst(size);
  
      // get pointers for vector load and store
      int * src_ptr = src.data();
      int * dst_ptr = dst.data();
  
      __m256i vec_src;
      __m256i vec_op = _mm256_set1_epi32(2);
      __m256i vec_dst;
  
      omp_set_num_threads(4); // you can change thread count here
  
      // only measure the parallel part
      struct timeval one, two;
      double get_time;
      gettimeofday (&amp;one, NULL);
  
      #pragma omp parallel for private(vec_src, vec_op, vec_dst)
      for (int64_t i = 0; i &lt; size; i += 8) {
          // load needed data
          vec_src = _mm256_loadu_si256((__m256i const *)(src_ptr + i));
  
          // computation part
          vec_dst = _mm256_add_epi32(vec_src, vec_op);
          vec_dst = _mm256_mullo_epi32(vec_dst, vec_src);
          vec_dst = _mm256_slli_epi32(vec_dst, 1);
          vec_dst = _mm256_add_epi32(vec_dst, vec_src);
          vec_dst = _mm256_sub_epi32(vec_dst, vec_src);
  
          // store results
          _mm256_storeu_si256((__m256i *)(dst_ptr + i), vec_dst);
      }
  
      gettimeofday(&amp;two, NULL);
      double oneD = one.tv_sec + (double)one.tv_usec * .000001;
      double twoD = two.tv_sec + (double)two.tv_usec * .000001;
      get_time = 1000 * (twoD - oneD);
      std::cout &lt;&lt; "took time: " &lt;&lt; get_time &lt;&lt; std::endl;
  
      // output something in case the computation is optimized out
      int64_t i = (int)((rand() / (float)RAND_MAX) * size);
      for (int64_t i = 0; i &lt; size; ++i)
          std::cout &lt;&lt; i &lt;&lt; ": " &lt;&lt; dst[i] &lt;&lt; std::endl;
  
      return 0;
  }
  </code></pre>
  
  <p>It is compiled using <code>icpc -g -std=c++11 -march=core-avx2 -O3 -qopenmp test.cpp -o test</code> and the elapsed time of the parallel part is measured. The result is as follows (the median value is picked out of 5 runs each):</p>
  
  <p><code>1 thread: 92.519</code></p>
  
  <p><code>2 threads: 89.045</code></p>
  
  <p><code>4 threads: 90.361</code></p>
  
  <p>The computations seem embarrassingly parallel, as different threads can load their needed data simultaneously given different indices, and the case is similar for writing the results, but why no speedups?</p>
  
  <p><strong>More information:</strong></p>
  
  <ol>
  <li><p>I checked the assembly code using <code>icpc -g -std=c++11 -march=core-avx2 -O3 -qopenmp -S test.cpp</code> and found vectorized instructions are generated;</p></li>
  <li><p>To check if it is memory-bound, I commented the computation part in the loop, and the measured time decreased to around <code>60</code>, but it does not change much if I change the thread count from <code>1 -&gt; 2 -&gt; 4</code>.</p></li>
  </ol>
  
  <p>Any advice or clue is welcome.</p>
  
  <p><strong>EDIT-1:</strong></p>
  
  <p>Thank @JerryCoffin for pointing out the possible cause, so I did the Memory Access Analysis using Vtune. Here are the results:</p>
  
  <p><code>1-thread: Memory Bound: 6.5%, L1 Bound: 0.134, L3 Latency: 0.039</code></p>
  
  <p><code>2-threads: Memory Bound: 18.0%, L1 Bound: 0.115, L3 Latency: 0.015</code></p>
  
  <p><code>4-threads: Memory Bound: 21.6%, L1 Bound: 0.213, L3 Latency: 0.003</code> </p>
  
  <p>It is an Intel 4770 Processor with 25.6GB/s (23GB/s measured by Vtune) max. bandwidth. The memory bound does increase, but I am still not sure if that is the cause. Any advice?</p>
  
  <p><strong>EDIT-2 (just trying to give thorough information, so the appended stuff can be long but not tedious hopefully):</strong></p>
  
  <p>Thanks for the suggestions from @PaulR and @bazza. I tried 3 ways for comparison. One thing to note is that the processor has <code>4</code> cores and <code>8</code> hardware threads. Here are the results:</p>
  
  <p>(1) just initialize <code>dst</code> as all zeros in advance: <code>1 thread: 91.922; 2 threads: 93.170; 4 threads: 93.868</code> --- seems not effective;</p>
  
  <p>(2) without (1), put the parallel part in an outer loop over 100 iterations, and measure the time of the 100 iterations: <code>1 thread: 9109.49; 2 threads: 4951.20; 4 threads: 2511.01; 8 threads: 2861.75</code> --- quite effective except for 8 threads;</p>
  
  <p>(3) based on (2), put one more iteration before the 100 iterations, and measure the time of the 100 iterations: <code>1 thread: 9078.02; 2 threads: 4956.66; 4 threads: 2516.93; 8 threads: 2088.88</code> --- similar with (2) but more effective for 8 threads.</p>
  
  <p>It seems more iterations can expose the advantages of openmp + SIMD, but the computation / memory access ratio is unchanged regardless loop count, and locality seems not to be the reason as well since <code>src</code> or <code>dst</code> is too large to stay in any caches, therefore no relations exist between consecutive iterations.</p>
  
  <p>Any advice?</p>
  
  <p><strong>EDIT 3:</strong></p>
  
  <p>In case of misleading, one thing needs to be clarified: in (2) and (3), the openmp directive is outside the added outer loop </p>
  
  <pre><code>#pragma omp parallel for private(vec_src, vec_op, vec_dst)
  for (int k = 0; k &lt; 100; ++k) {
      for (int64_t i = 0; i &lt; size; i += 8) {
          ......
      }
  }
  </code></pre>
  
  <p>i.e. the outer loop is parallelized using multithreads, and the inner loop is still serially processed. So the effective speedup in (2) and (3) might be achieved by enhanced locality among threads.</p>
  
  <p>I did another experiment that the the openmp directive is put inside the outer loop:</p>
  
  <pre><code>for (int k = 0; k &lt; 100; ++k) {
      #pragma omp parallel for private(vec_src, vec_op, vec_dst)
      for (int64_t i = 0; i &lt; size; i += 8) {
          ......
      }
  }
  </code></pre>
  
  <p>and the speedup is still not good: <code>1 thread: 9074.18; 2 threads: 8809.36; 4 threads: 8936.89.93; 8 threads: 9098.83</code>.</p>
  
  <p>Problem still exists. :(</p>
  
  <p><strong>EDIT-4:</strong></p>
  
  <p>If I replace the vectorized part with scalar operations like this (the same calculations but in scalar way):</p>
  
  <pre><code>#pragma omp parallel for
  for (int64_t i = 0; i &lt; size; i++) { // not i += 8
      int query = src[i];
      int res = src[i] + 2;
      res = res * query;
      res = res &lt;&lt; 1;
      res = res + query;
      res = res - query;
      dst[i] = res;
  }
  </code></pre>
  
  <p>The speedup is <code>1 thread: 92.065; 2 threads: 89.432; 4 threads: 88.864</code>. May I come to the conclusion that the seemingly embarassing parallel is actually memory bound (the bottleneck is load / store operations)? If so, why can't load / store operations well parallelized?</p>