Wanted: People who have discovered huge graphs with simple structures connecting one million CPUs in a future supercomputer! - Graph Golf Competition 2019 to be Held--Finding Graphs that Represent Efficient Network Configurations -
National Institute of Informatics (NII; Director General: Dr. Kitsuregawa Masaru; Tokyo, Japan) will hold the Graph Golf(*1) Competition 2019. In this competition, entrants compete to find graphswith simple structures that correspond to complex network configurations used in supercomputers and lead to efficient design of networks inside and between central processing unit (CPU) chips.
This year, a huge graph with one million vertices will be added as a new problem. Entries are accepted at the dedicated website (http://research.nii.ac.jp/graphgolf) from April 29 to October 14, 2019. Entrants who have discovered excellent graphs will receive awards at CANDAR2019(*2), an international symposium on computing and networking that will be held in Nagasaki City, Nagasaki Prefecture, in November. The Graph Golf Competition has been held annually since fiscal year 2015, making this the fifth 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 the competition, network topology is considered as a graph with cores regarded as vertices and wires connecting cores regarded as 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 is to find the graph with the smallest possible diameter and the smallest possible ASPL under the specified conditions (see the figure below).
[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 ASPL.
Conservative graph-generating programs and presentation materials provided by past award winners are available to facilitate participation in the competition. Entries will be published weekly from July 23 onward(*3), and rankings will be displayed. The dedicated website will allow entrants to check the best graphs among the entries and the ranking of their submitted graph, which will add to the thrill of the competition.
The competition consists of the General Graph Category and the Grid Graph Category. More than 900 entries(*4) have been submitted so far. The exponential increases in supercomputer performance requires 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. This year, a huge graph with one million vertices has been added as a new problem by making assumptions about the structure of an exascale supercomputer (which is capable of processing more than 1018 floating-point operations per second)(*5), which will appear in the future. A parallel program for quickly calculating the number of hops in a huge graph, which was provided as a courtesy by an entrant, has made it easy to attempt to create huge graphs.
The results of the Graph Golf Competition 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, Graph Golf will contribute to academia and the industry.
Outline of the Graph Golf Competition 2019
Submission period:Monday, April 29, 2019 to Monday, October 14, 2019
Awards ceremony: To be held at CANDAR 2019, the international symposium on computing and networking that takes place from Tuesday, November 26 to Friday, November 29, 2019 in Nagasaki City, Nagasaki Prefecture
General Graph Category
Graphs for network configurations of the most recent supercomputers(*6) and those of future supercomputers are included. 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.
Condition Eleven patterns, each consisting of the number of vertices (50 to 1,000,000) and the number of edges from the vertex (4 to 32)
Grid Graph Category
A grid graph which has vertices and edges on a two-dimensional plane. It has vertices in a rectangular pattern, and there is a constraint on the length of edges on the plane. It represents lengths of cables in a machine room, lengths of wires between memories on a motherboard, or a computer system which has a constraint on the length of wires in chips for a reason related to mounting.
Condition Eleven patterns, each consisting of the number of vertices (25 to 10,000), the number of edges at the vertex (4 to 8), and the maximum edge length (2 to 4)
(*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 2019: The international symposium on computing and networking (http://is-candar.org/). (*3) Published weekly from July 22 onward: All entries received up to and including on July 22 will be published on July 23, 2019. Entries with identical contents will be ranked in order of publication. (*4) More than 900 entries: 284 entries in 2015, 131 in 2016, 269 in 2017, and 239 in 2018 (*5) Exascale supercomputer: This was assumed based on the examples of exascale system configuration shown in HPCI Gijutsu Roadmap Hakusho (HPCI Technology Roadmap White Paper). (http://open-supercomputer.org/wp-content/uploads/2012/03/hpci-roadmap.pdf) (In Japanese) (*6) Most recent supercomputers: Based on the specifications of some of the top 10 systems in the supercomputer performance ranking, Top500 (https://www.top500.org/), as of November 2018