OpenMP 性能问题：并行性没有改善执行时间

Question

我有这个代码；

 #include <stdio.h>
#include <stdlib.h>
#include <omp.h>
#include <limits.h>

#define NUM_VERTICES 1024

int distance[NUM_VERTICES];
int shortestPathTree[NUM_VERTICES];
int predecessor[NUM_VERTICES];

int main(void) 
{
    int i;

    double start_time = omp_get_wtime();

    #pragma omp parallel for num_threads(3)
    for (i = 0; i < NUM_VERTICES; ++i) {
        distance[i] = INT_MAX;
        shortestPathTree[i] = 0;
        predecessor[i] = -1;
    }

    double end_time = omp_get_wtime();
    double iteration_time = end_time - start_time;

    printf("Execution time: %f seconds\n", iteration_time);

    return 0; 
}

已经尝试过这个版本，这是最接近规格的。我还尝试过改变方法、使用分段并测试不同的调度策略。我尝试的最后一件事是添加打印语句（如注释中所示）来观察每个线程的行为。然而，我注意到，当线程 2 启动时，它会处理迭代 30 次以后，而不允许其他线程打印，几乎就好像一旦它获取了资源，它就不会放弃它们。

我已经为此工作了大约三天，尝试了不同的事情，但似乎没有任何效果。我还发现令人沮丧的是，在此之后，我将实现 Dijkstra 算法，其中最佳线程数似乎是 5。看起来代码可以在某种程度上并行化，但对于其他任务来说并不一致。

以下是我观察到的不同线程配置的一些结果：

• 1 个线程和 2 个线程：0.000142 秒

• 1 个线程和 3 个线程：0.000129 秒

• 1 个线程和 4 个线程：0.000120 秒

正如我们所看到的，最初随着更多线程的增加，时间往往会减少，但最终会出现一个点，即添加更多线程将不会产生进一步的改进。

• 1 个线程和 5 个线程：0.000115 秒

• 1 个线程和 6 个线程：0.000121 秒

所以我的电脑似乎能够并行化，但不能达到只有 1 个线程最好的起点

Answer 1

最有价值的信息是对您的问题的评论。我将直接回答这个问题：为什么您没有看到并行循环的执行时间得到改善。

因为初始化和线程管理开销克服了实际的数据处理。尝试下面的代码。这是您的代码的稍加修改的版本。你应该看到效果了。

#include <stdio.h>
#include <stdlib.h>
#include <omp.h>
#include <limits.h>

#define NUM_VERTICES 1024 * 1024
#define N_THREADS_0    1
#define N_THREADS_1    4

int main(void) 
{
    int i;

    double start_time;
    double end_time;
    double iteration_time;
    int *distance;
    int *shortestPathTree;
    int *predecessor;

    distance         = malloc(NUM_VERTICES * sizeof(int));
    shortestPathTree = malloc(NUM_VERTICES * sizeof(int));
    predecessor      = malloc(NUM_VERTICES * sizeof(int));

    if((NULL == distance) || (NULL == shortestPathTree) || (NULL == predecessor)) {
        return 0;
    }

    start_time = omp_get_wtime();

    #pragma omp parallel for num_threads(N_THREADS_0)
    for (i = 0; i < NUM_VERTICES; ++i) {
        distance[i]         = INT_MAX;
        shortestPathTree[i] = 0;
        predecessor[i]      = -1;
    }

    end_time = omp_get_wtime();
    iteration_time = end_time - start_time;

    printf(" 1* execution time: %f seconds\n", iteration_time);

    start_time = omp_get_wtime();

    #pragma omp parallel for num_threads(N_THREADS_1)
    for (i = 0; i < NUM_VERTICES; ++i) {
        distance[i]         = INT_MAX;
        shortestPathTree[i] = 0;
        predecessor[i]      = -1;
    }

    end_time = omp_get_wtime();
    iteration_time = end_time - start_time;

    printf(" 2* execution time: %f seconds\n", iteration_time);

    return 0; 
}