OpenMP 작업 지시문을 사용하여 PI 계산

Nov 15 2020

OpenMP 작업 지시문과 함께 π 에 대한 Leibniz 공식을 사용하여 숫자 π 를 계산하는 코드를 병렬화해야합니다.

라이프니츠 공식

그래서 순차 코드를 얻었습니다.

double sequential_execution(long long n)
{
    long long i;
    double factor;
    double sum = 0.0;
    double startTime = omp_get_wtime();

    for (i = 0; i < n; i++) {
        factor = (i % 2 == 0) ? 1.0 : -1.0;
        sum += factor / (2 * i + 1);
    }
    double endTime = omp_get_wtime();
    printf("Sequential execution took %f seconds\n", endTime - startTime);
    sum = 4.0 * sum;
    return sum;
}

첫 번째 아이디어는 for 루프의 내용을 n = 100000000 인 단일 작업으로 캡처하는 것이 었습니다.

double parallel_execution(long long n)
{
    long long i=0;
    double factor;
    double sum = 0.0;
    long long index; 
    long squareRootN = ceil(sqrt(n));

    double startTime = omp_get_wtime();
#pragma omp parallel default(none) private(i,factor) shared(n,sum) 
{
    #pragma omp single
    {
        for ( i = 0; i < n; i++) {
            #pragma omp task
            {
                factor = (i % 2 == 0) ? 1.0 : -1.0;
                #pragma omp atomic
                sum += factor / (2 * i + 1);
            }
        }
    }
}
    double endTime = omp_get_wtime();
    printf("Parallel execution took %f seconds\n", endTime - startTime);
    sum = 4.0 * sum;
    return sum;
}

하지만 순차 실행은 훨씬 더 빨랐습니다 (시퀀스 시간 : 0.3 초, Par. 시간 : 87 초).

두 번째 아이디어는 하나의 작업의 세분성을 높이고 0에서 n-1로가는 하나의 for 루프가 각각 0에서 sqrt (n) -1로가는 두 개의 중첩 된 루프로 분할되는 방식으로 작업의 수를 줄이는 것입니다. 이제 각 작업에는 0에서 sqrt (n) -1로 이동하는 for 루프가 있으며, n = 100000000에 대해 다시 sqrt (n) 작업이 생성됩니다.

double parallel_execution(long long n)
{
    long long i=0;
    double factor;
    double sum = 0.0;
    long long index; 
    long squareRootN = ceil(sqrt(n));

    double startTime = omp_get_wtime();
#pragma omp parallel default(none) shared(sum,n,squareRootN) private(i,factor,index)
{
    #pragma omp single
    {
        for (i=0;i<squareRootN;i++)
        #pragma omp task
        {
            for (long j=0;j<squareRootN;j++)
            {
                index = i*squareRootN + j;
                if (index > n) break;
                factor = (index % 2 == 0)?1.0 : -1.0; 
                #pragma omp atomic
                sum += factor / (2*index + 1);
            }
        }
    }
}
    double endTime = omp_get_wtime();
    printf("Parallel execution took %f seconds\n", endTime - startTime);
    sum = 4.0 * sum;
    return sum;
}

이제 더 좋은 시간을 얻었지만 순차 실행 (Seq : 0.3s, Par : 11s)보다 훨씬 느 렸습니다.

이 시점에서 작업 지시문을 사용하여 속도를 높일 수 없다고 생각하기 시작했지만 다시 한 번 내가 잘못한 것이 있거나 더 나은 성능을 얻기 위해 문제를 재구성하는 방법이 있습니까? 감사

편집 : 지금까지 최고의 기능 :

double parallel_execution(long long n)
{
    double factor;
    int totalThreads = 0;
    long squareRootN = ceil(sqrt(n));
    double master_sum = 0;
    double *sum;
    double startTime = omp_get_wtime();
#pragma omp parallel default(none) shared(sum,n,squareRootN,totalThreads) private(factor)
{
    #pragma omp single
    {
        totalThreads = omp_get_num_threads();
        sum = (double*)calloc(totalThreads,sizeof(double));
        for (long long i=0;i<squareRootN;i++)
        #pragma omp task
        {
            for (long long j=0;j<squareRootN;j++)
            {
                long long index = i*squareRootN + j;
                if (index > n) break;
                factor = (index % 2 == 0)?1.0 : -1.0; 
                sum[omp_get_thread_num()] += factor / (2*index + 1);
            }
        }
    }
}
    for (int i=0;i<totalThreads;i++) master_sum += sum[i];
    double endTime = omp_get_wtime();
    printf("Parallel execution took %f seconds\n", endTime - startTime);
    master_sum*=4;
    return master_sum;
}

입력 크기 : n = 1000000000 Seq. 시간 : 3.19s Par. 시간 : 4 초

답변

1 dreamcrash Nov 15 2020 at 21:41

당신이하는 지불 의 오버 헤드 atomic작동과 작업 작성 및 관리합니다. parallel for감소 를 통해 더 간단하게 더 나은 속도를 얻을 수 있습니다 .

#pragma omp parallel default(none) shared(n) reduction( + : sum ) 
for ( i = 0; i < n; i++) {
     double factor = (i % 2 == 0) ? 1.0 : -1.0;
     sum += factor / (2 * i + 1);
}

사전에 짝수와 배당률을 분리하여 순차 코드를 약간 개선 할 수 있습니다.

#pragma omp parallel default(none) shared(n, sum) nowait
{
     #pragma omp for reduction( + : sum ) 
     for (int i = 0; i < n; i+=2 ) {
        sum += 1.0 / (2 * i + 1);
    }
    #pragma omp for reduction( + : sum ) 
    for (int i = 1; i < n; i += 2) {
        sum += -1.0 / (2 * i + 1);
    }
}

해당 루프의 각 반복에 대해 짝수 및 승산 계산을 수행 하는 단일 루프 를 사용 하여 더 개선 할 수 있습니다 .

'i'루프에서 만들 필요는 없으며 OpenMP에 private암시 적 private으로 있습니다 .

당신이 경우 정말 작업을 사용해야합니다, 당신은 변수 복제하여 동기화 오버 헤드를 최소화하기 위해 시도 할 수 있습니다 sum스레드 사이를, 그리고의 마지막에 수동으로 감소 parallel region(나는 가정하고, n >= 2하고 n있는 even단지 단순 위해) :

double sum[total_threads];

#pragma omp parallel default(none) shared(n, sum)
{
    int threadID = omp_get_thread_num();
    sum[threadID] = 0.0;
    #pragma omp single
    {
        for ( i = 0; i < n; i+=2) {
            #pragma omp task
            {
                sum[threadID] += 1.0 / (2 * i + 1);
                sum[threadID] += -1.0 / (2 * (i + 1) + 1);
            }
        }
    }
  }

double master_sum = 0.0;
for(int i = 0; i < total_threads; i++)
    master_sum += sum[i];

COpenMP를 지원 하는 컴파일러를 4.5사용하는 경우보다 정교한 생성자, 즉를 사용하고 taskloop Construct이를 reduction변수의 와 결합 할 수 sum있습니다.