Despite the high off-chip bandwidth and on-chip parallelism offered by today's near-memory accelerators, software-based (CPU and GPU) graph processing frameworks still suffer performance degradation from under-utilization of available memory bandwidth because graph traversal often exhibits poor locality. Emerging FPGAbased graph accelerators tackle this challenge by designing specialized graph processing pipelines and application-specific memory subsystems to maximize bandwidth utilization and efficiently utilize high-speed on-chip memory. To use the limited on-chip (BRAM) memory effectively while handling larger graph sizes, several FPGAbased solutions resort to some form of graph slicing or partitioning during preprocessing to stage vertex property data into the BRAM. While this has demonstrated performance superiority for small graphs, this approach breaks down with larger graph sizes. For example, GraphLily [19], a recent high-performance FPGA-based graph accelerator, experiences up to 11X performance degradation between graphs having 3M vertices and 28M vertices. This makes prior FPGA approaches impractical for large graphs.

Interest in high performance analytics for dynamic (constantly evolving) graphs has been on the rise in the last decade, especially due to the prevalence and rapid growth of social networks today. The current state-of-the art data structures for dynamic graph processing rely on the adjacency list model of edge blocks in updating graphs. This model suffers from long probe distances when following edges, leading to poor update throughputs. Furthermore, both current graph processing models-the static model that requires reprocessing the entire graph after every batch update, and the incremental model in which only the affected subset of edges need to be processed-suffer drawbacks. In this paper, we present GraphTinker, a new, more scalable graph data structure for dynamic graphs. It uses a new hashing scheme to reduce probe distance and improve edge-update performance. It also better compacts edge data. These innovations improve performance for graph updates as well as graph analytics. In addition, we present a hybrid engine which improves the performance of dynamic graph processing by automatically selecting the most optimal execution model (static vs. incremental) for every iteration, surpassing the performance of both. Our evaluations of GraphTinker shows a throughput improvement of up to 3.3X compared to the stateof-the-art data structure (STINGER) when used for graph updates. GraphTinker also demonstrates a performance improvement of up to 10X over STINGER when used to run graph analytics algorithms. In addition, our hybrid engine demonstrates up to 2X improvement over the incremental compute model and up to 3X improvement over the static model.