Многопоточность внутри цикла for - OpenMP

Question

Я пытаюсь добавить многопоточность в коде C ++. Цель - цикл for внутри функции. Цель состоит в том, чтобы сократить время выполнения программы. Выполнение занимает 3,83 секунды.

Я попытался добавить команду #pragma omp parallel for reduction(+:sum) во внутренний цикл (перед циклом j ), но этого оказалось недостаточно. Это заняло 1,98 секунды. Цель состоит в том, чтобы уменьшить время до 0,5 секунд.

Я провел некоторые исследования, чтобы увеличить скорость, и некоторые люди рекомендуют метод векторизации Strip Mining для улучшения результатов. Однако я пока не знаю, как это реализовать.

Может кто-нибудь знать, как это сделать?

Код:

void filter(const long n, const long m, float *data, const float threshold, std::vector &result_row_ind) {

  for (long i = 0; i < n; i++) {
    float sum = 0.0f;
    for (long j = 0; j < m; j++) {
      sum += data[i*m + j];
    } 
    if (sum > threshold) 
      result_row_ind.push_back(i);
  }
  std::sort(result_row_ind.begin(),
            result_row_ind.end());
}

Большое спасибо

Answer 1

Когда это возможно, вы, вероятно, захотите распараллелить внешний цикл. Самый простой способ сделать это в OpenMP - это сделать:

#pragma omp parallel for
for (long i = 0; i < n; i++) {
  float sum = 0.0f;
  for (long j = 0; j < m; j++) {
    sum += data[i*m + j];
  }
  if (sum > threshold) {
    #pragma omp critical
    result_row_ind.push_back(i);
  }
}
std::sort(result_row_ind.begin(),
          result_row_ind.end());

Это работает, и, вероятно, намного быстрее, чем распараллеливание внутреннего цикла (запуск параллельной области стоит дорого), но он использует критическую секцию для блокировки для предотвращения гонок. Эту гонку также можно избежать, используя определяемое пользователем сокращение по векторам с сокращением в этом цикле, если число потоков очень велико, а количество совпадающих результатов очень мало, это может быть медленнее, но в противном случае это, вероятно, заметно быстрее , Это не совсем верно, тип вектора неполный, поскольку его нет в списке, но он должен быть довольно близок:

#pragma omp declare \
  reduction(CatVec: std::vector<T>: \
    omp_out.insert(omp_out.end(), omp_in.begin(), omp_in.end())) \
  initializer(omp_priv=std::vector<T>())

#pragma omp parallel for reduction(CatVec: result_row_ind)
for (long i = 0; i < n; i++) {
  float sum = 0.0f;
  for (long j = 0; j < m; j++) {
    sum += data[i*m + j];
  }
  if (sum > threshold) {
    result_row_ind.push_back(i);
  }
}
std::sort(result_row_ind.begin(),
          result_row_ind.end());

Answer 2

Если у вас есть компилятор C ++ с поддержкой политик выполнения, вы можете попробовать std::for_each с политикой выполнения std::execution::par, чтобы посмотреть, поможет ли это. Пример:

#include <iostream>
#include <vector>
#include <algorithm>
#if __has_include(<execution>)
# include <execution>
#elif __has_include(<experimental/execution_policy>)
# include <experimental/execution_policy>
#endif

// iterator to use with std::for_each
class iterator {
    size_t val;
public:
    using iterator_category = std::forward_iterator_tag;
    using value_type = size_t;
    using difference_type = size_t;
    using pointer = size_t*;
    using reference = size_t&;

    iterator(size_t value=0) : val(value) {}
    inline iterator& operator++() { ++val; return *this; }
    inline bool operator!=(const iterator& rhs) const { return val != rhs.val; }
    inline reference operator*() { return val; }
};

std::vector<size_t> filter(const size_t rows, const size_t cols, const float* data, const float threshold) {
    std::vector<size_t> result_row_ind;
    std::vector<float> sums(rows);

    iterator begin(0);
    iterator end(rows);

    std::for_each(std::execution::par, begin, end, [&](const size_t& row) {
        const float* dataend = data + (row+1) * cols;
        float& sum = sums[row];

        for (const float* dataptr = data + row * cols; dataptr < dataend; ++dataptr) {
            sum += *dataptr;
        }
    });

    // pushing moved outside the threaded code to avoid using mutexes
    for (size_t row = 0; row < rows; ++row) {
        if (sums[row] > threshold)
            result_row_ind.push_back(row);
    }
    std::sort(result_row_ind.begin(),
        result_row_ind.end());

    return result_row_ind;
}

int main() {
    constexpr size_t rows =  1<<15, cols = 1<<18;
    float* data = new float[rows*cols];

    for (int i = 0; i < rows*cols; ++i) data[i] = (float)i / (float)100000000.;

    std::vector<size_t> res = filter(rows, cols, data, 10.);
    std::cout << res.size() << "\n";

    delete[] data;
}