面向非规则大数据分析应用的多核帮助线程预取方法

doi:10.3969/j.issn.1000-436x.2014.08.017

摘要/Abstract

摘要：

大数据分析应用往往采用基于大型稀疏图的遍历算法，其主要特点是非规则数据密集访存。以频繁使用的具有大型稀疏图遍历特征的介度中心算法为例，提出一种基于帮助线程的多参数预取控制模型和参数优化方法，从而达到提高非规则数据密集程序性能的目的。在商用多核平台Q6600和I7上运用该方法后，介度中心算法在不同规模输入下平均性能加速比分别为1.20和1.11。实验结果表明，帮助线程预取能够有效提升该类非规则应用程序的性能。

关键词: 帮助线程预取, 非规则数据密集应用, 介度中心性

Abstract:

Big data analysis applications often use sparse graph traversal algorithm which characterized by irregular data intensive memory access. For improving performance of memory access in sparse graph traversal algorithm, helper thread prefetching could convert discontinuous locality into continuous-instant spatial-temporal locality effectively by using the shared last level cache of chip multi-processor platforms. Betweenness centrality algorithm was used as a case study, the multi-parameter prefetching model of helper thread and optimized instances were presented and evaluated on commercial CMP platforms Q6600 and I7, the average speedup of betweenness centrality algorithm at different input scale is 1.20 and 1.11 respectively. The experiment results show that helper thread prefetching can improve the perform-ance of irregular applications effectively.

Key words: helper thread prefetching, irregular data intensive applications, betweenness centrality

张建勋,古志民,胡潇涵,蔡旻. 面向非规则大数据分析应用的多核帮助线程预取方法[J]. 通信学报, 2014, 35(8): 137-146.

Jian-xun ZHANG,Zhi-min GU,Xiao-han HU,Min CAI. Multi-core helper thread prefetching for irregular data intensive applications[J]. Journal on Communications, 2014, 35(8): 137-146.

图/表 13

图1

表1

图2

表2

图3

图4

图5

图6

图7

图8

图9

图10

图11

参考文献 19

