News

News Release

A Host-Switch Graph Category with more specific conditions newly created!
Graph Golf Competition for Finding Network Configurations for Supercomputers

 National Institute of Informatics (NII; Director General: Dr. KITSUREGAWA Masaru; Tokyo, Japan) will hold the Graph Golf Competition 2021(*1). In this competition, entrants compete to find graphs with simple structures that correspond to given complex network configurations used in supercomputers, and lead to efficient design of networks inside and between central processing unit (CPU) chips. This year, a Host-Switch Graph Category featuring more specific conditions was introduced. Entries will be accepted at the dedicated website (http://research.nii.ac.jp/graphgolf) from April 27 to October 11, 2021. Entrants who have discovered excellent graphs will receive awards at CANDAR 2021(*2), an international symposium on computing and networking that will be held in Matsue City, Shimane Prefecture, in November. The Graph Golf Competition has been held every year since fiscal year 2015 except 2020, making this the sixth competition.

 Recently, computers are becoming larger and more complicated, and supercomputers consist of several million 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, it is assumed that for a graph that achieves a network topology, its vertices and edges correspond to the cores and the wires connecting them. The maximum shortest distance between any pair of vertices is known as the diameter, where the average shortest distance between each pair of vertices is known as the average shortest path length (ASPL). The challenge in Graph Golf is to find the graph with the smallest diameter and the smallest ASPL under the specified conditions (see the figure below).

nii_newsrelease_201210427_en-image1.png

[Figure] Examples of graphs with 16 vertices and 4 edges at each vertex. The leftmost graph is considered to be the best, because it has both the smallest diameter and ASP.

 Conservative graph-generating programs, presentation materials provided by past award winners, and a list of related research papers are provided to facilitate participation of researchers and students who are not graph experts in the competition. Results submitted from entrants will be published weekly from July 27 onward(*3) at the dedicated website, and their rankings will be shown. Thus, entrants can check the best graphs among the entries and the ranking of their own graphs, which will provide entrants with the thrill of the competition.
 More than 2,300 entries(*4) have been submitted in the past competitions. The exponential increases in supercomputer performance cause us to update the requirement of the network configurations every year. Accordingly, the Graph Golf Competition changes its problems every year in accordance with the latest trends of next-generation supercomputers. Many recent supercomputers use network switches(*5) for indirect connections between CPUs. To express this composition, a Host-Switch Graph Category, where host (CPU) vertices and switch vertices are distinguished from each other as different types of graph vertices, has been newly created. With this and the existing General Graph Category, there are two categories in the 2021 Graph Golf Competition. The problems in the Host-Switch Graph Category are more difficult than in the General Graph Category. In response, the organizers provide a sample program capable of generating host-switch graphs and a program which calculates the number of hops in an arbitrary host-switch graph, which allows entrants to apply for this new category without difficulty.

 The results of the Graph Golf Competition are expected to be used directly in network topologies designed on the most recent supercomputers and computer processor chips, where the focus is on reducing communication delay. The competition continues to update and open a catalog of the graphs, to contribute to academic and industry research.

Outline of the Graph Golf Competition 2021

Submission period:  Tuesday, April 27, 2021 to Monday, October 11, 2021
Website: http://research.nii.ac.jp/graphgolf
Awards ceremony: To be held at CANDAR 2021, the international symposium on computing and networking that takes place from Tuesday, November 23 to Friday, November 26, 2021 in Matsue City, Shimane Prefecture

Category

Condition

General Graph Category

It can be called an attempt to configure the most efficient network possible for the latest or a future supercomputer from the viewpoint of hop counts.

Eight patterns, each consisting of the number of vertices (40 to 100,000) and the number of edges from the vertex (5 to 128)

Host-Switch Graph Category

Entrants compete to find graphs with the minimum number of hops between host vertices. It can be said that this category has more room for devising creative measures because there are no restrictions on the number of switch vertices used.

Thirteen patterns, each consisting of a number of host vertices (32 to 65,536) and a number of edges from the switch vertex (4 to 100)

Related Link

Graph Golf Competition 2021

News Release: PDF

A Host-Switch Graph Category with more specific conditions newly created!
Graph Golf Competition for Finding Network Configurations for Supercomputers


(*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.
(*2) CANDAR 2021: The international symposium on computing and networking (http://is-candar.org/)
(*3) Published weekly from July 26 onward: All entries received up to and including on July 26 will be published on July 27, 2021. Entries with identical content will be ranked in order of publication.
(*4) More than 2,300 entries: 284 entries in 2015, 131 in 2016, 269 in 2017, 239 in 2018, and 1,382 in 2019
(*5) Network switch: A hub which relays and transfers data exchanged between devices
4892

SPECIAL