最小、最大、中央値、平均の OpenMp C++ アルゴリズム [非公開]

StackOverflow https://stackoverflow.com/questions/978222

質問

Google で簡単な OpenMp アルゴリズムを提供するページを検索していました。おそらく、巨大なデータ配列から最小値、最大値、中央値、平均値を計算する例があると思われますが、私にはそれを見つけることができません。

少なくとも、通常は配列をコアごとに 1 つのチャンクに分割し、その後境界計算を行って完全な配列の結果を取得しようとします。

ただ車輪を再発明したくなかったのです。

追加のコメント:単純なリダクションで機能する例が何千もあることを私は知っています。例えば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;

しかし、この種のアルゴリズムが使用できない場合、アルゴリズムを削減する例はほとんど残されていません。

役に立ちましたか？

解決

のOpenMP（少なくとも2.0）がなく、最大値と最小値のため、いくつかの簡単な操作のための削減をサポートしています。

次の例で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;
}

他のヒント

OpenMP 3.1 以降では、reduction 句を使用して min、max を実装できます。これをカバーする詳細な例を以下で見ることができます。 このリンク.

OpenMPのは、これらのリダクション操作をサポートしていません。あなたが任意のアルゴリズムを実装することができますインテルスレッディング・ビルディング・ブロックparallel_reduceアルゴリズムを、考えてみます。

ここでは一例。これは、部分的な結果の合計を使用しています。あなたが望む任意の関数を実装することがあります。

#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/11分の30 / 301132_301132.pdf＃ページ= 19 のパラグラフ3.3.1に目を通してください。アレイ内の最小値を求めるに例があります。

これは典型的な削減の問題です。

Suvesh ので指さページのほかに、あなたが持っているかもしれません reduction節のドキュメントを見てください。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top