A Topology-Aware Framework for Graph Traversals
| العنوان: | A Topology-Aware Framework for Graph Traversals |
|---|---|
| المؤلفون: | Huashan Yu, Jia Meng, Liang Cao |
| المصدر: | Algorithms and Architectures for Parallel Processing ISBN: 9783319654812 ICA3PP |
| بيانات النشر: | Springer International Publishing, 2017. |
| سنة النشر: | 2017 |
| مصطلحات موضوعية: | Speedup, Graph labeling, Computer science, Locality, Graph partition, 0102 computer and information sciences, 02 engineering and technology, Topology, 01 natural sciences, 010201 computation theory & mathematics, Work stealing, Graph traversal, Clique-width, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, Null graph, MathematicsofComputing_DISCRETEMATHEMATICS |
| الوصف: | Computation on a large-scale graph is to propagate and update the vertex values systematically. Efficient graph computing depends on techniques compatible with the algorithm’s value propagating pattern. Graph traversing is a value propagating pattern used by representative graph applications. This paper presents an efficient value propagating framework for large-scale graph traversing applications. By partitioning the input graph based on the topology, it allows values for different source vertices to be propagated together, so as to reduce value propagating overhead. A locality-based vertex partitioning strategy is proposed to improve locality on processors. To improve parallel efficiency of graph traversals, a novel task scheduling mechanism has been devised. The mechanism allows the framework to improve load balance without loss of locality. A prototype for the framework has been implemented. On four large real graphs and a synthetic graph, the work was evaluated with two typical graph applications. By comparing with the owner-computing rule, experimental results show that this work has an overall speedup from 1.28 to 2.67. The speedup to Ligra is more than 5 in most cases. |
| ردمك: | 978-3-319-65481-2 |
| URL الوصول: | https://explore.openaire.eu/search/publication?articleId=doi_________::bbe887f50c2523563191a1290eb797f4 https://doi.org/10.1007/978-3-319-65482-9_11 |
| حقوق: | CLOSED |
| رقم الأكسشن: | edsair.doi...........bbe887f50c2523563191a1290eb797f4 |
| قاعدة البيانات: | OpenAIRE |
| ردمك: | 9783319654812 |
|---|