Channels ▼

Clay Breshears

Dr. Dobb's Bloggers

Beneath the Planet of the Iterative Quicksort

October 18, 2011

In the parallel version of the aforementioned serial code, we would need to use the return value of the dequeue() method. The modification allows safe access to the empty queue. After testing the return value, the algorithm will realize there is nothing in the queue and then jump around the partitioning and queue loading code to begin another run through a while-loop iteration, which would simply repeat this pattern until Done was set to TRUE. This is a spin-wait (but you already knew that, right?). It's a pretty long one that simply spins the thread through a loop, doing nothing useful, until a conditional expression is met. We could write the spin-wait in a more recognizable fashion.

while(1) {
  while (Q.dequeue(&d) == EMPTY_QUEUE) { //spin };
  if (Done) break; // signal to terminate 
  . . .
  if (tCount == N) SetEvent(tSignal);   // Signal main thread that sorting is done
  . . . 

Another algorithmic change shown in the above code snippet is what to do when the count of sorted items reaches N. An event is signaled to some external thread (say, the main thread). The main thread, after launching the sorting threads, waits for the signal that the sort is complete and then sets Done to TRUE. Unfortunately, this won't allow the threads to stop execution of QuickSort() because all the sorting threads will be "stuck" in the short spin-wait loop. The only way to get them out is to put something into the queue that will break the conditional test of the queue being empty. Thus, after setting Done, the main thread should fill the queue with index pairs, one for each of the sorting threads. Subsequently, after a thread falls out of the spin-wait loop by retrieving something from the queue, it will find Done == TRUE and exit the function. (If we used the original while(1) loop as the spin-wait, threads would execute the test on Done as part of the spin-wait body and exit.)

That's one way to do it. It's not my favorite because of all the spin-wait execution. I'm not a big fan of consuming computational resources for any good reason if I can provide an alternative. For a parallel iterative Quicksort, I would keep a count of the number of items in the queue and only allow a thread to attempt access to the queue if there was something to be removed from the queue. When the queue is empty, threads should be blocked. For counting the number of resources available for use (or consumption), we have the Windows semaphore object available. The code here illustrates how I would apply semaphores to the parallel iterative QuickSort() function.

unsigned __stdcall QuickSort(LPVOID pArg)
{
  int p, r, q;
  qSortIndex d, d1, d2;
  long t = 0;

  while (1) {
    WaitForSingleObject(hSem, INFINITE); 
    if (Done) break; //external signal to terminate threads 
    Q.dequeue(&d);
    p = d.lo; r = d.hi;
    if (p < r) {
      q = Partition(p, r);
      InterlockedIncrement(&tCount);
      d1.lo = p; d1.hi = q-1;
      Q.enqueue(d1);
      d2.lo = q+1; d2.hi = r;
      Q.enqueue(d2);
      ReleaseSemaphore(hSem, 2, NULL);  // Two items added to queue; 
                                        // increment semaphore count by 2
    }
    else if (p == r) {
      t = InterlockedIncrement(&tCount);
      if (t == N) SetEvent(tSignal);   
    }
  } // while (1)
  return 0;
}

With the semaphore, hSem, keeping track of the number of index pairs on the queue, the first thing a sorting thread does is make sure that there is at least one item in the queue by testing the semaphore value. The WaitForSingleObject() call performs that test (and decrements a non-zero semaphore value). In addition, if the queue is empty, the thread blocks on this call until something is put into the queue and the semaphore value is no longer zero.

The value of the semaphore object is increased in two places. The first is shown in the code above. After partitioning the current sub-array, a thread puts the two index pairs into the shared queue and adds 2 to the semaphore value via the ReleaseSemaphore() call. The second place the semaphore value will be increased is back in the main thread. As in the code snippet above, after receiving the signal (sent when tCount has reached the desired value) the main thread sets Done, adds enough index pairs to the queue for each thread, and then sets the semaphore value to the number of threads executing QuickSort(). This releases the threads waiting on the semaphore value so they can test Done and exit gracefully.

By using the semaphore, threads no longer need to spin-wait when there is an empty queue. They will block until there is something in the queue to consume. The problem of separate function calls for testing an empty queue and for removing data from the queue alluded to in the fifth paragraph will be moot by using a semaphore. A thread is only allowed to access the queue if the semaphore value indicates there is something. It is like getting a table reservation at a restaurant. If there is a table available, your name is put on a list and you know there will be a table for your party even if someone else gets another table held for them after you, but the second party arrives before you do. The second party only got a reservation because there were at least two tables available and it doesn't matter which table each party gets (as long as it's not near the kitchen).

Next time: I've got one more look (for now) at Iterative Quicksort.

Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 


Video