测量图分析性能

什么是图分析，为什么它很重要？

图是表示一组对象及其之间关系的好方法（图 1）。图分析是一套从实体之间的连接中提取信息的Techniques。

例如，图分析可用于

• 在社交网络中获得朋友之间的推荐
• 在通信网络或电网中找到关键点
• 确定药物对生化途径的影响
• 在电信网络中检测机器人电话
• 在地图上找到位置之间的最佳路线

图分析最近受到了很多关注，这可能与Gartner将其列为2019年十大数据和分析技术趋势之一有关。

“图处理和图数据库的应用将以每年100%的速度增长，直到2022年，以持续加速数据准备并实现更复杂、自适应的数据科学。”

（来源：Gartner 确定了2019年十大数据和分析技术趋势）

英特尔在图分析领域拥有悠久的领导历史。例如，英特尔共同撰写了GraphBLAS*规范，将图问题表述为稀疏线性代数。尽管GraphBLAS API于2017年才发布，但最初的提案和宣言是在10多年前发布的。如今，同样的行业和学术界合作伙伴正在共同撰写即将发布的LAGraph*规范，用于图算法库。英特尔还被DARPA选中开发一种新的处理器来处理大型图数据集（参见“DARPA 选择英特尔开发图分析芯片项目”）。我们将继续创新并推动图分析的前沿。

衡量图分析性能

图分析是一个广阔而多样的领域。即使是图 1中的简单示例也显示出不同的特征。例如，一些网络高度连接；另一些则较为稀疏。网页网络与Twitter用户网络的连通性不同，后者的一些用户拥有数百万粉丝，而大多数用户只有几个。因此，没有一种图算法、图拓扑或图大小的组合能够充分代表整个领域。

因此，我们使用加州大学伯克利分校的GAP Benchmark Suite*来衡量图分析性能。GAP指定了六种常用算法（表 1）和五个小型到中型图（表 2）。每种图都具有不同的特征，这很重要，因为对一种图拓扑有效的优化可能对其他图拓扑无效。例如，Road图相对较小，但其高直径可能会给某些算法带来问题。因此，30个GAP数据点提供了对图分析领域的良好覆盖。

GAP的优点还在于它是一个定义明确、客观、现成的基准测试。它不需要特殊的硬件或软件配置，因此易于运行。

以下是我运行基准测试的步骤

1. 下载GAP包。
2. 在gapbs-master子目录中运行“make”以构建六个图分析内核的参考实现。目前，我只使用默认的GAP构建参数（GNU C++编译器，带有-std=c++11 -O3 -Wall -fopenmp选项）。我的系统安装了GNU* v7.4.0编译器。
3. 在同一目录中，运行“make -f benchmark/bench.mk bench-graphs”以下载或生成五个基准图，并将它们转换为更有效的输入格式。
4. GAP的参考实现使用OpenMP*进行并行化，因此设置线程数很重要。否则，GAP将使用所有可用核心，即使这不会带来最佳的并行效率。例如，“export OMP_NUM_THREADS=32”命令将OpenMP线程数设置为32。
5. 最后，运行“make -f benchmark/bench.mk bench-run”来启动基准测试并生成结果（表 3）。

我试图生成NVIDIA V100*的比较数据，但遇到了一些技术障碍

1. GAP图中的只有一个（Road）适合单个V100的内存。
2. RAPIDS cuGraph*中的GAP算法只有一个（PR）可以使用多个V100的总内存。
3. cuGraph的当前版本不提供BC实现。
4. cuGraph的API和文档不公开某些实现细节或算法参数。例如，cuGraph中的多V100 PR实现不提供收敛容差参数，这使得与GAP结果进行逐项比较变得困难。

因此，只能运行30个GAP测试中的9个（表 4）。正如您所看到的，当GAP可以在两种架构上运行时，Intel® Xeon®处理器在大多数测试中都优于V100，即使图足够小以适合GPU内存（即Road），或者算法可以使用多个GPU（即PageRank）。此外，TCO显然有利于Intel Xeon处理器进行图分析（表 5）。

这些结果突出了一个基准测试套件的优势，该套件在不同的图拓扑上测试多种算法。例如，SSSP实现通常允许用户指定delta步进参数来提高高直径图的性能。cuGraph实现不提供此类选项，因此其内部默认值可能不是高直径图（如Road）的最佳选择。cuGraph CC实现也可能如此。

结论

通过一些简单的更改，我可能会在Intel Xeon处理器平台（表 3）上改进GAP结果，例如使用Intel编译器、激进的优化和向量化、调整OpenMP的OMP_PROC_BIND和OMP_PLACES环境变量、尝试numactl实用程序、调整页面大小等，但这并非此博客的重点。⁵我的目标是展示如何轻松获得*全面*、*客观*和*可重现*的图分析性能数据，而无需进行混淆或采用基准测试技巧。