# On Solving the Decycling Problem in a Torus Network

Authors: Antoine Bossard
Journal: Wireless Communications and Mobile Computing
 (2021)

---

## Abstract

Modern supercomputers are massively parallel systems: they embody thousands of computing nodes and sometimes several millions. The torus topology has proven very popular for the interconnect of these high-performance systems. Notably, this network topology is employed by the supercomputer ranked number one in the world as of November 2020, the supercomputer Fugaku. Given the high number of compute nodes in such systems, efficient parallel processing is critical to maximise the computing performance. It is well known that cycles harm the parallel processing capacity of systems: for instance, deadlocks and starvations are two notorious issues of parallel computing that are directly linked to the presence of cycles. Hence, network decycling is an important issue, and it has been extensively discussed in the literature. We describe in this paper a decycling algorithm for the 3-dimensionalk-ary torus topology and compare it with established results, both theoretically and experimentally. (This paper is a revised version of Antoine Bossard (2020)).


---

## Body

## 1. Introduction

The supercomputers of the 21st century are massively parallel systems: they embody thousands of compute nodes. Some recent devices even include several millions of nodes (e.g., 10,649,600 nodes for the Sunway TaihuLight as of November 2020’s TOP500 list [1]). The interconnection of these compute nodes is thus a critical issue so as to maximise the parallel processing performance and thus the machine performance overall. Thanks to its advantageous topological properties, such as regularity, the torus network topology has proven very popular for the interconnect of modern supercomputers. For example, the supercomputer ranked number one in the world in the November 2020 TOP500 ranking, the supercomputer Fugaku built by Fujitsu and RIKEN, employs the torus topology to connect its nodes (Tofu interconnect D [2]). The IBM Blue Gene/L and Blue Gene/P, Cray Titan (Gemini interconnect [3]), and Fujitsu SORA-MA (Tofu interconnect 2 [4]) are other examples of supercomputers based on the torus topology.It is well known that parallel processing is harmed by the presence of cycles: they are at the source of the deadlock, livelock, and starvation notorious resource allocation issues [5]. Notably, because it has important implications for parallel processing, the decycling problem, also known as the minimum feedback vertex set problem, has been extensively addressed in the literature. Karp has shown that finding a decycling set of minimum size (i.e., an optimal decycling set) in any graph is NP-complete [6]. For instance, Fomin et al. have described an algorithm that solves this problem in any graph in O1.7548n time [7]. Furthermore, polynomial solutions have been described for several particular classes of graphs such as 3-regular graphs [8], convex bipartite graphs [9], permutation graphs [10], and hypercube-based networks [11, 12]. Among others, the size of an optimal decycling set (i.e., the decycling number) in the case of cubes and grids has been discussed in [13, 14] and for hypercubes in [15]. We describe in this paper a polynomial time decycling algorithm for a 3-dimensional k-ary torus network. One should note that while the case of a grid as mentioned above seems close, or at least related, to the case of the torus which we investigate hereinafter, the wrap-around edges of the torus invalidate the grid decycling approach (refer to the next section for additional details).The rest of this paper is organised as follows. Notations, definitions, and previous results are recalled in Section2. The decycling algorithm is presented in Section 3, including the proof of its correctness and complexity analysis. Theoretical and empirical evaluations are conducted in Section 4. Finally, concluding remarks are given in Section 5.


## 2. Preliminaries

