Implementing the Multiprefix Operation on Parallel and Vector Computers

摘要

For an ordered set of n values, each with an associated integer label, themultiprefix operation calculates a partial sum for each value that is the sum of all preceding values with the same 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 used integer sorting to gather elements with the same label together or have suggested special hardware. In this paper we present a work efficient algorithm for the multiprefix operation on n elements that runs in S =