.png){kind=icon}
返回
Work efficient parallel algorithms for large graph exploration on emerging heterogeneous architectures
.png){kind=icon}
PRE
AI
DOI：10.1016/j.jpdc.2014.11.006.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
Graph algorithms play a prominent role in several fields of sciences and engineering. Notable among them are graph traversal, finding the connected components of a graph, and computing shortest paths. There are several efficient implementations of the above problems on a variety of modern multiprocessor architectures. It can be noticed in recent times that the size of the graphs that correspond to real world datasets has been increasing. Parallelism offers only a limited succor to this situation as current parallel architectures have severe short-comings when deployed for most graph algorithms. At the same time, these graphs are also getting very sparse in nature. This calls for particular solution strategies aimed at processing large, sparse graphs on modern parallel architectures. In this paper, we introduce graph pruning as a technique that aims to reduce the size of the graph. Certain elements of the graph can be pruned depending on the nature of the computation. Once a solution is obtained on the pruned graph, the solution is extended to the entire graph. Towards, this end we investigate pruning based on two strategies that justifies their use in current real world graphs. We apply the above technique on three fundamental graph algorithms: breadth first search (BFS), Connected Components (CC), and All Pairs Shortest Paths (APSP). For experimentations, we use three different sources for real world graphs. To validate our technique, we implement our algorithms on a heterogeneous platform consisting of a multicore CPU and a GPU. On this platform, we achieve an average of 35% improvement compared to state-of-the-art solutions. Such an improvement has the potential to speed up other applications reliant on these algorithms. (C) 2014 Elsevier Inc. All rights reserved.
Keyword:
Graph algorithms
Irregular computations
Heterogeneous computing
Input pruning
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
4
论文数:
3.8K
被引数:
4.8K
机构
引用论文
Sex, life, death, geography: fragmentary remarks inspired by ‘Foucault's population geographies’
.png){kind=icon}
PREAI
分享收藏
Anisotropic Etching of Crystalline Silicon in Alkaline Solutions: I . Orientation Dependence and Behavior of Passivation Layers晶体硅在碱性溶液中的各向异性蚀刻: I.钝化层的取向依赖性和行为
PREAI
分享收藏The oxidation of ethane in the presence and absence of tetrachloromethane on calcium hydroxyapatites with incorporated lead在含铅的羟基磷灰石钙上存在和不存在四氯甲烷的情况下乙烷的氧化
PREAI
分享收藏
查看更多内容