News Release

Launch of Competition to Find Graphs Representing / Efficient Network Configurations

Launch of Competition to Find Graphs Representing
Efficient Network Configurations
How Would You Connect CPUs in a Supercomputer?

Japan's National Institute of Informatics (NII; Chiyoda-ku, Tokyo; Dr. Masaru KITSUREGAWA, Director General) has launched its Graph Golf (*1) competition. In this competition, complex network configurations used in supercomputers are replaced by simple graphs,(*2) and entrants compete to find graphs with simple structures that will lead to efficient design of networks inside and between central processing unit (CPU) chips. Entries will be accepted via a dedicated website until October 14. Outstanding graph finders will receive their awards at CANDAR 2018,(*3) an international symposium on computing and networking to be held in November in Takayama, Gifu Prefecture, Japan. The Graph Golf competition has been held annually since fiscal year 2015, making this the fourth competition.

The latest computers have become large and 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 the competition, network topology is modeled as a graph with cores regarded as vertices and wires connecting cores regarded as edges. The number of hops (total number of vertices passed through + final vertex) 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 is to find the graph with as small as possible diameter and ASPL under the specified conditions (see figure).


[Figure] Examples of graphs with 16 vertices and 4 edges extending from each edge. The leftmost graph is considered to be the best as it has both the smallest diameter and the smallest ASPL.

An example graph generating program and presentation materials from past award winners are made available to make it easy for people to take part in the competition. Entries will be published weekly from July 23 onward,(*4) and rankings will be displayed. Via the dedicated website, entrants will be able to check the best graphs among the entries and discover the ranking of the graph that they have submitted, which will add to the excitement of the competition.

The results of Graph Golf are expected to be used directly in network topology design of the most recent supercomputers and computer processor chips, where the focus is on reducing communication delay. The competition will continue to be held in the future, and by storing a catalog of the graphs (network topologies) in Graph Bank,(*5) Graph Golf will contribute to academia and industry.

Graph Golf Competition Summary

Submission period: May 16 (Wed)-October 14 (Sun), 2018
Categories: General Graph Category, Grid Graph Category (*see the dedicated website for specific conditions)
Awards ceremony and workshop: To be held at CANDAR 2018, an international symposium on computing and networking, which will take place November 27 (Tue)-30 (Fri), 2018, in Takayama, Gifu Prefecture, Japan.

PDF Download

Launch of Competition to Find Graphs Representing / Efficient Network Configurations / How Would You Connect CPUs in a Supercomputer?

  • (*1) Graph Golf: The name compares the flow of a signal passing through each core to golf, 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) Graph: A collection of vertices and edges. Edges represent interrelationships between vertices.
  • (*3) CANDAR 2018: An international symposium on computing and networking.
  • (*4) Published weekly from July 22 onward: All entries received up to and including July 22 will be published on July 23. Entries with identical contents will be ranked in order of publication.
  • (*5) Graph Bank: A database of characteristics of various graphs, including configuration information, diameter, and ASPL.
  • (*6) Most recent supercomputers: Established from the specifications of some of the top 10 systems in the supercomputer performance ranking, Top500, as of November 2017, and supercomputers predicted to enter the top rank in the future.