wcs@skep2.ATT.COM (Bill.Stewart.<wcs@skep2.ATT.COM>) (04/27/88)
I'm trying to find good algorithms for sorting and scatter/gather for
vector machines in general, but for Cray and Alliant in particular.
I'm interested both in general theory and cookbooks;
in addition to good references, pointers to built-in routines on those
machines would be nice.
Batcher's bitonic sort takes N log**2(N) time, and can use up to N processors.
However, N*sqrt(n) is less than N log**2(N) for N < 64K, so those
algorithms are worth considering.
The sorting problems I'm tring to solve are typically <128 items, with
a lot of zero items, and I'm primarily concerned with minimum-delay sorting.
The Cray typically has 128-vectors/processor; the Alliant has 8
processors with 32 vectors/processor, and a compiler which tries to
vectorize inner loops and parallelize the next outer loop.
In both cases, crude algorithms which keep all the processors full are
valuable; if I had a scatter/gather taking N*sqrt(N) or less it would
be easy to adapt counting-sort to run very fast.
By scatter-gather I mean the problem of
Given X[i] = {0,1}, find
Y[] = { i such that X[i] = 0 } and
Z[] = { i such that X[i] = 1 }
--
# Thanks;
# Bill Stewart, AT&T Bell Labs 2G218, Holmdel NJ 1-201-949-0705 ihnp4!ho95c!wcs
# skep2 is a local machine I'm trying to turn into a server. Please send
# mail to ho95c or ho95e instead. Thanks.