Exploiting reuse for GPU subgraph enumeration (extended abstract)
Subgraph enumeration is important for many applications such as network motif discovery, community detection, and frequent subgraph mining. To accelerate the execution, recent works utilize graphics processing units (GPUs) to parallelize subgraph enumeration. The performances of these parallel schem...
Saved in:
Main Authors: | , , |
---|---|
Format: | text |
Language: | English |
Published: |
Institutional Knowledge at Singapore Management University
2023
|
Subjects: | |
Online Access: | https://ink.library.smu.edu.sg/sis_research/8500 |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Institution: | Singapore Management University |
Language: | English |
id |
sg-smu-ink.sis_research-9503 |
---|---|
record_format |
dspace |
spelling |
sg-smu-ink.sis_research-95032024-01-04T04:18:03Z Exploiting reuse for GPU subgraph enumeration (extended abstract) GUO, Wentiao LI, Yuchen TAN, Kian-Lee Subgraph enumeration is important for many applications such as network motif discovery, community detection, and frequent subgraph mining. To accelerate the execution, recent works utilize graphics processing units (GPUs) to parallelize subgraph enumeration. The performances of these parallel schemes are dominated by the set intersection operations which account for up to 95% of the total processing time. (Un)surprisingly, a significant portion (as high as 99%) of these operations is actually redundant, i.e., the same set of vertices is repeatedly encountered and evaluated. Therefore, in this paper, we seek to salvage and recycle the results of such operations to avoid repeated computation. Our solution consists of two phases. In the first phase, we generate a reusable plan that determines the opportunity for reuse. The plan is based on a novel reuse discovery mechanism that can identify available results to prevent redundant computation. In the second phase, the plan is executed to produce the subgraph enumeration results. This processing is based on a newly designed reusable parallel search strategy that can efficiently maintain and retrieve the results of set intersection operations. Our implementation on GPUs shows that our approach can achieve up to 5 times speedups compared with the state-of-the-art GPU solutions. 2023-04-07T07:00:00Z text https://ink.library.smu.edu.sg/sis_research/8500 info:doi/10.1109/ICDE55515.2023.00309 Research Collection School Of Computing and Information Systems eng Institutional Knowledge at Singapore Management University Graphics processing units Search problems Data engineering Recycling Databases and Information Systems Graphics and Human Computer Interfaces |
institution |
Singapore Management University |
building |
SMU Libraries |
continent |
Asia |
country |
Singapore Singapore |
content_provider |
SMU Libraries |
collection |
InK@SMU |
language |
English |
topic |
Graphics processing units Search problems Data engineering Recycling Databases and Information Systems Graphics and Human Computer Interfaces |
spellingShingle |
Graphics processing units Search problems Data engineering Recycling Databases and Information Systems Graphics and Human Computer Interfaces GUO, Wentiao LI, Yuchen TAN, Kian-Lee Exploiting reuse for GPU subgraph enumeration (extended abstract) |
description |
Subgraph enumeration is important for many applications such as network motif discovery, community detection, and frequent subgraph mining. To accelerate the execution, recent works utilize graphics processing units (GPUs) to parallelize subgraph enumeration. The performances of these parallel schemes are dominated by the set intersection operations which account for up to 95% of the total processing time. (Un)surprisingly, a significant portion (as high as 99%) of these operations is actually redundant, i.e., the same set of vertices is repeatedly encountered and evaluated. Therefore, in this paper, we seek to salvage and recycle the results of such operations to avoid repeated computation. Our solution consists of two phases. In the first phase, we generate a reusable plan that determines the opportunity for reuse. The plan is based on a novel reuse discovery mechanism that can identify available results to prevent redundant computation. In the second phase, the plan is executed to produce the subgraph enumeration results. This processing is based on a newly designed reusable parallel search strategy that can efficiently maintain and retrieve the results of set intersection operations. Our implementation on GPUs shows that our approach can achieve up to 5 times speedups compared with the state-of-the-art GPU solutions. |
format |
text |
author |
GUO, Wentiao LI, Yuchen TAN, Kian-Lee |
author_facet |
GUO, Wentiao LI, Yuchen TAN, Kian-Lee |
author_sort |
GUO, Wentiao |
title |
Exploiting reuse for GPU subgraph enumeration (extended abstract) |
title_short |
Exploiting reuse for GPU subgraph enumeration (extended abstract) |
title_full |
Exploiting reuse for GPU subgraph enumeration (extended abstract) |
title_fullStr |
Exploiting reuse for GPU subgraph enumeration (extended abstract) |
title_full_unstemmed |
Exploiting reuse for GPU subgraph enumeration (extended abstract) |
title_sort |
exploiting reuse for gpu subgraph enumeration (extended abstract) |
publisher |
Institutional Knowledge at Singapore Management University |
publishDate |
2023 |
url |
https://ink.library.smu.edu.sg/sis_research/8500 |
_version_ |
1787590781179002880 |