ThunderRW: An in-memory graph random walk engine
As random walk is a powerful tool in many graph processing, mining and learning applications, this paper proposes an efficient inmemory random walk engine named ThunderRW. Compared with existing parallel systems on improving the performance of a single graph operation, ThunderRW supports massive par...
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/6132 https://ink.library.smu.edu.sg/context/sis_research/article/7135/viewcontent/2107.11983.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-7135 |
---|---|
record_format |
dspace |
spelling |
sg-smu-ink.sis_research-71352021-09-29T12:14:34Z ThunderRW: An in-memory graph random walk engine SUN, Shixuan CHEN, Yuhang LU, Shengliang HE, Bingsheng LI, Yuchen As random walk is a powerful tool in many graph processing, mining and learning applications, this paper proposes an efficient inmemory random walk engine named ThunderRW. Compared with existing parallel systems on improving the performance of a single graph operation, ThunderRW supports massive parallel random walks. The core design of ThunderRW is motivated by our profiling results: common RW algorithms have as high as 73.1% CPU pipeline slots stalled due to irregular memory access, which suffers significantly more memory stalls than the conventional graph workloads such as BFS and SSSP. To improve the memory efficiency, we first design a generic step-centric programming model named Gather-Move-Update to abstract different RW algorithms. Based on the programming model, we develop the step interleaving technique to hide memory access latency by switching the executions of different random walk queries. In our experiments, we use four representative RW algorithms including PPR, DeepWalk, Node2Vec and MetaPath to demonstrate the efficiency and programming flexibility of ThunderRW. Experimental results show that ThunderRW outperforms state-of-the-art approaches by an order of magnitude, and the step interleaving technique significantly reduces the CPU pipeline stall from 73.1% to 15.0%. 2021-08-01T07:00:00Z text application/pdf https://ink.library.smu.edu.sg/sis_research/6132 https://ink.library.smu.edu.sg/context/sis_research/article/7135/viewcontent/2107.11983.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 Databases and Information Systems Data Storage Systems |
institution |
Singapore Management University |
building |
SMU Libraries |
continent |
Asia |
country |
Singapore Singapore |
content_provider |
SMU Libraries |
collection |
InK@SMU |
language |
English |
topic |
Databases and Information Systems Data Storage Systems |
spellingShingle |
Databases and Information Systems Data Storage Systems SUN, Shixuan CHEN, Yuhang LU, Shengliang HE, Bingsheng LI, Yuchen ThunderRW: An in-memory graph random walk engine |
description |
As random walk is a powerful tool in many graph processing, mining and learning applications, this paper proposes an efficient inmemory random walk engine named ThunderRW. Compared with existing parallel systems on improving the performance of a single graph operation, ThunderRW supports massive parallel random walks. The core design of ThunderRW is motivated by our profiling results: common RW algorithms have as high as 73.1% CPU pipeline slots stalled due to irregular memory access, which suffers significantly more memory stalls than the conventional graph workloads such as BFS and SSSP. To improve the memory efficiency, we first design a generic step-centric programming model named Gather-Move-Update to abstract different RW algorithms. Based on the programming model, we develop the step interleaving technique to hide memory access latency by switching the executions of different random walk queries. In our experiments, we use four representative RW algorithms including PPR, DeepWalk, Node2Vec and MetaPath to demonstrate the efficiency and programming flexibility of ThunderRW. Experimental results show that ThunderRW outperforms state-of-the-art approaches by an order of magnitude, and the step interleaving technique significantly reduces the CPU pipeline stall from 73.1% to 15.0%. |
format |
text |
author |
SUN, Shixuan CHEN, Yuhang LU, Shengliang HE, Bingsheng LI, Yuchen |
author_facet |
SUN, Shixuan CHEN, Yuhang LU, Shengliang HE, Bingsheng LI, Yuchen |
author_sort |
SUN, Shixuan |
title |
ThunderRW: An in-memory graph random walk engine |
title_short |
ThunderRW: An in-memory graph random walk engine |
title_full |
ThunderRW: An in-memory graph random walk engine |
title_fullStr |
ThunderRW: An in-memory graph random walk engine |
title_full_unstemmed |
ThunderRW: An in-memory graph random walk engine |
title_sort |
thunderrw: an in-memory graph random walk engine |
publisher |
Institutional Knowledge at Singapore Management University |
publishDate |
2021 |
url |
https://ink.library.smu.edu.sg/sis_research/6132 https://ink.library.smu.edu.sg/context/sis_research/article/7135/viewcontent/2107.11983.pdf |
_version_ |
1770575834177863680 |