Как реализовать argmax с OpenMP?

Question

Как реализовать argmax с OpenMP?

Я пытаюсь реализовать argmax с OpenMP. Если коротко, у меня есть функция, которая вычисляет значение с плавающей запятой:

double toOptimize(int val);

Я могу получить целое число, максимизирующее значение с помощью:

double best = 0;
#pragma omp parallel for reduction(max: best)
for(int i = 2 ; i < MAX ; ++i)
{
double v = toOptimize(i);
if(v > best) best = v;
}

Теперь, как я могу получить значение i соответствует максимуму?

Редактировать:

Я пытаюсь это, но хотел бы убедиться, что это действительно:

double best_value = 0;
int best_arg = 0;
#pragma omp parallel
{
double local_best = 0;
int ba = 0;
#pragma omp for reduction(max: best_value)
for(size_t n = 2 ; n <= MAX ; ++n)
{
double v = toOptimize(n);
if(v > best_value)
{
best_value = v;
local_best = v;
bn = n;
}
}
#pragma omp barrier
#pragma omp critical
{
if(local_best == best_value)
best_arg = bn;
}
}

И, в конце концов, я должен был best_arg Аргмакс toOptimize,

1

c++openmp parallel-processing reduction

Решение

Другие решения

Я бы просто создал отдельный буфер для каждого потока, чтобы сохранить val а также idx и затем выберите максимальное значение из буфера впоследствии.

    std::vector<double> thread_maxes(omp_get_max_threads());
std::vector<int>    thread_max_ids(omp_get_max_threads());

#pragma omp for reduction(max: best_value)
for(size_t n = 2 ; n <= MAX ; ++n)
{
int thread_num = omp_get_num_threads();
double v = toOptimize(n);
if(v > thread_maxes[thread_num])
{
thread_maxes[thread_num] = v;
thread_max_ids[thread_num] = i;
}
}

std::vector<double>::iterator max =
std::max_element(thread_maxes.begin(), thread_maxes.end());
best.val = *max;
best.idx = thread_max_ids[max - thread_maxes.begin()];

1

Ваше решение в порядке. Имеет сходимость O (nthreads) с критической секцией. Однако это можно сделать с помощью конвергенции O (Log (nthreads)).

Например, представьте, что было 32 темы.
Сначала вы найдете локальный максимум для 32 потоков. Затем вы можете объединить пары с 16 потоками, затем 8, затем 4, затем 2, затем 1. За пять шагов вы можете объединить локальные максимальные значения без критической секции и свободных потоков в процессе. Но ваш метод объединит локальные максимальные значения за 32 шага в критическом разделе и использует все потоки.

Та же логика относится и к сокращению. Вот почему лучше позволить OpenMP делать сокращение, а не делать это вручную с атомарным разделом. Но, по крайней мере, в реализации OpenMP на C / C ++ нет простого способа получить максимум / мин в O (Log (nthreads)). Это может быть возможно с помощью задач, но я не пробовал это.

На практике это может не иметь значения, поскольку время объединения локальных значений даже с критическим разделом, вероятно, ничтожно мало по сравнению с временем выполнения параллельного цикла. Это, вероятно, имеет большее значение для графического процессора, хотя там, где количество «потоков» намного больше.

0

Источник

Accepted Answer

Ваше решение полностью соответствует стандартам. В любом случае, если вы хотите добавить немного синтаксического сахара, вы можете попробовать что-то вроде следующего:

#include<iostream>

using namespace std;

double toOptimize(int arg) {
return arg * (arg%100);
}

class MaximumEntryPair {
public:

MaximumEntryPair(size_t index = 0, double value = 0.0) : index_(index), value_(value){}

void update(size_t arg) {
double v = toOptimize(arg);
if( v > value_ ) {
value_ = v;
index_ = arg;
}
}

bool operator<(const MaximumEntryPair& other) const {
if( value_ < other.value_ ) return true;
return false;
}

size_t index_;
double value_;
};int main() {
MaximumEntryPair best;
#pragma omp parallel
{
MaximumEntryPair thread_local;
#pragma omp for
for(size_t ii = 0 ; ii < 1050 ; ++ii) {
thread_local.update(ii);
} // implicit barrier
#pragma omp critical
{
if ( best < thread_local ) best = thread_local;
}

} // implicit barries
cout << "The maximum is " << best.value_ << " obtained at index " << best.index_ << std::endl;
cout << "\t toOptimize(" << best.index_ << ") = " << toOptimize(best.index_) << std::endl;
return 0;
}

1