Implementing the multiprefix operation on parallel and vector computers
Thomas J. Sheffler · 1993
For a sequence of n values, each with an associated integer label, the multiprefix operation calculates a partial sum for each value summing all preceding values with the same label, and for each label, a reduction value summing all values with that label.The multiprefix operation has been proposed as a parallel primitive because of its power for expressing many data parallel algorithms succinctly.However, most approaches to implementing this operation have been based on speciat hardware, limiting its usefulness.This paper presents an algorithm for the multiprefix operation on n elements that runs in S = 0(W) parallel steps on a p = @ processor CRCW-ARBITRARY PRAM.Because this algorithm performs only W = O(n) work, it is work efficient.While approaches based on sorting could be implemented in asymptotically fewer parallel steps, the work efficiency of this algorithm, and its low overhead make it attractive for use in real applications.A fully vectorized version of this algorithm has been designed for the CRAY Y-MP and provides good performance for a number of important algorithms.Performance data collected from integer sorting and sparse matrix-vector multiplication benchmarks based on the multiprefix operation achieve speeds that are often better than currently employed algorithms for that machine.