Two Efficient Message-passing Exclusive Scan Algorithms∗ Jesper Larsson Träff TU Wien Faculty of Informatics Institute of Computer Engineering, Research Group Parallel Computing 191-4 Treitlstrasse 3, 5th Floor, 1040 Vienna, Austria
arXiv:2604.25667v1 [cs.DS] 28 Apr 2026
April 2026
Abstract Parallel scan primitives compute element-wise inclusive or exclusive prefix sums of input vectors contributed by p consecutively ranked processors under an associative, possibly expensive, binary operator ⊕. In message-passing systems with bounded, one-ported communication capabilities, at least ⌈log2 p⌉ or ⌈log2 (p − 1)⌉ 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 ⌈log2 p⌉ send-receive communication rounds with ⌈log2 p⌉ applications of the ⊕ 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 ⊕ 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 ⊕ operator. For any chosen number of inclusive scan q′ communication rounds q ′ ≥ 1, the algorithm performs q = ⌈log2 (p − 1) + log2 2q2′ −1 ⌉ = q′
⌈log2 2q2′ −1 (p − 1)⌉ send-receive communication rounds with q + q ′ − 2 applications of the ⊕ operator. The smallest number of inclusive scan rounds with q = ⌈log2 p⌉ rounds in total is q ′ ≥ q − log2 (2q − 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 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 ⊕ operator is dependent on the number of bits set (popcount of) in 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, ∗
This note improves significantly over arXiv:2507.04785
1
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 ⊕. Each of the p processors r, 0 ≤ r < p has an input vector Vr of m elements and computes its element-wise, rth prefix sum Wr as follows: • Inclusive scan, for 0 ≤ r < p: Wr = ⊕ri=0 Vi • Exclusive scan, for 0 < r < p: Wr = ⊕r−1 i=0 Vi 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 sharedmemory arrays, the difference is possibly not too important, since the rth 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 ⌈log2 p⌉ communication rounds in which processors simultaneously send and receive partial results [6, 7, 8] (or ⌈logk+1 p⌉ 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 2k . 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 ⌈log2 (p−1)⌉ 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 + ⌈log2 (p − 1)⌉ 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 ⌈log2 p⌉ communication rounds, but at the expense of two applications of the ⊕ operator per round (except for the first round, so the number of applications is actually 2⌈log2 p⌉ − 2). This 2
can be a significant drawback when ⊕ is expensive and as m becomes larger. Performing an inclusive scan and then letting each processor remove its own contribution would give ⌈log2 p⌉ communication rounds with ⌈log2 p⌉ + 1 operator applications, but works only if the ⊕ operator has an inverse ⊕−1 which is often not the case (min/max operators). We first present an algorithm that combines the two observations and performs the excluq′ sive scan in q = ⌈log2 (p − 1) + log2 2q2′ −1 ⌉ simultaneous send-receive communication rounds with q − q ′ − 2 applications of the ⊕ operator where q ′ is the number of initial inclusive scan communication rounds and can be chosen freely. A smallest q ′ for which the total number of rounds is q = ⌈log2 p⌉ is given by q ′ ≥ q − log2 (2q − p + 1). Secondly, we modify a round-optimal algorithm for the all-reduce (MPI Allreduce) operation [1, 17] to solve instead the exclusive prefix sums problem. This algorithm takes always ⌈log2 p⌉ communication rounds, but the number of additional applications of the ⊕ operator depends on the popcount (number of bits set) in p − 1 as popcnt(p − 1) − 1 − even(p). It remains open whether an algorithm running in ⌈log2 (p−1)⌉ rounds with at most ⌈log2 (p− 1)⌉ applications of ⊕ exists. In the appendix, we collect experimental evidence on a small high-performance cluster with 36 compute nodes, each with 32 processor cores with two commonly used, state-of-the-art MPI libraries to show that the considerations, apart from being theoretically interesting, can be worthwhile and have concrete, practical impact for MPI implementations of the parallel exclusive scan primitive.
2
Inclusive and Exclusive Scan Algorithms
We consider algorithms where the p processors communicate using a circulant graph pattern [3, 17]. In a communication round, processor r, 0 ≤ r < p simultaneously receives a vector from processor r − s (if ≥ 0) and sends a vector to processor r + s (if < p) for some positive skip s which in each round is the same for all processors. We denote the skip for round k as sk . The number of processors p and the sequence of some q skips sk , k = 0, 1, . . . , q − 1, both of which depend on p, define the circulant graph. In well-known, standard, logarithmic round inclusive scan algorithms, call them either Hillis-Steele [6], Kogge-Stone [7] or Kruskal-Rudolph-Snir [8], the processors maintain a partial result of the form Wr = ⊕ri=max(0,r−sk +1) Vi as an invariant that holds before round k, k = 0, 1, . . . , ⌈log2 p⌉ − 1 for a sequence of straight doubling skips sk = 2k . Before the first round with k = 0, this invariant can easily be established by locally copying Vr into Wr , and if the invariant holds before round k, processor r can receive the computed partial result Wr−sk from processor r − sk (as long as r − sk ≥ 0) and add it with ⊕ to its own computed partial result Wr . Since sk + sk = 2k + 2k = 2k+1 = sk+1 , the invariant now holds before round k + 1. When sk > r, the invariant implies that processor r has indeed computed the rth inclusive prefix sum. To avoid unfairly giving preference, we term this algorithm the straight doubling inclusive scan algorithm. The straight doubling inclusive scan algorithm can be extended compute both the inclusive and the exclusive scan by maintaining after the first communication round instead the invariant Wr = ⊕r−1 i=max(0,r−sk +1) Vi which implies that processor r has computed the rth exclusive prefix sum upon termination. Processor r would then have to send in Wr ⊕ Vr to processor r + sk in round k (as long as 3
Algorithm 1 Algorithm for the exclusive prefix sums operation for processor r with adjusted doubling skips s. Each processor has input in V and computes the rth element wise exclusive prefix sum in rank order into W . The associative reduction operator is ⊕. For a given p′ , p′ < p, exclusive and inclusive prefix sums are computed by doubling s as long as s < p′ . After this, s is adjusted to s − 1 and doubled further to compute only exclusive prefix sums as long as s < p. ′ For a chosen number of inclusive scan rounds q ′ , set p′ = 2q . The best p′ is 2⌈ log2 p⌉ − p + 1. procedure ExScan(V, W, ⊕) s←1 ▷ First skip t, f ← r + s, r − s ▷ To- and from-processors for first round if 0 ≤ f ∧ t < p then Send(V, t) ∥ Recv(W, f ) else if 0 ≤ f then Recv(W, f ) else if t < p then Send(V, t) end if s ← s↑1 ▷ Double while s < p′ do ▷ Inclusive scan phase, straight doubling t, f ← r + s, r − s ▷ To- and from-processors if 0 ≤ f ∧ t < p then W′ ← W ⊕ V Send(W ′ , t) ∥ Recv(T, f ) W ←T ⊕W else if 0 ≤ f then Recv(T, f ) W ←T ⊕W else if 0 < r ∧ t < p then W′ ← W ⊕ V ▷ Do this W ′ computation at most once ′ Send(W , t) else if 0 = r ∧ t < p then Send(V, t) end if s ← s↑1 end while s ← s − 1 ▷ Adjust skip and switch to exclusive scan phase, processor r = 0 is now done while s < p − 1 do t, f ← r + s, r − s ▷ To- and from-processors if 1 ≤ f ∧ t < p then Send(W, t) ∥ Recv(T, f ) W ←T ⊕W else if 1 ≤ f then Recv(T, f ) W ←T ⊕W else if 1 ≤ r ∧ t < p then Send(W, t) end if s ← s↑1 ▷ Double end while end procedure
4
r + sk < p), requiring two applications of ⊕ in each round, except the first. We call this exclusive scan algorithm the two-⊕ doubling exclusive scan algorithm. The exclusive scan seems more elusive than the inclusive scan. The natural invariant, complementary to the inclusive scan invariant, would be to maintain Wr = ⊕r−1 i=max(0,r−sk ) Vi and use a similar, doubling communication pattern. Even with s0 = 1, the invariant does not hold before the first round, since processor r is missing the input from processor r − 1 (for r > 0). In order to establish the invariant, we first let each processor r receive Vr−1 into Wr from processor r − 1. The invariant now holds for the next round, and with sk = 2k−1 for k = 1, 2, . . . , ⌈log2 (p − 1)⌉, we can let each processor receive the computed partial result Wr−sk from processor r − sk and ⊕ it into the partial result Wr . Since r−1 k −1 V ⊕ ⊕ V Wr−sk ⊕ Wr = ⊕r−s i i i=max(0,r−sk −sk ) i=max(0,r−sk ) = ⊕r−1 i=max(0,r−sk+1 ) Vi the invariant is reestablished and holds again before round k + 1. The invariant is void for processor r = 0, therefore after the initial round with s0 = 1, there is no further communication with processor r = 0 necessary, and ⌈log2 (p − 1)⌉ additional rounds suffice to complete the exclusive scan. In total, the number of communication rounds is 1 + ⌈log2 (p − 1)⌉. We term this exclusive scan algorithm the 1-doubling exclusive scan algorithm. It is essentially the same algorithm as first shifting the input from processor r to processor r + 1 and then performing a straight doubling scan on the p − 1 processors r, r > 0. This algorithm has the advantage that it performs only ⌈log2 (p − 1)⌉ applications of ⊕. To get the number of communication rounds closer to only ⌈log2 (p − 1)⌉ without doubling the number of applications of ⊕, a new idea is needed. Assume we first perform q ′ initial rounds of the two-⊕ doubling exclusive scan algorithm. In the last of these rounds, q ′ − 1, processor r computes r−s −1 q ′ −1 r−1 V Wr−sq′ −1 ⊕ Vr−sq′ −1 ⊕ Wr = ⊕i=max(0,r−s V ⊕ V ⊕ ⊕ i i r−s q ′ −1 i=max(0,r−sq′ −1 +1) q ′ −1 −sq ′ −1 +1) = ⊕r−1 i=max(0,r−sq′ −1 −sq′ −1 +1) Vi V . = ⊕r−1 i i=max(0,r−s ′ q
′
The last computed ⊕ sum follows if we take sq′ = sq′ −1 + sq′ −1 − 1 = 2q − 1, which indeed gives the desired exclusive prefix sums invariant after round q ′ − 1. From this round on, we can continue doubling as in the 1-doubling exclusive scan algorithm. We term this hybrid the q ′ -doubling exclusive scan algorithm. It indeed contains both the 1-doubling and the two-⊕ doubling algorithms as special cases, and is shown in full detail as Algorithm 1. The algorithm ′ doubles the skip s as long as s < p′ where p′ is chosen as 2q with two applications of ⊕ in each round, then adjusts the skip s for the next round by subtracting one, and finishes by doubling s as long as now s < p − 1 (since processor r = 0 is done) with only one application of ⊕ per round. The notation Send(W, t) ∥ Recv(T, f ) denotes a simultaneous send and receive operation with data in buffers W and T to and from processors t and f . We use s ↑ 1 to denote doubling by shifting (binary) s upwards by one position. We have the following proposition. Proposition 1. For any chosen q ′ , 1≤ q ′ ≤ ⌈log2mp⌉, the exclusive scan problem is solved in q′
′
2q (p − 1) simultaneous send-receive communication 2q′ −1 ′ rounds by Algorithm 1 with at most q + q − 2 applications of the associative, binary operator ⊕
q = ⌈log2 (p − 1) + log2 2q2′ −1 ⌉ = ⌈log2
by any processor. 5
′
Proof. Let q ′ be the chosen number of inclusive scan rounds and take p′ = 2q . By the initial round and the first while-loop, there are clearly 1 + (q ′ − 1) = q ′ communication rounds for the inclusive scan phase. After that, processor r = 0 is done, and the second while-loop takes q − q ′ communication rounds for the exclusive scan phase. The total number of communication rounds is therefore q ′ + (q − q ′ ) = q. The total round count q must be at least ⌈log2 p⌉ and if chosen too large, the last rounds will, by the conditions, entail no communication. The exact number of actual communication rounds is computed as follows. ′
′
(2q − 1)2q−q < p − 1 ⇔ p−1 ′ ⇔ 2q−q < q′ 2 −1 p−1 q − q ′ < log2 q′ ⇔ 2 −1 p−1 q < log2 q′ + q′ 2 −1 p−1 ′ + log2 2q = log2 q′ 2 −1 ′ 2q = log2 (p − 1) + log2 q′ 2 −1 ′ q 2 (p − 1) = log2 q′ 2 −1 The first round has no applications of ⊕, but the q ′ − 1 inclusive scan rounds have two applications each at most for any processor. The final q − q ′ exclusive scan only rounds each have one application of ⊕ for the processors that are receiving partial results. The total number of applications is therefore at most 2(q ′ − 1) + (q − q ′ ) = q + q ′ − 2 for any processor. For the implementation, the smallest number of inclusive scan rounds q ′ for which the the total number of rounds is still at most ⌈log2 p⌉ can easily be computed. Corollary 1. The smallest number q ′ of inclusive scan rounds in Algorithm 1 for which the total number of rounds is q = ⌈log2 p⌉ is q ′ ≥ q − log2 (2q − p + 1). Proof. We solve ′
′
2q−q (2q − 1) ≥ p − 1 ⇔ ′
2q − 2q−q ≥ p − 1 ⇔ 2q 2q − p + 1 ≥ q′ ⇔ 2 2q q′ 2 ≥ q 2 −p+1 and and arrive at the claim by taking the logarithm. The corresponding best p′ to use in Algorithm 1 to achieve this smallest number of q ′ inclusive scan rounds is 2⌈log2 p⌉ − p + 1. We term the corresponding algorithm the best-doubling exclusive scan algorithm. With q ′ = 1 and q ′ = q, Algorithm 1 contains the 1-doubling and two-⊕ doubling exclusive scan algorithms as special cases. Choosing p′ as in Corollary 1 gives the best-doubling algorithm. The number of communication rounds q and number of ⊕ applications for some small number of processors p (as used in the experimental evaluation in the appendix) are listed in Table 1. 6
Table 1: Communication rounds q versus number of ⊕ operator applications for Algorithm 1 and Algorithm 2 for small processor counts p, 24 ≤ p < 37 and 1140 ≤ p < 1153. For Algorithm 1, we show the cases q ′ = 1, corresponding to the 1-doubling algorithm, q ′ = q, corresponding to the two-⊕ doubling algorithm; we list the computed q ′ for the best-doubling algorithm. Algorithm 2 is the roughly halving algorithm.
p
q′ = 1 q ⊕
Best q ′ q ⊕ q′
q′ = q q ⊕
Roughly halving q ⊕
24 25 26 27 28 29 30 31 32 33 34 35 36
6 6 6 6 6 6 6 6 6 6 7 7 7
5 5 5 5 5 5 5 5 5 5 6 6 6
5 5 5 5 5 5 5 5 5 6 6 6 6
5 5 6 6 6 6 6 6 6 5 6 6 6
2 2 3 3 3 3 4 4 5 1 2 2 2
5 5 5 5 5 5 5 5 5 6 6 6 6
6 6 6 6 6 6 6 6 6 8 8 8 8
5 5 5 5 5 5 5 5 5 6 6 6 6
6 5 5 6 6 6 6 7 7 5 5 6 6
1140 1141 1142 1143 1144 1145 1146 1147 1148 1149 1150 1151 1152
12 12 12 12 12 12 12 12 12 12 12 12 12
11 11 11 11 11 11 11 11 11 11 11 11 11
11 11 11 11 11 11 11 11 11 11 11 11 11
11 11 11 11 11 11 11 11 11 11 11 11 11
2 2 2 2 2 2 2 2 2 2 2 2 2
11 11 11 11 11 11 11 11 11 11 11 11 11
18 18 18 18 18 18 18 18 18 18 18 18 18
11 11 11 11 11 11 11 11 11 11 11 11 11
14 14 14 15 15 14 14 15 15 15 15 16 16
7
The chosen q ′ for the best-doubling algorithm is also listed. The 1-doubling algorithm achieves the smallest number of ⊕ applications at the expense of one extra communication round. The number of ⊕ applications are bounded as by Proposition 1. The best q ′ increases gradually towards q as p approaches a power of two 2q from below. In the appendix, the three variants are ran with two concrete MPI libraries and illustrate that the differences can have practical impact.
3
Another Exclusive Scan Algorithm
It is known that the so-called all-reduce operation (in MPI: MPI Allreduce), in which all processors compute the same result W = ⊕p−1 i=0 Vi can be performed in exactly ⌈log2 p⌉ communication rounds if the ⊕operator is commutative [1, 17]. This is achieved with a so-called roughly halving circulant graph communication pattern where the kth skip sk for round k, k = 0, 1, . . . q is computed from the (k + 1)th skip by halving and rounding up, sk = ⌈sk+1 /2⌉ (with sq = p). The invariant maintained by the all-reduce algorithm of [17] can naturally be adopted to the exclusive scan problem, even without relying on commutativity. The adopted invariant states that processor r has computed the partial result Wr = ⊕r−1 i=max(0,r−sk+1 +1) Vi after round k. In other words, processor r has computed an exclusive prefix sum over the inputs from processor r − sk+1 + 1 up to but excluding processor r itself. As for the allreduce algorithm [17], we can maintain this invariant with a roughly halving circulant graph by distinguishing the two cases sk + sk = sk+1 (sk+1 even) and sk + sk = sk+1 + 1 (sk+1 odd), and adjusting the communication pattern accordingly. If sk+1 is even, we receive a partial result from processor r − sk , and if sk+1 is odd from processor r − (sk − 1) = r − sk + 1. Computing sk by roughly halving from p, it obviously holds that ( (sk − 1) + (sk − 1) if sk+1 is odd sk+1 − 1 = (sk − 1) + (sk − 1) + 1 if sk+1 is even It follows that sk+1 − 1 is exactly the most significant q − (k + 1) bits of p − 1 = sq − 1. We can therefore compute each sk directly sk ≡ (p − 1) ↓ (q − k) + 1 where (p − 1) ↓ (q − k) denotes shifting (binary) p − 1 downwards by q − k positions. Proposition 2. The exclusive scan problem is solved in ⌈log2 p⌉ send-receive communication rounds by Algorithm 2 using a roughly halving skip sequence sk = ⌈sk+1 /2⌉ = (p − 1) ↓ (q − k) + 1 with at most q + popcnt(p − 1) − 2 − even(p) applications of the associative ⊕ operator for any processor. Proof. By distinguishing the two cases sk+1 odd and sk+1 even, it can easily be seen that the claimed invariant holds. This implies that for each processor, W is the exclusive prefix sum over the inputs from the smaller numbered processors. In the first round, there is no application of the ⊕ operator by any processor. In the q − 1 following commutation rounds, all receiving 8
Algorithm 2 Algorithm for the exclusive scan operation for processor r on the circulant graph with adjusted roughly halving skips sk = ⌈sk+1 /2⌉ for k = 0, 1, . . . , q − 1 and sq = p. Each processor has an input vector V and computes the result into W . The associative operator for pairwise reduction of vectors is ⊕. The first communication round has no application of ⊕ and the remaining rounds at most one or two according to whether sk+1 is even or odd. procedure ExScan(V, W, ⊕) if p = 1 then ▷ For good measure, handle p = 1 case W ←V return end if ▷ Now p > 1 f, t ← r − s0 , r + s0 ▷ To- and from-processors for round 0 if 0 ≤ f ∧ t < p then Send(V, t, Cps ) ∥ Recv(W, f ) else if 0 ≤ f then Recv(W, f ) else if t < p then Send(V, t) end if ▷ First communication round, p > 1 for k = 1, . . . , q − 1 do if odd(sk+1 ) then ε ← 1 else ε ← 0 end if f, t ← r − sk + ε, r + sk − ε ▷ To- and from-processors if ε ≤ f ∧ t < p then if ε = 0 then W ′ ← W ⊕ V ▷ Compute partial result else W ′ ≡ W ▷ Alias to invariant result end if Send(W ′ , t) ∥ Recv(T, f ) W ←T ⊕W else if ε ≤ f then Recv(T, f ) W ←T ⊕W else if 0 < r ∧ t < p then if ε = 0 then W ′ ← W ⊕ V ▷ At most once, since nothing more is received ′ else W ≡ W end if Send(W ′ , t) else if r = 0 ∧ ε = 0 then Send(V, t) end if end for end procedure
9
processors perform a reduction, and in the rounds where sk+1 is even, sending processors perform an additional reduction. In the last round, if p is even, all processors either send or receive, but not both, which yields one less reduction. The claim then follows from the observation since the number of even sk for k = 2, . . . , q − 1 is popcnt(p − 1) − 1. The number of ⊕ applications for different, small numbers of processors p are also shown in Table 1 and are in accordance with Proposition 2.
4
Summary
This note surveyed known algorithms for the message-passing inclusive and exclusive scan operations (like MPI Scan and MPI Exscan in MPI [12]) suitable for small input and output vectors. We gave two efficient algorithms for the exclusive scan operation that can both readily be used to implement the MPI Exscan collective. The first algorithm is a configurable, hybrid algorithm q′ that computes the exclusive scan in q = ⌈log2 (p − 1) + log2 2q2′ −1 ⌉ simultaneous send-receive communication rounds with at most q − q ′ − 2 applications of the given, associative (and possibly expensive) binary operator for any given choice of initial rounds q ′ . We also gave a best q ′ for q = ⌈log2 p⌉ communication rounds overall. The second algorithm is a specialization of a round-optimal all-reduce algorithm which runs in ⌈log2 p⌉ communication rounds with q + popcnt(p − 1) − 2 − even(p) applications of the operator. It is an open question whether an algorithm exists that can compute the exclusive scan in ⌈log2 (p−1)⌉ communication rounds and at most the same number of operator applications. The algorithms discussed use a circulant graph communication pattern, and complement the algorithms discussed in [16, 17] for all the other MPI collective operations.
References [1] Amotz Bar-Noy, Shlomo Kipnis, and Baruch Schieber. An optimal algorithm for computing census functions in message-passing systems. Parallel Processing Letters, 3(1):19–23, 1993. [2] Guy E. Blelloch. Scans as primitive parallel operations. IEEE Transactions on Computers, 38(11):1526–1538, 1989. [3] Jehoshua Bruck, Ching-Tien Ho, Schlomo Kipnis, Eli Upfal, and Derrick Weathersby. Efficient algorithms for all-to-all communications in multiport message-passing systems. IEEE Transactions on Parallel and Distributed Systems, 8(11):1143–1156, 1997. [4] Sudheer Chunduri, Scott Parker, Pavan Balaji, Kevin Harms, and Kalyan Kumaran. Characterization of MPI usage on a production supercomputer. In International Conference for High Performance Computing, Networking, Storage, and Analysis (SC), pages 30:1–30:15. IEEE/ACM, 2018. [5] Marcin Copik, Tobias Grosser, Torsten Hoefler, Paolo Bientinesi, and Benjamin Berkels. Work-stealing prefix scan: Addressing load imbalance in large-scale image registration. IEEE Transactions on Parallel and Distributed Systems, 33(3):523–535, 2022. [6] W. Daniel Hillis and Jr. Guy L. Steele. Data parallel algorithms. Communications of the ACM, 29(12):1170–1183, 1986.
10
[7] Peter M. Kogge and Harold S. Stone. A parallel algorithm for the efficient solution of a general class of recurrence equations. IEEE Transactions on Computers, 22(8):786–793, 1973. [8] Clyde P. Kruskal, Larry Rudolph, and Marc Snir. The power of parallel prefix. IEEE Transactions on Computers, C-34(10):965–968, 1985. [9] Ignacio Laguna, Ryan Marshall, Kathryn Mohror, Martin Ruefenacht, Anthony Skjellum, and Nawrin Sultana. A large-scale study of MPI usage in open-source HPC applications. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, (SC), pages 31:1–31:14, 2019. [10] Kartik Lakhotia, Fabrizio Petrini, Rajgopal Kannan, and Viktor K. Prasanna. Accelerating prefix scan with in-network computing on intel PIUMA. In 29th IEEE International Conference on High Performance Computing, Data, and Analytics (HiPC), pages 59–68, 2022. [11] Yen-Chun Lin and Ching-Sung Yeh. Efficient parallel prefix algorithms on multiport message-passing systems. Information Processing Letters, 71:91–95, 1999. [12] MPI Forum. MPI: A Message-Passing Interface Standard. Version 4.1, November 2nd 2023. www.mpi-forum.org. [13] Peter Sanders, Jochen Speck, and Jesper Larsson Träff. Two-tree algorithms for full bandwidth broadcast, reduction and scan. Parallel Computing, 35(12):581–594, 2009. [14] Peter Sanders and Jesper Larsson Träff. Parallel prefix (scan) algorithms for MPI. In Recent Advances in Parallel Virtual Machine and Message Passing Interface. 13th European PVM/MPI Users’ Group Meeting, volume 4192 of Lecture Notes in Computer Science, pages 49–57. Springer, 2006. [15] Jesper Larsson Träff. mpicroscope: Towards an MPI benchmark tool for performance guideline verification. In Recent Advances in Message Passing Interface. 19th European MPI Users’ Group Meeting, volume 7490 of Lecture Notes in Computer Science, pages 100–109. Springer, 2012. [16] Jesper Larsson Träff. Optimal broadcast schedules in logarithmic time with applications to broadcast, reduction, all-broadcast and all-reduction. ACM Transactions on Parallel Computing, 12(3):1–21, 2025. [17] Jesper Larsson Träff. Optimal, non-pipelined reduce-scatter and allreduce algorithms with an application to all-to-all communication. ACM Transactions on Parallel Computing, 12(4):1–23, 2025. [18] Jesper Larsson Träff and Sascha Hunold. Decomposing MPI collectives for exploiting multilane communication. In IEEE International Conference on Cluster Computing (CLUSTER), pages 270–280. IEEE Computer Society, 2020. [19] Jesper Larsson Träff and Ioannis Vardas. Library development with MPI: Attributes, request objects, group communicator creation, local reductions and datatypes. In 30th European MPI Users’ Group Meeting (EuroMPI), 2023.
11
A
An Experimental Evaluation
We have implemented the two exclusive scan algorithms for and in MPI [12] exactly as shown in Algorithm 1 and Algorithm 2. Simultaneous send and receive is implemented with MPI Sendrecv, and local application of a pre- or user-defined MPI operator with MPI Reduce local. The latter is a two-argument operation, taking an input and an input-output vector and reducing these together in this order. In the inclusive scan phase of Algorithm 1 where an inclusive prefix sum partial result W ⊕ V has to be sent, as well as for Algorithm 2 when sk+1 is even, a threeargument local reduction function would have been desirable [19] to avoid an extra copy into an intermediate reduce buffer. ′ We aim to estimate how Algorithm 1 performs for different choices of p′ = 2q in comparison to the library native MPI Exscan operation, and how this compares against Algorithm 2. To possibly see the small differences by one communication round, we experiment with small p = 36 as well as with the full system with p = 36 × 32 processors, see Table 1. Our experimental system is a medium sized 36 × 32 processor cluster with 36 dual socket compute nodes, each with two Intel(R) Xeon(R) Gold 6130F 16-core CPUs. The compute nodes are interconnected via dual Intel Omnipath interconnects each with a bandwidth of 100 Gbytes/s. We give results with two available MPI libraries, namely mpich 4.1.2 and OpenMPI 4.1.6, and observe that MPI libraries differ highly in both absolute performance and in scalability characteristics. The implementations and benchmarks were compiled with gcc 12.1.0 with the -O3 option. As element type for the scan operations, we have used MPI LONG, and MPI BXOR as the binary operator. Our benchmarking procedure performs, for each element count, 155 measurement repetitions with 12 warmup measurements. We synchronize the MPI processes with MPI Barrier (twice), and for each experiment determine the time for the slowest process to complete the exclusive scan operation. Over the 155 repetitions, the minimum of these times is reported [15]. The results for the two MPI libraries, mpich 4.1.2 and OpenMPI 4.1.6, for element counts from c = 0 to c = 100 000 in p = 36 × 1 and p = 36 × 32 MPI processes are shown in Table 2 and Table 3. The OpenMPI 4.1.6 library obviously has a poor implementation of MPI Exscan upon which the new algorithms both improve easily by a large factor. The mpich 4.1.2 library (which seems the overall best performing library among our available libraries) apparently applies a logarithmic round algorithm all the way up to the large count of c = 100 000 elements; this can possibly be improved by using other algorithms [10, 13, 14]. Neither of the libraries seem to do the MPI Exscan operation in a hierarchical fashion when the compute nodes are full; this can possibly be improved [18]. The new algorithms perform comparably in the two libraries: The OpenMPI 4.1.6 library has better performance in comparison when the compute nodes are full, whereas the mpich 4.1.2 library performs better in the case with only one MPI process per node. For both libraries, the best-doubling algorithm almost everywhere fares the best. For the small element counts with c = 1, 10, 100, the two-⊕ algorithm can sometimes be slightly better (with very little difference to the q−1-doubling algorithm), but as c grows, the extra applications of ⊕ noticeably decreases the performance. The results illustrate that care must be taken when implementing MPI Exscan, and that the configurability offered by Algorithm 1 can have a practical impact. With the best choice of q ′ , this algorithm also does better than Algorithm 2. The implementation of both algorithms is straightforward, and it would make sense to include either in MPI libraries.
12
Table 2: Measured running times for the native MPI Exscan operation and the q ′ -doubling algorithm with the mpich 4.1.2 library in the p = 36 × 1 and p = 36 × 32 MPI process configurations, respectively, for element counts c = 1, 10, 100, 1 000, 10 000, 100 000 and q ′ = 1, q, best q ′ and the roughly halving halving. p = 36 × 1 MPI processes c (MPI LONG)
MPI Exscan (µseconds)
1-doubling (µseconds)
best-doubling (µseconds)
two-⊕ (µseconds)
halving (µseconds)
0 1 10 100 1000 10000 100000
0.08 9.85 17.22 19.05 36.39 255.52 2774.59
0.06 0.05 0.05 9.18 9.12 8.20 18.22 16.83 15.91 19.70 18.08 17.26 34.66 32.47 35.10 254.67 230.51 267.71 1571.19 1510.11 1969.52 p = 36 × 32 MPI processes
0.07 10.40 17.38 19.34 36.00 248.16 1707.75
c (MPI LONG)
MPI Exscan (µseconds)
1-doubling (µseconds)
best-doubling (µseconds)
two-⊕ (µseconds)
halving (µseconds)
0 1 10 100 1000 10000 100000
0.09 27.53 32.64 37.76 164.14 1015.59 11959.38
0.07 37.10 41.01 41.54 156.18 1095.81 11187.50
0.07 27.08 35.86 40.53 146.94 1037.51 10997.74
0.07 22.20 33.99 39.08 158.86 1113.78 14938.65
0.07 27.69 37.22 42.48 157.13 1106.17 13319.05
13
Table 3: Measured running times for the native MPI Exscan operation and the q ′ -doubling algorithm with the OpenMPI 4.1.6 library in the p = 36 × 1 and p = 36 × 32 MPI process configurations, respectively, for element counts c = 1, 10, 100, 1 000, 10 000, 100 000 and q ′ = 1, q, best q ′ and the roughly halving halving. p = 36 × 1 MPI processes c (MPI LONG)
MPI Exscan (µseconds)
1-doubling (µseconds)
best-doubling (µseconds)
two-⊕ (µseconds)
halving (µseconds)
0 1 10 100 1000 10000 100000
0.06 44.63 54.15 64.08 163.16 1127.28 7379.84
0.05 0.05 0.06 9.15 7.58 8.07 11.24 9.43 10.06 13.60 11.04 12.13 31.56 26.64 32.65 286.57 261.02 290.96 1844.17 1729.44 2246.06 p = 36 × 32 MPI processes
0.07 8.61 10.65 12.53 32.05 294.75 2078.20
c (MPI LONG)
MPI Exscan (µseconds)
1-doubling (µseconds)
best-doubling (µseconds)
two-⊕ (µseconds)
halving (µseconds)
0 1 10 100 1000 10000 100000
0.18 917.53 1462.47 2017.98 6618.10 34326.68 357144.19
0.06 15.56 19.26 29.10 135.03 1065.49 10423.22
0.15 16.10 19.13 26.80 129.20 1000.15 10674.83
0.17 14.12 17.41 25.41 137.45 1030.18 14456.33
0.40 17.06 21.73 30.38 143.70 1097.96 12879.54
14