We recall in this section several notations, definitions, and previously established results. The set of the vertices of a graphG is denoted by VG, and the set of its edges by EG. A path in a graph G is a subgraph of G that is an alternating sequence of distinct vertices and edges. Such a vertex–edge sequence but whose two terminal vertices are the same vertex is called a cycle. The length of a path or cycle is its number of edges. A graph that contains no cycle is said to be acyclic and is isomorphic to a tree.Definition 1.
Ann-dimensional k-ary torus, denoted by Tn,k, with n≥1 and k≥1, consists in the kn vertices induced by the set 0,1,⋯,k−1n. Two vertices u=u0,u1,⋯,un−1 and v=v0,v1,⋯,vn−1 of a Tn,k are adjacent if and only if there exists j (0≤j<n) such that ∀i (0≤i<n, i≠j) ui=vi and uj=vj±1modk.A torusTn,k is thus a regular graph of degree 2n, of diameter nk/2 and has nkn edges. An essential torus property is next recalled.Property 2.
For a dimensionδ (0≤δ<n), a Tn,k consists in k subtori Ti,δn−1,k (0≤i<k). Each subtorus Ti,δn−1,k is induced by the kn−1 vertices u0,u1,⋯,uδ−1,i,uδ+1,⋯,un−1 of Tn,k with uj0≤j<n,j≠δ the vertex coordinate for the dimension j and i the vertex coordinate for the dimension δ.A torusT2,3 is shown in Figure 1(a) and its recursive structure is illustrated in Figure 1(b).Figure 1
(a) A torusT2,3. (b) A torus has a recursive structure: a T2,3 consists in three subtori T1,3.
(a)(b)Next, previously established results are recalled.Beineke and Vandell have established a lower bound on the size of a decycling set for any graph [16]. This result is recalled in Theorem 3 below.Theorem 3 (see [16]).
Given a graphG=V,E of maximum degree Δ, any decycling set S of G satisfies the following relation:(1)S≥E−V+1Δ−1.We were unaware until very recently (after the publication of [17]) that Pike and Zou have shown how to calculate a decycling set of minimum size for a 2-dimensional torus in [18]. The corresponding result is recalled in Theorem 4 below.Theorem 4 (see [18]).
In aT2,k with k≥3, a decycling set Sk of minimum size with(2)Sk=3k2=6,k=4,k2+23,otherwise,can be found in Ok2 time.


## 3. The Case of aT3,k

We describe in this section the details of our approach to decycle a 3-dimensionalk-ary torus T3,k.


### 3.1. Algorithm Description

We give below a constructive proof in the form of a decycling algorithm whose input is an arityk (k≥1) and which outputs a decycling set Sk.The main idea is to consider one dimensionδ to reduce T3,k into k 2-dimensional subtori as per Property 2 and to alternate for each such subtorus the optimal decycling of a T2,k (i.e., Theorem 4) and two other decycling methods of a T2,k which induce a graph with no edge.The casek=1 is trivial: T3,1 consists of one unique vertex and is thus acyclic; S1=∅ is thus a decycling set for this trivial graph. A T3,2 is isomorphic to a 3-dimensional hypercube; S2=0,0,0,1,1,0,1,1,1 is thus an optimal decycling set by Theorem 3. Hence, we can now assume that k≥3.Step 1.
We distinguish the two casesk even and k odd.
Casek even:
Define two decycling setsS1k, S2k in a two-dimensional k-ary torus T2,k as follows:(3)S1k=i,j∈VT2,k0≤i,j≤k−1,i+j≡1mod2,S2k=i,j∈VT2,k0≤i,j≤k−1,i+j≡0mod2.
In other words, the setS1k is induced by the vertices of T2,k that are taken in one particular “quincunx” manner, and the set S2k by the vertices of T2,k that are taken in the other “quincunx” manner. Precisely, we have S2k=VT2,k\S1k and S1k=VT2,k\S2k.
The setsS1k and S2k when k=4 are illustrated in Figures 2(a) and 2(b), respectively; they consist in the red vertices.
Casek odd:
Define two decycling setsS1k, S2k in a two-dimensional k-ary torus T2,k as follows:(4)S1k=i,j∈VT2,k0≤i,j≤k−1,i+j≡1mod2∪i,k−10≤i≤k−1∪k−1,i0≤i≤k−1,S2k=i,j∈VT2,k0≤i,j≤k−1,i+j≡0mod2∪i,k−10≤i≤k−1∪k−1,i0≤i≤k−1.Figure 2
The setsS1k (a) and S2k (b) as defined in a T2,k when k=4; they consist in the red vertices.
(a)(b)In other words, the setS1k is induced by the vertices of T2,k that are taken in one particular “quincunx” manner and also includes the vertices of the top row and those of the right row. The sets S1k and S2k when k=5 are illustrated in Figures 3(a) and 3(b), respectively; they consist in the red vertices.Step 2.
Letδ=0 and consider the k subtori Ti,δ2,k (0≤i≤k−1) as per Property 2. Define S0k the optimal decycling set of T2,k as induced by Theorem 4. We distinguish the three cases that are induced by the value of kmod3.
Casek≡0mod3:
Decycle each subtorusTi,δ2,k0≤i≤k−1 with the vertex set Simod3k (see Figure 4). In this figure, where there can be edges on the third dimension between two subtori, sample edges are shown.
Casek≡1mod3:
Decycle each subtorusTi,δ2,k0≤i≤k−2 with the vertex set Simod3k and Tk−1,δ2,k with the vertex set S2k (see Figure 5). Again in this figure, where there can be edges on the third dimension between two subtori, sample edges are shown.
Casek≡2mod3:
Decycle each subtorusTi,δ2,k0≤i≤k−2 with the vertex set Simod3k and Tk−1,δ2,k with the vertex set VTk−1,δ2,k (see Figure 6). Again in this figure, where there can be edges on the third dimension between two subtori, sample edges are shown.Figure 3
The setsS1k (a) and S2k (b) as defined in a T2,k when k=5; they consist in the red vertices.
(a)(b)Figure 4
An illustration of the casek≡0mod3 with k=6. The selected decycling set for each of the Ti,δ2,k (0≤i≤k−1) subtori is given below it. Where there can be edges on the third dimension between two subtori, sample edges are shown.Figure 5
An illustration of the casek≡1mod3 with k=7. The selected decycling set for each of the Ti,δ2,k (0≤i≤k−1) subtori is given below it. Where there can be edges on the third dimension between two subtori, sample edges are shown.Figure 6
An illustration of the casek≡2mod3 with k=5. The selected decycling set for each of the Ti,δ2,k (0≤i≤k−1) subtori is given below it. Where there can be edges on the third dimension between two subtori, sample edges are shown.


