# Toward unprivileged, portable and generic network topology discovery

Thibaut Pepin, Julien Jaeger, Guillaume Mercier, Brice Goglin

► To cite this version:

Thibaut Pepin, Julien Jaeger, Guillaume Mercier, Brice Goglin. Toward unprivileged, portable and generic network topology discovery. SCA/HPCAsia 2026 - Supercomputing Asia and International Conference on High Performance Computing in Asia Pacific Region, Jan 2026, Osaka, Japan. pp.271-283, 10.1145/3773656.3773657. hal-05468186

HAL Id: hal-05468186

https://hal.science/hal-05468186v1

Submitted on 20 Jan 2026

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
Toward Unprivileged, Portable and Generic
Network Topology Discovery

Thibaut Pépin

CEA, DAM, DIF

Arpajon, F-91297, France

Inria, LaBRI, Université of Bordeaux

Talence, F-33400, France

thibaut.pepin@cea.fr

Guillaume Mercier

Bordeaux-INP, Inria, CNRS, LaBRI, UMR 5800

Talence, F-33400, France

guillaume.mercier@bordeaux-inp.fr

Julien Jaeger

CEA, DAM, DIF

Arpajon, F-91297, France

julien.jaeger@cea.fr

Brice Goglin

Inria, LaBRI, Université of Bordeaux

Talence, F-33400, France

brice.goglin@inria.fr

**Abstract**

With the increase in size and complexity of supercomputers, it has become crucial to match applications and communication libraries to the underlying network topology. This matching may allow minimizing the time spent in waiting for high-latency communication and limiting contention on the network. While MPI implementations rely mostly on software such as `hwloc` to retrieve information about nodes topology, no tool currently gathers network topology information in a generic and portable fashion.

In this paper, we propose an algorithm inspired by the Steiner Spanner problem that exploits end-to-end latency measurements to reconstruct a network topology. Our solution reconstructs the topology graph from a matrix of measured communication times. This is achieved by iteratively adding nodes to the graph while trying to match the shortest path length in the graph to the communication times. The total weight and the number of edges in the graph are also minimized.

**CCS Concepts**

* **Computing methodologies → Parallel computing methodologies; Networks → Network monitoring; Programming interfaces.**

**Keywords**

HPC, Hardware topologies, Message Passing, Hierarchical Collective Communications, Graph Reconstruction

**ACM Reference Format:**

Thibaut Pépin, Julien Jaeger, Guillaume Mercier, and Brice Goglin. 2026. Toward Unprivileged, Portable and Generic Network Topology Discovery. In *SCA/HPCAsia 2026: Supercomputing Asia and International Conference on High Performance Computing in Asia Pacific Region (SCA/HPCAsia 2026), January 26–29, 2026, Osaka, Japan*. ACM, New York, NY, USA, 13 pages. https://doi.org/10.1145/3773656.3773657

<figure><img src="image_2.png" /></figure>

This work is licensed under a Creative Commons Attribution 4.0 International License. SCA/HPCAsia 2026, Osaka, Japan

© 2026 Copyright held by the owner/author(s).

ACM ISBN 979-8-4007-2067-3/2026/01

https://doi.org/10.1145/3773656.3773657

**1 Introduction**

Fully harnessing the computing power of a parallel architecture at its maximum raises a lot of issues for any High-Performance Computing (HPC) application. One actual challenge stems from the fact that such applications are deployed on an ever-growing number of computing nodes, which translates into an increase in the number of data exchanges taking place during the execution of the application. As a consequence, it is more than ever crucial to adapt the placement and mapping of tasks or processes as well as the communication pattern of the applications to the topology of the underlying target physical architecture.

**1.1 Motivation and Objectives**

Our main research objective hinges around improving the performance of communications in parallel applications (e.g., collective communication operations in MPI). Topology-aware communications are the target of numerous optimizations that can yield substantial benefits (e.g., improved performance and reduced network contention [1, 2]). However, in order to apply such optimizations, one needs to access the hardware topology information of the target platform. One example of such a tool is `hwloc` [3], which can retrieve information about computing nodes topology. Its use has become so widespread that `hwloc` can now be almost considered as a *de facto* standard, serving both as a programming interface as well as a visualization tool. One could expect even better results by taking into consideration the interconnection network, but this requires substantial information about its layout and topology. To this end, an extension to `hwloc` was designed and prototyped (Netloc [4]). Unfortunately, the lack of portability (one major strength of the original `hwloc`), combined with the necessity to possess administrator privileges to deploy and run `netloc` hampered its development and wide acceptance. The question that arises is therefore: how can one circumvent these portability and privileges issues and come up with a leverageable tool providing tractable information about the network topology?

The motivation of this work is to design and devise a method instantiated in a tool that can provide information about the network topology without administrator privileges. This method is based on two steps. In the first step, we measure the latencies in
the target platform and store them as a matrix. In the second step, we reconstruct the network topology by building a graph, greedily adding vertices and edges so that it matches the latency matrix. We also seek to minimize the number of edges in the resulting reconstructed graph.

## 1.2 Information Retrieval Methods and Approaches

One of the most straightforward approaches to gather the required information about the network is to use performance benchmarks [5–7]. They can deliver information such as latency and bandwidth values between the computing nodes. It can help the application developer to get a better understanding of the network layout. For instance, when a heat map is used, the presence of rectangular areas of similar latencies tends to indicate that processes share a resource. However, as the network size and complexity grow, the results become less understandable, even more so if the nodes on the heat map are shuffled.

Another method to gather information on the network is to determine which routes between computing nodes share a section and then to leverage this piece of information to reconstruct the topology graph. Detecting such shared sections is possible with bandwidth measurements [8, 9]. Whilst this does not constitute an issue in the case of less efficient networks, it can be a problem when the network bandwidth is large enough to prevent its saturation or with duplicated paths (as in our case, see section 4).

Modifying the messages source address to update the switches routing tables [10] is a possible technique to obtain the information. However, it is not applicable in an HPC context since in most HPC networks, the message headers are handled directly by (and in) the hardware.

A widespread technique to retrieve precise information on a network topology is to use hardware-specific tools (e.g., the OFED utilities in the case of Infiniband). Such tools allow the user to query the routing tables in the switches in order to build the network topology graph. Their use to accurately build a representation of the network topology raises a major issue which is the lack of portability because each tool is tailored for a specific network. Moreover, they necessitate administrator privileges to be used. Several solutions [4, 11–15] rely on such a hardware-specific approach. Also, some tools impose restrictions on the network topology they can handle [16] and therefore lack genericity.

## 1.3 Contributions and Plan

According to the previous sections, the ideal network topology information gathering tool should possess the following features: the ability to be deployed and run easily by unprivileged users, portability and robustness to handle current and future network topologies all the while being able to expose clearly to the user the gathered information.

In this paper, we present a work that addresses the aforementioned issues and that supports the desired features.

The contributions of this paper are the following:

(1) *The greedy edge split algorithm*: a generic hardware-agnostic method to gather network topology information from end-to-end latency measurements.

(2) *NetMAC*: a library that manages performance measurements and avoids unnecessary reruns thanks to relevant information storage.

(3) *GESlib*: a library implementing the greedy edge split algorithm.

None of these contributions require or rely on special privileges.

The remainder of this paper is organized as follows: the algorithm that constitutes the core of our method is described in details in Section 2, while Section 3 details its implementation. Section 4 exposes the various tests of topologies reconstruction we carried out to validate our proposal. Last, Section 5 concludes this paper and presents potential future work.

# 2 The Greedy Edge Split Algorithm

As stated previously, our goal is to provide the user with tractable information about the network topology of the target platform. This information can take the form of a graph representing the network topology. This graph reconstruction process needs some input data as well as an algorithm to process it.

