An efficient hardware accelerator for monotonic graph algorithms on dynamic directed graphs
Article
Yang, Yun, Yu, Hui, Zhao, Jin, Zhang, Yu, Liao, Xiaofei, Jiang, Xinyu, Jin, Hai, Liu, Haikun, Mao, Fubing, Zhang, Ji and Wang, Biao. 2023. "An efficient hardware accelerator for monotonic graph algorithms on dynamic directed graphs." Scientia Sinica Informationis. 53 (8), pp. 1575-1592. https://doi.org/10.1360/SSI-2022-0191
Article Title | An efficient hardware accelerator for monotonic graph algorithms on dynamic directed graphs |
---|---|
Article Category | Article |
Authors | Yang, Yun, Yu, Hui, Zhao, Jin, Zhang, Yu, Liao, Xiaofei, Jiang, Xinyu, Jin, Hai, Liu, Haikun, Mao, Fubing, Zhang, Ji and Wang, Biao |
Journal Title | Scientia Sinica Informationis |
Journal Citation | 53 (8), pp. 1575-1592 |
Number of Pages | 18 |
Year | 2023 |
Publisher | Science China Press., Co. Ltd. |
Place of Publication | China |
ISSN | 1674-7267 |
2095-9486 | |
Digital Object Identifier (DOI) | https://doi.org/10.1360/SSI-2022-0191 |
Web Address (URL) | https://www.sciengine.com/SSI/doi/10.1360/SSI-2022-0191 |
Abstract | With the rapidly growing demand for dynamic graph processing in the real world, existing research has proposed various methods to efficiently support the processing of monotonic graph algorithms on dynamic directed graphs. Despite of many research efforts, for iterative analysis of evolving directed graphs, existing solutions suffer from slow convergence speed and high data access cost, because many vertices are ineffectively reprocessed for lots of rounds so as to update their states according to other active vertices regardless of their dependencies. In this paper, we propose a novel and efficient accelerator DSGraphfor incremental processing of dynamic directed graphs for monotonic graph algorithms. Compared with existing methods, the unique feature of DSGraph is that it can efficiently take advantage of the dependencies between the vertices to reduce the data access cost and improve the convergence speed of iterative processing of dynamic directed graphs. Specifically, DSGraph performs asynchronous iterative processing according to the topological dependency order of vertices on dynamic directed graphs at runtime, thus significantly reducing redundant vertex state updates. Meanwhile, DSGraph designs a multi-stage pipeline architecture. It performs asynchronous iterative processing of vertices according to the dependency order, which speeds up the vertex state propagation and reduces the data access overhead. Finally, DSGraph proposes a non-blocking data synchronization mechanism to reduce the system synchronization overhead by performing state updates of local vertices and data synchronization of external vertices in parallel. Experimental results show that DSGraph speeds up iterative dynamic graph processing by 11.2 times on average in comparison with the state-of-the-art software dynamic graph processing systems. |
Keywords | dependency-aware; monotonic graph algorithms |
ANZSRC Field of Research 2020 | 460299. Artificial intelligence not elsewhere classified |
Public Notes | Files associated with this item cannot be displayed due to copyright restrictions. |
Byline Affiliations | Huazhong University of Science and Technology, China |
School of Mathematics, Physics and Computing |
Permalink -
https://research.usq.edu.au/item/z2730/an-efficient-hardware-accelerator-for-monotonic-graph-algorithms-on-dynamic-directed-graphs
157
total views0
total downloads15
views this month0
downloads this month