SoCo: Graph Storage and Software Prefetch Co-Design for Dynamic Graph Processing
There has been growing demands in the dynamic graph, in which a continuous stream of graph updates is mixed with graph computation. For the above scenarios, the compact physically continuous structures and the dispersed but logically continuous structures become the two ends of the scale. In princip...
Main Author: | |
---|---|
Format: | Text |
Language: | unknown |
Published: |
2023
|
Subjects: | |
Online Access: | http://arxiv.org/abs/2312.14396 |
id |
ftarxivpreprints:oai:arXiv.org:2312.14396 |
---|---|
record_format |
openpolar |
spelling |
ftarxivpreprints:oai:arXiv.org:2312.14396 2024-01-28T10:09:32+01:00 SoCo: Graph Storage and Software Prefetch Co-Design for Dynamic Graph Processing Li, Hongfu 2023-12-21 http://arxiv.org/abs/2312.14396 unknown http://arxiv.org/abs/2312.14396 Computer Science - Databases text 2023 ftarxivpreprints 2023-12-31T02:10:31Z There has been growing demands in the dynamic graph, in which a continuous stream of graph updates is mixed with graph computation. For the above scenarios, the compact physically continuous structures and the dispersed but logically continuous structures become the two ends of the scale. In principle, the Pointers become the weights. The number of them determines which side of the scale the data structure leans towards. The Pointers make it easier to update the graph but they will result in poor cache locality. This paper presents SoCo, a graph storage and software prefetch co-design for dynamic graph processing that significantly improves on both graph updating and graph computation. We utilize C++20 coroutines and software prefetching techniques to optimize cache miss overhead during computation, and design a data structure that not only meets the requirements of dynamic graph processing but is also more suitable for prefetching. We also conduct extensive experiments on different datasets and show that SoCo could outperform state-of-the-arts by 10.48x on average and at the same time guarantee a pioneer insertion performance (1st place in 5 cases and 2nd place in 2 cases). Text The Pointers ArXiv.org (Cornell University Library) |
institution |
Open Polar |
collection |
ArXiv.org (Cornell University Library) |
op_collection_id |
ftarxivpreprints |
language |
unknown |
topic |
Computer Science - Databases |
spellingShingle |
Computer Science - Databases Li, Hongfu SoCo: Graph Storage and Software Prefetch Co-Design for Dynamic Graph Processing |
topic_facet |
Computer Science - Databases |
description |
There has been growing demands in the dynamic graph, in which a continuous stream of graph updates is mixed with graph computation. For the above scenarios, the compact physically continuous structures and the dispersed but logically continuous structures become the two ends of the scale. In principle, the Pointers become the weights. The number of them determines which side of the scale the data structure leans towards. The Pointers make it easier to update the graph but they will result in poor cache locality. This paper presents SoCo, a graph storage and software prefetch co-design for dynamic graph processing that significantly improves on both graph updating and graph computation. We utilize C++20 coroutines and software prefetching techniques to optimize cache miss overhead during computation, and design a data structure that not only meets the requirements of dynamic graph processing but is also more suitable for prefetching. We also conduct extensive experiments on different datasets and show that SoCo could outperform state-of-the-arts by 10.48x on average and at the same time guarantee a pioneer insertion performance (1st place in 5 cases and 2nd place in 2 cases). |
format |
Text |
author |
Li, Hongfu |
author_facet |
Li, Hongfu |
author_sort |
Li, Hongfu |
title |
SoCo: Graph Storage and Software Prefetch Co-Design for Dynamic Graph Processing |
title_short |
SoCo: Graph Storage and Software Prefetch Co-Design for Dynamic Graph Processing |
title_full |
SoCo: Graph Storage and Software Prefetch Co-Design for Dynamic Graph Processing |
title_fullStr |
SoCo: Graph Storage and Software Prefetch Co-Design for Dynamic Graph Processing |
title_full_unstemmed |
SoCo: Graph Storage and Software Prefetch Co-Design for Dynamic Graph Processing |
title_sort |
soco: graph storage and software prefetch co-design for dynamic graph processing |
publishDate |
2023 |
url |
http://arxiv.org/abs/2312.14396 |
genre |
The Pointers |
genre_facet |
The Pointers |
op_relation |
http://arxiv.org/abs/2312.14396 |
_version_ |
1789339537475895296 |