* For the input data, we rely on a matrix of latencies between the compute nodes because latencies are correlated to physical distances in the network. Also, such data is rather easy to gather.

* As for the algorithm, we propose the *Greedy Edge Split* algorithm (GES in the rest of this paper) to reconstruct a graph from a latency matrix.

In this Section, we provide a detailed description of our GES algorithm.

## 2.1 Problem Statement

The objective of GES is to reconstruct a graph in which the length of each shortest path between vertices associated to compute nodes matches the latency values measured on the target hardware platform. We shall refer to such vertices as *compute vertices* in the rest of this paper. In order to simplify the route selection for a message (and hence the problem), we make the assumption of the shortest path routing.

We add a constraint to minimize the number of edges and the sum of the edges lengths in the generated graph (known as the graph weight).

This constraint avoids the trivial case of building a complete graph where the edge between a pair of *compute vertices* features the same length as the latency value. Minimizing the graph weight entails to group portions of paths between *compute vertices*, which introduces new vertices in the graph. Those vertices represent physical routing hardware items (e.g., network switches and routers). We shall refer to such vertices as *switch vertices* in the rest of this paper.

The problem we seek to solve with GES is hence similar to the Steiner Spanner problem [17]. The Graph Spanner problem deals with the minimization of a graph weight and its number of connections while keeping the shortest paths lengths within a stretch factor of the ones in the input graph. One variant allows the creation of new vertices in the graph which do not belong to the initial set of vertices in order to allow further optimizations while keeping the distances between vertices closer to that of the
<figure><img src="image_3.png" /><figcaption>Figure 1: GES reconstruction.</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>Figure 2: The Gap function principle.</figcaption></figure>

input graph. However, no algorithm to solve the Steiner Spanner problem currently exists. Current studies on the problem [18–20] focus on improving the bound on the properties of the generated graph. Furthermore, most of these studies are restricted to two-dimensional geometric graphs while most network graphs do not fall into this category. Moreover, methods described for higher dimensions in euclidean and non-euclidean spaces [21, 22] produce bipartite graphs between the vertices in the original graph and the added vertices. This does not fit our requirements as compute nodes can be connected without a switch and multiple switches can be interconnected. Even though the problem solved by GES can be considered as an instance of the Steiner Spanner graph problem, some adjustments are necessary to better address usual HPC network topologies such as fat-trees, tori, grids — and more specifically — dragonflies.

The choice to consider only latencies allows both portability and to not resort to specific privileges. However, it also creates some side-effects on the reconstructable topology types. More specifically, two network topologies generating similar latency matrices will be reconstructed in the same way. One paradigmatic instance of this case is represented by complete graphs and star-shaped graphs which are indistinguishable from the perspective of GES. This is not an intrinsic limitation of our GES algorithm, but rather a consequence of the modeling and the chosen input data.

## 2.2 Algorithm Application

Figure 1 shows the algorithm applied to a basic example (a tree). The input of the algorithm is the 4x4 latency matrix on the left.

The first step is to connect together the first two compute vertices. In the second step, vertex 2 is being added to the graph. A new switch vertex is created on the edge between vertices 0 and 1 to attach vertex 2. The new edges match the shortest path length in the graph with the latency matrix between vertices 0, 1 and 2. The insertion of vertex 3 follows the same pattern as for vertex 2 but three edges are searched for an ideal connection point, instead of a single one previously.

## 2.3 Graph Edge Evaluation

Generally, the objective of the iterative reconstruction process at the core of GES is to connect a compute vertex to the existing graph. To do so, we keep selecting edges to insert a switch vertex on, which we can then connect to the compute vertex being inserted with a new edge.

In order to minimize the number of edges and the weight of the graph, we use a function to evaluate each edge. This function returns the largest set of compute vertices whose shortest paths lengths to the compute vertex being currently inserted matches the latency matrix, should a switch vertex be inserted on the evaluated edge. The position of said switch vertex is also returned, as well as the length of the new edge we need to create between the switch vertex and the new compute vertex.

### 2.3.1 The Gap Function.
For each compute vertex X being inserted, we want to connect it to at least one preexisting edge in the graph. Let the first of these tested edges be $e_j$, an arbitrary edge in the graph. The connection point in $e_j$ is a switch vertex C, with E being the new edge between X and C (see Figure 2). To find the best position for C, we evaluate the shortest path length between C and an already existing compute vertex $x_i$ in the graph. Then, we compare it to the registered latency between X and $x_i$. We define the Gap Function of $(x_i, e_j)$ as the difference between the measured length and the registered latency, depending on the position of C between the two extremities of $e_j$.

Using this definition, given a position on an edge, the Gap Function returns the length of the edge E needed to match the shortest path length in the graph to the registered latency for a specific compute vertex $x_i$. For the same edge $e_j$, if the Gap Functions of multiple preexisting compute vertices intersect, only one edge will need to be created to match the shortest path length to the latency for all those compute vertices. This is why we search for intersections between Gap Functions to minimize both the number of edges and the weight of the graph.

Let us define:

* $d(a, b)$ as the shortest path length in the graph between vertices a and b

* $D(x_1, x_2)$ as the latency between computing nodes $x_1$ and $x_2$

* $c_0$ and $c_1$ as the two extremities of edge $e_j$

* $f \in [0, 1]$ as the position of C on $e_j$ (at $f = 0$, $C = c_0$ and at $f = 1$, $C = c_1$)

* L as the length of $e_j$

The Gap function is defined as:

$$g_{x_i, e_j}(f) = D(X, x_i) - d(C, x_i) = l$$

with l as the length of the to-be-created edge E between X and C.
Three possible behaviors are possible for the Gap Function depending on the direction of the shortest paths from $c_0$ and $c_1$ to $x_i$. In order to distinguish these behaviors, we look at the result of $d(c_1, x_i) - d(c_0, x_i)$.

* **Behavior 1:** The shortest path from $c_0$ to $x_i$ does not go through $e_j$ and the shortest path from $c_1$ to $x_i$ goes through $e_j$.

$$ \begin{cases} d(C, x_i) = d(c_0, x_i) + f \times L \\ d(c_1, x_i) - d(c_0, x_i) = (d(c_0, x_i) + L) - d(c_0, x_i) = L \end{cases} \quad (1) $$

$$ g_{x_i, e_j}(f) = D(X, x_i) - d(C, x_i) = D(X, x_i) - d(c_0, x_i) - f \times L \quad (2) $$
⇒ The Gap Function decreases.

* **Behavior 2:** The shortest path from $c_1$ to $x_i$ does not go through $e_j$ and the shortest path from $c_0$ to $x_i$ goes through $e_j$.

$$ \begin{cases} d(C, x_i) = d(c_1, x_i) + (1-f) \times L \\ d(c_1, x_i) - d(c_0, x_i) = (d(c_0, x_i) - L) - d(c_0, x_i) = -L \end{cases} \quad (3) $$

$$ g_{x_i, e_j}(f) = D(X, x_i) - d(C, x_i) = D(X, x_i) - d(c_1, x_i) - (1-f) \times L \quad (4) $$
⇒ The Gap Function increases.

* **Behavior 3:** The shortest path from $c_0$ to $x_i$ does not go through $e_j$ and the shortest path from $c_1$ to $x_i$ does not go through $e_j$.

$$ \begin{cases} d(C, x_i) = \min(d(c_0, x_i) + f \times L, d(c_1, x_i) + (1-f) \times L) \\ d(c_1, x_i) - d(c_0, x_i) \in [-L, L] \end{cases} \quad (5) $$

In this case, a position F on the edge does exist where:

$$ \begin{align} D(X, x_i) - d(c_0, x_i) - F \times L &= D(X, x_i) - d(c_1, x_i) - (1-F) \times L \nonumber \\ \Rightarrow F &= \frac{d(c_1, x_i) - d(c_0, x_i) + L}{2 \times L} \tag{6} \end{align} $$

