modeling the locality in graph traversals

ISCAS OpenIR

	modeling the locality in graph traversals
	Yuan Liang; Ding Chen; &#; tefankovic Daniel; Zhang Yunquan
	2012
会议名称	41st International Conference on Parallel Processing, ICPP 2012
会议录名称	Proceedings of the International Conference on Parallel Processing
页码	138-147
会议日期	September 10, 2012 - September 13, 2012
会议地点	Pittsburgh, PA, United states
收录类别	EI
ISSN	0190-3918
ISBN	9780769547961
部门归属	(1) Lab. of Parallel Software and Computational Science Institute of Software Chinese Academy of Sciences China; (2) State Key Laboratory of Computer Science Institute of Software Chinese Academy of Sciences China; (3) Graduate University of Chinese Academy of Sciences China; (4) Computer Science Department University of Rochester United States
摘要	An increasing number of applications in physical and social sciences require the analysis of large graphs. The efficiency of these programs strongly depends on their memory usage especially the locality of graph data access. Intuitively, the locality in computation should reflect the locality in graph topology. Existing locality models, however, operate either at program level for regular loops and arrays or at trace level for arbitrary access streams. They are not sufficient to characterize the relation between locality and connectivity. This paper presents a new metrics called the vertex distance and uses it to model the locality in breadth-first graph traversal (BFS). It shows three models that use the average node degree and the edge distribution to predict the number of BFS levels and the reuse distance distribution of BFS. Finally, it evaluates the new models using random and non-random graphs. © 2012 IEEE.; An increasing number of applications in physical and social sciences require the analysis of large graphs. The efficiency of these programs strongly depends on their memory usage especially the locality of graph data access. Intuitively, the locality in computation should reflect the locality in graph topology. Existing locality models, however, operate either at program level for regular loops and arrays or at trace level for arbitrary access streams. They are not sufficient to characterize the relation between locality and connectivity. This paper presents a new metrics called the vertex distance and uses it to model the locality in breadth-first graph traversal (BFS). It shows three models that use the average node degree and the edge distribution to predict the number of BFS levels and the reuse distance distribution of BFS. Finally, it evaluates the new models using random and non-random graphs. © 2012 IEEE.
主办者	Int. Assoc. Comput. Commun. (IACC)
语种	英语
内容类型	会议论文
URI标识	http://ir.iscas.ac.cn/handle/311060/15873
专题	中国科学院软件研究所
推荐引用方式 GB/T 7714	Yuan Liang,Ding Chen,&#,et al. modeling the locality in graph traversals[C],2012:138-147.