[1]	SOFFER A , HEILD M . Big data meets social analytics[A]. Proc of 2012 Conference of IBM Lotusphere[C]. Orlando, Florida, USA, 2012.
[2]	BRANDES U . A faster algorithm for betweenness centrality[J]. Jour-nal of Mathematical Sociology, 2001, 25(2): 163-177.
[3]	BADER D , MADDURI K , GILBERT J , et al. Designing scalable synthetic compact applications for benchmarking high productivity computing systems[J]. CTWatch Quarterly, 2006, 4B(2): 1-10.
[4]	LUK C . Tolerating memory latency through software controlled pre-execution in simultaneous multithreading processors[A]. Proc of the 28th Annual International Symposium on Computer Architecture (ISCA)[C] G?teborg, Sweden, 2001. 40-51.
[5]	SMITH JE . Decoupled access/execute computer architectures[A]. Proc of the 9th International Symposium on Computer Architecture (ISCA)[C]. Austin, TX, USA, 1982. 112-119.
[6]	SONG Y , KALOGEROPULOS S , TIRUMALAI P . Design and im-plementation of a compiler framework for helper threading on multi-core processors[A]. Proc of the 14th International Conference on Par-allel Architectures and Compilation Techniques (PACT)[C]. Saint Louis, MO, USA, 2005. 99-109.
[7]	KIM D , LIAO S , WANG P , et al. Physical experimentation with pre-fetching helper threads on Intel's hyper-threaded processors[A]. Proc of the International Symposium on Code generation and Optimization (CGO)[C]. Palo Alto, Calif, 2004. 27-38.
[8]	LEE J , JUNG C , KIM D , et al. Prefetching with helper threads for lossely coupled multiprocessor systems[A]. IEEE Transactions on Par-allel and Distributed System[C]. 2009, 20(9): 1309-1324.
[7]	LU J , DAS A , HSU W , et al. Dynamic helper threaded prefetching on the Sun UltraSparc CMP processor[A]. Proc of 38th Annual IEEE/ACM International Symposium Micro Architecture (MI-CRO)[C]. Barcelona, Spain, 2005. 93-104.
[10]	ZHOU J , CIESLEWICZ J , ROSS K , et al Improving database per-formance on simultaneous multithreading processors[A]. Proc of the 31th International Conference on Very Large Data Bases[C] Trond-heim, Norway, 2005. 49-60.
[11]	HUANG Y , TANG J , GU Z , et al. The performance optimization of threaded prefetching for linked data structures[A]. International Journal of Parallel Programming 2012, 40(2): 141-163.
[12]	DUDAS A , JUHASZ S . Reconfigurable pre-execution in data parallel applications on multicore systems[A]. Electrical Engineering and In-telligent Systems Lecture Notes in Electrical Engineering 2013. 29-38.
[13]	MADDURI K , EDIGER D , JIANG K , et al. A faster parallel algo-rithm and efficient multithreaded implementations for evaluating be-tweenness centrality on massive datasets[A]. Proc of IEEE Interna-tional Symposium on Parallel ＆ Distributed Processing(IPDPS)[C]. Rome, Italy, 2009. 1-8.
[14]	TU D , TAN G , SUN N . Fine-grained parallel betweenness centrality algorithm without lock synchronization[A]. Journal of Software 2011, 22(5): 986-995.
[15]	EDMONDS N , HOEFLER T , LUMSDAINE A , et al. A space-efficient parallel algorithm for computing betweenness centrality in distributed memory[A]. roc of International Conference on High Performance Computing (HiPC)[C]. Goa, India, 2010. 1-10.
[16]	TU D , TAN G . Characterizing betweenness centrality algorithm on multi-core architectures[A]. Proc of IEEE International Symposium on Parallel and Distributed Processing with Application(ISPA)[C]. Chengdu, China, 2009. 182-189.
[17]	TAN G , VUGRANAM C , SREEDHAR , et al. Analysis and perform-ance results of computing betweeness centrality on IBM Cyclops64[A]. Journal of Supercomputing 2011, 1(56): 1-24.
[18]	TAN G , VUGRANAM C , SREEDHAR , et al. Just-in-time locality and percolation for optimizing irregular applications on a manycore archi-tecture[A]. Proc of Conference on languages and compilers for parallel Computing Lecture Notes in Computer Science[C]. Edmonton, Can-ada, 2008. 331-342.
[19]	ZHANG J , GU Z . Exposing the shared cache behavior of helper thread on CMP platforms[A]. Proc of the 14th IEEE International Conference on Computational Science and Engineering(CSE)[C] Dalinan, China, 2011. 379-386.

热点模块	时钟数(10³)	指令数(10³)	LLC 缺失数(10³)	每指令时钟数（CPI）时钟百分比/%	LLC缺失百分比/%
SSCA2程序	75 474 000	25 504 000	221 000	2.959 301100	100
BC算法程序	69 198 000	21 040 000	219 000	3.288 87891.68	99.10
BFS模块	48 420 000	16 624 000	135 500	2.912 65664.15	61.31
Backtrack模块	18 646 000	3 352 000	82 500	5.562 64924.71	37.33

处理器	Intel Core 2 Quad Processor Q6600	Intel Core I7-930 with Hyperthreading
内存大小	2 GB(DDR 667, non-ECC)	4 GB(DDR3, non-ECC)
L1 数据缓存	32 KB×4 8 路组相联缓存行大小64 byte	32 KB×4 8路组相联缓存行大小64 byte
L1 指令缓存	32 KB×4 8路组相联缓存行大小64 byte	32 KB×4 4路组相联缓存行大小64 byte
L2 缓存	4 096 KB×2 16 set-association cache line 64 byte	256 KB×4 8路组相联缓存行大小64 byte
L3 缓存	—	8 192 KB×1 16路组相联缓存行大小64 byte
前端总线速度	1 066 MHz	4.80 GT/s Intel^?QPI
编译器	gcc version 4.3.0	gcc version 4.3.0
操作系统	Fedora 9 with kernel 2.6.25	Redhat Enterprise with kernel 2.6.37.1