Algoritmi OpenMp C++ per min, max, media, media

Question

Stavo cercando su Google una pagina che offrisse alcuni semplici algoritmi OpenMp. Probabilmente c'è un esempio per calcolare min, max, mediana, media da un enorme array di dati, ma non sono in grado di trovarlo.

Almeno normalmente proverei a dividere l'array in un blocco per ogni core e a eseguire successivamente un calcolo dei limiti per ottenere il risultato per l'array completo.

Non volevo reinventare la ruota.

---

nota aggiuntiva: So che ci sono migliaia di esempi che funzionano con semplice riduzione. ad es. 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 semplici operazioni, ma non per max e min.

Nell'esempio seguente la clausola reduction viene utilizzata per creare una somma e una sezione critical viene utilizzata per aggiornare una variabile condivisa utilizzando una locale thread-thread 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

Questi sono i tipici problemi di riduzione.

Oltre a the page pointed by Suvesh, è possibile dare un'occhiata alla documentazione per reduction clause.

Answer 3

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

Ecco un esempio. Usa la somma dei risultati parziali. Puoi implementare qualsiasi funzione tu voglia.

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

Controllare questo collegamento per ulteriori algoritmi di riduzione. http://cache-www.intel.com/cd/00/00/30/11/301132_301132.pdf#page=19 Consultare il paragrafo 3.3.1. C'è un esempio sulla ricerca del valore minimo in una matrice.

Answer 4

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