title: C OpenMP parallel quickSort
body: <p>Once again I'm stuck when using openMP in C++. This time I'm trying to implement a parallel quicksort.</p>
  
  <p><strong>Code:</strong></p>
  
  <pre><code>#include &lt;iostream&gt;
  #include &lt;vector&gt;
  #include &lt;stack&gt;
  #include &lt;utility&gt;
  #include &lt;omp.h&gt;
  #include &lt;stdio.h&gt;
  
  #define SWITCH_LIMIT 1000
  
  using namespace std;
  
  template &lt;typename T&gt;
  void insertionSort(std::vector&lt;T&gt; &amp;v, int q, int r)
  {
      int key, i;
      for(int j = q + 1; j &lt;= r; ++j)
      {
          key = v[j];
          i = j - 1;
          while( i &gt;= q &amp;&amp; v[i] &gt; key )
          {
              v[i+1] = v[i];
              --i;
          }
          v[i+1] = key;
      }
  }
  
  stack&lt;pair&lt;int,int&gt; &gt; s;
  
  template &lt;typename T&gt;
  void qs(vector&lt;T&gt; &amp;v, int q, int r)
  {
      T pivot;
      int i = q - 1, j = r;
      //switch to insertion sort for small data
      if(r - q &lt; SWITCH_LIMIT) 
      {
          insertionSort(v, q, r);
          return;
      }
  
      pivot = v[r];
      while(true)
      {
          while(v[++i] &lt; pivot);
          while(v[--j] &gt; pivot);
          if(i &gt;= j) break;
          std::swap(v[i], v[j]); 
      }
      std::swap(v[i], v[r]);
  
      #pragma omp critical
      {
          s.push(make_pair(q, i - 1));
          s.push(make_pair(i + 1, r));        
      }
  }
  
  int main()
  {
      int n, x;
      int numThreads = 4, numBusyThreads = 0;
      bool *idle = new bool[numThreads];
      for(int i = 0; i &lt; numThreads; ++i)
          idle[i] = true;
      pair&lt;int, int&gt; p;
      vector&lt;int&gt; v;
      cin &gt;&gt; n;
      for(int i = 0; i &lt; n; ++i)
      {
          cin &gt;&gt; x;
          v.push_back(x);
      }
      cout &lt;&lt; v.size() &lt;&lt; endl;
      s.push(make_pair(0, v.size()));
  
      #pragma omp parallel shared(s, v, idle, numThreads, numBusyThreads, p) 
      {
          bool done = false;
          while(!done) 
          {
              int id = omp_get_thread_num();
              #pragma omp critical
              {
                  if(s.empty() == false &amp;&amp; numBusyThreads &lt; numThreads) 
                  {
                      ++numBusyThreads;
                      //the current thread is not idle anymore
                      //it will get the interval [q, r] from stack
                      //and run qs on it
                      idle[id] = false;
                      p = s.top();                    
                      s.pop();
                  }
                  if(numBusyThreads == 0)
                  {
                      done = true;
                  }
              }
              if(idle[id] == false)
              {
  
                  qs(v, p.first, p.second);
                  idle[id] = true;
                  #pragma omp critical 
                  --numBusyThreads;
              }
  
          }
      }
      return 0;
  }
  </code></pre>
  
  <p><strong>Algorithm:</strong></p>
  
  <p>To use openMP for a recursive function I used a stack to keep track of the next intervals on which the qs function should run. I manually add the 1st interval [0, size] and then let the threads get to work when a new interval is added in the stack.</p>
  
  <p><strong>The problem:</strong></p>
  
  <p>The program ends too early, not sorting the array after creating the 1st set of intervals ([q, i - 1], [i+1, r] if you look on the code. My guess is that the threads which get the work, considers the local variables of the quicksort function(qs in the code) shared by default, so they mess them up and add no interval in the stack.</p>
  
  <p><strong>How I compile:</strong></p>
  
  <pre><code>g++ -o qs qs.cc -Wall -fopenmp
  </code></pre>
  
  <p><strong>How I run:</strong></p>
  
  <p><code>./qs &lt; in_100000 &gt; out_100000</code></p>
  
  <p>where in_100000 is a file containing 100000 on the 1st line followed by 100k intergers on the next line separated by spaces.</p>
  
  <p>I am using gcc 4.5.2 on linux</p>
  
  <p>Thank you for your help,</p>
  
  <p>Dan  </p>