2

PS：我已经提到了我的问题的可能解决方案，但对它们有很多困惑，请给我一些建议。另外，如果这个问题不适合这个网站，请指点我到正确的网站，我会把问题移到那里。提前致谢。

对于一些研究工作，我需要执行一些重复的图论和复杂的网络算法来分析大约 2000 个无自环的无向简单图。每个图有大约 40,000 个节点和大约 600,000 条边（基本上使它们成为稀疏图）。

目前，我正在使用 NetworkX 进行分析，目前正在运行nx.algorithms.cluster.average_clustering(G)500nx.average_shortest_path_length(G)个这样的图表，代码运行了 3 天，并且只运行了一半。这让我担心我的全面分析会花费大量的出乎意料的时间。

在详细说明我的问题和我想到的可能的解决方案之前，让我提一下我的计算机配置，因为它可能会帮助您建议最佳方法。我在配备 32GB RAM 和一个 Zotac GeForce GTX 1050 Ti OC 版 ZT-P10510B-10L 4GB PCI Express 显卡的 Intel i7-9700K 处理器上运行 Windows 10。

解释我可能的解决方案以及我对它们的困惑：

A) 使用带有邻接矩阵的 GPU 作为图形数据结构：我可以在 GPU 上放置一个邻接矩阵，并通过使用循环手动使用PyCuda或Numba对它们进行编码来执行我的分析，因为递归无法由 GPU 处理。我能够搜索的最近的是stackoverflow上的this，但它没有很好的解决方案。

我的期望：我希望加速算法，例如所有对最短路径、两个节点之间的所有可能路径、平均聚类、平均最短路径长度和小世界属性等。如果它对每个图有显着的加速，我的结果可以是达到非常快。

我的困惑：

  1. 这些图算法可以在 GPU 中高效编码吗？
  2. 哪个会更好用？PyCuda 还是 Numba？
  3. 有没有其他方法可以在 GPU 上存储图，因为我的图是稀疏图，所以效率更高。
  4. 我是一名普通的 Python 程序员，没有 GPU 编程经验，所以我必须了解和学习使用 PyCuda/Numba 进行 GPU 编程。哪个更容易学？

B) 在 CPU 本身上并行化程序：我可以使用 Joblib 或任何其他库在我的 CPU 本身上并行运行程序。我可以再安排 2-3 台计算机，我可以在这些计算机上运行独立的小程序部分，或者每台计算机可以运行 500 个图形。

我的期望：我希望通过在计算机之间并行化和划分任务来加速算法。如果GPU解决方案不起作用，我可能通过这种方法仍然有一些希望。

我的困惑：

  1. 哪些其他库可作为 Joblib 的良好替代品？
  2. 我应该为我的程序分配所有 CPU 内核（i7 中的 8 个内核）还是使用更少的内核？

C）除了我可能的解决方案之外，您对我还有其他建议吗？如果除了 C/C++ 之外的任何其他语言都有更好更快的解决方案，您也可以建议它们，因为如果没有任何效果，我已经考虑将 C++ 作为后备计划。

正在进行的更新

  1. 在我社区中对此问题的评论和讨论的不同建议中，这些是我建议探索的要点。

    • GraphBLAS
    • boost.graph + 带有 python-wrappers 的扩展
    • 图形工具
    • 火花/黄昏
    • PyCuda/Numba
    • 使用 Pytorch 的线性代数方法

  2. 我尝试n_job=-1使用 Joblib 在我的 CPU 上运行 100 个图表（使用 ），CPU 持续达到 100°C 的温度。处理器运行 3 小时后跳闸。- 作为一种解决方案，我在多台计算机上使用了 75% 的可用内核（因此，如果可用内核为 8，我使用 6 个内核）并且程序运行良好。加速也不错。

4

1 回答 1

3

这是一个广泛但有趣的问题。让我试着回答一下。

2000 个无向简单图 [...] 每个图有大约 40,000 个节点和大约 600,000 条边

目前，我正在使用 NetworkX 进行分析，目前正在运行nx.algorithms.cluster.average_clustering(G)和nx.average_shortest_path_length(G)

NetworkX 使用纯 Python 实现，并未针对性能进行优化。它非常适合原型设计，但如果您遇到性能问题，最好使用另一个库重写您的代码。

除了 NetworkX，两个最流行的图形处理库是igraph和SNAP。两者都是用 C 编写并具有 Python API，因此您可以获得良好的单线程性能和易用性。它们的并行性非常有限，但这在您的用例中不是问题，因为您有很多图表，使您的问题令人尴尬地并行。因此，正如您在更新的问题中所说，您可以使用例如Joblib或什至并行运行 6-8 个作业xargs。如果您需要并行处理，请查看graph-tool，它也有一个 Python API。

关于您的 NetworkX 算法，我希望average_shortest_path_length在所有库中都得到合理的优化。该average_clustering算法很棘手，因为它依赖于节点三角形计数，并且一个简单的实现需要O(|E|^2)时间，而优化的实现将在O(|E|^1.5). 您的图表足够大，因此这两个成本之间的差异是在几秒钟内在图表上运行算法而不是在几个小时内运行算法。

“所有对最短路径”（ APSP）问题非常耗时，大多数库使用运行时间为O(|V|^3). 我不确定您正在使用“两个节点之间的所有可能路径”算法寻找什么输出 - 枚举所有路径会导致结果呈指数级增长，并且在这种规模下是不可行的。

我不会开始使用 GPU 来完成这项任务：Intel i7-9700K 应该可以胜任这项工作。基于 GPU 的图形处理库的设置具有挑战性，并且目前无法提供那么显着的加速 - 使用 GPU 代替 CPU 所获得的收益对于图形处理而言远没有机器学习算法那么显着。唯一可能获得大幅加速的问题是APSP，但这取决于您选择的库使用的算法。

如果您对基于 GPU 的库感兴趣，那么在该主题上有一些很有前途的方向，例如Gunrock、GraphBLAST和一个支持 CUDA 的正在开发中的 SuiteSparse:GraphBLAS 扩展。但是，我的估计是，您应该能够使用单台计算机及其 CPU 在几个小时内运行大部分算法（APSP 除外）。

于 2021-02-10T19:27:12.403 回答