如何使用OpenMP实现argmax？

我正在尝试使用OpenMP实现argmax。 如果简短，我有一个计算浮点值的函数：

double toOptimize(int val); 

我可以通过以下方式获得最大化值的整数：

 double best = 0; #pragma omp parallel for reduction(max: best) for(int i = 2 ; i  best) best = v; } 

现在，我如何获得对应于最大值的值？

编辑：

我正在尝试这个，但想确保它是有效的：

 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  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的toOptimize 。

Answer 1

您的解决方案完全符合标准。 无论如何，如果你愿意添加一些语法糖，你可以尝试类似以下的东西：

 #include 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; } 

Answer 2

我只是为每个线程创建一个单独的缓冲区来存储val和idx ，然后选择缓冲区的最大值。

  std::vector thread_maxes(omp_get_max_threads()); std::vector 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::iterator max = std::max_element(thread_maxes.begin(), thread_maxes.end()); best.val = *max; best.idx = thread_max_ids[max - thread_maxes.begin()]; 

Answer 3

你的解决方案很好。 它与临界区有O（nthreads）收敛。 但是，可以使用O（Log（nthreads））收敛来完成此操作。

例如，想象有32个线程。 您将首先找到32个线程的本地最大值。 然后你可以组合16个线程，然后是8个，然后是4个，然后是2个，然后是1.在五个步骤中，你可以合并本地最大值而不需要临界区和过程中的自由线程。 但是您的方法会在关键部分中以32个步骤合并本地最大值并使用所有线程。

同样的逻辑也适用于减少。 这就是为什么最好让OpenMP进行减少，而不是手动使用primefaces部分。 但至少在OpenMP的C / C ++实现中，没有简单的方法来获得O（Log（nthreads））中的max / min。 可能有可能使用任务，但我没有尝试过。

在实践中，这可能没有区别，因为与并行循环的时间相比，即使与临界区合并本地值的时间也可以忽略不计。 尽管“线程”的数量要大得多，但它可能会在GPU上产生更大的差异。