小编pio*_*rka的帖子

我必须从已知的图连通分量并行计算中找到最佳算法。

以下是我的数据和计算机架构的简要概述：

• 我可以访问具有数千个处理器的计算集群（内存不共享，但我希望单个节点中应该有足够的内存来评估我对整个数据的需求）。
• 我的图的边数与顶点数之比相当小（大约 5）
• 我预计大多数连接组件都非常小（2-3 个顶点）
• 然而，将会存在具有数百万个顶点的非常大的组件（甚至占总顶点数的 10%）。

我读过有关计算图连通分量的并行算法。正如我所注意到的，其中一些基于序列化案例的经典 BFS 方法。老实说，我对这些算法的数量有点迷失了。谁能给我一些建议，哪种算法最适合我的目的？

我必须处理8个处理器.我想按如下方式进行并行调整:

    vector<vector <int> > test;
    test.resize(10000);
    #pragma omp parallel num_threads(8)
    {
        #pragma omp for
        for (int i = 0;i < 10000;i++)test[i].resize(500000);
    }

我注意到程序没有使用100%的处理器能力 - 它只使用了15%.当我更改代码时

    vector<vector <int> > test;
    test.resize(1000000);
    #pragma omp parallel num_threads(8)
    {
        #pragma omp for
        for (int i = 0;i < 1000000;i++)test[i].resize(5000);
    }

该程序使用了大约60%的处理器功率.我不明白这种现象 - 我希望它能在僵硬的情况下使用100%的处理器能力.我在这里错过了什么吗？