Institutional Repository
| modeling the locality in graph traversals | |
| Yuan Liang; Ding Chen; &#; tefankovic Daniel; Zhang Yunquan | |
| 2012 | |
| Conference Name | 41st International Conference on Parallel Processing, ICPP 2012 |
| Source | Proceedings of the International Conference on Parallel Processing |
| Pages | 138-147 |
| Conference Date | September 10, 2012 - September 13, 2012 |
| Conference Place | Pittsburgh, PA, United states |
| Indexed Type | EI |
| ISSN | 0190-3918 |
| ISBN | 9780769547961 |
| 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 Abstract | 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. |
| Sponsorship | Int. Assoc. Comput. Commun. (IACC) |
| Language | 英语 |
| Content Type | 会议论文 |
| URI | http://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. | |||||
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment