LPMA - An Efficient Data Structure for Dynamic Graph on GPUs

There is a growing interest to offload dynamic graph computation to GPU and resort to its high parallel processing ability and larger memory bandwidths compared with CPUs. The existing GPU graph systems usually use compressed sparse row (CSR) as de-facto structure. However, CSR has a critical weakness for dynamic change due to the large overhead of re-balance process after update. GPMA+ is the state-of-art dynamic CSR-oriented structure that uses PMA structure and optimized segment-oriented parallel update procedure to address the dynamic weakness of CSR but still has a bottleneck on the array expansion. In this paper, we propose an optimized dynamic structure LPMA, which is a leveled structure instead of continues array to retain low time complexity and high parallel update and lift the expansion bottleneck of GPMA+. Theoretical analysis and extensive experiments on four real-life large graphs prove the superiority of LPMA.