Journal of Software:2011.22(5):986-995

(中国科学院 计算技术研究所 计算机系统结构重点实验室,北京 100190;中国科学院 研究生院,北京 100049)
Fine-Grained Parallel Betweenness Centrality Algorithm Without Lock Synchronization
TU Deng-Biao,TAN Guang-Ming,SUN Ning-Hui
(Key Laboratory of Computer System and Architecture, Institute of Computing Technology, The Chinese Academy of Sciences, Beijing 100190, China; Graduate University, The Chinese Academy of Sciences, Beijing 100049, China)
Chart / table
Similar Articles
Article :Browse 4002   Download 3982
Received:August 01, 2008    Revised:December 25, 2009
> 中文摘要: 通过结合体系结构和算法进行研究发现,基于锁的同步机制是细粒度并行介度中心(betweenness centrality,简称BC)算法在现有多核平台上高效执行的主要瓶颈.提出了一种消除锁同步的数据驱动(data-centric)并行算法,在AMD 32 核SMP 和Intel 8 核SMP 两个平台上获得了2 倍左右的加速比.
Abstract: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.
文章编号:     中图分类号:    文献标志码:
基金项目:国家自然科学基金(60803030, 60633040, 60921002, 60925009) 国家自然科学基金(60803030, 60633040, 60921002, 60925009)
Foundation items:
Reference text:


TU Deng-Biao,TAN Guang-Ming,SUN Ning-Hui.Fine-Grained Parallel Betweenness Centrality Algorithm Without Lock Synchronization.Journal of Software,2011,22(5):986-995