无锁同步的细粒度并行介度中心算法  

Fine-Grained Parallel Betweenness Centrality Algorithm Without Lock Synchronization

作　　者：涂登彪[1,2] 谭光明[1] 孙凝晖[1] 

机构地区：[1]中国科学院计算技术研究所计算机系统结构重点实验室,北京100190 [2]中国科学院研究生院,北京100049

出　　处：《软件学报》2011年第5期986-995,共10页Journal of Software

基　　金：国家自然科学基金(60803030;60633040;60921002;60925009)

摘　　要：通过结合体系结构和算法进行研究发现,基于锁的同步机制是细粒度并行介度中心(betweenness centrality,简称BC)算法在现有多核平台上高效执行的主要瓶颈.提出了一种消除锁同步的数据驱动(data-centric)并行算法,在AMD 32核SMP和Intel8核SMP两个平台上获得了2倍左右的加速比.Through a joint study in architecture and application, it is found that lock synchronization in a fine-grained parallel betweenness centrality （BC） program poses an obstacle for the efficient execution of parallel architectures. This paper proposes a data-centric parallel algorithm that eliminates lock synchronization. This algorithm reduces execution time and improves speeds up twice as fast on both AMD 32 core SMP and Intel 8core SMP.

关 键 词：介度中心 锁同步 细粒度并行 数据驱动 多核 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]