Salvato in:
| Autori principali: | , , , , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2312.14396 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912316817145856 |
|---|---|
| author | Li, Hongfu Tao, Qian Yu, Song Gong, Shufeng Zhang, Yanfeng Yao, Feng Yu, Wenyuan Yu, Ge Zhou, Jingren |
| author_facet | Li, Hongfu Tao, Qian Yu, Song Gong, Shufeng Zhang, Yanfeng Yao, Feng Yu, Wenyuan Yu, Ge Zhou, Jingren |
| contents | An efficient data structure is fundamental to meeting the growing demands in dynamic graph processing. However, the dual requirements for graph computation efficiency (with contiguous structures) and graph update efficiency (with linked list-like structures) present a conflict in the design principles of graph structures. After experimental studies of existing state-of-the-art dynamic graph structures, we observe that the overhead of cache misses accounts for a major portion of the graph computation time. This paper presents GastCoCo, a system with graph storage and coroutine-based prefetch co-design. By employing software prefetching via stackless coroutines and introducing a prefetch-friendly data structure CBList, GastCoCo significantly alleviates the performance degradation caused by cache misses. Our results show that GastCoCo outperforms state-of-the-art graph storage systems by 1.3x - 180x in graph updates and 1.4x - 41.1x in graph computation. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_14396 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | GastCoCo: Graph Storage and Coroutine-Based Prefetch Co-Design for Dynamic Graph Processing Li, Hongfu Tao, Qian Yu, Song Gong, Shufeng Zhang, Yanfeng Yao, Feng Yu, Wenyuan Yu, Ge Zhou, Jingren Databases An efficient data structure is fundamental to meeting the growing demands in dynamic graph processing. However, the dual requirements for graph computation efficiency (with contiguous structures) and graph update efficiency (with linked list-like structures) present a conflict in the design principles of graph structures. After experimental studies of existing state-of-the-art dynamic graph structures, we observe that the overhead of cache misses accounts for a major portion of the graph computation time. This paper presents GastCoCo, a system with graph storage and coroutine-based prefetch co-design. By employing software prefetching via stackless coroutines and introducing a prefetch-friendly data structure CBList, GastCoCo significantly alleviates the performance degradation caused by cache misses. Our results show that GastCoCo outperforms state-of-the-art graph storage systems by 1.3x - 180x in graph updates and 1.4x - 41.1x in graph computation. |
| title | GastCoCo: Graph Storage and Coroutine-Based Prefetch Co-Design for Dynamic Graph Processing |
| topic | Databases |
| url | https://arxiv.org/abs/2312.14396 |