Table of Contents


qutil_qsort, qutil_mergesort - sorts an array of doubles in parallel


#include <qthread.h>
#include <qthread/qutil.h>

qutil_qsort (double *array, size_t length);

qutil_mergesort (double *array, size_t length);


These functions take as input an array of length numbers and sorts their values.

In qutil_qsort(), large amounts of parallelism is achieved by using a strided lagging-loop structure for the partitioning phases of the sort, and a tree structure (with a minimum leaf-size) for the divide-and-conquer phases of the sort. The design is based, partly, upon work done by CRAY for their MTA-threaded quicksort. For sufficiently small arrays or sub-arrays, the libc qsort() function is used.

In qutil_mergesort(), the parallelism is achieved solely from the obvious divide-and-conquer tree. The merge phases of the algorithm use an in-place merge rather than a lookaside merge. As a result, the merge phases are rather computationally intensive. (This sort exists primarily as a proof of concept rather than as a useful alternative.)

The parallelism in these sorts is NOT limited by the futurelib resource restrictions, because of the divide-and-conquer trees in both. Future implementations may use the futurelib if and when futurelib is reimplemented to allow forward progress without exceeding memory restrictions (significantly) even when there are an extremely large number of futures attempting to spawn new futures.

The result of the sort is an array in increasing order.

See Also

qutil_double_sum(3) , qutil_double_mult(3) , qutil_double_min(3) , qutil_double_max(3) , qutil_uint_sum(3) , qutil_uint_mult(3) , qutil_uint_min(3) , qutil_uint_max(3) , qutil_int_sum(3) , qutil_int_mult(3) , qutil_int_min(3) , qutil_int_max(3) , qsort(3)

Table of Contents