c++ - 与串行版本相比，使用openMP进行插入排序的并行化可提供非常醒目的结果

语境
你好!
我刚刚完成了POSIX pthreads和OpenMP的使用经验，试图将两者与Insertion Sort的串行实现进行比较，以查看哪种输入在哪种输入上表现良好。
至少可以说，我得到的结果很奇怪。
可能是我的代码有错误。我要说的是，我的pthread实现肯定是并且需要做很多工作，因为这是一个非常糟糕的实现。但是，看看OpenMP和Serial花费的时间，我看到了非常奇怪的趋势。
码
在向您展示我所花费的时间图之前，这里是每个代码。
对于串行，

static inline void *
insertionSort(void *arrayMetaDataToUnpack)
{
    // UNPACK START
    ull *_Array = ((InsertionSortPacking *)arrayMetaDataToUnpack)->Array;
    size_t sizeOfArray = ((InsertionSortPacking *)arrayMetaDataToUnpack)->ArraySize;
    // UNPACK END

    // Compulsory use of reinterpret_cast to keep everything consistent
    ull *__tempArray = reinterpret_cast<ull *>(_Array);

    for (int i = 1; i < sizeOfArray; i++)
    {
        int __temp = __tempArray[i];
        int j = i - 1;

        while (j >= 0 && __temp <= __tempArray[j])
        {
            __tempArray[j + 1] = __tempArray[j];
            j = j - 1;
        }

        {
            __tempArray[j + 1] = __temp;
        }
    }

    return __tempArray;
}
static inline void *
insertionSort(void *arrayMetaDataToUnpack)
{
    // UNPACK START
    ull *_Array = ((InsertionSortPacking *)arrayMetaDataToUnpack)->Array;
    size_t sizeOfArray = ((InsertionSortPacking *)arrayMetaDataToUnpack)->ArraySize;
    // UNPACK END

    // Compulsory use of reinterpret_cast to keep everything consistent
    ull *__tempArray = reinterpret_cast<ull *>(_Array);

    for (int i = 1; i < sizeOfArray; i++)
    {
        int __temp = __tempArray[i];
        int j = i - 1;

        while (j >= 0 && __temp <= __tempArray[j])
        {
            __tempArray[j + 1] = __tempArray[j];
            j = j - 1;
        }

        {
            __tempArray[j + 1] = __temp;
        }
    }

    return __tempArray;
}

OpenMP实现，

static inline void *
openmp_insertionSort(void *arrayMetaDataToUnpack)
{
    // UNPACK START
    ull *_Array = ((InsertionSortPacking *)arrayMetaDataToUnpack)->Array;
    size_t sizeOfArray = ((InsertionSortPacking *)arrayMetaDataToUnpack)->ArraySize;
    // UNPACK END

    // Compulsory use of reinterpret_cast to keep everything consistent
    ull *__tempArray = reinterpret_cast<ull *>(_Array);

#pragma omp for
    for (int i = 1; i < sizeOfArray; i++)
    {
        int __temp = __tempArray[i];
        int j = i - 1;

        while (j >= 0 && __temp <= __tempArray[j])
        {
            __tempArray[j + 1] = __tempArray[j];
            j = j - 1;
        }

#pragma omp critical
        {
            __tempArray[j + 1] = __temp;
        }
    }

    return __tempArray;
}

再次声明，免责声明，我是OpenMP的新手，我可能已经很好地并行化了代码，但这是我在初学者阶段就知道的所有使用它的方法。它确实可以很好地进行排序，而没有竞争条件。
输入项
因此，对于输入，

    const int INPUTSIZE = 25;

    int inputSizes[INPUTSIZE] = {1000, 1500, 2000, 2500, 3000, 3500, 4000, 4500, 5000,
                                5500, 6000, 6500, 7000, 7500, 8000, 8500, 9000, 9500,
                                10000, 10500, 11000, 11500, 12000, 12500, 13000};

我的程序在使用clock_t查找每种输入的每种方法所花费的时间之后，生成一个csv文件。
图形
我得到的最终图形是由上面提到的csv文件生成的，看起来像这样

哪里，

X轴是输入大小

Y轴是以秒为单位的时间

Serial是

的串行实现

Pthread是pthread实现

OpenMP是openMP实现

花费的时间...是我的程序生成inputSize [i]大小的数组

所花费的时间

机器细节

通过使用以下逻辑

测量时间

    clock_t __start = clock();

    Array = functionName((void *)&packingMetadata);

    clock_t __end = clock();

    double __inputTimeUsed = ((double)(__end - __start)) / CLOCKS_PER_SEC;
    std::cout << "Overall time taken, using " << printStatement << __inputTimeUsed << ".\n";

其中functionName是指向串行版本，pthread版本或openmp版本的函数指针。 packingMetaData是将打包数据作为传递给它的结构，它由指向在main()中创建的数组的指针和数组大小组成

减少噪音的测量方法...不确定到底是什么意思

编译命令为g++ -std=gnu++17 -std=c++17 insertion.cpp -o insertion -lpthread

编译器是g++

机器信息，
Linux内核版本:5.4.0-47-generic
操作系统类型:64位
处理器:1.90GHz时8个Intel®Core™i7-8665U CPU
内存:15.5 GiB的RAM

问题/问题
我的pthread实现不好，明白了，这是我的错，可以改进。
那么OpenMP的实现呢？为什么会这样呢？为什么输出如此之字形？
所以我想问的事情很多，但主要是

为什么会出现尖峰和随机性？和

我如何继续观察如何进一步改进并行实现？

最佳答案

实际上，是的，您应该更加仔细地检查结果，因为仅通过添加omp for和omp critical不能并行化插入排序。当前代码无法正常工作，因为插入会产生错误的结果。
让我们向后退，以了解为什么它不是那么简单。实际上，我们尝试并行插入多个元素。但是，插入需要更大的数组移动元素。元素的移动很难并行完成(实际上，效率不高)。将while循环放在关键部分中将使所有排序顺序进行。因此，我们需要找到另一种并行化代码的方法。更准确地说，我们需要找到可以并行运行的独立工作。
一种解决方案是寻找要平行插入的元素的位置，然后执行屏障，然后平行移动元素。但是，这种解决方案不是很有效，尤其是对于小型阵列(由于过度同步和小的工作粒度)。
更好的解决方案是将数组(实际上)分成N个部分，然后对每个部分并行执行独立插入排序，然后设置障碍，最后merge排序数组。
请注意，与其他算法(例如对相当大的数据进行快速排序或合并排序)相比，插入排序通常效率不高。如果您想要达到高性能，那么直接实现并行快速/合并排序(甚至更好:并行introsort)可能是明智的。

关于c++ - 与串行版本相比，使用openMP进行插入排序的并行化可提供非常醒目的结果，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/63944548/