Paper Info
Title
PageRank Acceleration for Large Graphs with Scalable Hardware and Two-Step SpMV
Abstract
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.
Year
DOI
Venue
2018
10.1109/HPEC.2018.8547561
2018 IEEE High Performance extreme Computing Conference (HPEC)
Keywords
Field
DocType
graphs,scalable hardware,notorious memory access behavior,core kernel,energy efficiency,SPMV,vertex ranking algorithm,random access memory,commercial off-the-shelf,DRAM streaming,sparse matrix dense vector multiplication,pagerank acceleration,ASIC,magnitude improvement
Kernel (linear algebra),PageRank,Shared memory,Computer science,Parallel computing,Application-specific integrated circuit,Memory management,Sparse matrix,Random access,Scalability
Conference
ISSN
ISBN
Citations 
2377-6943
978-1-5386-5990-8
2
PageRank 
References 
Authors
0.36
0
7
Name
Order
Citations
PageRank
Fazle Sadi1244.35
Joe Sweeney270.79
Scott Mcmillan39315.01
Tze Meng Low414619.62
James C. Hoe52048141.34
Larry Pileggi61029108.97
Franz Franchetti797488.39