TDGraph

• DOI: 10.1145/3470496.3527409
• Publication Date: 2022-05-31T19:06:01Z
• Authors: Jin Zhao; Yun Yang; Yu Zhang; Xiaofei Liao; Lin Gu; Ligang He; Bingsheng He; Hai Jin; Haikun Liu; Xinyu Jiang; Hui Yu
• Keywords: Instruction prefetch; Speedup

Many solutions have been recently proposed to support the processing of streaming graphs. However, for each graph snapshot a graph, new states vertices affected by updates are propagated irregularly along topology. Despite years' research efforts, existing approaches still suffer from serious problems redundant computation overhead and irregular memory access, which severely underutilizes many-core processor. To address these issues, this paper proposes topology-driven programmable accelerator TDGraph, is first augment processors achieve high performance Specifically, we propose an efficient incremental execution approach into design more regular state propagation better data locality. TDGraph takes as roots prefetch other topology synchronizes computations them on fly. In way, most propagations originated multiple different can be conducted together topology, help reduce access cost. Besides, through coalescing accesses vertex states, further improves utilization cache bandwidth. We evaluated simulated 64-core The results show that, state-of-the-art software system achieves speedup 7.1~21.4 times after integrating with while incurring only 0.73% area Compared four cutting-edge accelerators, i.e., HATS, Minnow, PHI, DepGraph, gains speedups 4.6~12.7, 3.2~8.6, 3.8~9.7, 2.3~6.1 times, respectively.