### 3.2. Correctness and Complexities

In this section, we prove the correctness of the proposed algorithm and establish its complexities.Theorem 5.
In a 3-dimensionalk-ary torus T3,k (k≥1), a decycling set Sk of 0 vertex when k=1, 3 vertices when k=2, and in the other cases with(5)Sk=kk2+2/3+k23,k≡0mod3,30,k≡1mod3,k=4,k−1k2+2/3+k23+k22,k≡1mod3,k>4k+1k2+2/3+k23,k≡2mod3,when k is even, and with(6)Sk=kk2+2/3+k2+2k−13,k≡0mod3,k−1k2+2/3+k2+2k−13+k2−12+k,k≡1mod3,k−2k2+2/3+k2+2k−13+3k2−12+k,k≡2mod3,
whenk is odd can be found in optimal Ok3 time.Proof.
The cases induced byk≤2 are trivial; they have already been shown at the beginning of Section 3.1. So, we can assume k≥3.By definition, the subgraph ofT2,k induced by the vertices of the set VT2,k\S1k has no edge. And similarly, the subgraph of T2,k induced by the vertices of the set VT2,k\S2k has no edge either.Hence, by definition of the algorithm, each subtorusTi,δ2,k (0≤i≤k−1) is acyclic. Moreover, the only edges on the third dimension are at a vertex of a graph induced by a subtorus decycled with S0k. Consider two such graphs induced by a subtorus decycled with S0k, say the graphs that correspond to Ti,δ2,k and Tj,δ2,k where i<j and j−i minimal. In the case k≡0mod3, we have j−i=3 and the greatest such j is k−3. And since for every edge on the third dimension the vertex that is not in a graph induced by a subtorus decycled with S0k is inside a graph induced by a subtorus that has no edge, the resulting graph is acyclic. In the case k≡1mod3, we have j−i=3 and the greatest such j is k−4. So, again and for the same reason, the resulting graph is acyclic. In the case k≡2mod3, we have j−i=3 and the greatest such j is k−2, so there could be a path on the third dimension between a vertex of Tk−2,δ2,k (i.e., the rightmost graph induced by S0k) and of T0,δ2,k (which is also induced by S0k). However, all the vertices of Tk−1,δ2,k are removed, so there is no such path and the resulting graph is thus acyclic.The setS1k and the set S2k each have k2/2 vertices when k is even and k−12/2+2k−1=k2−1/2+k when k is odd. They can thus each be calculated in Ok2 time. By Theorem 4, the set S0k has 3k/2 vertices when k=4 and k2+2/3 vertices otherwise, and this set can be calculated in Ok2 time.Hence, in aT3,k, a decycling set Sk with Sk=kS0k+S1k+S2k/3 when k≡0mod3, Sk=k−1S0k+S1k+S2k/3+S2k when k≡1mod3, and Sk=k−2S0k+S1k+S2k/3+S0k+k2 when k≡2mod3 can be found in Ok3 time. By further distinguishing the two cases k even and k odd, we obtain the expected set sizes.From Theorem3, we have in a T3,k that S≥3k3−k3+1/5=2k3+1/5. Therefore, Ok3 is optimal time.


