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

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

Abstract

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

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.

Figures/Tables 13

References 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.

Metrics

Recommended 0

No Suggested Reading articles found!

热点模块	时钟数(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

Multi-core helper thread prefetching for irregular data intensive applications

RichHTML

PDF

Knowledge

Cited

Abstract

Cite this article

share this article

Figures/Tables 13

References 19

Related Articles 2

Metrics

Recommended 0

[1]	Zhuang-liang GAO,Yan-fei LYU,Hong ZHANG. Key nodes discovery in network graph based on Graphlab [J]. Journal on Communications, 2016, 37(3): 182-189.
[2]	. Multi-core helper thread prefetching for irregular data intensive applications [J]. Journal on Communications, 2014, 35(8): 17-146.