Prefix computations on symmetric multiprocessors

We introduce a new prefix computation algorithm on linked lists which build s upon the sparse ruling set approach of Reid-Miller and Blelloch. Besides being somewhat simpler and requiring nearly half the number of memory acces ses, we can bound our complexity with high probability instead of merely on average. Moreover, whereas Reid-Miller and Blelloch targeted their algorit hm for implementation on a vector multiprocessor architecture, we develop o ur algorithm for implementation on the symmetric multiprocessor architectur e (SMP). These symmetric multiprocessors dominate the high-end server marke t and are currently the primary candidate for constructing large scale mult iprocessor systems. Our prefix computation algorithm was implemented in C u sing POSIX threads and run on four symmetric multiprocessors: the HP-Convex Exemplar (S-Class), the IBM SP-2 (High Node), the SGI Power Challenge, and the DEC AlphaServer. We ran our code using a variety of benchmarks which w e identified to examine the dependence of our algorithm on memory access pa tterns. For some problems, our algorithm actually matched or exceeded the p erformance 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 t o 16 processors, which was the largest platform available to us, (C) 2001 A cademic Press.