Подтвердить что ты не робот

Алгоритмы OpenMp С++ для минимального, максимального, среднего, среднего

Я искал Google для страницы, предлагающей некоторые простые алгоритмы OpenMp. Вероятно, есть пример для вычисления min, max, median, average из огромного массива данных, но я не могу его найти.

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

Я просто не хотел изобретать велосипед.

Дополнительные замечания: Я знаю, что есть тысячи примеров, которые работают с простым сокращением. например Вычисление PI.

const int num_steps = 100000; 
double x, sum = 0.0; 
const double step = 1.0/double(num_steps); 
#pragma omp parallel for reduction(+:sum) private(x) 
for (int i=1;i<= num_steps; i++){ 
  x = double(i-0.5)*step; 
  sum += 4.0/(1.0+x*x); 
} 
const double pi = step * sum;

но если эти алгоритмы не используются, почти нет примеров для сокращения алгоритмов.

4b9b3361

ОТВЕТЫ

Ответ 1

OpenMP (не менее 2.0) поддерживает сокращение для некоторых простых операций, но не для max и min.

В следующем примере предложение reduction используется для создания суммы, а раздел critical используется для обновления общей переменной с использованием локального потока без конфликтов.

#include <iostream>
#include <cmath>

int main()
{
  double sum = 0;
  uint64_t ii;
  uint64_t maxii = 0;
  uint64_t maxii_shared = 0;
#pragma omp parallel shared(maxii_shared) private(ii) firstprivate(maxii)
  {
#pragma omp for reduction(+:sum) nowait
    for(ii=0; ii<10000000000; ++ii)
      {
        sum += std::pow((double)ii, 2.0);
        if(ii > maxii) maxii = ii;
      }
#pragma omp critical 
    {
      if(maxii > maxii_shared) maxii_shared = maxii;
    }
  }
  std::cerr << "Sum: " << sum << " (" << maxii_shared << ")" << std::endl;
}

EDIT: более чистая реализация:

#include <cmath>
#include <limits>
#include <vector>
#include <iostream>
#include <algorithm>
#include <tr1/random>

// sum the elements of v
double sum(const std::vector<double>& v)
{
  double sum = 0.0;
#pragma omp parallel for reduction(+:sum)
  for(size_t ii=0; ii< v.size(); ++ii)
    {
      sum += v[ii];
    }
  return sum;
}

// extract the minimum of v
double min(const std::vector<double>& v)
{
  double shared_min;
#pragma omp parallel 
  {
    double min = std::numeric_limits<double>::max();
#pragma omp for nowait
    for(size_t ii=0; ii<v.size(); ++ii)
      {
        min = std::min(v[ii], min);
      }
#pragma omp critical 
    {
      shared_min = std::min(shared_min, min);
    }
  }
  return shared_min;
}

// generate a random vector and use sum and min functions.
int main()
{
  using namespace std;
  using namespace std::tr1;

  std::tr1::mt19937 engine(time(0));
  std::tr1::uniform_real<> unigen(-1000.0,1000.0);
  std::tr1::variate_generator<std::tr1::mt19937, 
    std::tr1::uniform_real<> >gen(engine, unigen);

  std::vector<double> random(1000000);
  std::generate(random.begin(), random.end(), gen);

  cout << "Sum: " << sum(random) << " Mean:" << sum(random)/random.size()
       << " Min:" << min(random) << endl;
}

Ответ 2

в OpenMP 3.1, который можно реализовать для предложения min, max through reduction, вы можете посмотреть подробный пример, охватывающий это в этой ссылке.

Ответ 3

OpenMP не поддерживает эти операции сокращения. Рассмотрим алгоритм параллельных вычислений Intel Threading Building Blocks, где вы можете реализовать произвольный алгоритм.

Вот пример. Он использует суммирование частичных результатов. Вы можете реализовать любую функцию, которую вы хотите.

#include <stdio.h>
#include <tbb/blocked_range.h>
#include <tbb/parallel_reduce.h>
#include <tbb/task_scheduler_init.h>


///////////////////////////////////////////////////////////////////////////////


class PiCalculation
{
private:
    long num_steps;
    double step;

public:

    // Pi partial value
    double pi;

    // Calculate partial value
    void operator () (const tbb::blocked_range<long> &r) 
    {
        double sum = 0.0;

        long end = r.end();

        for (int i = r.begin(); i != end; i++)
        {
            double x = (i + 0.5) * step;
            sum += 4.0/(1.0 + x * x);
        }

        pi += sum * step;
    }

    // Combine results. Here you can implement any functions
    void join(PiCalculation &p)
    {
        pi += p.pi;
    }

    PiCalculation(PiCalculation &p, tbb::split)
    {
        pi = 0.0;
        num_steps = p.num_steps;
        step = p.step;
    }

    PiCalculation(long steps)
    {
        pi = 0.0;
        num_steps = steps;
        step = 1./(double)num_steps;
    }
};


///////////////////////////////////////////////////////////////////////////////


int main()
{
    tbb::task_scheduler_init init;

    const long steps = 100000000;

    PiCalculation pi(steps);

    tbb::parallel_reduce(tbb::blocked_range<long>(0, steps, 1000000), pi);

    printf ("Pi is %3.20f\n", pi.pi);
}

Пожалуйста, проверьте эту ссылку для дополнительных алгоритмов сокращения. http://cache-www.intel.com/cd/00/00/30/11/301132_301132.pdf#page=19 Пожалуйста, ознакомьтесь с параграфом 3.3.1. Существует пример поиска минимального значения в массиве.