DBR: A Depth-Branch-Resorting Algorithm for Locality Exploration in Graph Processing
Lin Jiang, Ru Feng, Junjie Wang, Junyong Deng · 2022 Asia-Pacific Signal and Information Processing Association Annual Summit and Conference (APSIPA ASC) · 2022
Unstructured and irregular graph data causes strong randomness and poor locality of data access in graph processing. In order to alleviate this problem, this paper proposes a Depth-Branch-Resorting (DBR) Algorithm for locality exploration in graph processing, and the corresponding graph data compression format DBR_DCSR. The DBR algorithm and DBR_DCSR format are tested and verified on the framework GraphBIG. The results show that in terms of execution time, the DBR algorithm and DBR_DCSR format reduce GraphBIG execution time by 55.6% compared with the original GraphBIG framework, and 71.7%, 11.46% less than the frameworks of Ligra, Gemini respectively. While compared with the original GraphBIG framework, the optimized GraphBIG framework in DBR_DCSR format has a maximum reduction of 87.9%in data movement and 52.3% in data computation. Compared to the Ligra, Genimi, the amount of data movement are reduced by 33.5% and 49.7%, the amount of data calculation reduced by 54.3% and 43.9% respectively.