OpenMP C ++ algoritmi per min, max, mediana, media [chiuso]

Question

ero alla ricerca di Google per una pagina che offre alcuni semplici algoritmi OpenMP. Probabilmente v'è un esempio per il calcolo min, max, media, media da una vasta gamma di dati, ma io non sono in grado di trovarlo.

Almeno io normalmente cercare di dividere la matrice in un unico pezzo per ogni core e fare qualche calcolo confine in seguito per ottenere il risultato per la gamma completa.

Ho appena non volevo reinventare la ruota.

---

Nota aggiuntiva: So che ci sono migliaia di esempi che funzionano con semplice riduzione. per esempio. Calcolo 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;

ma quando questo tipo di algoritmi non sono utilizzabili non ci sono quasi esempi lasciato per ridurre algoritmi.

Answer 1

OpenMP (almeno 2.0) supporta la riduzione per alcune operazioni semplici, ma non per max e min.

Nell'esempio seguente la clausola reduction è usato per fare una somma e una sezione critical viene utilizzato per aggiornare una variabile condivisa utilizzando un unico filo-locale senza conflitti.

#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: un'implementazione più pulito:

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

Answer 2

in OpenMP 3.1 in poi si può implementare per min, max attraverso la clausola di riduzione, si può dare un'occhiata a questo esempio dettagliato che copre in questo link .

Answer 3

OpenMP non supporta queste operazioni di riduzione. Considerare algoritmo parallel_reduce Intel Threading Building Blocks', in cui è possibile implementare l'algoritmo arbitrario.

Ecco un esempio. Esso utilizza somma dei risultati parziali. Si può realizzare qualsiasi funzione che si desidera.

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

Si prega di controllare questo link per gli algoritmi di riduzione supplementare. http://cache-www.intel .com / cd / 00/00/30/11 / 301132_301132.pdf # page = 19 Si prega di guardare attraverso il paragrafo 3.3.1. C'è un esempio su come trovare il valore minimo in un array.

Answer 4

Questa sono problemi tipici di riduzione.

pagina puntato da Suvesh , si potrebbe avere un consultare la documentazione per il clausola di riduzione .