  As large graph processing emerges, we observe a costly fork-processing
pattern (FPP) that is common in many graph algorithms. The unique feature of
the FPP is that it launches many independent queries from different source
vertices on the same graph. For example, an algorithm in analyzing the network
community profile can execute Personalized PageRanks that start from tens of
thousands of source vertices at the same time. We study the efficiency of
handling FPPs in state-of-the-art graph processing systems on multi-core
architectures. We find that those systems suffer from severe cache miss penalty
because of the irregular and uncoordinated memory accesses in processing FPPs.
  In this paper, we propose ForkGraph, a cache-efficient FPP processing system
on multi-core architectures. To improve the cache reuse, we divide the graph
into partitions each sized of LLC capacity, and the queries in an FPP are
buffered and executed on the partition basis. We further develop efficient
intra- and inter-partition execution strategies for efficiency. For
intra-partition processing, since the graph partition fits into LLC, we propose
to execute each graph query with efficient sequential algorithms (in contrast
with parallel algorithms in existing parallel graph processing systems) and
present an atomic-free query processing by consolidating contending operations
to cache-resident graph partition. For inter-partition processing, we propose
yielding and priority-based scheduling, to reduce redundant work in processing.
Besides, we theoretically prove that ForkGraph performs the same amount of
work, to within a constant factor, as the fastest known sequential algorithms
in FPP queries processing, which is work efficient. Our evaluations on
real-world graphs show that ForkGraph significantly outperforms
state-of-the-art graph processing systems with two orders of magnitude
speedups.
