Prefix Computations on Symmetric Multiprocessors
Prefix Computations on Symmetric Multiprocessors
Files
Publication or External Link
Date
1998-10-15
Authors
Helman, David R.
JaJa, Joseph
Advisor
Citation
DRUM DOI
Abstract
We introduce a new optimal prefix computation algorithm on linked lists
which builds upon the sparse ruling set approach of Reid-Miller and Blelloch.
Besides being somewhat simpler and requiring nearly half the number of memory
accesses, we can bound our complexity with high probability instead of merely
on average. Moreover, whereas Reid-Miller and Blelloch targeted their
algorithm for implementation on a vector multiprocessor architecture, we
develop our algorithm for implementation on the symmetric multiprocessor
architecture (SMP). These symmetric multiprocessors dominate the high-end
server market and are currently the primary candidate for constructing large
scale multiprocessor systems. Our prefix computation algorithm was
implemented in C using POSIX threads and run on three symmetric
multiprocessors - the DEC AlphaServer, the SGI Power Challenge, and the
HP-Convex Exemplar. We ran our code using a variety of benchmarks which we
identified to examine the dependence of our algorithm on memory access
patterns. For some problems, our algorithm actually matched or exceeded the
optimal sequential solution using only a single thread. Moreover, in spite
of the fact that the processors must compete for access to main memory,
our algorithm still resulted in scalable performance up to 16 processors,
which was the largest platform available to us.
(Also cross-referenced as UMIACS-98-38)