최소, 최대, 중간, 평균에 대한 OpenMp C++ 알고리즘

Question

몇 가지 간단한 OpenMp 알고리즘을 제공하는 페이지를 Google에서 검색하고있었습니다. 아마도 거대한 데이터 배열로부터 최소, 최대, 중앙값, 평균을 계산하는 예제가 있지만 그것을 찾을 수는 없습니다.

적어도 나는 각 코어에 대해 하나의 청크로 배열을 분할하고 나중에 전체 배열에 대한 결과를 얻기 위해 경계 계산을 시도합니다.

나는 바퀴를 재발 명하고 싶지 않았습니다.

---

추가 비고 : 나는 간단한 감소와 함께 작동 예 수천이 있다는 것을 알고있다. 예 : 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; 

그러나 이러한 종류의 알고리즘을 사용할 수없는 경우 알고리즘을 줄이기위한 예제가 거의 없습니다.

Answer 1

OpenMP (최소 2.0)는 몇 가지 간단한 연산에서는 감소를 지원하지만 최대 및 최소에서는 지원하지 않습니다.

다음 예제에서는 reduction 절을 사용하여 합계를 만들고 critical 섹션을 사용하여 스레드 로컬 하나를 사용하여 공유 변수를 업데이트합니다 (충돌없이).

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

편집 : 깨끗한 구현 : OpenMP를 3.1

#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

이것은 일반적인 감소 문제입니다.

the page pointed by Suvesh 외에도 reduction clause에 대한 설명서를 볼 수 있습니다.

Answer 3

OpenMP는 이러한 축소 작업을 지원하지 않습니다. 임의의 알고리즘을 구현할 수있는 인텔 스레딩 구성 요소의 parallel_reduce 알고리즘을 고려하십시오.

여기 예입니다. 부분 결과의 합계를 사용합니다. 원하는 기능을 구현할 수 있습니다.

#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 절을 살펴보십시오. 배열에 최소값을 찾는 예제가 있습니다.

Answer 4

는 이후 한 분 구현할 수 감소 절을 통해 최대, 당신은 this link이를 포함하는 자세한 예를 살펴 수 있습니다.