Discovery of the indirect network with the smallest theoretical diameter in the Graph Golf, a competition to find graphs leading to the efficient design of supercomputers.
-- Effective also in configurations where network switches are used for indirect connections between CPUs --
National Institute of Informatics (NII; Director General: Dr. KITSUREGAWA Masaru; Tokyo, Japan) held an award ceremony today, on November 24 for Graph Golf 2021（*1）, a competition for finding network configurations for future supercomputers, at CANDAR2021（*2）, an international symposium held online. The Graph Golf 2021 is a competition to find graphs by which the connections between CPUs that correspond to the network configurations used in supercomputers were shown, leading to the efficient design of networks between CPUs. This year's award winners include the team of NAKAO Masahiro (RIKEN Center for Computational Science), TSUKAMOTO Masao (Kansai University), HANADA Yoshiko (Kansai University) and others who discovered outstanding graphs. These graphs are expected to find practical applications, such as minimizing the communication time for massively parallel computations in next-generation supercomputers.
Recently, computers are becoming larger and more complicated, and supercomputers consist of 10 million or more interconnected processor cores. Network topology design determines how to interconnect vast numbers of cores efficiently, and it has a large impact on the processing power of supercomputers. In this competition, a graph achieving network topology consists of CPUs that are called vertices and wires connecting CPUs that are called edges. The number of hops (total number of edges) from one vertex to the most remote vertex is known as the diameter, and the average number of hops between each pair of vertices is known as the average shortest path length (ASPL). The challenge in Graph Golf was to find the graph with the smallest possible diameter and the smallest possible ASPL under the specified conditions.
This year, for the sixth competition, a Host-Switch Graph Category, where host (CPU) vertices and network switch vertices are distinguished from each other as different types of graph vertices, was introduced. A host-switch graph shows network configurations for supercomputers where network switches, such as InfiniBand, are used for indirect connections between CPUs. Entries were accepted from April to October（*3）, and 91 valid entries were received (a total of 2,396 entries（*4） for all past six competitions). As a result, we were able to find graphs with the smallest theoretical diameter in 4 out of 8 questions in the general graph category and 6 out of 13 questions in the host-switch graph category. In the host-switch graph category, Nakao's team and others have found a case where it is important to make the number of host vertices connected to switch vertices non-uniform (Figure 1). This result is an evidence in which the characteristics of the indirect network（*5） are clearly visible.
Figure 1: Host-switch graph found by Nakao's team, an award winner. Host vertices and their links are shown in red, and links between switch vertices are shown in blue.
With the full cooperation of the award winners of the past five competitions, presentation materials from international conferences and other events related to the Graph Golf are made available on the Graph Golf website (http://research.nii.ac.jp/graphgolf/2021/candar21/) to provide easy-to-understand explanations of how to configure a variety of excellent graphs. In addition, a list of a total of 26 academic papers and technical reports related to the Graph Golf is presented on the above website for future reference in graph discovery.
From a practical point of view, a reduction in the diameter of the graph directly leads to a reduction in the longest communication delay of supercomputers, while a reduction in the average path length of the graph directly leads to a reduction in the average communication delay of supercomputers. The exponential increases in supercomputer performance require the corresponding suitable network configurations every year. Of the top 500 supercomputers（*6）, about 80% use InfiniBand or Ethernet, which can implement any network configuration, and it is technically possible to adopt superior graphs as network configurations. This competition will contribute to academic and industry research by making the submitted graphs public.
（*1）Graph Golf: It was named after golf by comparing the flow of a signal passing through each core to the sport where players accumulate strokes one by one and compete to get the lowest score. This is intended to make people who are not experts feel familiar with the competition, and so encourage more people to participate. The results of the competition can be found at http://research.nii.ac.jp/graphgolf/ranking.html.