## 3.1. Algorithm Description

We give below a constructive proof in the form of a decycling algorithm whose input is an arityk (k≥1) and which outputs a decycling set Sk.The main idea is to consider one dimensionδ to reduce T3,k into k 2-dimensional subtori as per Property 2 and to alternate for each such subtorus the optimal decycling of a T2,k (i.e., Theorem 4) and two other decycling methods of a T2,k which induce a graph with no edge.The casek=1 is trivial: T3,1 consists of one unique vertex and is thus acyclic; S1=∅ is thus a decycling set for this trivial graph. A T3,2 is isomorphic to a 3-dimensional hypercube; S2=0,0,0,1,1,0,1,1,1 is thus an optimal decycling set by Theorem 3. Hence, we can now assume that k≥3.Step 1.
We distinguish the two casesk even and k odd.
Casek even:
Define two decycling setsS1k, S2k in a two-dimensional k-ary torus T2,k as follows:(3)S1k=i,j∈VT2,k0≤i,j≤k−1,i+j≡1mod2,S2k=i,j∈VT2,k0≤i,j≤k−1,i+j≡0mod2.
In other words, the setS1k is induced by the vertices of T2,k that are taken in one particular “quincunx” manner, and the set S2k by the vertices of T2,k that are taken in the other “quincunx” manner. Precisely, we have S2k=VT2,k\S1k and S1k=VT2,k\S2k.
The setsS1k and S2k when k=4 are illustrated in Figures 2(a) and 2(b), respectively; they consist in the red vertices.
Casek odd:
Define two decycling setsS1k, S2k in a two-dimensional k-ary torus T2,k as follows:(4)S1k=i,j∈VT2,k0≤i,j≤k−1,i+j≡1mod2∪i,k−10≤i≤k−1∪k−1,i0≤i≤k−1,S2k=i,j∈VT2,k0≤i,j≤k−1,i+j≡0mod2∪i,k−10≤i≤k−1∪k−1,i0≤i≤k−1.Figure 2
The setsS1k (a) and S2k (b) as defined in a T2,k when k=4; they consist in the red vertices.
(a)(b)In other words, the setS1k is induced by the vertices of T2,k that are taken in one particular “quincunx” manner and also includes the vertices of the top row and those of the right row. The sets S1k and S2k when k=5 are illustrated in Figures 3(a) and 3(b), respectively; they consist in the red vertices.Step 2.
Letδ=0 and consider the k subtori Ti,δ2,k (0≤i≤k−1) as per Property 2. Define S0k the optimal decycling set of T2,k as induced by Theorem 4. We distinguish the three cases that are induced by the value of kmod3.
Casek≡0mod3:
Decycle each subtorusTi,δ2,k0≤i≤k−1 with the vertex set Simod3k (see Figure 4). In this figure, where there can be edges on the third dimension between two subtori, sample edges are shown.
Casek≡1mod3:
Decycle each subtorusTi,δ2,k0≤i≤k−2 with the vertex set Simod3k and Tk−1,δ2,k with the vertex set S2k (see Figure 5). Again in this figure, where there can be edges on the third dimension between two subtori, sample edges are shown.
Casek≡2mod3:
Decycle each subtorusTi,δ2,k0≤i≤k−2 with the vertex set Simod3k and Tk−1,δ2,k with the vertex set VTk−1,δ2,k (see Figure 6). Again in this figure, where there can be edges on the third dimension between two subtori, sample edges are shown.Figure 3
The setsS1k (a) and S2k (b) as defined in a T2,k when k=5; they consist in the red vertices.
(a)(b)Figure 4
An illustration of the casek≡0mod3 with k=6. The selected decycling set for each of the Ti,δ2,k (0≤i≤k−1) subtori is given below it. Where there can be edges on the third dimension between two subtori, sample edges are shown.Figure 5
An illustration of the casek≡1mod3 with k=7. The selected decycling set for each of the Ti,δ2,k (0≤i≤k−1) subtori is given below it. Where there can be edges on the third dimension between two subtori, sample edges are shown.Figure 6
An illustration of the casek≡2mod3 with k=5. The selected decycling set for each of the Ti,δ2,k (0≤i≤k−1) subtori is given below it. Where there can be edges on the third dimension between two subtori, sample edges are shown.