$$ \begin{cases} f \in [0, F], g_{x_i, e_j}(f) = D(X, x_i) - d(c_0, x_i) - f \times L \\ f \in [F, 1], g_{x_i, e_j}(f) = D(X, x_i) - d(c_1, x_i) - (1-f) \times L \end{cases} \quad (7) $$
⇒ The Gap Function decreases, then increases.

### 2.3.2 The Points Selection Problem.
Once the Gap Function of each compute vertex in the graph has been associated with its behavior for edge $e_j$, we can search for a point belonging to a Gap Function. With this point $(f, l = g_{x_i, e_j}(f))$ selected, we create a switch vertex at position $f$ on $e_j$ and connect it to $X$ with an edge of length $l$.

The selected point has to fulfill one condition to be considered valid:

* No other Gap Function must be larger for the selected point. This is to prevent the creation of a path shorter than the value in the latency matrix. If such a point $(f_0, l_0)$ were to be selected on the Gap Function of the compute vertex $x_i$ with the Gap Function of the compute vertex $x_j$ being larger, the consequence would be:

$$ \begin{cases} g_{x_i, e_k}(f_0) = l_0 \\ g_{x_j, e_k}(f_0) > l_0 \end{cases} \quad (8) $$

This would imply that a path even shorter than the latency value between $X$ and $x_j$ is created:

$$ \begin{align} g_{x_j, e_k}(f_0) &= D(X, x_j) - d(f_0, x_j) > l_0 \nonumber \\ &\Rightarrow l_0 + d(f_0, x_j) < D(X, x_j) \tag{9} \end{align} $$

In Figure 3a, the point $(f_0, l_0)$ is invalid. The creation of this edge would create a path too short between compute vertices $X$ and $0$ as $g_0(f_0) > g_1(f_0)$.

As previously written, our objectives are to minimize the number of edges in the graph as well as its total weight. The two following conditions stem from these objectives. They are ordered from highest to lowest-ranking priority.

* The selected point should belong to as many Gap Functions as possible (i.e. on the intersection between Gap Functions should there be any), in order to match the length of each shortest path in the graph to the values in the latency matrix for the highest number of compute vertices.

In Figure 3b, both points are valid but since two Gap Functions intersect at $(f_0, l_0)$ against one at $(f_1, l_1)$, $(f_0, l_0)$ is selected.

* The selected point should have the lowest Gap value to minimize the length of the created edge.

In Figure 3c, both points are valid and have the same number of intersections but as $g_0(f_0) < g_0(f_1)$, $(f_0, l_0)$ is selected.

### 2.3.3 Solving the Selection Problem with Gap Function Segments.
Finding an intersection value for the Gap Functions in the case of increasing or decreasing Gap Functions is rather straightforward. However, taking into account the third type of behavior requires some modifications.

To prevent the complexity cost of searching an intersection point for each of the compute vertices complying with these behaviors, we split the Gap Function at its inflection point into two segments, one ascending and the other one descending.

Each such segment is characterized by:

* An interval.

* An anchor value: the Gap value at $f = 0$. If the segment interval does not include 0, we artificially extend it to obtain its anchor value.

* The group of compute vertices whose Gap Function includes this segment.

* A slope: ascending or descending.

With this modification, segments featuring the same anchor values and the same slopes can be regrouped or packed. This can lead to the generation of new segments with larger group of compute vertices. For example, a segment on the interval $[0, 0.5]$ with the compute vertices group $\{0\}$ and a segment on the interval $[0.25, 1]$ with the compute vertices group $\{1, 2\}$, both featuring same anchor values and slopes, will be packed into three segments:

* interval $[0, 0.25]$, compute vertices group $\{0\}$

* interval $[0.25, 0.5]$, compute vertices group $\{0, 1, 2\}$

* interval $[0.5, 1]$, compute vertices group $\{1, 2\}$

To only consider segments in the edges evaluation algorithm, we also create segments for compute vertices with the first two Gap Function behaviors (i.e., monotonically increasing or decreasing). A single segment is created (before packing) from each of those compute vertices as their Gap Functions are monotonic.
<figure><img src="image_5.png" /><figcaption>Figure 3: Selection criteria for edges evaluation.</figcaption></figure>

Once this packing step is done, we can select the best point by checking segment intersections. An important possible optimization in order to reduce the complexity of the segment intersection search is to keep only the segments for each slope type with the highest anchor value. This is possible because according to the first condition in section 2.3.2, the selection of a point on a segment with a Gap function value smaller than any other segment is not allowed. This optimization reduces the number of segments and simplifies the segments intersection checks as all segments with the same slope share the same anchor value.

Figure 3d shows the Gap Function of 7 compute vertices. With the previously mentioned optimization, we only consider the following segments:

* Increasing segment $s_0$: interval $[0, f_1]$, anchor $l_1$, compute vertices group {4}

* Increasing segment $s_1$: interval $[f_1, f_2]$, anchor $l_1$, compute vertices group {3, 4}

* Increasing segment $s_2$: interval $[f_2, 1]$, anchor $l_1$, compute vertices group {3, 4, 6}

* Decreasing segment $s_3$: interval $[0, 1]$, anchor $l_2$, compute vertices group {2}

The segments $s_2$ and $s_3$ intersect at $(f_0, l_0)$. This represents the intersection of the 4 Gap Functions from compute vertices 2, 3, 4 and 6. It is the optimal point in our example.

### 2.3.4 The Edges Evaluation Algorithm.

Algorithm 1 presents the edges evaluation algorithm. This function evaluates all edges to find the one where the most of Gap Functions intersect (if there is an intersection) and with the lowest Gap Function value in case of equality. To this end, for each edge in the graph we loop over the compute vertices to get their Gap Function. The Gap Functions are segmented and packed to keep only the segment of each slope type with the highest anchor value. We then check for an intersection between those two segments if they both exists.

Once this step is achieved, we split the returned edge at the returned position and create an edge between the compute vertex

**Algorithm 1** The EvaluateEdges algorithm.

Require: computeVertex X

Ensure: edge $e_j$, group, factor, length

1: **for all** $e_j \in \text{edges} \text{ do}$

2:   **for all** $x_i \in \text{compute\_vertices} \text{ do}$

3:   SegmentCreateAndPack($X$, $x_i$, $e_j$, segments\_asc, segments\_desc)

4: **end for**

5:   (group, factor, length) ← SegmentIntersection(segments\_asc, segments\_desc, $e_j$, compute\_vertex)

6: Keep the tuple ($e_j$, group, factor, length) with the larger group, or the lower length in case of equality.

7: **end for**

currently being inserted and the created switch vertex. This edge possesses a length equal to the returned gap value.

## 2.4 Graph Pruning

During the graph reconstruction, some patterns can cause the creation of edges and switch vertices which do not actually belong to the underlying hardware. We call these elements construction edges and switch vertices since their sole task is to help with the reconstruction of the graph. This might happen if cycles are present in the original topology. They should be removed as soon as possible during the reconstruction process. We now detail cleaning methods to remove them.

### 2.4.1 Construction Edges Removal. Construction edges characteristic is that they can be removed without lengthening any shortest paths between compute vertices.

However, while adding edges to the graph and updating the shortest paths is easy and can be done efficiently, this is not the case when trying to detect an edge no longer needed due to the insertion of another edge elsewhere in the graph.

To alleviate this issue, GES features a function that detects if an edge can safely be removed without increasing the distance
between compute vertices. This function loops over all edges and removes them individually. Once an edge is removed, all paths lengths between compute vertices are checked. If the shortest path between two compute vertices conflicts with the value in the latency matrix, the deleted edge is inserted back. Note that the removal of edges can lead to switch vertices featuring an arity lower than 3 that can be safely removed.

