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: | Article in Journal/Newspaper |
| Language: | unknown |
| Published: |
arXiv
2023
|
| Subjects: | |
| Online Access: | https://dx.doi.org/10.48550/arxiv.2312.14396 https://arxiv.org/abs/2312.14396 |
| Summary: | 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 ... |
|---|