Algoritmos OpenMp C++ para mínimo, máximo, mediano, promedio

Question

Estaba buscando en Google una página que ofreciera algunos algoritmos simples de OpenMp. Probablemente haya un ejemplo para calcular el promedio mínimo, máximo, medio, de una enorme matriz de datos, pero no puedo encontrarlo.

Al menos normalmente trataría de dividir la matriz en un fragmento para cada núcleo y luego hacer un cálculo de límite para obtener el resultado de la matriz completa.

Simplemente no quería reinventar la rueda.

---

Observación adicional: Sé que hay miles de ejemplos que funcionan con reducción simple. p. 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) admite reducción para algunas operaciones simples, pero no para max y min.

En el siguiente ejemplo, la cláusula reduction se usa para hacer una suma y una sección critical se usa para actualizar una variable compartida utilizando una cadena 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

Estos son problemas típicos de reducción.

Además de the page pointed by Suvesh, puede consultar la documentación del reduction clause.

Answer 3

OpenMP no es compatible con estas operaciones de reducción. Considere el algoritmo parallel_reduce de Intel Threading Building Blocks, donde puede implementar algoritmos arbitrarios.

Aquí un ejemplo. Utiliza la suma de resultados parciales. Puede 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 obtener algoritmos de reducción adicionales. http://cache-www.intel.com/cd/00/00/30/11/301132_301132.pdf#page=19 Consulte el párrafo 3.3.1. Hay un ejemplo sobre cómo encontrar el valor mínimo en una matriz.

Answer 4

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