### 2.4.2 Construction Switch Vertices Merging.
Some switch vertices might also end up being duplicated. This can occur when dealing with network topologies that feature cycles of switches. Figure 4 shows the switch vertices merger steps with a “cycle of stars” type of network. The first compute vertex of a star (9 in the example) is inserted into the cycle by creating two edges. The insertion of the second compute vertex of the star (10) will split both edges previously created. Both switch vertices represent the same network switch and must be merged. This is easier than the edges removal process as there is less updates to do in the graph and as mergeable switch vertices are at a 2 hops distance. Indeed, the direction to all compute vertices from any vertices does not change when construction switch vertices are merged.

Every time a new compute vertex is connected to the graph, we loop over its neighboring switch vertices. For each pair of switch vertices, we check if the edges to vertices connected to both switch vertices are of the same length. We also check if the merging of both switch vertices creates a path shorter than the shortest path between any pair of compute vertices. If this is not the case, the pair of switch vertices is merged.

During our tests, switch vertices which could be merged were created by the insertion of a single compute vertex, e.g. in Figure 4, both switch vertices to merge are created by the insertion of compute vertex 10. Switch vertices being created as the outcome of the insertion of different compute vertices can not be merged for the time being. However, this case was never encountered practically.

## 2.5 Dragonfly Topologies Management

As stated previously, the GES algorithm cannot differentiate between a complete graph and a star-shaped network. This can be especially problematic for dragonfly topologies. The GES algorithm can still produce a graph representing the network hierarchy, but with inaccuracies as some supplemental switch vertices can be inserted (see Figure 5). Since dragonfly topologies are widely used in the most powerful supercomputers ranked in the Top500¹, it is therefore crucial to reconstruct accurately this type of topologies.

To overcome this issue, we added a post-processing step that removes the switch vertices located at the center of stars and that rebuilds the complete graph. This step relies on a dragonfly network pattern detection.

Network switches in a dragonfly topology are direct, meaning that they are all connected to a compute node. We introduce the notion of second-level directness, where a switch is “second-direct” if it is only connected to direct switches. Our post-processing step looks for second-direct switch vertices with a cycle connecting two of its nearest neighbors.

<caption>**Algorithm 2** The Greedy Edge Split algorithm.</caption>

```c
Require:compute safex[ ], latencyMatrix[ ][ ]
1: Connect(host0, host1, latencyMatrix[host0][host1])
2: for all host_source_i ∈ compute safex[2 : n] do
3:     do_match ← {}
4:     while do_match ≠ compute safex[0 : i] do
5:         (edge, group, factor, length)
6:         ← EvaluateEdges(host_source_i)
7:         switch safex
8:         ← SplitEdge edge, factor
9:         do_match
10:        ← do_match ∪ group
11:        Connect(host_source_i, switch safex, length)
12:        MergeSwitches(host_source_i, switch safex)
13:    end while
14:    PruneGraph()
15: end for
16: PostProcessing()
```

Although the use of this pass allows to correctly reconstruct dragonfly topologies, it also modifies graphs representing non-dragonfly ones. While this might be problematic, we did not encounter undesired modifications in our test cases. The theoretical examples potentially harmed by such modifications are systems featuring unusual topologies, such as a cycle of two-level trees connected by their middle-level switch vertices but not by their roots. In such very specific cases, the post-processing step can always be deactivated. Figure 9g presents a dragonfly reconstructed by GES using the post processing step.

This post-processing step is the only modification in the algorithm that strays from the solution to the Steiner spanner problem (cf. Section 2.1) since both the total weight of the graph as well as its edges number are increased.

## 2.6 Algorithm Description

Algorithm 2 presents the different steps of the GES algorithm. Compute vertices are inserted one by one in any order while matching the length of each shortest path in the graph with the latency matrix for all already placed compute vertices.

The first two compute vertices are connected with the length specified in the latency matrix (Line 1). For each new compute vertex, we create the minimal number of connections to match the latency matrix. To achieve this, each edge in the graph is evaluated with EvaluateEdges (Line 5, see algorithm 1).

The evaluation function (see section 2.3) selects an edge on which we can insert a new switch vertex. This selection process maximizes the size of the group of compute vertices whose shortest path length in the graph matches the value in the latency matrix once the switch vertex is created. This group is returned along the selected edge, as well as the chosen point comprised of the position on the edge (factor) and the Gap Function value (length). A new switch vertex is then created and an edge is added between the new switch vertex and the compute vertex being inserted.

We check to see if the new switch vertex needs to be merged with another (Line 9, see 2.4.2). Once the new compute vertex is fully

<footnote n="1">¹Eight supercomputers among the top 10 as of the writing of this paper.</footnote>
<figure><img src="image_6.png" /><figcaption>Figure 4: Switch vertices merging in the case of a cycle of stars.</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>Figure 5: Dragonfly topology reconstruction (before post-processing).</figcaption></figure>

inserted in the graph, we remove construction edges and *switch vertices* (Line 11, see 2.4.1). The post-processing step for dragonfly topologies is performed when the reconstruction process is over (Line 13, see 2.5).

More connections are added to the *compute vertex* currently being inserted until the latency matrix is consistent with the length of each shortest path to all already placed *compute vertices*.

# 3 Implementation

This section gives some insights about the implementation of our solution, which actually relies on two pieces of software. The first one, called NetMAc, is responsible of gathering latency information and of managing the resulting latency matrices. The second reconstructs the network topology using those latency matrices and is the actual implementation of GES, GESlib.

## 3.1 NetMAc

NetMAc is the library that manages the creation and the storage of network latency matrices. We detail its key points in the following subsections.

### 3.1.1 Latency Assessments.
To obtain a matrix of latencies, NetMAc relies on MPI ping-pong benchmarks. The time needed for a communication can be modeled as $time = overhead + latency + msg_size/bandwidth$. In the case of small messages (1 byte in our case), the bandwidth term is negligible. Exiting the send function of MPI does not guarantee that the message has been received. That is why we wait for an acknowledgment and instead measure $2 * (overhead + latency)$. Measurements are performed multiple times but only the median latency between pairs of compute nodes is kept.

While the complexity of this performance assessment is in $O(n^2)$ when carried out sequentially, it can be reduced to $O(n)$ if done in parallel. This is possible because the latency tests generate only a small amount of congestion on the network.

### 3.1.2 Storing Latency Matrices.
The latency measurement phase is likely to remain costly: a sensible approach is then to store the results in order to avoid running the same tests over again.

The custom file format used by NetMAc provides the possibility to aggregate together latency matrices obtained from multiple runs

of the ping-pong benchmark. This allows the user to obtain the full latency matrix of the target platform part by part, without the need to reserve the whole cluster. Hence, it facilitates the reconstruction of the network topology for a regular user through several resource reservations. The latency matrix of our test cluster was gathered using multiple reservations of approximately 10% of the cluster at a time. Since network failures or topology changes may occur between several NetMAc invocations, it uses a time invalidation parameter on the measured latencies.

#### 3.1.3 Utilization.
Once queried to fill a latency matrix for a specific node reservation, NetMAc will first read in the global shared file containing the latency matrix for the whole cluster. As some latency values might be missing or outdated, it will run ping pong benchmarks to gather them. The shared file will be updated according to the newly measured latencies. Thus, the latency matrix is updated on a regular basis.

During the benchmark phase, as NetMAc offers the possibility to only reserve a part of the machine, other users may also run programs on the machine at the same time. This can generate congestion on the network and disturb the measurement process. However, in our tests measuring latencies on 10% of the nodes of our test cluster, the network congestion generated by other users did not impede the ability of GESlib to successfully retrieve meaningful latencies and reconstruct the underlying network topology.

