Engineering Scalable Distributed List Ranking Peter Sanders[0000−0003−3330−9349] , Matthias Schimek[0009−0002−6402−9016] , Tim Niklas Uhl[0000−0001−9295−1388] , and Thomas Weidmann
arXiv:2606.09318v1 [cs.DC] 8 Jun 2026
Karlsruhe Institute of Technology, Karlsruhe, Germany {sanders,schimek,uhl}@kit.edu [email protected]
Abstract. The list ranking problem is one of the classical problems of parallel computing, with nontrivial algorithms and many applications as a subroutine for solving other problems. While it has been intensively studied in the early days of parallel computing, few things happened in the last 20 years. In particular, there is little work on scaling list ranking to large machines and input sizes. We reconsider list ranking starting from the ground-breaking results of Sibeyn a quarter century ago. We employ algorithm and performance engineering to improve his sparse ruling-set algorithm, making it capable of scaling to many processors, and provide a more detailed analysis of the impact of the algorithm’s parameters, further guiding our practical implementation. We perform an extensive experimental study across a variety of input instances with different structural properties. We demonstrate that indirect communication, exploiting input locality, and message coalescing allows scaling to billions of elements on up to 24 576 cores. Keywords: List Ranking · Distributed Memory Parallelism · Graph Algorithms · Algorithm Engineering
1
Introduction
List ranking is one of the most fundamental tasks in parallel processing, where we ask for the distance of list elements to the end of their list. This can be used to compute prefix sums on lists, converting lists to arrays, or to perform basic operations on trees (and graphs) using the Euler tour technique [8]. More concrete applications can be found in bioinformatics, e.g. for chain compaction in de Bruijn graph based genome assembly [11]. There is a trivial sequential linear-time algorithm. Pointer chasing basically just traverses the lists. However, designing fast and work-optimal parallel algorithms is challenging. Historically, the list ranking problem has been extensively studied in parallel computing, starting with Wyllie’s simple, fast, yet suboptimal pointer doubling [24]. Subsequent work achieved work-optimality and logarithmic time on PRAMs [10, 3]. Most of these algorithms share the same general approach: They splice out elements of the initial list, solve the remaining smaller subproblem, and then reinsert the removed elements, updating their ranks. For example, independent set removal (ISR) splices out a constant fraction of nonadjacent
2
Sanders et al.
elements [1]. However, many of these algorithms are not work efficient with respect to the involved constant factors and thus not a good basis for a practical implementation. A more efficient alternative is to remove all but a sparse set of ruler elements [14, 2]. The sublists between two rulers are spliced out using pointer chasing. Thus, most work in this sparse ruling set (SRS) algorithm is as efficient as the sequential algorithm. This makes SRS attractive as the basis for designing efficient distributed memory algorithms. The arguably most comprehensive line of work in this research direction is due to Sibeyn [18, 20, 16, 17, 19], presenting distributedmemory adaptations of SRS, ISR, and pointer doubling and a practical evaluation on random input lists on up to 130 processors [20]. This evaluation shows that the SRS algorithm is the most efficient one for sufficiently large input sizes. Our work revisits the most efficient distributed-memory algorithm, SRS with spawning [17], providing the first practical evaluation of it. We show that it scales across a large variety of inputs by considering input locality, machine topology, and reducing the number of communication start-ups and the number of communication rounds. Our Contributions. – We provide the first practical systematic evaluation of sparse ruling-set with spawning. – We scale to two orders of magnitude more processors than previous studies on general purpose list ranking, demonstrating scalability up to 24 576 cores. – We use a variety of input instances with and without locality. – We show that hardware-topology aware indirection, exploiting locality, and message coalescing are essential to achieve scalability. – We provide a refined scalability analysis of sparse ruling-set with spawning which considers messages indirection and locality. This helps us to choose good parameters in practice. 1.1
Problem Definition and Notation
The list ranking problem is defined as follows: As input we consider a set L of singly-linked lists, with elements labeled 0..n − 11 . We call a list element initial if it has no predecessor, and terminal if it has no successor. The list ranking problem now asks for identifying each list element i with the terminal element iterm of its list, and to determine the number of links to follow to reach iterm from i. This is denoted as the rank of i. More concretely, L is represented as a successor array succ[0..n − 1] of size n, where succ[i] denotes the successor of element i. Terminal elements are indicated by pointing to themselves, i.e., succ[i] = i. A list ranking algorithm will then modify succ, such that succ[i] points to the terminal element of i. The element ranks are stored in an array rank[0..n − 1]. 1
a..b is shorthand for the sequence [a, a + 1, . . . , b − 1, b]
Engineering Scalable Distributed List Ranking
3
A generalization of this is the weighted list ranking problem where each link to a successor succ[i ] is additionally associated with a weight. Then rank[i] is defined as the weighted distance from i to its terminal element, i.e., the sum of the weights over the path from i to the terminal element. We assume that the weight of i is initially stored in rank[i], and the array is modified in-place. Note that an instance with input rank[i] = 0 for terminal elements and rank[i] = 1 for all other elements is equivalent to the unweighted case. 1.2
Machine Model and Input Format
We consider a distributed-memory system consisting of p processing elements (PEs) numbered 0..p − 1 allowing single-ported point-to-point communication between arbitrary communication partners [15]. Sending a message of length ℓ from one PE to another takes time α + βℓ, where α is the time required to initiate a connection and β the subsequent transmission time for sending a machine word. We assume that the input and output arrays are stored equally distributed across the PEs, such that PE j is responsible for a contiguous index range aj ..bj of size Θ(n/p) and holds the partial data succ[aj ..bj ], rank[aj ..bj ]. We call aj ..bj the local elements of PE j and define owner(i) = j if element i is local to PE j. All other elements are remote elements for PE j. PE j can only access local elements directly, for remote elements it explicitly sends a request. 1.3
Other Related Work
Sparse ruling-set and independent set removal have also been adapted for the coarse-grained bulk-synchronous CGM and BSP computational model [4, 5, 9] and evaluated in practice. The problem has also been examined on GPUs [13, 23]. Apart from bulk-synchronous algorithms, Sibeyn proposed an approach using p communication rounds, where each processor communicates with at most one or two others per round. This results in expected communication volume in O(n/p ln p) and an overall number of O(p) messages sent and received by each processor for random inputs [16], outperforming plain pointer-doubling in practice. A related idea with similar bounds has been described by Träff [21].
2
Engineering a Scalable List Ranking Algorithm
We will first outline the sparse ruling-set algorithm in detail, and then focus on how to adapt this approach to scale to today’s largest machines by exploiting locality (Section 2.3), employing message indirection (Section 2.4), and additional practical consideration (Section 2.5). Many of these optimizations can also be applied to pointer doubling and independent set removal to improve scalability, but the algorithmic properties of sparse ruling-set make it a prime candidate for ranking lists at scale. Finally, we analyze the scalability of our algorithm and derive an optimal ruler selection strategy in Section 2.6.
4
Sanders et al.
Algorithm 1: The sparse ruling-set algorithm. Data: succ[aj ..bj ], rank[aj ..bj ] Input: PE index j, number of desired rulers r 1 (succ, rank) ← reverseList(succ, rank) b −a
Ij ← findInit(succ); rj ← r j n j ; Rj ← pickRulers(rj − |Ij |, aj ..bj ) ∪ Ij 3 foreach r ∈ Rj do // Ruler chasing 4 send (rank[r ], succ[r ], r) to owner(succ[r]) 5 succ[r] ← r; rank[r] ← 0
2
while messages to send do on message (w, i, r) do 8 if i is terminal or ruler then // Ruler-spawning 9 select unvisited node r0 ∈ ai ..bi as new ruler 10 succ[r0 ] ← r0 ; rank[r0 ] ← 0; Rj ← Rj ∪ {r0 } 11 send (rank[r0 ], succ[r0 ], r0 ) to owner(succ[r]) 12 else 13 send (w + rank[i], succ[i], r) to owner(succ[i]) 6
7
14
succ[i] ← r; rank[i] ← w
listRanking(succ[Rj ], rank[Rj ]) // Base case forall i ∈ aj ..bj that are no rulers do // Ruler propagation 17 request (succ[succ[i]], rank[succ[i]]) from owner(succ[i]) then 18 succ[i] ← succ[succ[i]] 19 rank[i] ← rank[succ[i]] + rank[i]
15 16
2.1
The Sparse Ruling-Set Algorithm
As introduced in Section 1 sparse ruling-set aims to reduce the problem size by running multiple sequential list-traversals in parallel from a set of starting elements (called rulers). When such a search reaches another ruler, we compress the list segment between the two rulers to a single link with the total weight of the segment. Then, we recurse on the subproblem consisting only of rulers. Once the subproblem has been fully ranked, we reinsert the compressed list segments between rulers and adjust ranks and terminal elements accordingly. Algorithm 1 describes sparse ruling-set in more detail: First, we randomly sample a set of r rulers. This can be done without communication by randomly sampling r/p elements per PE. Note that we also need to include all initial elements in the set of rulers to guarantee that the full list is traversed (line 2). In the subsequent ruler-chasing phase, we start packet waves from the rulers: For each ruler r, we send a message consisting of (rank[r], succ[r], r) to the PE owning succ[r] and set rank[r] = 0 and succ[r] = r. Upon receiving a message (w, i, r) dedicated to element i, we update the succ and rank value of i accordingly with r and w and forward the message to succ[i], increasing the transmitted weight by rank[i]. When i is a ruler or a terminal element, we still update the values, but do not send a new packet. A straightforward way of implementing the communication during ruler chasing (lines 6–14) is to use bulk-synchronous
Engineering Scalable Distributed List Ranking
5
communication rounds. However, this has a major shortcoming: The number of rounds is determined by the maximum length of a sublist between two rulers. In case of bad ruler selection, this may lead to load imbalances which may hinder scalability. This was addressed by Sibeyn [17] using so-called ruler-spawning, which we will discuss in Section 2.2. After ruler chasing, each element points to the ruler it was reached from, including rulers themselves. We interpret the succ array, limited to rulers, as a new weighted list ranking problem and apply a base-case list ranking algorithm to compute the distance from each ruler to the initial element of its list. Finally, we need to fix the rank and initial element of the elements that have been eliminated by ruler chasing. In the ruler-propagation phase, each non-ruler element i sends a request to the ruler it was reached from, which is stored in succ[i]. A ruler r then replies with its initial node succ[r] distance rank[r], and each non-ruler updates its local result accordingly. Since ruler chasing effectively reverses the list direction in the subproblem, the algorithm as described above computes ranks with respect to the initial instead of terminal elements. This can be fixed by reversing the list as a preprocessing step, effectively using the predecessor array as input. 2.2
Ruler Spawning
In the basic sparse ruling-set algorithm, the length of sublists between rulers may differ. When using bulk-synchronous communication, the overall running time is therefore dominated by the length of the longest sublist. This can be fixed using ruler spawning (lines 9–11) introduced by Sibeyn [17]: Whenever a wave reaches another ruler, we randomly choose a new ruler from the set of unreached elements and start another wave. This ensures that there are always r active waves, reducing the number of unreached vertices by r in each round. To localize the spawning process, we select the new rulers from local unreached elements and only let a wave “die” if there are none left. Sibeyn shows that for r ≫ p log p all elements are reached in n/r + 1 rounds with high probability assuming a random input [17]. Hence, ruler chasing terminates after about n/r rounds and is not dominated by long chains at the cost of ≈ ln(n/r) times larger remaining subproblems [17]. Preliminary experiments indicate that ruler spawning improves scalability, which is why we use it in our practical evaluation. 2.3
Exploiting Input Locality
Many inputs emerging from applications tend to possess locality, i.e., contain sublists consisting only of local elements. These can be compressed to reduce the input size. In a preprocessing step, we identify local initial elements, i.e., elements which have no non-local predecessors by a single pass over the local succ array. We then sequentially traverse the local lists starting from local initial elements l, marking all visited elements as removed, until we reach an element j whose successor succ[j] is non-local. We then insert a shortcut between l and succ[j] by setting succ[l] ← succ[j] and the corresponding rank[l] to the sum of weights
6
Sanders et al.
from l to succ[j ]. After this step, the input to the distributed algorithms consists of the local initial and terminal elements only. To restore the updated rank and terminal elements for locally removed elements in the end, we can simply propagate the values from the local initial elements by traversing the local sublist again. Since we only modify the successor of the local list start, we can retain all local list information by just storing the original successor for each local initial element. The whole process of local preprocessing requires no communication, since we only access and update local elements of succ and rank, and runs in time O(n/p). While the idea of compacting local sublists has been explored for various other list-ranking algorithms before [21, 12, 7, 9], it has not been considered for sparse ruling-set with spawning before. 2.4
Indirect Communication
A challenge in scaling discrete algorithmic problems to a large number of PEs is to communicate efficiently. Many traditional HPC applications rely on stencil communication with large amounts of data. In contrast, communication in list ranking requires exchanging small messages between all PEs. Sparse ruling-set only communicates a small amount of data in each round, but performs many rounds of all-to-all exchanges. In the point-to-point model, this means that each exchange is dominated by the the startup factor αp, which becomes increasingly impactful when scaling p. To address this, we employ message indirection: Instead of delivering all messages directly, we arrange PEs √ in a logical grid with side lengths of p, assuming that p is square2 . Then, we first forward each message to the correct processor column and then along this column to the correct row, as depicted in Fig. 1a. While this requires sending each message twice and therefore increases the communication volume by a factor of √ 2, we can limit the number of communication partners per step to p instead of p, meaning that we reduce the impact of the startup factor. The idea of indirect message delivery for reducing startups in the sparse ruling-set algorithm has been previously proposed by Sibeyn [20], but becomes increasingly important when scaling on today’s HPC systems with very fast interconnects (where β is very small compared to α) and increasing degree of parallelism. It can be further generalized to d-dimensional grids. Topology-Aware Indirection. We propose an additional topology-aware indirection strategy, which takes the structure of real-world systems into account. Here we arrange PEs into p′ groups of size c, such that we have p = cp′ . Inside processor group i, we number the PEs Pi,0 , . . . , Pi,c−1 . To send a message from Pi,u to Pj,v , we first send it to Pi,v , located in the same group (intra-node communication), and then to its final destination in group j (inter-node communication). We visualize this in Fig. 1b. In our practical implementation, we set c to the size of a single compute node, grouping PEs belonging to the same node. This 2
For arbitrary p, we use MPI_Dims_create to compute a balanced processor grid.
Engineering Scalable Distributed List Ranking
(a) Logical 2D-grid based indirection.
7
(b) Topology-aware indirection.
Fig. 1: Visualization of message indirection schemes.
comes with two benefits: (1) Intra-node communication has lower startup latency and transmission time. (2) Indirection requires transmitting additional message metadata such as the destination rank for routing, that can be omitted from the final inter-node communication step. Using fast intra-node communication when sending additional payload mitigates the increased communication volume. Similar to grid-based based indirection, the topology-aware scheme can extended to incorporate additional dimensions, e.g, based on physical racks.
2.5
Further Optimizations
Avoiding Communication. As mentioned in Section 2.1, the basic sparse ruling-set algorithm ranks elements with respect to initial elements instead of terminal elements, requiring a preprocessing step, which reverses all links in the input. Preliminary experiments indicate that this step is costly, since each PE has to communicate all O(n/p) elements in the worst case. However, reversing the input can be avoided by a postprocessing step sending only O(|L|p) messages in total. At the end of the sparse ruling-set each element knows the initial element of the list. The terminal elements now send their index and rank to their initial element. Then, all elements can request this data and adjust their final succ and rank values accordingly. Since each PE only requests this information at most once per list, we can limit the number of messages to O(|L|p) by locally aggregating the requests. This can also be combined with indirection to coalesce identical requests at intermediate indirection levels. Ruler Selection and Spawning. A new ruler can be selected by drawing random elements from the local list until an unvisited one is found. However, when ruler-chasing is close to termination, there are much more visited than unvisited local elements, leading to many retries, each requiring a random memory access. We avoid this by initially computing a random permutation of the local index set aj ..bj . Initial ruler selection then merely requires taking the first r/p elements of that permutation, skipping over terminal elements. We keep track of the current position in the permutation. For spawning a new ruler, we continue scanning from this position until we reach an unvisited element. This allows to perform ruler selection and spawning in O(n/p) local work.
8
Sanders et al.
2.6
Scalability Analysis
The efficiency of sparse ruling-set directly depends on the number of rulers, since it influences both the number of communication rounds and the subproblem size. We do not try to establish rigorous worst-case bounds on the parallel running time of the algorithm. Rather, we make some simplifying assumptions in order to characterize the impact of algorithmic choices and locality on performance. In particular, we would like to understand how the initial number of rulers and the degree of indirect communication should be chosen in our practical sparse ruling-set implementation. Our main assumption is that all the performed work is well-balanced over all PEs at all time. This can be approximated probabilistically by randomly (re-)distributing the data. Under these assumptions, an all-to-all exchange using d-dimensional grid-based indirection (as outlined in Section 2.4) with at most h words per PE can be performed in time about Tall2all (p, h, d) = αdp1/d + βdh. The sparse ruling-set algorithm needs time about dβn n + αdp1/d + Tbase (p, n′ ) T (p, n, r) = O p r where Tbase is the running time of the base-case algorithm used, n′ is the remaining problem size, and r denotes the number of initially selected rulers. This equation is based on summing the cost of all-to-all communications over n/r rounds. For simplicity, we will perform a single round of sparse ruling-set and use pointer doubling as the base case, which requires parallel execution time n . Tdoubling (p, n) = O log(n) αdp1/d + βd p With ruler spawning, the expected total number of rulers and therefore the size of the base case instance is n′ ≈ r ln(n/r) [17]. Both log nr and log(r log nr ) will be Θ(log p) for the range of values that will turn out to be interesting3 and we get dβn r log2 p 1/d n 1/d T (n, p, r) = O + αdp + αdp log p + βd . p r p Solving ∂T /∂r = 0, we observe the following. Observation 1. For sparse ruling-set with pointer doubling as base case and messageindirection using d levels, we achieve an optimal running time by setting √ αnp1+1/d /β ∗ r =Θ , giving us a running time of log p s ! dβn αβn T ∗ (n, p) = T (n, p, r∗ ) = O + αdp1/d log p + d log p . p p1−1/d 3
This is wrong when n is superpolynomial in p. However, in this case the algorithm is efficient anyway (and the input will likely not fit in memory).
Engineering Scalable Distributed List Ranking
9
From that we can derive the following corollary. 1/d Corollary 1. For np ≫ α log2 p input elements per PE, the algorithm is βp efficient.
Thus, for smaller n, larger d (i.e., more indirect message delivery) makes sense at the cost of larger communication overhead. Input locality can be modeled using with a locality parameter δ, denoting the ratio of elements having successor owned by the same PE. If locality is perfectly balanced between PEs, applying the local preprocessing step from Section 2.3 reduces the input size and total running time to T ∗ ((1 − δ)n, p) + O(n/p). Unbalanced locality can be handled by randomly redistributing the data after local preprocessing. However, this only saves a constant factor on running time, since the bottleneck communication volume is still O(n/p) in the worst case.
3
Experimental Evaluation
Experimental Setup. We implement our algorithm variants using C++ and provide an open-source implementation4 . We run our experiments on the thin nodes of SuperMUC-NG. Each node is equipped with an Intel Skylake Xeon Platinum 8174 processor with 48 cores. The available memory per node is limited to 96 GB. The interconnect is an OmniPath network with 100 Gbit/s. Our code is built on top of the C++ MPI interface KaMPIng [22], is compiled using g++-15.1.0 and Intel MPI 2021.15.0, and uses optimization flags -O3 and -march=native. Methodology. For each experiment, we generate input instances and perform 5 iterations, where we discard the first run since it might incur communication setup overhead. We report the mean total running time (excluding input generation) over the remaining iterations. Errors bars indicate the minimum and maximum running time observed on a specific configuration. We perform weak-scaling experiments, where we fix the input size n/p per MPI process and scale it proportional to the number of MPI processes p. We choose the number of rulers based on the results from our analysis, scaling the local number of rulers per PE relative to the local input size per PE. Using a parameter study, we determined suitable constant factors. We run two rounds of sparse ruling-set and use pointer doubling as the base case algorithm, which proved to be more efficient than a single round. Additional experiments indicate that more than two rounds do not pay off. We engineered the pointer-doubling implementation to apply the same optimizations as our sparse ruling-set algorithm, with support for message indirection and locality exploitation. Input Instances. We use two classes of input instances. First, we generate lists of size n, where we set succ[i] = i + 1. Then the parameter γ ∈ [0, 1] controls the degree of locality: We sample γn indices from 0..n − 1, which we randomly 4
https://github.com/niklas-uhl/kascade
10
Sanders et al.
permute. This means that for γ = 0.0 we get a list where each PE is assigned a contiguous sub-list, while γ = 1.0 fully permutes the list such that there is no locality. We denote these instances as List(n/p, γ). We derive additional instances from random graphs. We use the communication free graph generators from KaGen [6] to generate random Erdős-Rényi graphs (GNM) and two-dimensional random geometric graphs (RGG2D). We then perform a breadth-first search to construct a tree, which we transform to a Euler-tour [8]. This allows us to generate lists which follow the locality properties of the input graphs.
3.1
Exploiting Input Locality
Plain 20
List(2 , γ = 0.0) time /s
0.4
20
22
24
26
0.6
1.5
0.4
1
0.2
0.5
0
20
LocalContraction
List(220 , γ = 0.1)
List(2 , γ = 0.01)
0.2 0
LocalChasing 20
0 0 2 22 24 26 22 24 26 # compute nodes (×48 cores)
List(220 , γ = 1.0) 2 1 0
20
22
24
26
Fig. 2: Evaluation of different locality-aware techniques on random lists with varying degree of locality. We do not use message indirection.
In Fig. 2, we investigate our different locality-aware optimizations for the sparse ruling-set algorithm. The Plain variant does not employ any optimizations for local elements. The LocalityChasing variant provides a straightforward way to exploit locality: it runs the distributed algorithm but follows local ruler chains until reaching a non-local successor before participating in the next communication round. The LocalContraction variant performs the local sublist contraction step described in Section 2.3, before running the actual distributed sparse ruling-set algorithm. This has the advantage that we can use the effective number of elements as a parameter for ruler selection. We see that these two optimization techniques are highly effective for inputs with a high degree of locality. For γ = 0.0, LocalContraction is up to 4× faster than Plain. Furthermore, we see that these optimizations add almost no overhead in case there is no locality in the input (γ = 1.0). Therefore, we enable LocalContraction for all following experiments.
Engineering Scalable Distributed List Ranking
3.2
11
Scaling Experiments
Fig. 3 shows the running times of the sparse ruling-set (SRS) and the pointer doubling (PD) algorithms on random list instances with n/p ∈ {216 , 218 , 220 222 } elements and on two Euler tour instances with ≈ n/p = 220 elements, constructed from graphs with n/p = 219 vertices and m/p = 222 edges. We run each algorithm in two variants – one using direct communication and one using topology-aware indirect communication enabled (+Ind suffix, see Section 2.4 for details). Overall, we see that SRS+Ind scales well to even the largest configurations (12 228 cores), especially for n/p ∈ {220 , 222 }. The sparse ruling-set variants are up to 15× faster than pointer doubling. As expected, indirect communication pays off for both algorithms as the number of cores increases. For n/p = 216 elements, SRS+Ind becomes faster from 768 cores on. For larger input sizes the break-even shifts to higher core counts, as the larger communication volume hides the latency costs. Nevertheless, even for n/p = 222 elements SRS+Ind outperforms SRS from 3 072 cores on. For pointer doubling, direct communication remains preferable up to higher core counts than for sparse ruling-set, as the larger amount of work performed by the algorithm, combined with a smaller number of communication rounds, hides the latency costs for longer. With further increases in the core count, indirect communication eventually becomes faster as well. Across all instances and core counts, the better variant of sparse rulingset is always faster than the better pointer-doubling variant for the respective configuration. On the RGG2D-based instances, PD+Ind is competitive with SRS+Ind. These inputs have high locality, which only leaves about one percent of the initial problem after local preprocessing. Here, both PD+Ind and SRS+Ind are dominated by latency. GNM-based instances show results similar to random lists, since the graphs possess almost no locality. Additionally, we scaled SRS+Ind to 24 576 cores on a reduced set of inputs. In this configuration, SRS+Ind requires only 2.5 and 6.7 seconds on random lists with n/p = 220 and n/p = 222 elements, respectively, ranking over 100 billion elements in the latter case. Performance Breakdown. In Fig. 4, we further analyze the impact of the different indirection techniques and give a more detailed insight into the running time of the main three phases of the sparse ruling-set algorithm. We show absolute running times for sparse ruling-set (with and without indirect communication) on random (γ = 1.0) lists with n/p = 222 elements (left) and break them down into the ruler-chasing, ruler-propagation and base-case phases (right). We compare the 2D-grid and topology-aware indirection strategies introduced in Section 2.4. We see that topology-aware communicator grouping has a positive but limited effect on the running time, by up to 10 percent. Further analysis explains why this effect is not more pronounced: While intra-node communication is substantially (up to 1.5× – 3×) faster than communicating between distant compute nodes, the 2D-grid based indirection scheme still groups physically close processors, where communication performance is almost as fast as inside a node.
12
Sanders et al.
List(216 , γ = 1.0)
List(218 , γ = 1.0)
List(220 , γ = 1.0)
1
time /s
10 10
List(222 , γ = 1.0) 102
0
101
100
101
10−1
0
10 10−1
time /s
20 22 24 26 28 GNM(219 , 222 )
20 22 24 26 28 RGG2D(219 , 222 )
20 22 24 26 28
20 22 24 26 28
10−0.5
101
PD SRS
100
PD+Ind SRS+Ind
10−1 20 22 24 26 28
20 22 24 26 28 # compute nodes (×48 cores)
5 0
20 22 24 26 28 # compute nodes (×48 cores)
15 other
10 5
re c 2D t gr id to po .-a wa re
10
Direct 2Dgrid TopoAware
di
time /s
15
per phase time /s
Fig. 3: Scalability of pointer doubling and sparse ruling-set on different instances.
ruler propagation ruler chasing base case
0
20 24 28 # compute nodes (×48 cores)
Fig. 4: Impact of different message indirection techniques on List(222 , γ = 1.0) and detailed phase breakdown.
The plot on the right shows that, for small core configurations, ruler chasing and ruler propagation dominate the running time. With increasing core count, the time spent in the base case increases. This is expected as the size of the base-case subproblem, i.e., the number of selected rulers, grows with the total problem size while the local input size remains constant in this weak-scaling experiment.
4
Conclusion and Future Work
We present a carefully engineered distributed-memory implementation of the sparse ruling-set algorithm and evaluate it on up to 24 576 processors across a variety of instances with differing characteristics, increasing the scale of previous experimental studies by two orders of magnitude. Furthermore, we provide
Engineering Scalable Distributed List Ranking
13
detailed insights on the effects of the applied optimization techniques, which are of independent interest for designing scalable algorithms for other discrete problems. We also conducted preliminary experiments with low-latency asynchronous communication and MPI’s remote-direct memory access (RMA). While the asynchronous approach showed promising results when the number of communication partners is low, and can hide latency by avoiding hard synchronization, it requires further engineering to match the performance of our highly tuned synchronous variants. Limited support for highly irregular accesses by MPI’s RMA interface prohibits straightforward implementations. In the future, we want to adapt our techniques to the more general tree rooting problem, which has applications in e.g. distributed MST computations. While indirect communication and locality exploitation also apply here, tree rooting requires revised ruler selection and needs to consider contention for elements with many predecessors. Lastly, scaling to higher processor counts will require additional levels of indirection to effectively tame startup latencies. Acknowledgments. The authors gratefully acknowledge the Gauss Centre for Supercomputing e.V. (www.gauss-centre.eu) for funding this project by providing computing time on the GCS Supercomputer SuperMUC-NG at Leibniz Supercomputing Centre (www.lrz.de). The authors gratefully acknowledge the computing time provided on the high-performance computer HoreKa by the National High-Performance Computing Center at KIT (NHR@KIT). This center is jointly supported by the Federal Ministry of Education and Research and the Ministry of Science, Research and the Arts of Baden-Württemberg, as part of the National High-Performance Computing (NHR) joint funding program (https://www.nhr-verein.de/en/our-partners). HoreKa is partly funded by the German Research Foundation (DFG).
References 1. Anderson, R.J., Miller, G.L.: A simple randomized parallel algorithm for listranking. Inf. Process. Lett. 33(5), 269–273 (1990). https://doi.org/10.1016/00200190(90)90196-5 2. Anderson, R.J., Miller, G.L.: Deterministic parallel list ranking. Algorithmica 6(6), 859–868 (1991). https://doi.org/10.1007/BF01759076 3. Cole, R., Vishkin, U.: Approximate and exact parallel scheduling with applications to list, tree and graph problems. In: FOCS. pp. 478–491. IEEE Computer Society (1986). https://doi.org/10.1109/SFCS.1986.10 4. Dehne, F., Song, S.W.: Randomized parallel list ranking for distributed memory multiprocessors. Int. J. Parallel Program. 25(1), 1–16 (1997). https://doi.org/10.1007/BF02700044 5. Dehne, F.K.H.A., et al.: Efficient parallel graph algorithms for coarsegrained multicomputers and BSP. Algorithmica 33(2), 183–200 (2002). https://doi.org/10.1007/S00453-001-0109-4 6. Funke, D., et al.: Communication-free massively distributed graph generation. J. Parallel Distributed Comput. 131, 200–217 (2019). https://doi.org/10.1016/J.JPDC.2019.03.011
14
Sanders et al.
7. Hameed, F., et al.: Contour ranking on coarse grained machines: a case study for low-level vision computations. Concurr. Pract. Exp. 9(3), 203–221 (1997) 8. JáJá, J.F.: An Introduction to Parallel Algorithms. Addison-Wesley (1992) 9. Lassous, I.G., Gustedt, J.: Portable list ranking: An experimental study. ACM J. Exp. Algorithmics 7, 7 (2002). https://doi.org/10.1145/944618.944625 10. Miller, G.L., Reif, J.H.: Parallel tree contraction and its application. In: FOCS. pp. 478–489. IEEE Computer Society (1985). https://doi.org/10.1109/SFCS.1985.43 11. Pan, T., et al.: Fast de bruijn graph compaction in distributed memory environments. IEEE ACM Trans. Comput. Biol. Bioinform. 17(1), 136–148 (2020). https://doi.org/10.1109/TCBB.2018.2858797 12. Patel, J.N., et al.: Scalable parallel implementations of list ranking on finegrained machines. IEEE Trans. Parallel Distributed Syst. 8(10), 1006–1018 (1997). https://doi.org/10.1109/71.629484 13. Rehman, M.S., et al.: Fast and scalable list ranking on the GPU. In: ICS. pp. 235–243. ACM (2009). https://doi.org/10.1145/1542275.1542311 14. Reid-Miller, M.: List ranking and list scan on the cray C-90. In: SPAA. pp. 104–113. ACM (1994). https://doi.org/10.1145/181014.181049 15. Sanders, P., et al.: Sequential and Parallel Algorithms and Data Structures - The Basic Toolbox. Springer (2019). https://doi.org/10.1007/978-3-030-25209-0 16. Sibeyn, J.F.: Better trade-offs for parallel list ranking. In: SPAA. pp. 221–230. ACM (1997). https://doi.org/10.1145/258492.258514 17. Sibeyn, J.F.: Ultimate parallel list ranking? In: HiPC. Lecture Notes in Computer Science, vol. 1745, pp. 197–201. Springer (1999). https://doi.org/10.1007/978-3540-46642-0_28 18. Sibeyn, J.F.: List-ranking on interconnection networks. Inf. Comput. 181(2), 75–87 (2003). https://doi.org/10.1016/S0890-5401(02)00029-9 19. Sibeyn, J.F.: Minimizing global communication in parallel list ranking. In: EuroPar. Lecture Notes in Computer Science, vol. 2790, pp. 894–902. Springer (2003). https://doi.org/10.1007/978-3-540-45209-6_123 20. Sibeyn, J.F., Guillaume, F., Seidel, T.: Practical parallel list ranking. J. Parallel Distributed Comput. 56(2), 156–180 (1999). https://doi.org/10.1006/JPDC.1998.1508 21. Träff, J.L.: Portable randomized list ranking on multiprocessors using MPI. In: PVM/MPI. Lecture Notes in Computer Science, vol. 1497, pp. 395–402. Springer (1998). https://doi.org/10.1007/BFB0056600 22. Uhl, T.N., et al.: Kamping: Flexible and (near) zero-overhead C++ bindings for MPI. In: SC. p. 44. IEEE (2024). https://doi.org/10.1109/SC41406.2024.00050 23. Wei, Z., JáJá, J.F.: Optimization of linked list prefix computations on multithreaded gpus using CUDA. Parallel Process. Lett. 22(4) (2012). https://doi.org/10.1142/S0129626412500120 24. Wyllie, J.: The Complexity of Parallel Computations. Ph.D. thesis, Cornell University, USA (1979)