## 3.2. Correctness and Complexities

In this section, we prove the correctness of the proposed algorithm and establish its complexities.Theorem 5.
In a 3-dimensionalk-ary torus T3,k (k≥1), a decycling set Sk of 0 vertex when k=1, 3 vertices when k=2, and in the other cases with(5)Sk=kk2+2/3+k23,k≡0mod3,30,k≡1mod3,k=4,k−1k2+2/3+k23+k22,k≡1mod3,k>4k+1k2+2/3+k23,k≡2mod3,when k is even, and with(6)Sk=kk2+2/3+k2+2k−13,k≡0mod3,k−1k2+2/3+k2+2k−13+k2−12+k,k≡1mod3,k−2k2+2/3+k2+2k−13+3k2−12+k,k≡2mod3,
whenk is odd can be found in optimal Ok3 time.Proof.
The cases induced byk≤2 are trivial; they have already been shown at the beginning of Section 3.1. So, we can assume k≥3.By definition, the subgraph ofT2,k induced by the vertices of the set VT2,k\S1k has no edge. And similarly, the subgraph of T2,k induced by the vertices of the set VT2,k\S2k has no edge either.Hence, by definition of the algorithm, each subtorusTi,δ2,k (0≤i≤k−1) is acyclic. Moreover, the only edges on the third dimension are at a vertex of a graph induced by a subtorus decycled with S0k. Consider two such graphs induced by a subtorus decycled with S0k, say the graphs that correspond to Ti,δ2,k and Tj,δ2,k where i<j and j−i minimal. In the case k≡0mod3, we have j−i=3 and the greatest such j is k−3. And since for every edge on the third dimension the vertex that is not in a graph induced by a subtorus decycled with S0k is inside a graph induced by a subtorus that has no edge, the resulting graph is acyclic. In the case k≡1mod3, we have j−i=3 and the greatest such j is k−4. So, again and for the same reason, the resulting graph is acyclic. In the case k≡2mod3, we have j−i=3 and the greatest such j is k−2, so there could be a path on the third dimension between a vertex of Tk−2,δ2,k (i.e., the rightmost graph induced by S0k) and of T0,δ2,k (which is also induced by S0k). However, all the vertices of Tk−1,δ2,k are removed, so there is no such path and the resulting graph is thus acyclic.The setS1k and the set S2k each have k2/2 vertices when k is even and k−12/2+2k−1=k2−1/2+k when k is odd. They can thus each be calculated in Ok2 time. By Theorem 4, the set S0k has 3k/2 vertices when k=4 and k2+2/3 vertices otherwise, and this set can be calculated in Ok2 time.Hence, in aT3,k, a decycling set Sk with Sk=kS0k+S1k+S2k/3 when k≡0mod3, Sk=k−1S0k+S1k+S2k/3+S2k when k≡1mod3, and Sk=k−2S0k+S1k+S2k/3+S0k+k2 when k≡2mod3 can be found in Ok3 time. By further distinguishing the two cases k even and k odd, we obtain the expected set sizes.From Theorem3, we have in a T3,k that S≥3k3−k3+1/5=2k3+1/5. Therefore, Ok3 is optimal time.