To facilitate its integration, NetMAc can be called both from inside or outside of an MPI implementation by relying on function pointers.

## 3.2 GESlib

For the implementation details of the GES algorithm, we present the noise management included in the latency assessment as well as the graph merging functionality of GESlib to improve performance. We also propose a study of the algorithmic complexity of GES before addressing the various corner-cases it has to tackle.

#### 3.2.1 Noise Mitigation.
As we rely on a matrix of latencies measured by ping-pong benchmarks, the algorithm must take into account the noise included in these measurements. This is managed by the following six parameters with fixed values :
*   **Splitting error:** When splitting an edge to insert a *switch vertex*, if we are close to the end of the edge, we directly connect to the vertex at the extremity without creating a *switch vertex*.

Value: 3% of the edge length.

*   **Intersection error:** When checking for intersections between segments, if two segments with different behaviors almost intersect, we consider that they actually do.

Value: 5% of a segment length between the endpoint of the segment and the intersection point.

*   **Validation error:** When checking if the distance in the graph between a pair of *compute vertices* matches the value in the latency matrix, the difference between them should be lower than the validation error to be considered as a match.

Value: 5% of the latency.

*   **Grouping error:** When packing segments, we pack two segments together if they have similar anchor value.

Value: 5% of the anchor value closest to 0.

*   **Behavior error:** When checking the Gap Function behavior, the inflection point of the Gap Function for the third behavior can be close to the end of the edge. In that case we select the behavior from the two monotonic behaviors.

Value: 5% of the edge length.

*   **Switch merging error:** While checking if two *switch vertices* can be merged together, we verify that they both connect to the same vertices, with edges of approximately the same length.

Value: 0.2% of the smallest edge length.

The values listed above are the ones chosen for our testbed. These parameters values are selected empirically and might need some tweaking depending on the network characteristics and on the chosen MPI implementation. As the choice of the parameters affects the level of details in the graph, the values are bounded by the relative length of the edges we want to keep in the graph. This bound depends mostly on two factors:

*   The characteristics of the different kinds of networks in the case of a mixed setting.

*   The overhead of the MPI function. As this overhead is included in the latency value, it is added to the length of edges egressing from *compute vertices*. This increases the edge length difference between two *switch vertices* and between a *compute vertex* and any other vertex. The lower the MPI function overhead, the more aggressive we can act on the noise mitigation parameters.

### 3.2.2 Improving Performance with Graph Merging.
In order to split the full reconstruction process into multiple smaller steps and thus decreasing the time needed for reconstruction and easing the parallelisation of the implementation, we implement the merging of two graphs.

Reconstructing multiple subgraphs before merging them pairwise decreases the time needed for the full reconstruction as problems of smaller sizes are tackled. Indeed, the merger step does not need to add as many edges because some are already present in the subgraphs. The full latency matrix is still required. Merging subgraphs instead of reconstructing the graph from scratch yields the same result.

The current solution relies on applying the GES algorithm to match the shortest path length to the latency values between *compute vertices* of one subgraph to the other. We rely on the graph pruning phase to remove construction and duplicated edges and *switch vertices*. Figure 6 illustrates the merging of two subgraphs A and B, both reconstructed separately as 4-node tori. In step 1, we match the shortest path length between the first *compute vertex* of subgraph B and all *compute vertices* of subgraph A to the latency matrix (not shown in this example). To do so, we split the edge between vertices 0 and 2 and then insert vertex 1 at the connection point. Once the subgraphs are no longer disconnected, we can apply the graph cleaning step. We continue to create edges to match the shortest paths length between *compute vertices* of subgraphs A and B. In step 2, after the insertion of vertex 3 on the edge between vertices 2 and 4, the edge between vertices 1 and 3 is removed as it does not create any shortest path. In step 3, similar to step 2, the insertion of vertex 5 causes the removal of the edge between 3 and 5. At the end of step 4, all edges present in subgraph B are removed. However, this constitutes a worst-case scenario where subgraphs A and B are completely interlocked. In more regular cases, we expect some parts of subgraph B to not be interlocked with subgraph A and hence to remain in the resulting graph. This method is best suited for graphs where *compute vertices* are directly connected to one another without *switch vertices*. When it is not the case, the second subgraph might be rebuilt, effectively duplicating it, leading to edges getting deleted in the graph cleaning phase. Thus, the graph merging would not provide any benefits.

### 3.2.3 Algorithmic Complexity.
GES fares high in the cost spectrum due to its time complexity and its memory utilization. Memory-wise, we need to load the full latency matrix and store the graph. With $n$ being the number of compute nodes, the latency matrix uses $O(n^2)$ memory space. The reconstructed graph has $n$ *compute vertices*, $s$ *switch vertices* and $e$ edges. $s$ and $e$ are in $[O(n), O(n^2)]$ and $[O(1), O(n^2)]$ respectively depending on the topology. To avoid unnecessary recomputations, we store the shortest paths information in the graph. Each vertex possesses an array representing the distance and direction of all *compute vertices*. This representation leads to a memory complexity of $O((n+s) * n)$ which is between $O(n^2)$ and $O(n^3)$.

As far as time is concerned, the complexity of GES is in $O(n^3)$ in the case of grids, tori and trees because their number of edges is in $O(n)$. In the worst-case scenario, i.e. when dealing with complete graphs featuring an edge number in $O(n^2)$, time complexity rises up to $O(n^5)$. All *compute vertices* are placed one by one (depth level 1, $O(n)$). We create connections as long as the length of each shortest path does not match the latencies, with $n$ connections at most at each step (depth level 2, $O(e/n)$). To create a connection, each edge is evaluated (depth level 3, $O(e)$). To do so, we loop over the *compute vertices* to create segments (depth level 4, $O(n)$). We then look for intersections between the two segments with the higher anchor value of each slope type (depth level 4, $O(1)$). Additionally, after matching the distance in the graph to the latency matrix, we apply an edge cleaning phase (depth level 2) by looping over all edges (depth level 3, $O(e)$) and by checking whether the shortest path length between all *compute vertices* still complies with the values in the latency matrix (depth level 4, $O(n \times e)$). The edges evaluation
<figure><img src="image_8.png" /><figcaption>Figure 6: Graph merging.</figcaption></figure>

is performed in parallel using OpenMP since there are no data dependencies when evaluating multiple edges.

### 3.2.4 The Corner Cases of GES.
The GES algorithm reconstructs a topology graph based on a latency matrix used as a distance matrix. As multiple graphs can produce similar distance matrices, it can be impossible to distinguish some patterns from others. The most noticeable of these patterns are:

*   Duplicated paths: if a path is set up in such a way that one of the path can be removed without lengthening a shortest path between two nodes, it will not have any impact on the latency matrix and will not be reconstructed by GES. This happens in the case of fat-trees: the duplicated paths and switches are not reconstructed and the result is a regular tree.

*   Complete graphs and stars: in both cases of complete graphs and star topologies with uniform edge lengths, all nodes are at the same distance one from another. Since we minimize the number of edges and the total weight of the graph, the star pattern is always preferred.

*   Switches with an arity lower than 3: as *switch nodes* are created in the graph by merging common sections of paths between nodes, a consequence is that a switch featuring an arity of 2 or less is not reconstructed by GES.

## 3.3 Integration

The deployment of GES in its current state is rather straightforward. GESlib as well as NetMAc' source code will be made available and use an autotool-based build system. A file accessible by multiple users is required to store the latency matrices and share them between users.

