Sorting Benchmarks

Our nine sorting benchmarks are defined as follows, in which n and p are assumed for simplicity but without loss of generality to be powers of two and , the maximum value allowed for doubles, is approximately .

1. Uniform [U], a uniformly distributed random input, obtained by calling the C library random number generator random(). This function, which returns integers in the range 0 to , is seeded by each processor with the value (21 + 1001i). For the double data type, we ``normalize'' the integer benchmark values by first subtracting the value and then scaling the result by .
2. Gaussian [G], a Gaussian distributed random input, approximated by adding four calls to random() and then dividing the result by four. For the double data type, we normalize the integer benchmark values in the manner described for [U].
3. Zero [Z], a zero entropy input, created by setting every value to a constant such as zero.
4. Bucket Sorted [B], an input that is sorted into p buckets, obtained by setting the first elements at each processor to be random numbers between 0 and , the second elements at each processor to be random numbers between and , and so forth. For the double data type, we normalize the integer benchmark values in the manner described for [U].
5. g-Group [g-G], an input created by first dividing the processors into groups of consecutive processors of size g, where g can be any integer which partitions p evenly. If we index these groups in consecutive order from 1 up to , then for group j we set the first elements to be random numbers between and , the second elements at each processor to be random numbers between
   and , and so forth. For the double data type, we normalize the integer benchmark values in the manner described for [U].
6. Staggered [S], created as follows: if the processor index i is less than or equal to , then we set all elements at that processor to be random numbers between and . Otherwise, we set all elements to be random numbers between and . For the double data type, we normalize the integer benchmark values in the manner described for [U].
7. Worst-Load Regular [WR] - an input consisting of values between 0 and designed to induce the worst possible load balance at the completion of our regular sorting. Specifically, at the completion of sorting, the odd-indexed processors will hold elements, whereas the even-indexed processors will hold elements. The benchmark is defined as follows. At processor , for odd values of j between 1 and (p - 2), the elements with indices through are set to random values between and , the elements with indices through are set to , the elements with indices through are set to random values between and , and the element with index is set to . At processor , for j equal to (p - 1), the elements with indices through are set to random values between and , the elements with indices through are set to , and the elements with indices through are set to random values between and . At processor (i > 1), for odd values of j between 1 and p, the elements with indices through are set to random values between and , the elements with index is set to , and the elements with indices through are set to random values between and . For the double data type, we normalize the integer benchmark values in the manner described for [U].
8. Deterministic Duplicates [DD], an input of duplicates in which we set all elements at each of the first processors to be , all elements at each of the next processors to be , and so forth. At processor , we set the first elements to be , the next elements to be , and so forth.
9. Randomized Duplicates [RD], an input of duplicates in which each processor fills an array T with some constant number range (range is 32 for our work) of random values between 0 and (range - 1) whose sum is S. The first values of the input are then set to a random value between 0 and (range - 1), the next values of the input are then set to another random value between 0 and (range - 1), and so forth.

See [14] for a detailed justification of these benchmarks.