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.