Databases
StackOverflow2013
Postsdbo
POC OpenMP parallel quickSort
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POC OpenMP parallel quickSort
    primarykey
    data
    text
    <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>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USsehe
    1. USDan Lincan
    plurals
    1. This table or related slice is empty.
    1. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POC OpenMP parallel quickSort
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POC OpenMP parallel quickSort
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POC OpenMP parallel quickSort
      1. USAdri C.S.
      1. VTFavorite
    1. COLast time I did omp (or even pthread) parallel sort, it was slower than serial + recursive. Unless you're sure that the **serialness** of the sort is the bottleneck, you're doing premature optimization.
      singulars
      1. POC OpenMP parallel quickSort
      1. USmoshbear
    2. COI am sure that the parallel solution should perform better. However I am learning to use openMP and I don't have in depth knowledge on what's really going on backstage.
      singulars
      1. POC OpenMP parallel quickSort
      1. USDan Lincan
    3. COOn a merge sort of 1,000,000 elements, parallelism had too high overhead. And you can't be 100% sure without a profiler and hard numbers. That being said, this isn't that bad of an exercise for learning omp, or pthreads for that matter. Pthreads is going to be a bit easier because it's easier to make recursive threads. That being said, you should use a thread pool and allocate helpers to the pool. Don't forget to use locking on the globals to avoid race conditions, deadlocks, and other nastiness.
      singulars
      1. POC OpenMP parallel quickSort
      1. USmoshbear
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload