Liu Leibo's team proposed graph computing acceleration technology for reconfigurable chips

From May 30 to June 3, 2020, the 47th International Conference on Computer Architecture (ISCA) was held online. Professors Wei Shaojun and Liu Leibo from Tsinghua University gave an academic report titled "GraphABCD: Scaling Out Graph Analytics with Asynchronous Block Coordinate Descent". The speaker Yang Yifan is the first author of the paper.

This report introduces a method to transform graph computing problems into optimization problems under a reconfigurable architecture and optimize the graph computing framework using a block coordinate descent algorithm. This method fully utilizes the spatial parallelism of the reconfigurable array and provides a new perspective on optimizing the performance of the graph computing framework, which has significant advantages over traditional methods.

Large-scale graph computing algorithms such as PageRank and collaborative filtering are the basis of big data analysis. In order to efficiently solve large-scale graph computing problems, graph computing frameworks have optimized the performance of various graph computing algorithms for specific computing architectures. However, when optimizing iterative graph computing algorithms, existing graph computing frameworks only focus on the execution time of a single iteration, and rarely discuss the number of iterations required for the algorithm to converge. The performance optimization of graph computing algorithms has encountered a bottleneck. If this bottleneck cannot be broken through, it will severely restrict the improvement of the graph computing framework and will also greatly limit the further development of fields such as big data analysis.

Image source: Department of Micro-Nano Electronics, Tsinghua University

To address this problem, the team of Wei Shaojun and Liu Leibo proposed a block coordinate descent execution model applied to the graph computing framework, which can simultaneously optimize the number of iterations and single iteration time of the graph computing algorithm.

The crux of the limitations of existing graph computing frameworks is that they adopt a global synchronous parallel execution model, that is, each iteration of the graph computing uses barriers for global synchronization. The global synchronous parallel model not only limits the scalability of the framework, but also fails to dynamically optimize the number of iterations required for algorithm convergence during the algorithm execution process. This study transforms the graph computing problem into an optimization problem and introduces the block coordinate descent method of optimization analysis into the graph computing framework for the first time.

Under the block coordinate descent execution model, the iterative process of the graph algorithm no longer relies on global synchronization, but selects one or more data blocks consisting of subgraphs in each iteration and updates them according to the coordinate descent method until the algorithm converges. This study can systematically optimize the number of iterations required for the algorithm to converge by analyzing the impact of block coordinate descent model parameters such as data block size, selection order, and update method on the convergence speed; at the same time, since there is no need for synchronization between multiple data blocks, asynchronous concurrent execution can be achieved.

This study extends the graph computing framework to reconfigurable chips in an asynchronous execution mode, and reduces the execution time of a single iteration with the help of heterogeneous reconfigurable computing resources. Experimental results show that in important graph algorithms such as single-source shortest path, PageRank, and collaborative filtering, the convergence rate and performance are improved by 4.8 times and 2 times respectively compared with the current mainstream graph computing framework.