## 4. Discussion

In this section, we discuss the obtained theoretical results and compare them with experimental data.


### 4.1. Comparison with the Lower Bound

We investigate in this section how close the size of the generated decycling set is to the lower bound given by Theorem3. Figure 7 shows the values obtained from Theorem 3 and Theorem 5. Let us recall that the result of Theorem 3 is a lower bound on the size of a decycling set, and not necessarily the size of an optimal decycling set. So, the difference plotted in Figure 7 is given for reference, and it shows that the size of the obtained decycling set is promising, possibly optimal in some cases, given that it is rather close, and sometimes equal, to the lower bound of Theorem 3.Figure 7
Investigating how close the size of the decycling set generated is to the lower bound of Theorem3.One can also notice that the size of the decycling set generated by the proposed algorithm is never smaller than the lower bound of Theorem3. If that were the case, this would indicate a hole in the proposed algorithm.


### 4.2. Comparison with the Results of a Computer Experiment

We have implemented a stochastic decycling algorithm in order to compare the obtained theoretical results with those obtained experimentally. As recalled in introduction, this is an NP-complete problem; hence, the graph decycling implementation we use only approximates the size of an optimal decycling set. This implementation follows the method described in [19]. The stochastic implementation was run 1,000 times.The values obtained from Theorem5 and the computer experiment are shown in Table 1. The minimum size and the average size of the decycling set generated by the stochastic implementation are given. The values from Theorem 3—a lower bound on the size of a decycling set, and not necessarily the size of an optimal decycling set—are also given for reference.Table 1
Comparison of the size of the decycling set obtained with the proposed method in aT3,k with that of the experimentally generated decycling sets. The theoretical lower bound is also given for reference.
AritykProposal (Theorem5)Experiment (minimum size)Experiment(average size)Lower bound (Theorem3)3181414.71114303033.85265856065.8651698106113.85877189171180.461388258257269.152059378371383.2129210452505526.01401From these results, it can be noticed that the proposed algorithm beats the stochastic implementation on each of all its 1,000 runs atk≡2mod4 and is equal or very nearly equal to it at k≡0mod4. In other words, when k is even, our proposal induces a smaller or nearly equal decycling set than the best decycling set found after 1,000 runs. And when k is odd, as k increases, the size difference between our proposal and the stochastic implementation continuously decreases, and at k=9, our proposal beats the stochastic implementation when considering the average value of its 1,000 runs.And, of course, the complexity of the stochastic implementation is always prohibitive [19], especially compared to the worst-case time complexity of the proposal (Ok3, see Theorem 5). These are very positive results which quantitatively show the significance of the proposal. For reference, in the case k=10, the stochastic implementation took more than 2.5 hours to complete the 1,000 runs on a midrange computer (Intel Core i5-1035G7 CPU, 8 GB RAM).Finally, it can also be noticed that the size of the decycling set generated by the proposed algorithm in aT3,k is Okn. Besides, by Theorem 4, the size of an optimal decycling set in a T2,k is also Okn. This is yet another positive indicator of the performance of our proposal.


## 4.1. Comparison with the Lower Bound

We investigate in this section how close the size of the generated decycling set is to the lower bound given by Theorem3. Figure 7 shows the values obtained from Theorem 3 and Theorem 5. Let us recall that the result of Theorem 3 is a lower bound on the size of a decycling set, and not necessarily the size of an optimal decycling set. So, the difference plotted in Figure 7 is given for reference, and it shows that the size of the obtained decycling set is promising, possibly optimal in some cases, given that it is rather close, and sometimes equal, to the lower bound of Theorem 3.Figure 7
Investigating how close the size of the decycling set generated is to the lower bound of Theorem3.One can also notice that the size of the decycling set generated by the proposed algorithm is never smaller than the lower bound of Theorem3. If that were the case, this would indicate a hole in the proposed algorithm.


