{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,22]],"date-time":"2026-01-22T09:17:50Z","timestamp":1769073470811,"version":"3.49.0"},"reference-count":19,"publisher":"Wiley","issue":"1","license":[{"start":{"date-parts":[[2021,4,12]],"date-time":"2021-04-12T00:00:00Z","timestamp":1618185600000},"content-version":"vor","delay-in-days":101,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["19K11887"],"award-info":[{"award-number":["19K11887"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["onlinelibrary.wiley.com"],"crossmark-restriction":true},"short-container-title":["Wireless Communications and Mobile Computing"],"published-print":{"date-parts":[[2021,1]]},"abstract":"<jats:p>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\u2010performance 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\u2010dimensional <jats:italic>k<\/jats:italic>\u2010ary torus topology and compare it with established results, both theoretically and experimentally. (This paper is a revised version of Antoine Bossard (2020)).<\/jats:p>","DOI":"10.1155\/2021\/5598173","type":"journal-article","created":{"date-parts":[[2021,4,13]],"date-time":"2021-04-13T00:05:27Z","timestamp":1618272327000},"update-policy":"https:\/\/doi.org\/10.1002\/crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["On Solving the Decycling Problem in a Torus Network"],"prefix":"10.1155","volume":"2021","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9381-9346","authenticated-orcid":false,"given":"Antoine","family":"Bossard","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2021,4,12]]},"reference":[{"key":"e_1_2_9_1_2","unstructured":"TOP500 TOP500 list - November 2020 June 2020 February 2021 https:\/\/www.top500.org\/lists\/top500\/list\/2020\/11\/."},{"key":"e_1_2_9_2_2","doi-asserted-by":"crossref","unstructured":"AjimaY. KawashimaT. OkamotoT. ShidaN. HiraiK. ShimizuT. HiramotoS. IkedaY. YoshikawaT. UchidaK. andInoueT. The Tofu interconnect D Proceedings of the IEEE International Conference on Cluster Computing September 2018 Belfast United Kingdom 646\u2013654.","DOI":"10.1109\/CLUSTER.2018.00090"},{"key":"e_1_2_9_3_2","doi-asserted-by":"crossref","unstructured":"AlversonR. RowethD. andKaplanL. The Gemini system interconnect Proceedings of the 18th IEEE Symposium on High Performance Interconnects August 2010 Mountain View CA USA 83\u201387.","DOI":"10.1109\/HOTI.2010.23"},{"key":"e_1_2_9_4_2","doi-asserted-by":"crossref","unstructured":"AjimaY. InoueT. HiramotoS. UnoS. SumimotoS. MiuraK. ShidaN. KawashimaT. OkamotoT. MoriyamaO. IkedaY. TabataT. YoshikawaT. SekiK. andShimizuT. Tofu interconnect 2: system-on-chip integration of high-performance interconnect Proceedings of the 29th International Supercomputing Conference June 2014 Leipzig Germany 498\u2013507.","DOI":"10.1007\/978-3-319-07518-1_35"},{"key":"e_1_2_9_5_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-3023-4_4"},{"key":"e_1_2_9_6_2","doi-asserted-by":"crossref","unstructured":"KarpR. M. Reducibility among combinatorial problems Proceedings of the Symposium on Complexity of Computer Computations March 1972 Yorktown Heights NY USA 85\u2013103.","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"e_1_2_9_7_2","doi-asserted-by":"crossref","unstructured":"FominF. V. GaspersS. andPyatkinA. V. Finding a minimum feedback vertex set in time O(1.7548n) 4169 Proceedings of the International Workshop on Parameterized and Exact Computation September 2006 Zurich Switzerland 184\u2013191.","DOI":"10.1007\/11847250_17"},{"key":"e_1_2_9_8_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0252-9602(17)30520-9"},{"key":"e_1_2_9_9_2","doi-asserted-by":"publisher","DOI":"10.1007\/s002360050088"},{"key":"e_1_2_9_10_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(94)00133-2"},{"key":"e_1_2_9_11_2","doi-asserted-by":"publisher","DOI":"10.1142\/S0219265913500060"},{"key":"e_1_2_9_12_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11227-014-1152-7"},{"key":"e_1_2_9_13_2","article-title":"Decycling cubes and grids","volume":"59","author":"Bau S.","year":"2001","journal-title":"Utilitas Mathematica"},{"key":"e_1_2_9_14_2","first-page":"285","article-title":"The decycling number of graphs","volume":"25","author":"Bau S.","year":"2002","journal-title":"The Australasian Journal of Combinatorics"},{"key":"e_1_2_9_15_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00373-003-0529-9"},{"key":"e_1_2_9_16_2","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0118(199705)25:1<59::AID-JGT4>3.0.CO;2-H"},{"key":"e_1_2_9_17_2","doi-asserted-by":"crossref","unstructured":"BossardA. On the decycling problem in a torus 1362 Proceedings of the 11th International Symposium on Parallel Architectures Algorithms and Programming (PAAP) December 2020 Shenzhen China 12\u201321.","DOI":"10.1007\/978-981-16-0010-4_2"},{"key":"e_1_2_9_18_2","doi-asserted-by":"publisher","DOI":"10.1137\/S089548010444016X"},{"key":"e_1_2_9_19_2","unstructured":"BossardA.andKanekoK. Approximating optimal decycling sets in HHC and HCN for small dimensions Proceedings of the 30th International Conference on Computers and Their Applications (CATA) March 2015 Honolulu HI USA 145\u2013150."}],"container-title":["Wireless Communications and Mobile Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/downloads.hindawi.com\/journals\/wcmc\/2021\/5598173.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/downloads.hindawi.com\/journals\/wcmc\/2021\/5598173.xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1155\/2021\/5598173","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,7]],"date-time":"2024-08-07T14:04:11Z","timestamp":1723039451000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1155\/2021\/5598173"}},"subtitle":[],"editor":[{"given":"Yong","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]}],"short-title":[],"issued":{"date-parts":[[2021,1]]},"references-count":19,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["10.1155\/2021\/5598173"],"URL":"https:\/\/doi.org\/10.1155\/2021\/5598173","archive":["Portico"],"relation":{},"ISSN":["1530-8669","1530-8677"],"issn-type":[{"value":"1530-8669","type":"print"},{"value":"1530-8677","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1]]},"assertion":[{"value":"2021-02-26","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-03-30","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-04-12","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"5598173"}}