Алгоритмы C++ OpenMp в течение минуты, макс., медианы, [закрытое] среднее число
Bool образует ограниченную решетку *, где False - это снизу , а True - сверху . Эта ограниченная решетка определяет (полное) упорядочение, где False действительно строго меньше, чем True. (Они также являются единственными элементами этой решетки.)
Булевы операции and и or также могут рассматриваться как , встречаются и , соединяются , соответственно в этой решетке. Meet находит наибольшую нижнюю границу, а join находит наименьшую верхнюю границу. Это означает, что a && False = False - это то же самое, что сказать, что нижняя граница дна и всего остального является нижней, а a || True = True - это то же самое, что сказать, что верхняя граница вершины и всего остального является верхней. Так что meet и join, которые используют свойство ordering логических значений, эквивалентны логическим операциям, с которыми вы знакомы.
Вы можете использовать min и max, чтобы показать это в Haskell:
False `min` True = False -- this is the greatest lower bound
False && True = False -- so is this
False `max` True = True -- this is the least upper bound
False || True = True -- so is this
Это показывает, что вы можете определить && и || только из Производный Ord экземпляр:
(&&) = min
(||) = max
Обратите внимание, что эти определения не эквивалентны при наличии другого вида дна , потому что (&&) и (||) являются короткозамкнутыми ( не является строгим во втором аргументе, когда первым является False или True, соответственно), в то время как min и max нет.
Также, небольшое исправление: предложение deriving не говорит о том, что Bool «происходит от» Ord. Он инструктирует GHC получить экземпляр класса типов Ord для типа Bool.
* Более конкретно, дополняется распределительная решетка . Точнее говоря, булева алгебра .
3 ответа
OpenMP (по крайней мере 2.0) поддерживает сокращение для некоторых простых операций, но не для max и min.
В следующем примере условие сокращения используется для вычисления суммы, а критическая секция используется для обновления совместно используемой переменной с использованием локальной переменной потока без конфликтов.
#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;
}
РЕДАКТИРОВАТЬ: более чистая реализация:
#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 не поддерживает эти операции сокращения. Рассмотрим алгоритм parallel_reduce от Intel Threading Building Blocks, в котором можно реализовать произвольный алгоритм.
Вот пример. Он использует суммирование частичных результатов. Вы можете реализовать любую функцию, которую хотите.
#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);
}
Пожалуйста, проверьте эту ссылку, чтобы узнать о дополнительных алгоритмах сокращения. http://cache-www.intel.com/cd/00/00/30/11/301132_301132.pdf#page=19 Просмотрите параграф 3.3.1. Вот пример поиска минимального значения в массиве.