## 4.2. Comparison with the Results of a Computer Experiment

We have implemented a stochastic decycling algorithm in order to compare the obtained theoretical results with those obtained experimentally. As recalled in introduction, this is an NP-complete problem; hence, the graph decycling implementation we use only approximates the size of an optimal decycling set. This implementation follows the method described in [19]. The stochastic implementation was run 1,000 times.The values obtained from Theorem5 and the computer experiment are shown in Table 1. The minimum size and the average size of the decycling set generated by the stochastic implementation are given. The values from Theorem 3—a lower bound on the size of a decycling set, and not necessarily the size of an optimal decycling set—are also given for reference.Table 1
Comparison of the size of the decycling set obtained with the proposed method in aT3,k with that of the experimentally generated decycling sets. The theoretical lower bound is also given for reference.
AritykProposal (Theorem5)Experiment (minimum size)Experiment(average size)Lower bound (Theorem3)3181414.71114303033.85265856065.8651698106113.85877189171180.461388258257269.152059378371383.2129210452505526.01401From these results, it can be noticed that the proposed algorithm beats the stochastic implementation on each of all its 1,000 runs atk≡2mod4 and is equal or very nearly equal to it at k≡0mod4. In other words, when k is even, our proposal induces a smaller or nearly equal decycling set than the best decycling set found after 1,000 runs. And when k is odd, as k increases, the size difference between our proposal and the stochastic implementation continuously decreases, and at k=9, our proposal beats the stochastic implementation when considering the average value of its 1,000 runs.And, of course, the complexity of the stochastic implementation is always prohibitive [19], especially compared to the worst-case time complexity of the proposal (Ok3, see Theorem 5). These are very positive results which quantitatively show the significance of the proposal. For reference, in the case k=10, the stochastic implementation took more than 2.5 hours to complete the 1,000 runs on a midrange computer (Intel Core i5-1035G7 CPU, 8 GB RAM).Finally, it can also be noticed that the size of the decycling set generated by the proposed algorithm in aT3,k is Okn. Besides, by Theorem 4, the size of an optimal decycling set in a T2,k is also Okn. This is yet another positive indicator of the performance of our proposal.


## 5. Concluding Remarks

The torus topology is nowadays ubiquitous in supercomputing. It is the network topology of choice for the interconnect of massively parallel systems: it is for instance employed by the supercomputer ranked number one in the world as of November 2020, the supercomputer Fugaku. Besides, it is common knowledge that cycles in the network of compute nodes harm parallel processing, and this is one reason why the decycling problem—NP-complete—has been extensively addressed in the literature. We have described in this paper a decycling algorithm for a torusT3,k. Thanks to the recursive property of the torus topology, this proposal can be used to decycle parts (i.e., subtori) of a torus of higher dimension, which as explained will consequently facilitate parallel processing. Precisely, we have given a constructive proof of a decycling set Sk for a torus T3,k where Sk has kS0k+2S1k/3 vertices when k≡0mod3, k−1S0k+2S1k/3+S1k vertices when k≡1mod3, k−2S0k+2S1k/3+S0k+k2 vertices when k≡2mod3 with S0k an optimal decycling set in T2,k, S1k=k2/2 when k even, and S1k=k2−1/2+k when k odd and can be obtained in Ok3 optimal time. We have formally evaluated the proposed algorithm and conducted evaluation experiments to compare it to conventional approaches. The obtained results have quantitatively shown the significance of the proposal.Regarding future works, refining the proposed decycling algorithm so that the generated decycling set includes a smaller number of vertices is a first meaningful objective. Then, it will be very interesting to investigate, for instance, as explained above by using the recursive property of the torus topology, how to rely on the obtained results to produce nontrivial decycling sets for tori of higher dimensions.



---

*Source: 5598173-2021-04-12.xml*