On November 2019, 11, the National Institute of Informatics held an award ceremony for the competition "Graph Golf 26" to discover the network configuration of future supercomputers at the international symposium "CANDAR 2019".The award was
Team RK by Masahiro Nakao of RIKEN, Masaaki Sakai and Yoshiko Hanada of Kansai University, and So Terao of the University of Electro-Communications.
This competition represents a complicated network configuration used for supercomputers, etc. with a simple graph, and competes for the discovery of a graph with a simple configuration that leads to efficient design of networks within and between CPU chips.
Modern supercomputers have up to 1 million or more interconnected processor cores.The design of an efficient network configuration (network topology) has a great influence on its processing capacity.In this competition, the core is regarded as the "vertex" and the wiring connecting the cores is regarded as the "edge", and a graph that achieves the network topology is constructed.The number of hops (number of sides passed) from one vertex to the farthest vertex is called "diameter", and the average value of the number of hops between each vertex is called "average path length". Set the problem of finding the smallest graph.
The fifth competition was held from April to October, and there were many applications (5) from Japan and overseas.As a result, a graph with the smallest diameter in theory was found in 4 questions for general graphs including a huge graph with 10 million vertices for which it is difficult to calculate the average path length, and 1,382 questions for all grid graphs.Mr. Nakao's team found 100 questions on the grid graph, and Mr. Terao found 5 questions on the general graph, each with a total of 11 patterns with the smallest average path length.
These graphs are expected to be applied to practical use, such as minimizing the communication time of massively parallel computing of next-generation supercomputers.
