NTT has developed an algorithm called “Forest Pruning” to quickly perform calculations (BFS) on graphs (data showing the relationships between things through vertices and branches) that trace all the connections from the starting point to the closest point. This is expected to improve the performance of a wide range of processes, such as data mining and AI, which use large-scale graph data.

This technology contributed to improving the top record held by the supercomputer Fugaku in the BFS category of the Graph500 supercomputer performance ranking by about 20%.

A graph here is a representation of the network structure of things. It is a data format that is applied in a wide range of fields, such as data mining and AI, and is expected to speed up processing and reduce labor.

A wide range of things can be understood from this graph. In recent years, it has been used to provide answers from AI, but it can also be used to identify the source of cyber attacks and to discover transactions related to money laundering by understanding the flow of money.
NTT has been researching high-speed graph processing technology for over 10 years. As part of this, they established “Forest Pruning,” an efficient algorithm for BFS.

Graph500 in November 2011 achieved the highest power efficiency of any commercially available processor. They have now implemented it on Fugaku and proven its effectiveness.

BFS performs processing by tracing the nearest vertices in order from the starting point of the graph.

This is a basic elemental technology in graph processing, and as a result of BFS, a BFS tree can be obtained. This tree represents the path taken by BFS to visit each vertex.

When applying BFS to a large graph (for example, one with more than 1 trillion vertices), an efficient program is required.

Graph500 is a contest based on BFS trees, and for the past 10 years, Japanese supercomputers “K” and “Fugaku” have monopolized the top spot. However, in recent years, Chinese computers have been catching up, and to maintain their lead, it is necessary to continuously improve computing performance.

※Translating Japanese articles into English with AI