【作者】 陈平； 王柏； 徐六通； 吴斌； 王艳辉；

【Author】 CHEN Ping, WANG Bai, XU Liu-long, WU Bin, WANG Yan-hui (Telecommunication Software Engineering Center, Beijing University of Posts and Telecommunications, Beijing 100876, China)

【机构】 北京邮电大学通信软件工程中心；

【摘要】 为了解决电信社群网络中介度(图的一个几何量)计算中的海量计算问题,研究并实现了高性能网格并行计算方法．该算法采用层次性的二分法分割数据,能在较短的时间内完成大规模社群网络图各顶点中的介度计算．为了提高计算的加速比,提出了一种改进的网格并行调度算法,并采用动静态结合的方法来平衡负载．论证表明, 改进算法的加速比、并行效率和平衡度都有提高,计算用时与网格上并行计算处理器数目成近似线形关系．更多还原

【Abstract】 For betweeness computation in telecom social network graph with huge amount of data, a grid based parallel algorithm is presented. It adopts the hierarchic dichotomy of data. Meanwhile a new schedule strategy is proposed, that combines static and dynamic methods to reach load balance. The experimental results justified that the algorithm achieves a higher speedup ratio and the parallel efficiency, and the time consumption is approximately proportion to the number of parallel CPUs as well.更多还原