- CS-TR-3915, UMIACS-TR-98-38.
- To be presented at IPPS '99.
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 Silicon Graphics 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.
PostScript
or
Compressed PostScript
Version of this report.
For more infomation on any of the these topics, click on the hotlink.
Any queries, comments, or inquiries to:
David R. Helman
E-mail: helman@umiacs.umd.edu
Office phone: (301)405-6757
FAX: (301)314-9658
Return to the Experimental Parallel Algorithmics page.