F. Sadi, Joe Sweeney, S. McMillan, Tze-Meng Low, James C. Hoe, Lawrence Pileggi and Franz Franchetti (Proc. High Performance Extreme Computing (HPEC), 2018)
PageRank Acceleration for Large Graphs with Scalable Hardware and Two-Step SpMV
Comment: Student Innovation Award
Preprint (1.7 MB)
Published paper (link to publisher)

PageRank is an important vertex ranking algorithm that suffers from poor performance and efficiency due to notorious memory access behavior. Furthermore, when graphs become bigger and sparser, PageRank applications are inhibited as most current solutions profoundly rely on large random access fast memory, which is not easily scalable. In this paper we present a 16nm ASIC based shared memory platform for PageRank implementation that fundamentally accelerates Sparse Matrix dense Vector multiplication (SpMV), the core kernel of PageRank. This accelerator is scalable, guarantees full DRAM streaming and reduces off-chip communication. More importantly, it is capable of handling very large graphs (2 billion vertices) despite using significantly less fast random access memory than current solutions. Experimental results show that our proposed accelerator is able to yield order of magnitude improvement in both energy efficiency and performance over state of the art shared memory commercial off-the-shelf (COTS) solutions.

Hardware, Acceleration, Graphs, Scalable, SpMV