  Efficient Graph processing is challenging because of the irregularity of
graph algorithms. Using GPUs to accelerate irregular graph algorithms is even
more difficult to be efficient, since GPU's highly structured SIMT architecture
is not a natural fit for irregular applications. With lots of previous efforts
spent on subtly mapping graph algorithms onto the GPU, the performance of graph
processing on GPUs is still highly memory-latency bound, leading to low
utilization of compute resources. Random memory accesses generated by the
sparse graph data structure are the major causes of this significant memory
access latency. Simply applying the conventional cache blocking technique
proposed for matrix computation have limited benefit due to the significant
overhead on the GPU. We propose GraphCage, a cache centric optimization
framework for highly efficient graph processing on GPUs. We first present a
throughput-oriented cache blocking scheme (TOCAB) in both push and pull
directions. Comparing with conventional cache blocking which suffers repeated
accesses when processing large graphs on GPUs, TOCAB is specifically optimized
for the GPU architecture to reduce this overhead and improve memory access
efficiency. To integrate our scheme into state-of-the-art implementations
without significant overhead, we coordinate TOCAB with load balancing
strategies by considering the sparsity of subgraphs. To enable cache blocking
for traversal-based algorithms, we consider the benefit and overhead in
different iterations with different working set sizes, and apply TOCAB for
topology-driven kernels in pull direction. Evaluation shows that GraphCage can
improve performance by 2 ~ 4x compared to hand optimized implementations and
state-of-the-art frameworks (e.g. CuSha and Gunrock), with less memory
consumption than CuSha.
