title: Prefix sums taking too long OpenMP
body: <p>I am implementing the prefix sums problem in OpenMP and I don't seem to get any speedup. Actually, the parallel implementation is taking longer than the sequential one. </p>
  
  <p>Here is my code for the prefix sums:</p>
  
  <pre><code>for (k = 1; k &lt; n; k = kk) {
      kk = k &lt;&lt; 1;
  
      #pragma omp parallel for 
      for (i = kk - 1; i &lt; n; i += kk) {
          x[i] = x[i-k] + x[i];
      }
   }
  
  for (k = k &gt;&gt; 1; k &gt; 1; k = kk) {
      kk = k &gt;&gt; 1;
  
      #pragma omp parallel for
      for (i = k - 1; i &lt; n - kk; i += k) {
          x[i + kk] = x[i] + x[i + kk];
      }
  }
  </code></pre>
  
  <p>I compiled this using gcc -fopenmp -O3 prefix_sums.c. The results that I get for 1 000 000 integers are:</p>
  
  <p>for the sequential implementation (compiled also with -O3):</p>
  
  <pre><code>0.001132
  0.000929
  0.000872
  0.000865
  0.000842
  </code></pre>
  
  <p>for the parallel implementation (5 re-runs on 4 cores):</p>
  
  <pre><code>0.025851
  0.005493
  0.006327
  0.007092
  0.030720
  </code></pre>
  
  <p>Could someone explain me what the problem could be? The implementation is giving the correct output, but why does it take so long?</p>
  
  <p>Thank you.</p>