Figure 7 illustrates the workflow of NetMAc and GESlib from a user's standpoint. The user sends a job request to the job scheduler which will select nodes in the supercomputer based on their availability and its internal rules. The job scheduler then launches the user application on the selected nodes. The first step of the toolchain to obtain the topology is to use NetMAc to get the latency matrix between the different nodes. The steps followed by NetMAc are described in section 3.1.3. With the latency matrix, it is up to GESlib to reconstruct the network topology using the GES algorithm. A simplified version is included in the figure. Once this is done the user is now in possession of the reconstructed topology.

While this toolchain gives the possibility to every user to gather network topological information, its use with MPI is trickier. A first possibility is to rely on the PMPI interface, making it possible

to add external code to initialize NetMAc and GESlib in MPI_init. However, the user would not have access to the internals of the MPI implementation. Indeed, it would be necessary to re-implement collective operations to use information on the network topology. A second possibility is to use an MPI implementation directly integrating GESlib and NetMAc. However this is out of the hands of most users. The most efficient algorithms will require the user to directly modify the MPI implementation or wait for an integration of GES in its code.

# 4 Topology Reconstruction Tests

In this section we present results obtained with the GES algorithm using as input data latencies measured in a real system and synthetic latency matrices. Then, we show the time needed for reconstructing a topology graph in the case of tori of various (increasing) sizes. The figures generated for this paper are created by inputting a string in dot format exported by GESlib into the neato layout engine which is part of Graphviz [23], an open source graph visualization software.

## 4.1 Real System

We first test GESlib on an Infiniband fat-tree cluster featuring two levels of switches and 129 compute nodes. The nodes, featuring 20-core Intel Skylake CPUs clocked at 2.4GHz, are connected by a Mellanox Infiniband ConnectX-4 EDR with a bandwidth of 100Gb/s. The topology of the cluster is presented in Figure 8. This topology is not synthetic and showcases an imbalance in the nodes distribution among the switches. The node count per switch ranges from 4 (switch `S_0_5`) to 21 (switch `S_0_1`, `S_0_3` and `S_0_4`). Compute nodes are grouped and connected to 9 first-layer switches, themselves connected to 5 second-layer switches.

The reconstruction test is done on 100 compute nodes out of the 129 available (indicated under the node group in Figure 8 with the label "Allocated"). We showcase in Figure 9h the result delivered by GESlib. In this figure, one can observe 6 groups of nodes labeled `c1` to `c6`, with variable number of nodes in each group. The size of each group is depicted in Table 1.

We now compare the reconstructed topology to the actual allocation and topology information. According to the group size, group `c5` in Figure 9h corresponds to switch `S_0_8`, as it displays 6 nodes which is the number of nodes under this switch in our allocation. We checked this mapping by comparing the host name in the group `c5` with the actual cluster information. We do the same verification with every reconstructed groups, mapping group `c1` to switch `S_0_0`, group `c2` to switch `S_0_2`, group `c3` to switch `S_0_1`, group `c4` to switch `S_0_4` and group `c6` to switch `S_0_3`.
<figure><img src="image_9.png" /><figcaption>Figure 7: GESlib and NetMAc workflow.</figcaption></figure>

<figure><img src="image_10.png" /><figcaption>Figure 8: Test cluster network topology.</figcaption></figure>

<table><caption>Table 1: Reconstructed groups size.</caption><thead><tr><th>Group name</th><th>c1</th><th>c2</th><th>c3</th><th>c4</th><th>c5</th><th>c6</th></tr></thead><tbody><tr><th>Size</th><td>17</td><td>15</td><td>21</td><td>21</td><td>6</td><td>20</td></tr><tr><th>Matching switch</th><td><i>S_0_0</i></td><td><i>S_0_2</i></td><td><i>S_0_1</i></td><td><i>S_0_4</i></td><td><i>S_0_8</i></td><td><i>S_0_3</i></td></tr></tbody></table>

By matching the reconstructed groups using their size and host names to the reference topology, we show that GESlib delivered a successful reconstruction of the network topology.

At the time of this experiment, the latency of a compute node was doubled in the group c1 attached to switch S_0_0. While the origin of this phenomenon remains undetermined, the graph reconstructed

by GESlib allowed us to pinpoint this faulty compute node in our test cluster. It is marked in red and located at the top right of the group c1. The edge connecting it to its switch vertex is longer than any other edge between the same switch vertex and other compute vertices.

As mentioned in Section 3.2.4, GESlib is not in the capacity of reconstructing duplicated paths due to the shortest path routing assumption. In this case, the second layer of switches is reconstructed as a single switch vertex since all second-layer switches provide identical routes between compute nodes.

To provide an insight on the algorithm robustness with regard to noise management, the latency matrix is gathered using two
different MPI implementations, Open MPI [24] and MPC [25]. As mentioned in section 3.2.1, the MPI function overhead limits the aggressiveness of the noise management parameters. Open MPI (resp. MPC) features a traversal cost for an additional switch level of 30% (resp. 5%). As a consequence, an edge connecting a *compute vertex* to a first-level *switch vertex* is 3.5 (resp. 20) times longer than an edge connecting *switch vertices*. In both cases, the topology was successfully reconstructed. Being able to reconstruct the topology with both data sets demonstrates the robustness of the noise management parameters.

## 4.2 Synthetic Latency Matrices

After validating the algorithm on a real-world computing system, we test GESlib on synthetic noiseless latency matrices built from widespread network topologies. The presented figures are graphs generated by GES. The test methodology is to first build a synthetic topology with link latencies exhibiting a behavior similar to the real system testbed. The latency matrix is then computed using the shortest path routing assumption. Lastly, the matrix serves as input to GES. All these reconstructions (except Figure 9h, see Section 4.1) are performed flawlessly: the regenerated topologies are the same as the synthetic ones (used as input). The algorithm successfully produces a graph topology for: N-dimensional hypercubes (Figure 9a), N-dimensional grids (Figure 9b), N-dimensional tori (Figure 9c), trees (Figure 9d), dragonflies (Figure 9g). We also try a combination of some of these topologies, in a setting where they are interconnected to a central *switch vertex* (Figure 9e and Figure 9f). We then test the same synthetic latency matrices with some added noise (up to 3%) and the results remain unchanged.

<figure><img src="image_11.png" /></figure>

<figure><img src="image_12.png" /></figure>

<figure><img src="image_13.png" /></figure>

<figure><img src="image_14.png" /></figure>

## 4.3 Performance Evaluation

We assess the topology graph reconstruction times in the case of tori, trees and dragonflies of various sizes on an AMD EPYC 7H12 64-Core 2.6GHz processor using a single thread. The latency matrices are noiseless and the reconstruction uses the graph merging functionality on the tori (see section 3.2.2). We first build *M* subgraphs and then merge them pairwise, following a binary tree pattern.

Table 2 presents the results for tori, trees and dragonflies. The sizes are described as follows:

* An "A × B" tree specifies a 3 level tree (2 plus root node) where "A" compute nodes are connected to each switch and "B" of those switches are connected to the root switch.

* An "A × B × C" torus specifies a 3D torus of dimensions "A × B × C".

* An "A × B × C" dragonfly specifies a dragonfly with "A" compute nodes connected to each switch, "B" switches form a clique, and "C" cliques form the dragonfly.

With these descriptions, an "A×B×C" topology always has A×B×C compute nodes. The size of the topologies were determined to keep the edges per node constant as much as possible across the different sizes, with 1.1 for trees, 3 for tori and 1.5 for dragonflies. M1, M2 and M8 indicate the number of subgraphs used during the reconstruction process (i.e. 1 — no merging —, 2 or 8). In the columns labeled *in order*, the compute nodes order in the latency matrix follows the torus dimensions. In the columns labeled *shuffled*,

