openmp for循环未并行化

Question

我正在尝试测量并行版本和串行版本的运行时间。

我有这样一个程序：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <omp.h>
#include <time.h>
#include <unistd.h>
#include <sys/types.h>
#include <errno.h>
#include <sys/resource.h>
#include <sys/times.h>

#define ARRAY_SIZE 1024 * 20

long time_delta = 0;

struct rusage rusage_start;
struct rusage rusage_finish;

void bubble_sort(unsigned int* array) {
    unsigned int tmp = 0;
    bool no_swap = 0;
    for (unsigned int i = ARRAY_SIZE - 1; i >= 0; --i)
    {
        no_swap = 1;
        {
            #pragma omp parallel for num_threads(4)
            for (unsigned int j = 0; j < i; j++)
            {
                if (array[j] > array[j + 1])
                {
                    tmp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = tmp;
                    no_swap = 0;
                }
            }
        }
        if (no_swap)
            break;
    }
}

int main(int argc, char* argv[]) {
    (void)argc;
    (void)argv;
    srand(time(NULL));
    unsigned int* array = malloc(sizeof(unsigned int) * ARRAY_SIZE);
    if(!array) { return -1; }
    for(unsigned int i = 0; i < ARRAY_SIZE; ++i) {
        array[i] = rand() % ARRAY_SIZE;
    }
    getrusage(RUSAGE_SELF, &rusage_start);
    
    //sort
    bubble_sort(array);

    getrusage(RUSAGE_SELF, &rusage_finish);
    time_delta = (1000000 * (rusage_finish.ru_utime.tv_sec - rusage_start.ru_utime.tv_sec)) + (rusage_finish.ru_utime.tv_usec - rusage_start.ru_utime.tv_usec);
    printf("Time: %li microseconds\n", time_delta);
    free(array);
    return 0;
}

我像这样编译和测量时间：

gcc -openmp main.c -o prog && for n in {1..10}; do ./prog; done

问题是，如果我在for之前更改了函数中的线程数，或者完全删除了该指令，则什么都不会改变。

我做错了什么？

一切似乎都是正确的。(我在具有4个内核的VM上运行代码；lscpu可以看到它们。)

Answer 1

您的for循环不能(或不应该)并行化，因为在其作用域(tmp)之外声明的变量在内部被修改。在您的示例中，可以通过删除tmp的当前声明并将其放入if块中来修复此特定问题：

    if (array[j] > array[j + 1])
    {
        unsigned int tmp = array[j]; // Now a LOCAL variable (one for each loop).
        array[j] = array[j + 1];
        array[j + 1] = tmp;
        no_swap = 0;
    }

在您的代码中，如果并行执行的循环试图同时读取或写入单个tmp变量，则存在(很高)数据争用的可能性。

但是，no_swap变量也有类似的问题，更重要的是，array数据本身也有类似的问题:如果一个循环的j与另一个循环的j + 1相同，那么交换元素的尝试将导致数据竞争(访问冲突)。

总而言之:冒泡排序的并行化是不切实际的，除非您创建更复杂的代码。例如，。