There has been significant recent interest in parallel graph processing due
to the need to quickly analyze the large graphs available today. Many graph
codes have been designed for distributed memory or external memory. However,
today even the largest publicly-available real-world graph (the Hyperlink Web
graph with over 3.5 billion vertices and 128 billion edges) can fit in the
memory of a single commodity multicore server. Nevertheless, most experimental
work in the literature report results on much smaller graphs, and the ones for
the Hyperlink graph use distributed or external memory. Therefore, it is
natural to ask whether we can efficiently solve a broad class of graph problems
on this graph in memory.
This paper shows that theoretically-efficient parallel graph algorithms can
scale to the largest publicly-available graphs using a single machine with a
terabyte of RAM, processing them in minutes. We give implementations of
theoretically-efficient parallel algorithms for 20 important graph problems. We
also present the optimizations and techniques that we used in our
implementations, which were crucial in enabling us to process these large
graphs quickly. We show that the running times of our implementations
outperform existing state-of-the-art implementations on the largest real-world
graphs. For many of the problems that we consider, this is the first time they
have been solved on graphs at this scale. We have made the implementations
developed in this work publicly-available as the Graph-Based Benchmark Suite
(GBBS).

本研究使用理论高效的并行图算法和优化技术，结合大规模图分析，能够使单机具有 1TB 内存的计算机在几分钟内处理超过 35 亿个节点和 1280 亿条边的实际网络图像。同时，研究组将开发的这些算法公开提供给社区，以用作图算法效果评价指标的基准。

理论上高效的并行图算法可以快速且可扩展

Theoretically Efficient Parallel Graph Algorithms Can Be Fast and  Scalable

Deep neural networks (DNNs) require very large amounts of computation both
for training and for inference when deployed in the field. A common approach to
implementing DNNs is to recast the most computationally expensive operations as
general matrix multiplication (GEMM). However, as we demonstrate in this paper,
there are a great many different ways to express DNN convolution operations
using GEMM. Although different approaches all perform the same number of
operations, the size of temporary data structures differs significantly.
Convolution of an input matrix with dimensions $C \times H \times W$, requires
$O(K^2CHW)$ additional space using the classical im2col approach. More recently
memory-efficient approaches requiring just $O(KCHW)$ auxiliary space have been
proposed.
We present two novel GEMM-based algorithms that require just $O(MHW)$ and
$O(KW)$ additional space respectively, where $M$ is the number of channels in
the result of the convolution. These algorithms dramatically reduce the space
overhead of DNN convolution, making it much more suitable for memory-limited
embedded systems. Experimental evaluation shows that our low-memory algorithms
are just as fast as the best patch-building approaches despite requiring just a
fraction of the amount of additional memory. Our low-memory algorithms have
excellent data locality which gives them a further edge over patch-building
algorithms when multiple cores are used. As a result, our low memory algorithms
often outperform the best patch-building algorithms using multiple threads.

本文提出两种新型基于 GEMM 的算法，分别只需要额外的 O (MHW) 和 O (KW) 的空间，显著降低了 DNN 卷积的空间开销，适用于内存受限的嵌入式系统，并且实验表明我们的低内存算法和最好的图案构建方法一样快，尽管需要的额外内存只相当于后者的一小部分。