Self-adaptive graph traversal on GPUs
GPU’s massive computing power offers unprecedented opportunities to enable large graph analysis. Existing studies proposed various preprocessing approaches that convert the input graphs into dedicated structures for GPU-based optimizations. However, these dedicated approaches incur significant prepr...
Saved in:
Main Authors: | , , |
---|---|
Format: | text |
Language: | English |
Published: |
Institutional Knowledge at Singapore Management University
2021
|
Subjects: | |
Online Access: | https://ink.library.smu.edu.sg/sis_research/6201 https://ink.library.smu.edu.sg/context/sis_research/article/7204/viewcontent/3448016.3457279.pdf |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Institution: | Singapore Management University |
Language: | English |
id |
sg-smu-ink.sis_research-7204 |
---|---|
record_format |
dspace |
spelling |
sg-smu-ink.sis_research-72042021-10-14T07:00:24Z Self-adaptive graph traversal on GPUs SHA, Mo LI, Yuchen TAN, Kian-Lee GPU’s massive computing power offers unprecedented opportunities to enable large graph analysis. Existing studies proposed various preprocessing approaches that convert the input graphs into dedicated structures for GPU-based optimizations. However, these dedicated approaches incur significant preprocessing costs as well as weak programmability to build general graph applications. In this paper, we introduce SAGE, a self-adaptive graph traversal on GPUs, which is free from preprocessing and operates on ubiquitous graph representations directly. We propose Tiled Partitioning and Resident Tile Stealing to fully exploit the computing power of GPUs in a runtime and self-adaptive manner. We also propose Sampling-based Reordering to further optimize the memory efficiency of SAGE through a lightweight and effective node reordering technique on the fly. Extensive experiments demonstrate that SAGE can achieve superior graph traversal performance over existing approaches under different architectural scenarios, i.e., singleGPU, out-of-core, and multi-GPU. 2021-06-01T07:00:00Z text application/pdf https://ink.library.smu.edu.sg/sis_research/6201 info:doi/10.1145/3448016.3457279 https://ink.library.smu.edu.sg/context/sis_research/article/7204/viewcontent/3448016.3457279.pdf http://creativecommons.org/licenses/by-nc-nd/4.0/ Research Collection School Of Computing and Information Systems eng Institutional Knowledge at Singapore Management University Graph Processing GPGPU Parallel Task Scheduling Databases and Information Systems Theory and Algorithms |
institution |
Singapore Management University |
building |
SMU Libraries |
continent |
Asia |
country |
Singapore Singapore |
content_provider |
SMU Libraries |
collection |
InK@SMU |
language |
English |
topic |
Graph Processing GPGPU Parallel Task Scheduling Databases and Information Systems Theory and Algorithms |
spellingShingle |
Graph Processing GPGPU Parallel Task Scheduling Databases and Information Systems Theory and Algorithms SHA, Mo LI, Yuchen TAN, Kian-Lee Self-adaptive graph traversal on GPUs |
description |
GPU’s massive computing power offers unprecedented opportunities to enable large graph analysis. Existing studies proposed various preprocessing approaches that convert the input graphs into dedicated structures for GPU-based optimizations. However, these dedicated approaches incur significant preprocessing costs as well as weak programmability to build general graph applications. In this paper, we introduce SAGE, a self-adaptive graph traversal on GPUs, which is free from preprocessing and operates on ubiquitous graph representations directly. We propose Tiled Partitioning and Resident Tile Stealing to fully exploit the computing power of GPUs in a runtime and self-adaptive manner. We also propose Sampling-based Reordering to further optimize the memory efficiency of SAGE through a lightweight and effective node reordering technique on the fly. Extensive experiments demonstrate that SAGE can achieve superior graph traversal performance over existing approaches under different architectural scenarios, i.e., singleGPU, out-of-core, and multi-GPU. |
format |
text |
author |
SHA, Mo LI, Yuchen TAN, Kian-Lee |
author_facet |
SHA, Mo LI, Yuchen TAN, Kian-Lee |
author_sort |
SHA, Mo |
title |
Self-adaptive graph traversal on GPUs |
title_short |
Self-adaptive graph traversal on GPUs |
title_full |
Self-adaptive graph traversal on GPUs |
title_fullStr |
Self-adaptive graph traversal on GPUs |
title_full_unstemmed |
Self-adaptive graph traversal on GPUs |
title_sort |
self-adaptive graph traversal on gpus |
publisher |
Institutional Knowledge at Singapore Management University |
publishDate |
2021 |
url |
https://ink.library.smu.edu.sg/sis_research/6201 https://ink.library.smu.edu.sg/context/sis_research/article/7204/viewcontent/3448016.3457279.pdf |
_version_ |
1770575890223202304 |