Analysis and performance results of computing betweenness centrality on IBM Cyclops64

doi:10.1007/s11227-009-0339-9

	Analysis and performance results of computing betweenness centrality on IBM Cyclops64
	Tan, Guangming 1,2; Sreedhar, Vugranam C.3; Gao, Guang R.2
	2011-04-01
发表期刊	JOURNAL OF SUPERCOMPUTING
ISSN	0920-8542
卷号	56 期号:1 页码:1-24
摘要	This paper presents a joint study of application and architecture to improve the performance and scalability of an irregular application-computing betweenness centrality-on a many-core architecture IBM Cyclops64. The characteristics of unstructured parallelism, dynamically non-contiguous memory access, and low arithmetic intensity in betweenness centrality pose an obstacle to an efficient mapping of parallel algorithms on such many-core architectures. By identifying several key architectural features, we propose and evaluate efficient strategies for achieving scalability on a massive multi-threading many-core architecture. We demonstrate several optimization strategies including multi-grain parallelism, just-in-time locality with explicit memory hierarchy and non-preemptive thread execution, and fine-grain data synchronization. Comparing with a conventional parallel algorithm, we get 4X-50X improvement in performance and 16X improvement in scalability on a 128-cores IBM Cyclops64 simulator.
关键词	Many-core architecture Betweenness centrality Just-in-time locality Multi-grain parallelism
DOI	10.1007/s11227-009-0339-9
收录类别	SCI
语种	英语
资助项目	IBM ; ET International ; Department of Defense ; Department of Energy[DE-FC02-01ER25503] ; National Science Foundation[CNS-0509332] ; National Natural Science Foundation of China[60803030] ; National Natural Science Foundation of China[60633040] ; National Natural Science Foundation of China[60925009] ; Chinese Academy of Sciences[KGCX1-YW-13]
WOS研究方向	Computer Science ; Engineering
WOS类目	Computer Science, Hardware & Architecture ; Computer Science, Theory & Methods ; Engineering, Electrical & Electronic
WOS记录号	WOS:000289102500001
出版者	SPRINGER
引用统计	被引频次：8[WOS] [WOS记录] [WOS相关记录]
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/12945
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Tan, Guangming
作者单位	1.Chinese Acad Sci, Inst Comp Technol, Beijing, Peoples R China 2.Univ Delaware, Comp Architecture & Parallel Syst Lab, Newark, DE 19716 USA 3.IBM TJ Watson Res Ctr, Cambridge, MA USA
推荐引用方式 GB/T 7714	Tan, Guangming,Sreedhar, Vugranam C.,Gao, Guang R.. Analysis and performance results of computing betweenness centrality on IBM Cyclops64[J]. JOURNAL OF SUPERCOMPUTING,2011,56(1):1-24.
APA	Tan, Guangming,Sreedhar, Vugranam C.,&Gao, Guang R..(2011).Analysis and performance results of computing betweenness centrality on IBM Cyclops64.JOURNAL OF SUPERCOMPUTING,56(1),1-24.
MLA	Tan, Guangming,et al."Analysis and performance results of computing betweenness centrality on IBM Cyclops64".JOURNAL OF SUPERCOMPUTING 56.1(2011):1-24.