Graph optimization algorithm for low-latency interconnection networks

• Published in: Parallel computing 2021-09, Vol.106, p.102805, Article 102805
• Main Authors: Nakao, Masahiro, Sakai, Maaki, Hanada, Yoshiko, Murai, Hitoshi, Sato, Mitsuhisa
• Format: Article
• Language: English
• Subjects: Graph theory; High-performance computing; Interconnection network; Network topology; Optimization
• ISSN: 0167-8191; 1872-7336
• DOI: 10.1016/j.parco.2021.102805

In various industrial products including parallel computing systems, it is expected that the performance of the whole system will be improved by applying a network topology with smaller diameter and average shortest path length (ASPL). Such network topologies can be defined as the order/degree problem in graph theory by modeling a network topology as an undirected graph. Although previous research indicates that the random graph has both small diameter and ASPL due to the small-world effect, there is still room for improvement. In this paper, we propose an algorithm for the order/degree problem that optimizes random graphs. The feature of the proposed algorithm is that by giving symmetry to the graph, the solution search performance is improved and the calculation time for obtaining the diameter and APSL is greatly reduced. The proposed algorithm is evaluated using various graphs, including a huge graph with one million vertices presented by Graph Golf, an international competition for the order/degree problem. The results show that the proposed algorithm can generate a network topology with sufficiently small diameter and APSL. In addition, we also simulate the latency, performance of the parallel benchmarks, and bisection on the generated network topologies. The results show that the generated network topology performs better than the random topology and a conventional k-ary n-cube topology.