Two Efficient Message-passing Exclusive Scan Algorithms

Jesper Larsson Träff · 2026

Read Two Efficient Message-passing Exclusive Scan Algorithms by Jesper Larsson Träff (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-25667.txt.

Introduction

Träff presents two message-passing exclusive scan algorithms for prefix sums over vectors held by ranked units. In message-passing systems with bounded one-ported links, such scans have been far less addressed than inclusive scans. From natural rules, he gives two methods efficient in both round count and operator uses. The first joins inclusive and exclusive phases, trading rounds against uses. The second adapts a round-optimal all-reduce algorithm, with extra work set by the popcount of the rank count minus one.

Catalog record

CREATORJesper Larsson Träff
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE35820
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.25667

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Two Efficient Message-passing Exclusive Scan Algorithms Thanks: This note improves significantly over arXiv:2507.04785 Jesper Larsson Träff Abstract Parallel scan primitives compute element-wise inclusive or exclusive prefix sums of input vectors contributed by p p consecutively ranked processors under an associative, possibly expensive, binary operator ⊕ \oplus . In message-passing systems with bounded, one-ported communication capabilities, at least ⌈ log 2 ⁡ p ⌉ \lceil\log_{2}p\rceil or ⌈ log 2 ⁡ ( p − 1 ) ⌉ \lceil\log_{2}(p-1)\rceil send-receive communication rounds are required to perform the scans. While there are well-known, simple algorithms for the inclusive scan that solve the problem in ⌈ log 2 ⁡ p ⌉ \lceil\log_{2}p\rceil send-receive communication rounds with ⌈ log 2 ⁡ p ⌉ \lceil\log_{2}p\rceil applications of the ⊕ \oplus operator, the exclusive scan is different and has been much less addressed. By considering natural invariants for the exclusive prefix sums problem, we present two different algorithms that are efficient in the number of communication rounds and in the number of applications of the ⊕ \oplus operator. The first algorithm consists of an inclusive scan phase and an exclusive scan phase and trades the number of communication rounds against the number of applications of the ⊕ \oplus operator. For any chosen number of inclusive scan communication rounds q ′ ≥ 1 q^{\prime}\geq 1 , the algorithm performs q = ⌈ log 2 ⁡ ( p − 1 ) + log 2 ⁡ 2 q ′ 2 q ′ − 1 ⌉ = ⌈ log 2 ⁡ 2 q ′ 2 q ′ − 1 ​ ( p − 1 ) ⌉ q=\lceil\log_{2}(p-1)+\log_{2}\frac{2^{q^{\prime}}}{2^{q^{\prime}}-1}\rceil=\lceil\log_{2}\frac{2^{q^{\prime}}}{2^{q^{\prime}}-1}(p-1)\rceil send-receive communication rounds with q + q ′ − 2 q+q^{\prime}-2 applications of the ⊕ \oplus operator. The smallest number of inclusive scan rounds with q = ⌈ log 2 ⁡ p ⌉ q=\lceil\log_{2}p\rceil rounds in total is q ′ ≥ q − log 2 ⁡ ( 2 q − p + 1 ) q^{\prime}\geq q-\log_{2}(2^{q}-p+1) . It includes as special cases two standard implementations of the exclusive scan operation, namely reducing the problem to an inclusive scan problem on p − 1 p-1 processors at the cost of one extra communication round, or modifying an inclusive scan algorithm to also compute the exclusive scan at the cost of twice as many operator applications. The other algorithm is a modification of a round-optimal all-reduce algorithm, and the number of additional applications of the ⊕ \oplus operator is dependent on the number of bits set (popcount of) in p − 1 p-1 . Both algorithms are relevant for small(er) input vectors where performance is dominated by the number of communication rounds. For large input vectors, other (pipelined, fixed-degree tree) algorithms must be used. Parallel scan primitives are included in MPI as the MPI_Scan and MPI_Exscan collectives. An experimental comparison with implementations in MPI of the MPI_Exscan collective operation indicates that the considerations here are of practical relevance. 1 Introduction The parallel scan is a fundamental primitive in parallel algorithmics, typically used for bookkeeping and load balancing purposes, but often also directly in and for the algorithms themselves, see for instance [ 2 , 10 , 5 ] . Scan operations compute the inclusive or exclusive prefix sums over inputs provided by p successively ranked (numbered) processors under a given, associative, binary operator \oplus . Each of the p processors r,0\leq r<p has an input vector V_{r} of m elements and computes its element-wise, r th prefix sum W_{r} as follows: • Inclusive scan, for 0\leq r<p : \displaystyle W_{r} \displaystyle=\oplus_{i=0}^{r}V_{i} • Exclusive scan, for 0<r<p : \displaystyle W_{r} \displaystyle=\oplus_{i=0}^{r-1}V_{i} For distributed memory, parallel message-passing programming, both inclusive and exclusive scan operations are commonly standardized in this way, e.g., in MPI [ 12 ] as MPI_Scan and MPI_Exscan , respectively. Both primitives find extensive use [ 4 , 9 ] . Arguably, the exclusive scan is the more important, more often used variant of the scan primitives [ 10 ] . In a shared-memory setting, where input and output are stored in shared-memory arrays, the difference is possibly not too important, since the r th exclusive prefix equals exactly the (r-1) th inclusive prefix which can be read immediately in the result array. In a distributed memory, message-passing setting, this reduction from exclusive to inclusive scan involves additional communication from processor r-1 to processor r for all processors r,0<r<p . Nevertheless, message-passing algorithms in the literature deal mostly with the inclusive scan primitive, and trivially reduce the exclusive scan primitive to an inclusive scan with one extra communication round either after or before the inclusive scan (which need to be performed on only p-1 processors). As can easily be seen and as has been discovered many times, the inclusive scan problem can be solved in \lceil\log_{2}p\rceil communication rounds in which processors simultaneously send and receive partial results [ 6 , 7 , 8 ] (or \lceil\log_{k+1}p\rceil rounds for k -ported systems [ 11 ] ): We will recapitulate the algorithm in Section 2 . In systems with one-ported communication capabilities, this is optimal, since the last processor r=p-1 needs information (partial results) from all p processors and the number of processors from which r can have information after k communication rounds is at most 2^{k} . These algorithms send and receive full, m -element input or partial result vectors in each communication round, and are therefore mostly relevant for vectors with small numbers of elements m . For large vectors, pipelined, fixed-degree tree algorithms should be used [ 10 , 13 , 14 ] , which, however, require a larger number of communication rounds and are therefore not as suitable for small vectors. MPI libraries use different combinations of algorithms and different choices for their implementations of MPI_Scan and MPI_Exscan , but, as can be seen in Appendix A , often select logarithmic round, full-vector algorithms up to quite large values of m . In this paper, we examine algorithms for the exclusive scan operation, focusing on the number of communication rounds which is one factor influencing the achievable and observable performance for small vectors on real, distributed-memory parallel computing systems. A round lower bound is clearly \lceil\log_{2}(p-1)\rceil since a reduction of p-1 inputs has to be computed; whether this is tight seems not to be known. The reduction of the exclusive scan to an inclusive scan plus an extra communication step will in the best case take 1+\lceil\log_{2}(p-1)\rceil communication rounds, which is at least one more than the lower bound. Modifying an inclusive scan algorithm to compute, in essence, both inclusive and exclusive scans, leads to an algorithm taking \lceil\log_{2}p\rceil communication rounds, but at the expense of two applications of the \oplus operator per round (except for the first round, so the number of applications is actually 2\lceil\log_{2}p\rceil-2 ). This can be a significant drawback when \oplus is expensive and as m becomes larger. Performing an inclusive scan and then letting each processor remove its own contribution would give \lceil\log_{2}p\rceil communication rounds with \lceil\log_{2}p\rceil+1 operator applications, but works only if the \oplus operator has an inverse \oplus^{-1} which is often not the case (min/max operators). We first present an algorithm that combines the two observations and performs the exclusive scan in q=\lceil\log_{2}(p-1)+\log_{2}\frac{2^{q^{\prime}}}{2^{q^{\prime}}-1}\rceil simultaneous send-receive communication rounds

Read the complete text