OpenMP C ++ algoritmos para min, max, mediana, media [cerrada]

Question

Yo estaba buscando en Google de una página que ofrece algunos algoritmos sencillos OpenMP. Probablemente hay un ejemplo para calcular mínimo, máximo, mediana, media entre todo tipo de datos, pero no soy capaz de encontrarlo.

Al menos yo normalmente tratar de dividir la matriz en un trozo de cada núcleo y hacer algún cálculo de límites después de obtener el resultado para la matriz completa.

Yo simplemente no quiero reinventar la rueda.

---

Observación adicional: Sé que hay miles de ejemplos que funcionan con reducción simple. p.ej. El cálculo 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;

pero cuando este tipo de algoritmos no están disponibles casi no hay ejemplos que quedan para la reducción de los algoritmos.

Answer 1

OpenMP (al menos 2,0) apoya la reducción para algunas operaciones simples, pero no para max y min.

En el siguiente ejemplo la cláusula reduction se utiliza para hacer una suma y una sección critical se utiliza para actualizar una variable compartida utilizando un uno subproceso local sin conflictos.

#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: una aplicación más limpia:

#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

en OpenMP 3.1 en adelante se puede aplicar para min, max través de la cláusula de reducción, se puede echar un vistazo a este ejemplo detallado que cubre en este enlace .

Answer 3

OpenMP no admite estas operaciones de reducción. Considere algoritmo parallel_reduce Intel Threading Building Blocks', donde se puede aplicar el algoritmo arbitrario.

Aquí un ejemplo. Utiliza suma de los resultados parciales. Es posible implementar cualquier función que desee.

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

Por favor, consulte este enlace para algoritmos de reducción adicionales. http://cache-www.intel .com / cd / 00/00/30/11 / 301132_301132.pdf # page = 19 por favor, revise el apartado 3.3.1. Hay un ejemplo en la búsqueda de valor mínimo en una matriz.

Answer 4

Estos son problemas de reducción típicos.

la página apuntada por Suvesh , es posible que tenga una mirar la documentación para el cláusula de reducción .