中国科学院机构知识库网格
Chinese Academy of Sciences Institutional Repositories Grid
首页 机构 成果 学者
  
  1. CAS IR Grid
  2. 计算技术研究所
  3. 中国科学院计算技术研究所
  4. 中国科学院计算技术研究所期刊论文
  5. 英文
Graphine: Programming Graph-Parallel Computation of Large Natural Graphs for Multicore Clusters

文献类型：期刊论文

作者Yan, Jie1; Tan, Guangming1; Mo, Zeyao2; Sun, Ninghui1
刊名IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS
出版日期2016-06-01
卷号27期号:6页码:1647-1659
关键词Graph-parallel parallel framework computational model
ISSN号1045-9219
DOI10.1109/TPDS.2015.2453978
英文摘要Graph-parallel computation has become a crucial component in emerging applications of web search, data analytics and machine learning. In practice, most graphs derived from real-world phenomena are very large and scale-free. Unfortunately, distributed graph-parallel computation of these natural graphs still suffers strong scalability issues on contemporary multicore clusters. To embrace the multicore architecture in distributed graph-parallel computation, we propose the framework Graphine, which features (i) A Scatter-Combine computation abstraction that is evolved from the traditional vertex-centric approach by fusing the paired scatter and gather operations, executed separately on two edge sides, into a one-sided scatter. Further coupled with active message mechanism, it potentially reduces intermediate message cost and enables fine-grained parallelism on multicore architecture. (ii) An Agent-Graph data model, which leverages an idea similar to vertex-cut but conceptually splits the remote replica into two agent types of scatter and combiner, resulting in less communication. We implement the Graphine framework and evaluate it using several representative algorithms on six large real-world graphs and a series of synthetic graphs with power-law degree distributions. We show that Graphine achieves sublinear scalability with the number of cores per node, number of nodes, and graph sizes (up to one billion vertices), and is 2 similar to 15 times faster than the state-of-the-art PowerGraph on a cluster of 16 multicore nodes.
资助项目National Natural Science Foundation of China[61272134] ; National Natural Science Foundation of China[31327901] ; National Natural Science Foundation of China[91430218] ; National Natural Science Foundation of China[60921002] ; National Natural Science Foundation of China[60925009] ; National Natural Science Foundation of China[61472395] ; National 863 Program[2009AA01A129] ; 973 Program[2012CB316502] ; 973 Program[2011CB302502]
WOS研究方向Computer Science ; Engineering
语种英语
WOS记录号WOS:000376106400008
出版者IEEE COMPUTER SOC
源URL[http://119.78.100.204/handle/2XEOYT63/8599]  
专题中国科学院计算技术研究所期刊论文_英文
通讯作者Yan, Jie; Tan, Guangming; Mo, Zeyao; Sun, Ninghui
作者单位1.Chinese Acad Sci, Inst Comp Technol, State Key Lab Comp Architecture, Beijing 100864, Peoples R China
2.Inst Appl Phys & Computat Math, Beijing, Peoples R China
推荐引用方式
GB/T 7714		 Yan, Jie,Tan, Guangming,Mo, Zeyao,et al. Graphine: Programming Graph-Parallel Computation of Large Natural Graphs for Multicore Clusters[J]. IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS,2016,27(6):1647-1659.
APA Yan, Jie,Tan, Guangming,Mo, Zeyao,&Sun, Ninghui.(2016).Graphine: Programming Graph-Parallel Computation of Large Natural Graphs for Multicore Clusters.IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS,27(6),1647-1659.
MLA Yan, Jie,et al."Graphine: Programming Graph-Parallel Computation of Large Natural Graphs for Multicore Clusters".IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 27.6(2016):1647-1659.

入库方式： OAI收割

来源：计算技术研究所

浏览0
下载0
收藏0
其他版本

除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。