Experimental Parallel Algorithmics
Experimental Data Sets:
Integers
Institute for Advanced Computer Studies
University of Maryland, College Park
Variables |
|
|---|---|
| n | total number of elements |
| p | number of processors |
| i | the processor number from ( 0 <= i <= p-1) |
[R] Random, entropy 31
[S] Random, entropy 6.2
[C] Consecutive
[N] NAS IS Benchmark data set
[A] Already Sorted
[Z] Zero Entropy
Random integers with entropy of 31 bits per key. Note that entropy of
31 implies that keys values are uniformly distributed in the range
[0,2^31).
Random integers with entropy of 6.2 bits per key. Note that entropy of
6.2 implies that each key is the result of the bitwise-AND boolean
operation applied to five successive keys of entropy 31.
Keys are consecutive in value (from 0 to n-1) and are
placed cyclically across the processors.
This input is taken from the NAS Parallel Benchmark
for Integer Sorting. Keys are integers in the range [0,2^19), and
each key is the average of four consecutive uniformly distributed
pseudo-random numbers generated by the following recurrence:
Processor i initially holds a sorted block of keys with values
from i × n/p to ((i+1) × n/p) - 1.
A zero entropy input, created by setting every value to a constant
such as zero.
Return to the Experimental Parallel Algorithmics Experimental Data Sets page.
dbader@umiacs.umd.edu
[R] Random, entropy 31
[S] Random, entropy 6.2
[C] Consecutive
[N] NAS IS Benchmark data set
where a=5^13 and the seed x[0] = 314159265.
Thus, the distribution of the key values is a Gaussian approximation.
On a p-processor machine, the first n/p generated keys
are assigned to processor 0, the next n/p to processor
1, and so forth, until each processor has n/p keys.
[A] Already Sorted
[Z] Zero Entropy
