Highlighted notes on:
GraSU: A Fast Graph Update Library for FPGA-based Dynamic Graph Processing.
While doing research work with Prof. Kishore Kothapalli.
In this paper researchers focus on optimizing graph update though a caching technique using on-chip UltraRAM of FPGA.
For dynamic graphs we can work on graph update, or graph algorithms. They work on graph update. They list geomean speedup.
For graph data structure they use Packed Memory Array (PMA) with CSR representation which supports fast edge addition and removal (I think they also mentioned use of fine-grained locking, instead of a per-vertex lock). A bitmap technique is used to avoid storing both UltraRAM and off-chip DRAM offsets. Algorithms to determine which vertex-edges to cache is run overalpped with graph algorithm (hidden overhead). It is based on "rich gets richer", that is high-degree vertices/recently updated vertices are most updated. Vertex data is stored in on-chip BRAM. Graph update is performed in batches. GraSU can be integrated with existing FPGA graph accelerators for static graphs.
Latest FPGA graph-accelerators for static graphs:
- AccuGraph, FabGraph, WaveScheduler, ForeGraph.
Latest CPU dynamic graphs systems:
- Stinger: CSR with block link list (slow traverse for high degree edges), per vertex lock
- Aspen: Based on purely functional search tree (typical cache policy not good enough)
Real-world dynamic graphs in <u, v, t> format:
- sx-askubuntu, sx-superuser, wiki-talk-temporal, sx-stackoverflow, soc-bitcoin.
How to allocate space for dynamic files? for dynamic vectors (in RAM)? For dynamic vertices? They seem very related, also to disk defragmentation.