c++ - 增加线程数，但程序不能更快地运行 C++ OpenMP 选择排序

问题描述

我正在尝试使用 C++ OpenMP 编写选择排序算法。我写了代码，它排序了，但是随着线程数量的增加，SelectionSort 算法的运行时间也增加了......我刚开始使用 OpenMP，所以我不太擅长它：DI 不能使用 OpenMP reduction，因为我正在使用 VisualStudio Community 2017 IDE .. 感谢您的帮助 ;)

#include "pch.h"
#include <iostream>
#include <omp.h>
#include <random>
#include <ctime>
#include <iomanip>
#include <algorithm>

using namespace std;

const int n = 10000;                            // count of numbers in vector

// ------------------- FUNCTIONS HEADERS -----------------------
vector<int> FillVector();
vector<int> SelectionSort(vector<int> data, int num_th);
void PrintArray(vector<int> data);

int main()
{
    std::vector<int> test_1(n);
    std::vector<int> test_2(n);
    std::vector<int> test_3(n);
    std::vector<int> test_4(n);

    cout << test_1.size() << endl;          // size of vector

    test_1 = FillVector();

    std::copy(std::begin(test_1), std::end(test_1), std::begin(test_2));    // copy vector test_1 to test_2
    std::copy(std::begin(test_1), std::end(test_1), std::begin(test_3));    // copy vector test_1 to test_3
    std::copy(std::begin(test_1), std::end(test_1), std::begin(test_4));    // copy vector test_1 to test_4

    // Testing times of sorting with different threads count


    // Number of Threads: 2
    int num_th = 2;
    clock_t begin = clock();
    test_1 = SelectionSort(test_1, num_th);     // sort vector test_1
    clock_t end = clock();
    double elapsed_secs = double(end - begin) / CLOCKS_PER_SEC;
    cout << elapsed_secs << endl;

    // Number of Threads: 4
    num_th = 4;
    begin = clock();
    test_2 = SelectionSort(test_2, num_th);     // sort vector test_2
    end = clock();
    elapsed_secs = double(end - begin) / CLOCKS_PER_SEC;
    cout << elapsed_secs << endl;

    // Number of Threads: 8
    num_th = 8;
    begin = clock();
    test_3 = SelectionSort(test_3, num_th);     // sort vector test_3
    end = clock();
    elapsed_secs = double(end - begin) / CLOCKS_PER_SEC;
    cout << elapsed_secs << endl;

    // Number of Threads: 16
    num_th = 16;
    begin = clock();
    test_4 = SelectionSort(test_4, num_th);     // sort vector test_4
    end = clock();
    elapsed_secs = double(end - begin) / CLOCKS_PER_SEC;
    cout << elapsed_secs << endl;

    return 0;
}

// ----------------- METHODS --------------------------------

// Fill vector with random integers
vector<int> FillVector() {
    vector<int> temp(n);

    srand(time(NULL));
    for (int i = 0; i < n; i++)
        temp[i] = rand() % n + 1;

    return temp;
}

// EXECUTE parallel Selection Sort usin OpenMP
vector<int> SelectionSort(vector<int> data, int num_th)
{
    // start parallel method (OpenMP)
    //VEIKIA !!!!!!
    vector<int> temp(n);
    std::copy(std::begin(data), std::end(data), std::begin(temp));      // make a temporary copy of array

    omp_set_num_threads(num_th);                                        // set threads number
    for (int i = 0; i < n - 1; i++)
    {
        int min_index = i;
#pragma omp parallel                                                    // start OpenMP parallel code block
        for (int j = i + 1; j < n; j++)
            if (temp[j] < temp[min_index])
                min_index = j;
        std::swap(temp[i], temp[min_index]);                            // std swap method
    }

    return temp;
}

// PRINT vector as 2D array
void PrintArray(vector<int> data)
{
    int rows, elem = 20;                                                // declare rows variable and column count

    if (n % elem != 0)                                                  // calculate rows count
        rows = n / elem + 1;
    else
        rows = n / elem;

    int iii = 0;
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < elem; j++) {
            if (iii != n) {
                cout << setw(3) << left << data[iii] << " ";
                iii++;
            }
            else
                break;
        }
        cout << endl;
    }
    cout << endl;
}

结果（当 n = 5000 时）：

尺寸：5000
线程 2：5.607
线程 4：8.421
线程 8：10.979
线程 16：27.989

打开图片

标签： c++multithreadingalgorithmopenmpselection-sort

c++ - 增加线程数，但程序不能更快地运行 C++ OpenMP 选择排序

问题描述

解决方案

推荐阅读