Dynamic graph management (DGM) systems are designed to effectively handle changing graph data, which is a fundamental problem for many graph-based applications. Recently, researchers have designed GPU-based solutions for DGM and its downstream applications, thanks to GPUs' massive parallelism power. However, there is a lack of universal models that summarize the features and design principles of GPU-accelerated DGM systems. Additionally, existing studies test GPU-based DGM systems without unified metrics and workloads. Under this circumstance, we propose a conceptual model for GPU-accelerated DGM to demonstrate a DGM system's components, key primitives, and optimization choices. Next, we evaluate six representative systems, testing their update and query performance with unified metrics and workloads of different algorithmic behaviors. We also extend existing systems to seek insight to fill the current research gap in multi-GPU support, concurrency control, resource utilization, and so on. Our evaluation yielded new insights on the pros and cons of different systems: (1) Hashing-based systems perform best for graph updates but may not be suitable for all applications. (2) Finding a system that fits all workloads is challenging, and hybrid data storage may be a solution. (3) To select the most suitable DGM system for a specific workload, it is essential to consider hardware-related metrics. Finally, we provide recommendations and suggestions for future studies based on our experimental results and observations.

Subgraph isomorphism plays a significant role in many applications, such as social networks and bioinformatics. However, due to the inherent NP-hardness, it becomes challenging to compute matches efficiently in large real-world graphs. Many researchers have attempted to solve this problem with the help of new hardware. Nevertheless, most of them focus on GPU. Due to the dataflow feature and burst I/O optimization, FPGA is a potential competitor to speed up subgraph isomorphism. However, there are very few subgraph matching algorithms on FPGA. In this paper, we present an efficient FPGA-friendly Subgraph Isomorphism algorithm FASI, designed on CPU- FPGA heterogeneous platform which leverages FPGA's features. Unlike the existing FPGA-based method FAST, we adopt the worst-case-optimal-join-based pipeline design. First, we propose an FPGA-friendly data structure LPCSR for efficient access to neighbor lists. Second, we offer a joint parallelized pipeline strategy to accelerate matching process. Third, we propose a memory coalescing mechanism and a space-saving pre-allocated write back strategy. Our experiments on both synthetic and real graphs show that FASI outperforms other state-of-the-art subgraph matching algorithms on CPU, GPU and FPGA.

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 the 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 a state-of-art dynamic PMA-based structure that uses PMA structure and segment-oriented parallel update procedure to address the dynamic weakness of CSR, but it still has a bottleneck on the array expansion. In this paper, we propose an leveled structure (called LPMA) instead of continue array to retain low time complexity and high parallel update and lift the expansion bottleneck of GPMA+. More specifically, we propose a series of optimization techniques, including bottom-up update, top-down update and on-demand hybrid update strategies as well as consistence-guaranteed parallel processing for update-query mixed workloads. We theoretically analyze the benefits of LPMA compared in terms of re-balance cost during updates. Extensive experiments on four large real-life graphs prove the superiority of LPMA compared with the-state-of-arts.