Experimental Parallel Algorithmics

Experimental Data Sets:

Variables
n	total number of elements
p	number of processors
i	the processor number from (0 <= i <= p-1)
h	an h-relation, where h is a multiple of n/p

Our input of size n is initially distributed cyclically across the p processors such that each processor i initially holds n/p keys, for (0 <= i <= p-1).
For h = n/p the input consists of v[0] = n/p keys labelled for P0, followed by v[1] = n/p keys labelled for P1, and so forth, (with v[i] = n/p keys labelled for Pi), with the last v[p-1] = n/p keys labelled for P[p-1].
For h > n/p, instead of an equal number of elements destined for each processor, the function v[i], for (0 <= i <= p-1), is characterized by

floor(h × {1 - [h / (2n-h)] i})	if i < 2n/h and i < p-1
0	if 2n/h <= i < p-1
n - Sum(from j=0 to 2n/h - 1) [floor(h × {1 - [h / (2n-h)] j})]	if i = p-1

dbader@umiacs.umd.edu