OpenMP c++ algorithmes pour min, max, médiane, moyenne [fermé]
Je cherchais Google pour une page offrant quelques algorithmes OpenMp simples. Il y a probablement un exemple pour calculer min, max, median, average à partir d'un énorme tableau de données mais je ne suis pas capable de le trouver.
Au moins, j'essaierais normalement de diviser le tableau en un morceau pour chaque noyau et de faire un calcul de limite par la suite pour obtenir le résultat pour le tableau complet.
Je ne voulais pas réinventer la roue.
Remarque Supplémentaire: Je sais qu'il y a des milliers d'exemples qui fonctionnent avec une simple réduction. par exemple, le 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 plus d'exemples pour réduire les algorithmes.
4 réponses
OpenMP (au moins 2.0) prend en charge la réduction pour certaines opérations simples, mais pas pour max et min.
Dans l'exemple suivant, la clause reduction est utilisée pour faire une somme et une section critical est utilisée pour mettre à jour une variable partagée en utilisant une variable locale de thread 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;
}
OpenMP ne prend pas en charge ces opérations de réduction. Considérez l'algorithme parallel_reduce D'Intel Threading Building Blocks, où vous pouvez implémenter un algorithme arbitraire.
Voici un exemple. Il utilise la sommation des résultats partiels. Vous pouvez implémenter n'importe quelle fonction 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);
}
Veuillez vérifier ce lien pour des algorithmes de réduction supplémentaires. http://cache-www.intel.com/cd/00/00/30/11/301132_301132.pdf#page=19 veuillez consulter le paragraphe 3.3.1. Il y a un exemple sur trouver la valeur minimale dans un tableau.
Ce sont des problèmes de réduction typiques.
Outre la page pointée par Suvesh , Vous pouvez consulter la documentation de la clause de réduction .