A lock-free approach to parallelizing personalized PageRank computations on GPU

作     者：Zhigang WANG Ning WANG Jie NIE Zhiqiang WEI Yu GU Ge YU Zhigang WANG;Ning WANG;Jie NIE;Zhiqiang WEI;Yu GU;Ge YU

作者机构：Faculty of Information Science&EngineeringOcean University of ChinaQingdao 266100China School of Computer Science and EngineeringNortheastern UniversityShenyang 110819China 

出 版 物：《Frontiers of Computer Science》 (中国计算机科学前沿（英文版）)

年 卷 期：2023年第17卷第1期

页      面：219-220页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：supported by the National Natural Science Foundation of China(Grant Nos.61902366 and 61902365) the Fundamental Research Funds for the Central Universities(202042008) the CCF-Huawei Innovation Research Plan,the Project funded by China Postdoctoral Science Foundation(2020T130623) the Qingdao Independent Innovation Major Project(20-3-2-12-xx) 

主　　题：PageRank GPU Push 

摘      要：1 Introduction Personalized PageRank(PPR)is a classic topology-based proximity measure and it is most widely computed by Forward *** 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 *** process converges until all scores hold ***,Graphical Processing Units(GPU)with massive threads has been extensively used to parallelize such compute-intensive *** yields performance improvement but also involves two atomic locks for *** locks are practically inefficient and become a new performance *** 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 *** best performance,a new Hybrid Framework is then designed to adaptively balance locking costs and reading costs.