如何使用OpenMP实现argmax

Question

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

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

Answer 1

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

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

Answer 2

我只需要为每个线程创建一个单独的缓冲区来存储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()];

Answer 3

您的解决方案很好。它与临界截面具有O（nthreads）收敛性。然而，使用O（Log（nthreads））收敛可以做到这一点。

例如，假设有32个线程。您将首先找到32个线程的本地最大值。然后，您可以组合具有16个线程的对，然后是8个线程，然后是4个线程，再是2个线程，最后是1个线程。在五个步骤中，您可以在没有关键部分和进程中空闲线程的情况下合并本地最大值。但是，您的方法将在一个关键部分中以32个步骤合并本地最大值，并使用所有线程。

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

在实践中，这可能没有什么区别，因为与进行并行循环的时间相比，合并局部值的时间（即使是关键部分）可能可以忽略不计。这可能会对GPU产生更大的影响，尽管"线程"的数量要多得多。