1 Introduction Personalized PageRank(PPR)is a classic topology-based proximity measure and it is most widely computed by Forward Push.That is,given a starting vertex in graph,it iteratively computes the importance score of any vertex in with respect to,and then broadcasts the new score as messages to’s neighboring vertices.The process converges until all scores hold stable.Recently,Graphical Processing Units(GPU)with massive threads has been extensively used to parallelize such compute-intensive process.It yields performance improvement but also involves two atomic locks for correctness.Such locks are practically inefficient and become a new performance bottleneck.This paper proposes a separation technique to partially eliminate atomic protections,termed as Lightweight Forward Push.A Forward Pull solution is further devised to support lock-free PPR computations but also causes useless reads.For best performance,a new Hybrid Framework is then designed to adaptively balance locking costs and reading costs.
展开▼
