| 摘要: |
| 通过结合体系结构和算法进行研究发现,基于锁的同步机制是细粒度并行介度中心(betweenness centrality,简称BC)算法在现有多核平台上高效执行的主要瓶颈.提出了一种消除锁同步的数据驱动(data-centric)并行算法,在AMD 32 核SMP 和Intel 8 核SMP 两个平台上获得了2 倍左右的加速比. |
| 关键词: 介度中心 锁同步 细粒度并行 数据驱动 多核 |
| DOI：10.3724/SP.J.1001.2011.03811 |
| 分类号: |
| 基金项目:国家自然科学基金(60803030, 60633040, 60921002, 60925009) |
|
| Fine-Grained Parallel Betweenness Centrality Algorithm Without Lock Synchronization |
|
TU Deng-Biao1,2, TAN Guang-Ming1, SUN Ning-Hui1
|
|
1.Key Laboratory of Computer System and Architecture, Institute of Computing Technology, The Chinese Academy of Sciences, Beijing 100190, China;2.Graduate University, The Chinese Academy of Sciences, Beijing 100049, China
|
| 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. |
| Key words: betweenness centrality lock synchronization fine-grained parallelism data-centric multi-core |
