ISCAS OpenIR
modeling the locality in graph traversals
Yuan Liang; Ding Chen; &#; tefankovic Daniel; Zhang Yunquan
2012
Conference Name41st International Conference on Parallel Processing, ICPP 2012
SourceProceedings of the International Conference on Parallel Processing
Pages138-147
Conference DateSeptember 10, 2012 - September 13, 2012
Conference PlacePittsburgh, PA, United states
Indexed TypeEI
ISSN0190-3918
ISBN9780769547961
Department(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
English AbstractAn 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.
SponsorshipInt. Assoc. Comput. Commun. (IACC)
Language英语
Content Type会议论文
URIhttp://ir.iscas.ac.cn/handle/311060/15873
Collection中国科学院软件研究所
Recommended Citation
GB/T 7714
Yuan Liang,Ding Chen,&#,et al. modeling the locality in graph traversals[C],2012:138-147.
Files in This Item:
There are no files associated with this item.
Related Services
Recommend this item
Bookmark
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[Yuan Liang]'s Articles
[Ding Chen]'s Articles
[&#]'s Articles
Baidu academic
Similar articles in Baidu academic
[Yuan Liang]'s Articles
[Ding Chen]'s Articles
[&#]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Yuan Liang]'s Articles
[Ding Chen]'s Articles
[&#]'s Articles
Terms of Use
No data!
Social Bookmark/Share
All comments (0)
No comment.
 

Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.