Acceleration of PageRank with Customized Precision Based on Mantissa Segmentation

Citations Over TimeTop 17% of 2020 papers

Abstract

We describe the application of a communication-reduction technique for the PageRank algorithm that dynamically adapts the precision of the data access to the numerical requirements of the algorithm as the iteration converges. Our variable-precision strategy, using a customized precision format based on mantissa segmentation (CPMS), abandons the IEEE 754 single- and double-precision number representation formats employed in the standard implementation of PageRank, and instead handles the data in memory using a customized floating-point format. The customized format enables fast data access in different accuracy, prevents overflow/underflow by preserving the IEEE 754 double-precision exponent, and efficiently avoids data duplication, since all bits of the original IEEE 754 double-precision mantissa are preserved in memory, but re-organized for efficient reduced precision access. With this approach, the truncated values (omitting significand bits), as well as the original IEEE double-precision values, can be retrieved without duplicating the data in different formats. Our numerical experiments on an NVIDIA V100 GPU (Volta architecture) and a server equipped with two Intel Xeon Platinum 8168 CPUs (48 cores in total) expose that, compared with a standard IEEE double-precision implementation, the CPMS-based PageRank completes about 10% faster if high-accuracy output is needed, and about 30% faster if reduced output accuracy is acceptable.

Related Papers

• → Optimizing the PCIT algorithm on stampede's Xeon and Xeon Phi processors for faster discovery of biological networks(2013)18 cited
• → The Impact of Multicore on Math Software and Exploiting Single Precision Computing to Obtain Double Precision Results(2006)4 cited
• → Performance Aspects of Collocated and Staggered Grids for Particle-in-Cell Plasma Simulation(2017)1 cited
• → The Impact of Multicore on Math Software and Exploiting Single Precision Computing to Obtain Double Precision Results(2006)1 cited