# OpenMp C++ algorithms for min, max, median, average

### Question

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.

1
27
6/20/2009 8:13:43 AM

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;
}
``````
23
5/17/2015 3:43:51 PM

in OpenMP 3.1 onwards one can implement for min, max through reduction clause, you can have a look at detailed example covering this in this link.