Graph algorithms:parallelization and scalability  

作　　者：Wenfei FAN Kun HE Qian LI Yue WANG 

机构地区：[1]School of Informatics,University of Edinburgh,Edinburgh EH89AB,UK [2]Shenzhen Institute of Computing Sciences,Shenzhen University,Shenzhen 518060,China [3]Beijing Advanced Innovation Center for Big Data and Brain Computing,Beihang University,Beijing 100191,China [4]Guangdong Province Key Laboratory of Popular High Performance Computers,Shenzhen University,Shenzhen 518060,China

出　　处：《Science China(Information Sciences)》2020年第10期230-250,共21页中国科学（信息科学）（英文版）

基　　金：supported in part by Shenzhen Institute of Computing Sciences,Beijing Advanced Innovation Center for Big Data and Brain Computing(Beihang University),Royal Society Wolfson Research Merit Award(Grant No.WRM/R1/180014);European Research Council(Grant No.652976);Engineering and Physical Sciences Research Council(Grant No.EP/M025268/1)。

摘　　要：For computations on large-scale graphs,one often resorts to parallel algorithms.However,parallel algorithms are difficult to write,debug and analyze.Worse still,it is difficult to make algorithms parallelly scalable,such that the more machines are used,the faster the algorithms run.Indeed,it is not yet known whether any PTIME computational problems admit parallelly scalable algorithms on shared-nothing systems.Is it possible to parallelize sequential graph algorithms and guarantee convergence at the correct results as long as the sequential algorithms are correct?Moreover,does a PTIME parallelly scalable problem exist on shared-nothing systems?This position paper answers both questions in the affirmative.

关 键 词：PARALLELIZATION parallel scalability PTIME problems graph algorithms shared-nothing systems 

分 类 号：TP338.6[自动化与计算机技术—计算机系统结构]