Multi-Mode SpMV Accelerator for Transprecision PageRank With Real-World Graphs

Abstract

With the development of Internet networks, the PageRank algorithm, which was initially developed to recommend important pages in Google’s web search systems, is widely used as the basis of various ranking systems in graph processing fields. However, PageRank algorithm requires Sparse Matrix-Vector Multiplication (SpMV) repeatedly which becomes main bottleneck for the calculation. In this study, we present the multi-mode SpMV accelerator for half-to-single transprecision PageRank with real-world graphs. To support transprecision, where the operation performs in half-precision (FP16) initially and changes its precision to single-precision (FP32), the proposed multi-mode SpMV accelerator can perform both dual FP16 mode and single FP32 mode. In dual FP16 mode, the proposed accelerator performs two FP16 SpMV in parallel, and in single FP32 mode, it performs one FP32 SpMV with the same hardware resources. Also, for the reduction of memory footprint, the proposed accelerator supports the Compressed Sparse Row (CSR) format. In addition, dual-issue accumulator and multi-mode transprecision multiplier are presented to support both FP16 and FP32 modes. Validation of the proposed transprecision PageRank algorithm is performed with four real-world graph datasets, resulting in a low 0-4% error rate and $1.3\times $ - $1.9\times $ speedup compared to single-precision PageRank computation without transprecision.

Keywords

• Transprecision
• sparse matrix vector multiplication (SpMV)
• PageRank (PR)
• floating-point multiplier
• single-precision (FP32)
• half-precision (FP16)