Openmp C ++ algorithmes pour min, max, la médiane, la moyenne [fermée]

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

Question

je recherche Google pour une page offrant des algorithmes de OpenMP simples. Il y a probablement un exemple pour calculer min, max, moyenne, moyenne à partir d'une vaste gamme de données, mais je ne suis pas capable de le trouver.

Au moins, je voudrais essayer de diviser normalement le tableau en un seul morceau pour chaque noyau et faire un peu de calcul limite ensuite pour obtenir le résultat pour le tableau complet.

Je ne voulais pas réinventer la roue.

Remarque supplémentaire: Je sais qu'il ya des milliers d'exemples qui fonctionnent avec une simple réduction. par exemple. Calcul de 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;

mais quand ce genre d'algorithmes ne sont pas utilisables, il n'y a presque pas d'exemples laissés pour réduire les algorithmes.

Était-ce utile?

La solution

OpenMP (au moins 2,0) supporte la réduction de certaines opérations simples, mais pas pour max et min.

Dans l'exemple suivant la clause de reduction est utilisé pour faire une somme et une section de critical est utilisé pour mettre à jour une variable partagée en utilisant un thread local sans conflits. 

#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: une implémentation plus propre: 

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

Autres conseils

dans OpenMP 3.1, on peut mettre en œuvre à compter de min, max par la clause de réduction, vous pouvez consulter exemple détaillé couvrant cela dans ce lien .

OpenMP ne supporte pas ces opérations de réduction. Considérez Intel Threading Building Blocks algorithme de parallel_reduce, où vous pouvez mettre en œuvre l'algorithme arbitraire.

Voici un exemple. Il utilise la somme des résultats partiels. Vous pouvez mettre en œuvre toutes les fonctions que vous voulez. 

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

S'il vous plaît vérifier ce lien pour les algorithmes de réduction supplémentaires. http://cache-www.intel .com / cd / 00/00/30/11 / 301132_301132.pdf # page = 19 S'il vous plaît regarder à travers le paragraphe 3.3.1. Il est un exemple sur la recherche de valeur minimale dans un tableau.

Ce sont des problèmes de réduction typiques.

En plus de la page pointée par Suvesh , vous pourriez avoir un consultez la documentation pour le

Non affilié à StackOverflow
scroll top