TY - CONF
T1 - Prefix computations on symmetric multiprocessors
T2 - Parallel and Distributed Processing, 1999. 13th International and 10th Symposium on Parallel and Distributed Processing, 1999. 1999 IPPS/SPDP. Proceedings
Y1 - 1999
A1 - Helman,D.R.
A1 - JaJa, Joseph F.
KW - access
KW - algorithms;
KW - AlphaServer;HP-Convex
KW - approach;symmetric
KW - architecture;symmetric
KW - Challenge;high-end
KW - computations;scalable
KW - DEC
KW - Exemplar;IBM
KW - Graphics
KW - market;large
KW - multiprocessor
KW - multiprocessors;Unix;distributed
KW - patterns;prefix
KW - performance;sparse
KW - power
KW - ruling
KW - scale
KW - server
KW - set
KW - SP-2;POSIX
KW - systems;memory
KW - threads;Silicon
AB - 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 (1996) 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 four symmetric multiprocessors-the IBM SP-2 (High Node), the HP-Convex Exemplar (S-Class), the DEC AlphaServer; and the Silicon Graphics Power Challenge. 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 performance of the standard 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 achieved scalable performance with up to 16 processors, which was the largest platform available to us
JA - Parallel and Distributed Processing, 1999. 13th International and 10th Symposium on Parallel and Distributed Processing, 1999. 1999 IPPS/SPDP. Proceedings
M3 - 10.1109/IPPS.1999.760427
ER -