Implementing the multiprefix operation efficiently
Evan Reid Cohn · Journal of Parallel and Distributed Computing · 1990
Abstract The multiprefix operation is a parallel primitive operation of significant generality. It is, for example, one of the two basic primitives proposed for the Fluent abstract machine [10]. It also subsumes the fetch-and-op primitive of the NYU Ultracomputer [6] and the scan operation of the Connection machine [2]. Ranade et al. [10] present an efficient randomized implementation of the multiprefix operation. In this paper, we present an efficient deterministic implementation of the multiprefix operation for the hypercube. This implementation can be used as a paradigm for implementing this primitive efficiently on other networks, such as the shuffle-exchange, mesh, butterfly, and mesh-of-trees [4] . We arrive at our implementation of the multiprefix operation in two steps. We first present an efficient implementation of another parallel primitive operation, Hillis' β operation [7], in terms of a number of simple primitives. We then show that this implementation can be modified to create an implementation for the multiprefix operation without increasing the use of any of the simple primitives by more than a constant factor.