Channels ▼

Clay Breshears

Dr. Dobb's Bloggers

Quicksort Partition via Prefix Scan

July 02, 2012

So, here's what I've been building up to in the two previous posts. I'm going to describe how to put into effect the partition functionality of the Quicksort algorithm using the Prefix Scan operation. What this will do, if we have a manycore processor with a core for each of the M elements in the unsorted list, is to reduce the span (execution time) from the serial, O(M), to the seriously parallel O(log M). I saw a description of this attempt to make use of manycore parallelism and shorten the execution time of parallel codes in slides from the keynote address Guy Blelloch gave at the 2009 Principles and Practice of Parallel Programming (PPoPP) conference entitled "Parallel Thinking."

The operation that I'll use is a Binary Selection, which gathers together elements from a set that share a property. (I'm not sure if I just coined the term "Binary Selection," but I wanted a different name to avoid confusion with the other Selection algorithm that is used to pick the K-th largest element from an unordered set. Both of these operations can be done in parallel and rely on Prefix Scan as a component.) For the Partition phase of Quicksort I need to generate subsets of elements with three mutually exclusive properties: less than the pivot element, equal to the pivot element, and greater than the pivot element. I'm going to describe how to create the subset of "less than" elements since the same algorithm can be used for determining the other two subsets.

If you're like me, you can better learn a new algorithm (or most anything unfamiliar) if you have an example to illustrate the data manipulations of the algorithm. So, let me take a set of eight integers that we need to partition for upcoming Quicksort processing. Since I need to deal with the relative order between items, and it will likely be stored in an array structure, I'll think of my data as being stored in an array or vector.

Data vector to sort: [6 1 7 4 0 3 5 2]

The first step is to create a mask vector of the same length as the data vector. This vector will be used to show whether or not the associated data item has the desired property. Since this is a binary decision the values in the mask vector are 0 and 1. These should be the integer values, not the logical FALSE and TRUE, because I will need to do some arithmetic operations on the mask values in the next step.

To know whether or not a data item is less than the pivot value, I first need to have a pivot element. For this example, I will pick the value '4' to be my pivot value. Thus, my 8-element mask vector will be [0 1 0 0 1 1 0 1]. Since I'm assuming that there are eight processors available to do the simple comparison of one data element to the pivot value, this step takes constant time, O(1).

The second step is to run a Prefix Scan with addition on the mask vector. If I have zero-based indexing (C/C++, Java), I use an exclusive scan; if I have 1-based indexing (Fortran), I use an inclusive scan. As I showed in my previous post, this will be an O(log M) operation with M processors.

The result of the exclusive scan on my example mask vector is [0 0 1 1 1 2 3 3]. This result will best be copied into an array separate from the vector mask. It's not essential since there is a way to "recover" the original mask value of each position, but keeping the results separate from the source makes for a cleaner implementation.

The third step is a data movement step. Each processor will copy the associated value in the data vector that has a '1' in the mask to a new subset vector in preparation of a Quicksort recursive call (or new task for parallel execution) on that subset vector. The moves will be done in parallel, so I must ensure that each element is moved to a unique location. To do that, I use the scan result values as the destination indices to the new subset vector.

Look what I get when I line up the mask vector with the scan result vector:

[0 1 0 0 1 1 0 1]
[0 0 1 1 1 2 3 3]

Everywhere I have a "1" in the mask vector, there is a different number in the corresponding position of the scan results vector. In fact, reading from left to right, these "marked" values are consecutive from zero to one less than the number of data elements that are less than the pivot value. So, any processor with a "1" in the corresponding mask vector position can move, in parallel, its data value to the new subset vector indexed by the corresponding value in the scan results vector. And it's all done in O(1) time.

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