<caption>Figure 9: Topologies reconstructed with GESlib.</caption>
<table><caption>Table 2: GESlib reconstruction times (in seconds) for torus, tree and dragonfly topologies.</caption><thead><tr><th rowspan="2">Torus size</th><th colspan="3">In order</th><th colspan="3">Shuffled</th></tr><tr><th>M1</th><th>M2</th><th>M8</th><th>M1</th><th>M2</th><th>M8</th></tr></thead><tbody><tr><td>5 × 4</td><td>1.3e-3</td><td>8.9e-4</td><td>1.3e-3</td><td>2.4e-3</td><td>5.8e-3</td><td>5.8e-3</td></tr><tr><td>5 × 4 × 2</td><td>2.4e-2</td><td>9.4e-3</td><td>8.3e-3</td><td>3.2e-2</td><td>4.2e-2</td><td>4.6e-2</td></tr><tr><td>5 × 4 × 4</td><td>5.5e-1</td><td>1.2e-1</td><td>9.3e-2</td><td>8.4e-1</td><td>5.9e-1</td><td>5.7e-1</td></tr><tr><td>10 × 4 × 4</td><td>7.2e+0</td><td>1.1e+0</td><td>6.7e-1</td><td>1.2e+1</td><td>5.4e+0</td><td>5.7e+0</td></tr><tr><td>10 × 10 × 4</td><td>2.1e+2</td><td>2.4e+1</td><td>9.7e+0</td><td>4.2e+2</td><td>1.7e+2</td><td>1.5e+2</td></tr><tr><td>10 × 10 × 10</td><td>7.4e+3</td><td>1.1e+3</td><td>2.7e+2</td><td>1.2e+4</td><td>7.9e+3</td><td>4.7e+3</td></tr></tbody></table>

<table><thead><tr><th>Tree size</th><th>In order</th><th>Shuffled</th></tr></thead><tbody><tr><td>10 × 2</td><td>1.7e-4</td><td>1.8e-4</td></tr><tr><td>10 × 4</td><td>8.8e-4</td><td>9.6e-4</td></tr><tr><td>10 × 4 × 2</td><td>5.8e-3</td><td>6.4e-3</td></tr><tr><td>10 × 4 × 4</td><td>4.3e-2</td><td>4.7e-2</td></tr><tr><td>10 × 10 × 4</td><td>6.1e-1</td><td>6.7e-1</td></tr><tr><td>10 × 10 × 10</td><td>9.5e+0</td><td>1.0e+1</td></tr><tr><td>10 × 10 × 10 × 2</td><td>8.9e+1</td><td>9.9e+1</td></tr><tr><td>test cluster (100 nodes)</td><td>X</td><td>1.4e-2</td></tr></tbody></table>

<table><thead><tr><th>Dragonfly size</th><th>In order</th><th>Shuffled</th></tr></thead><tbody><tr><td>4 × 5 × 1</td><td>2.1e-4</td><td>2.3e-4</td></tr><tr><td>4 × 5 × 2</td><td>1.1e-3</td><td>1.2e-3</td></tr><tr><td>4 × 5 × 4</td><td>9.0e-3</td><td>1.4e-2</td></tr><tr><td>5 × 4 × 8</td><td>1.2e-1</td><td>3.4e-1</td></tr><tr><td>10 × 10 × 4</td><td>6.5e-1</td><td>7.7e-1</td></tr><tr><td>10 × 10 × 10</td><td>1.2e+1</td><td>1.6e+1</td></tr><tr><td>10 × 10 × 20</td><td>2.4e+2</td><td>3.7e+2</td></tr></tbody></table>

the latency matrix is shuffled. We also included the time needed for the reconstruction of the test cluster presented in section 4.1.

The time needed for the reconstruction grows quickly with the problem size due to the complexity of the GES algorithm. Shuffling the latency matrix (for *M1*) increases the reconstruction times since more construction edges and *switch vertices* are added to the graph. Since they need subsequent removal, the time spent in the graph cleaning phase is increased.

Increasing the number of subgraphs decreases the overall execution time (see section 3.2.2). This phenomenon is even more pronounced in the case of a latency matrix that is *in order*. This is due to the subgraphs being completely independent in the overall topology. In such a case, the merger step only performs an interconnection of the subgraphs. In the case of a shuffled latency matrix, the subgraphs are more interlocked one with the other. Some edges and *switch vertices* end up being duplicated in multiple subgraphs. This increases the complexity of the merger step, hence decreasing the benefits of using multiple subgraphs.

## 5 Conclusion and Future Works

In this paper, we presented a methodology to gather and provide information about the network topology without leveraging administrator privileges. We implemented this methodology as two separate tools: GESlib and NetMac. It is a first step toward a netloc equivalent. As such, the purpose of the envisioned toolchain is to enable transparent optimizations taking into account the network topology, minimizing distance per byte or avoiding congestion on network links. By regularly updating the gathered information

about the network, it could also detect faulty links and avoid using them.

We showcased that GES is robust enough to handle current network topologies found in supercomputers. It relies on the assumption of the shortest path routing to evaluate edges during the graph reconstruction process in order to find the edges to insert. GESlib allows to retrieve topological information on the network topology, and in case of a hierarchical topology, to form nested node groups required for MPI 4.0 communicator hierarchical splitting. Such node groups can also be used to adapt MPI collective algorithms or neighborhood communicator rank reordering to the network topology. NetMac and GESlib have been designed to allow information retrieval and topology reconstruction by part. Indeed, it is not necessary to reserve the full cluster to exploit a useful topology. Each new resource reservation can build its own part of the topology with meaningful information for the associated job communications. This sub-topology can be combined, through our Graph Merging algorithm, with pre-existing reconstructions to gradually build the full machine topology.

The current implementation could be optimized in several ways. The pruning algorithm represents a large part of the execution time and currently has the best potential for performance improvement. The current brute force detection of the edges usefulness could be replaced by a method that tracks at each step the number of alternative paths along the shortest path. Sections of shortest paths with one or more alternative paths could be removed. Another performance improvement could be MPI parallelisation, as the problem size is the number of computing resources. Note that OpenMP parallelisation is already implemented for the edge evaluation.

While we only showcase the reconstruction of the network topology, GES relies solely on a distance matrix (representing network latencies in this paper) and could be used in other situations. It could be used to discover the file system network in a cluster or the intra-node multi-GPU interconnections. These use cases have not been tested and have the same constraints as those described in this paper: a probing method has to exist to obtain the distance matrix, the provided distances should be the shortest paths lengths, and the noise in the measurements should not be too large to avoid loss of details in the reconstruction.

Regarding future functionalities, GES currently only uses information on the latency of the network but adding bandwidth information could provide additional possibilities to differentiate between topologies producing similar latency matrices. Finally, the shortest path routing assumption may not hold for every type of network. Algorithmically, GES could handle other types of routing functions but at the cost of exponential complexity. This is due to having to perform the Gap function intersection check on all available paths between nodes. Handling this type of routing would require adaptation work to reduce this number of paths.

## Acknowledgments

We sincerely thank Lionel Eyraud-Dubois for his valuable help and constructive feedback throughout the preparation of this manuscript.
References

[1] T. Agarwal, A. Sharma, A. Laxmikant, and L.V. Kalé. 2006. Topology-aware task mapping for reducing communication contention on large parallel machines. In *Proceedings 20th IEEE International Parallel & Distributed Processing Symposium*. doi:10.1109/IPDPS.2006.1639379

[2] M. Soryani, M. Analoui, and G. Zarrinchian. 2013. Improving inter-node communications in multi-core clusters using a contention-free process mapping algorithm. *The Journal of Supercomputing* 66, 1 (2013), 488–513. doi:10.1007/s11227-013-0918-7

[3] F. Broquedis, J. Clet-Ortega, S. Moreaud, N. Furmento, B. Goglin, G. Mercier, S. Thibault, and R. Namyst. 2010. hwloc: A Generic Framework for Managing Hardware Affinities in HPC Applications. In *2010 18th Euromicro Conference on Parallel, Distributed and Network-based Processing*. 180–186. doi:10.1109/PDP.2010.67

