Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

OpenMp C++ algorithms for min, max, median, average [closed]

I was searching Google for a page offering some simple OpenMp algorithms. Probably there is an example to calculate min, max, median, average from a huge data array but I am not capable to find it.

At least I would normally try to divide the array into one chunk for each core and do some boundary calculation afterwards to get the result for the complete array.

I just didn't want to reinvent the wheel.


Additional Remark: I know that there are thousands of examples that work with simple reduction. e.g. Calculating 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; 

but when these kind of algorithms aren't usable there are almost no examples left for reducing algorithms.

like image 901
Totonga Avatar asked Jun 10 '09 21:06

Totonga


1 Answers

OpenMP (at least 2.0) supports reduction for some simple operations, but not for max and min.

In the following example the reduction clause is used to make a sum and a critical section is used to update a shared variable using a thread-local one without conflicts.

#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: a cleaner implementation:

#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; } 
like image 151
baol Avatar answered Oct 02 '22 16:10

baol