mpi 并行的快速图分区

Question

我是图划分的新手，但我想我问的问题应该已经有了很好的答案。我只想将一个巨大的网络（数十亿个节点）分成几个子图。所以在使用 MPI 时，每个子图由不同的处理器处理。我目前正在使用图形的邻接表表示。什么算法可以做到这一点？谢谢！

Answer 1

是的，您可以这样做，并且有多种开源工具可用。我最常使用的工具是parMETIS。

它是一个基于 MPI 的并行库，提供了包括图形划分在内的多种功能。您如何使用这个库完全取决于您的应用程序。通常，我更喜欢将输入图提供给 parMETIS，获取分区，然后将分区作为我的 MPI 程序的输入提供，但是您也可以从您的应用程序中调用函数来获取实时变化的图。