[4] B. Goglin, J. Hursey, and J.M. Squyres. 2014. Netloc: Towards a Comprehensive View of the HPC System Topology. In *2014 43rd International Conference on Parallel Processing Workshops*. 216–225. doi:10.1109/ICPPW.2014.38

[5] S. Saini, R. Ciotti, B.T.N. Gunney, T.E. Spelce, A. Koniges, D. Dossa, P. Adamidis, R. Rabenseifner, S.R. Tiyyagura, and M. Mueller. 2008. Performance evaluation of supercomputers using HPCC and IMB Benchmarks. *J. Comput. System Sci.* 74, 6 (2008), 965–982. doi:10.1016/j.jcs.2007.07.002 Performance Analysis and Evaluation of Parallel, Cluster, and Grid Computing Systems.

[6] T. Hoefler, T. Mehlan, A. Lumsdaine, and W. Rehm. 2007. Netgauge: A Network Performance Measurement Framework. In *High Performance Computing and Communications*, R. Perrott, B.M. Chapman, J. Subhlok, R.F. de Mello, and L.T. Yang (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 659–671. doi:10.1007/978-3-540-75444-2_62

[7] A. Salnikov, D. Andreev, and R. Lebedev. 2011. The Analysis of Cluster Interconnect with the Network_Tests2 Toolkit. In *Recent Advances in the Message Passing Interface*, Y. Cotronis, A. Danalis, D.S. Nikolopoulos, and J. Dongarra (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 160–169. doi:10.1007/978-3-642-24449-0_19

[8] A. Legrand, P. Mazoit, and M. Quinson. 2006. *An Application-Level Network Mapper*. Research Report RR-5792. INRIA. https://inria.hal.science/inria-00071214

[9] L. Bobelin and T. Muntean. 2008. Algorithms for Network Topology Discovery using End-to-End Measurements. In *2008 International Symposium on Parallel and Distributed Computing*. 267–274. doi:10.1109/ISPDC.2008.56

[10] R. Black, A. Donnelly, and C. Fournet. 2004. Ethernet topology discovery without network assistance. In *Proceedings of the 12th IEEE International Conference on Network Protocols*, 2004. ICNP 2004. 328–339. doi:10.1109/ICNP.2004.1348122

[11] H. Subramoni, J. Vienne, and D.K. Panda. 2013. A Scalable InfiniBand Network Topology-Aware Performance Analysis Tool for MPI. In *Euro-Par 2012: Parallel Processing Workshops*, I. Caragiannis, M. Alexander, R.M. Badia, M. Cannataro, A. Costan, M. Danelutto, F. Desprez, B. Krammer, J. Sahuquillo, S.L. Scott, and J. Weidendorfer (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 439–450. doi:10.1007/978-3-642-36949-0_49

[12] N. Dandapanthula, H. Subramoni, J. Vienne, K. Kandalla, S. Sur, D.K. Panda, and R. Brightwell. 2012. INAM - A Scalable InfiniBand Network Analysis and Monitoring Tool. In *Euro-Par 2011: Parallel Processing Workshops*, M. Alexander, P. D'Ambra, A. Belloum, G. Bosilca, M. Cannataro, M. Danelutto, B. Di Martino, M. Gerndt, E. Jeannot, R. Namyst, J. Roman, S.L. Scott, J.L. Traff, G. Vallée, and

J. Weidendorfer (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 166–177. doi:10.1007/978-3-642-29740-3_20

[13] H. Subramoni, S. Potluri, K. Kandalla, B. Barth, J. Vienne, J. Keasler, K. Tomko, K. Schulz, A. Moody, and D.K. Panda. 2012. Design of a scalable InfiniBand topology service to enable network-topology-aware placement of processes. In *SC '12: Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis*. doi:10.1109/SC.2012.47

[14] K. Kandalla, H. Subramoni, A. Vishnu, and D.K. Panda. 2010. Designing topology-aware collective communication algorithms for large scale InfiniBand clusters: Case studies with Scatter and Gather. In *2010 IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum (IPDPSW)*. doi:10.1109/IPDPSW.2010.5470853

[15] M.J. Rashti, J. Green, P. Balaji, A. Afsahi, and W. Gropp. 2011. Multi-core and Network Aware MPI Topology Functions. In *Recent Advances in the Message Passing Interface*, Y. Cotronis, A. Danalis, D.S. Nikolopoulos, and J. Dongarra (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 50–60. doi:10.1007/978-3-642-24449-0_8

[16] J. Lawrence and X. Yuan. 2008. An MPI tool for automatically discovering the switch level topologies of Ethernet clusters. In *2008 IEEE International Symposium on Parallel and Distributed Processing*. doi:10.1109/IPDPS.2008.4536545

[17] I. Althöfer, G. Das, D. Dobkin, D. Joseph, and J. Soares. 1993. On sparse spanners of weighted graphs. *Discrete & Computational Geometry* 9, 1 (Dec. 1993), 81–100. doi:10.1007/BF02189308

[18] H. Le and S. Solomon. 2020. Light Euclidean Spanners with Steiner Points. In *28th Annual European Symposium on Algorithms (ESA 2020) (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 173)*, Fabrizio Grandoni, Grzegorz Herman, and Peter Sanders (Eds.). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 671–672. doi:10.4230/LIPIcs.ESA.2020.67

[19] S. Bhore and C.D. Tóth. 2022. Euclidean Steiner Spanners: Light and Sparse. *SIAM Journal on Discrete Mathematics* 36, 3 (2022), 2411–2444. doi:10.1137/22M1502707

[20] H. Le and S. Solomon. 2025. Truly Optimal Euclidean Spanners. *SIAM J. Comput.* 54, 4 (2025), FOCS19–135–FOCS19–199. doi:10.1137/20M1317906

[21] S. Kisfaludi-Bak and G. van Wordragen. 2025. *Near-Optimal Dynamic Steiner Spanners for Constant-Curvature Spaces*. arXiv:2509.01443 [cs.CG] doi:10.48550/arXiv.2509.01443

[22] S. Kisfaludi-Bak and G. van Wordragen. 2025. A quadtree, a Steiner spanner, and approximate nearest neighbours in hyperbolic space. *Journal of Computational Geometry* 2 (Jul. 2025), 145–174. doi:10.20382/JOCG.V16I2A5

[23] J. Ellson, E. Gansner, L. Koutsofios, S.C. North, and G. Woodhull. 2002. Graphviz–Open Source Graph Drawing Tools. In *Graph Drawing*, P. Mutzel, M. Jünger, and S. Leipert (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 483–484. doi:10.1007/3-540-45848-4_57

[24] E. Gabriel, G.E. Fagg, G. Bosilca, T. Angskun, J.J. Dongarra, J.M. Squyres, V. Sahay, P. Kambadur, B. Barrett, A. Lumsdaine, R.H. Castain, D.J. Daniel, R.L. Graham, and T.S. Woodall. 2004. Open MPI: Goals, Concept, and Design of a Next Generation MPI Implementation. In *Recent Advances in Parallel Virtual Machine and Message Passing Interface*, D. Kranzlmüller, P. Kacsuk, and J. Dongarra (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 97–104. doi:10.1007/978-3-540-30218-6_19

[25] M. Pérache, H. Jourdren, and R. Namyst. 2008. MPC: A Unified Parallel Runtime for Clusters of NUMA Machines. In *Proceedings of the 14th International Euro-Par Conference on Parallel Processing* (Las Palmas de Gran Canaria, Spain) (*Euro-Par '08*). Springer-Verlag, Berlin, Heidelberg, 78–88. doi:10.1007/978-3-540-85451-7_9