OpenMP로 루핑하는 동안 스레드 안전성

Question

나는 C++과 GMP를 사용하여 작은 Collatz conjecture calculator에서 작업하고 있으며 OpenMP를 사용하여 병렬 처리를 구현하려고 시도하고 있지만 스레드 안전과 관련하여 문제가 발생합니다. 약자로, 코드를 실행하려고하면이를 얻을 것입니다 :

*** Error in `./collatz': double free or corruption (fasttop): 0x0000000001140c40 *** 
*** Error in `./collatz': double free or corruption (fasttop): 0x00007f4d200008c0 *** 
[1] 28163 abort (core dumped) ./collatz 

이 동작을 재현 할 수있는 코드입니다.

#include <iostream> 
#include <gmpxx.h> 

mpz_class collatz(mpz_class n) { 
    if (mpz_odd_p(n.get_mpz_t())) { 
     n *= 3; 
     n += 1; 
    } else { 
     n /= 2; 
    } 
    return n; 
} 

int main() { 
    mpz_class x = 1; 
#pragma omp parallel 
    while (true) { 
     //std::cout << x.get_str(10); 
     while (true) { 
      if (mpz_cmp_ui(x.get_mpz_t(), 1)) break; 
      x = collatz(x); 
     } 
     x++; 
     //std::cout << " OK" << std::endl; 
    } 
} 

내가 느린 화면 할 수있는 출력을, 주석을 해제 때이 오류가 발생하지 않았다는 것을 감안할 때, 나는 스레드 안전과 관련이있다 손에 문제를 가정, 동시 스레드가 x을 증가하는 것을 시도와 특히 동시에.

내 가정에서 정확합니까? 이 문제를 어떻게 해결하고 안전하게 실행할 수 있습니까?

Answer 1

나는 당신이하고 싶은 일은 collatz 추측이 모든 숫자에 대해 유효한지 확인하는 것입니다. 게시 한 프로그램이 여러 단계에서 순차적으로나 병렬 적으로 잘못되었습니다.

if (mpz_cmp_ui(x.get_mpz_t(), 1)) break; 

x != 1 일 때 중단됩니다. 올바른 0 == mpz_cmp_ui으로 바꾸면 코드가 계속해서 2을 반복해서 테스트합니다. 어쨌든 두 개의 변수가 있어야합니다. 하나는 검사하려는 항목을 나타내는 외부 루프 용이고 다른 하나는 검사를 수행하는 내부 루프 용입니다. 해당하는 기능을 할 경우이 권리를 얻을 쉽게 :

void check_collatz(mpz_class n) { 
    while (n != 1) { 
     n = collatz(n); 
    } 
} 

int main() { 
    mpz_class x = 1; 
    while (true) { 
     std::cout << x.get_str(10); 
     check_collatz(x); 
     x++; 
    } 
} 

while (true) 루프 추론 및 병렬, 그래서 그냥 동등한 for 루프 할 수 있도록 나쁜 : 이제

for (mpz_class x = 1;; x++) { 
    check_collatz(x); 
} 

을, 우리는 병렬 코드에 대해 이야기 할 수 있습니다. OpenMP 병렬 처리의 기본은 작업 공유 구조입니다. while 루프에서 #pragma omp parallel을 때 리면 안됩니다. 다행스럽게도 #pragma omp parallel for을 사용하여 특정 for 루프를 쉽게 표시 할 수 있습니다. 이를 위해, 그러나, 당신은 루프 변수로 mpz_class 사용할 수 없습니다, 당신은 루프의 종료를 지정해야합니다 check 암시 비공개

#pragma omp parallel for 
for (long check = 1; check <= std::numeric_limits<long>::max(); check++) 
{ 
    check_collatz(check); 
} 

하는 것으로,이 작업을 각 스레드에 대한 사본이있다. 또한 OpenMP는 작업을 배포하는 것을 담당 할 것입니다 [1 ...2^63]이 (가) 있습니다. 스레드가 check_collatz을 호출하면 새로운, 개인용 mpz_class 개체가 생성됩니다.

이제 루프 반복마다 새로운 mpz_class 개체를 반복적으로 만드는 것이 값 비싼 (메모리 할당) 것을 알 수 있습니다. 다시 check_collatz을 깨고 스레드 전용 (thread-private) mpz_class 작업 객체를 만들어 재사용 할 수 있습니다. 병렬 지역에서 x를 선언하는이 암시 적으로 개인 있는지 확인하고 적절하게 초기화됩니다

#include <gmpxx.h> 
#include <iostream> 
#include <limits> 

// Avoid copying objects by taking and modifying a reference 
void collatz(mpz_class& n) 
{ 
    if (mpz_odd_p(n.get_mpz_t())) 
    { 
     n *= 3; 
     n += 1; 
    } 
    else 
    { 
     n /= 2; 
    } 
} 

int main() 
{ 
#pragma omp parallel 
    { 
     mpz_class x; 
#pragma omp for 
     for (long check = 1; check <= std::numeric_limits<long>::max(); check++) 
     { 
      // Note: The structure of this fits perfectly in a for loop. 
      for (x = check; x != 1; collatz(x)); 
     } 
    } 
} 

주 :이 경우, 별도의 parallel 및 for 프라그 마를로 화합물 parallel for을 분할합니다. 밖에서 선언하고 그것을 private으로 표시하는 것이 좋습니다. 이것은 외부 범위의 명시 적 private 변수가 단위 화되기 때문에 종종 혼동을 일으킬 수 있습니다.

첫 번째 2^63 숫자 만 확인한다고 불평 할 수 있습니다. 그냥 실행하자. OpenMP를 전문가 수준으로 마스터하고 GMP 객체에 대한 사용자 정의 작업 공유를 작성할 수있는 충분한 시간을 제공합니다.

각 스레드에 대해 여분의 개체가있는 것에 대해 우려했습니다. 좋은 성능을 위해 필수입니다. 잠금/임계 구역/원자 (atomics)로는 이것을 효율적으로 해결할 수 없습니다. 각각의 모든 변수를 보호해야합니다. 을 읽고 관련 변수에만 쓰십시오. 평행법은 남지 않을 것입니다.

참고 : 거대한 for 루프에는로드 불균형이있을 수 있습니다. 따라서 일부 스레드는 다른 스레드보다 수 세기 앞당겨 질 것입니다. 동적 스케쥴링이나 더 작은 정적 청크로 해결할 수 있습니다.

편집 : 학업을 위해, 여기 GMP 객체에서 직접 작업 공유를 구현하는 방법을 하나 개의 아이디어는 :

#pragma omp parallel 
    { 
     // Note this is not a "parallel" loop 
     // these are just separate loops on distinct strided 
     int nthreads = omp_num_threads(); 
     mpz_class check = 1; 
     // we already checked those in the other program 
     check += std::numeric_limits<long>::max(); 
     check += omp_get_thread_num(); 
     mpz_class x; 
     for (; ; check += nthreads) 
     { 
      // Note: The structure of this fits perfectly in a for loop. 
      for (x = check; x != 1; collatz(x)); 
     } 
    } 

Answer 2

x과의 충돌이 맞을 수도 있습니다.

#pragma omp parallel private(x) 

각 스레드가이 스레드 안전해야한다 변수 x, 자신의 "버전"을 얻는이 방법을 : 당신은에 의해 비공개로 x를 표시 할 수 있습니다. 기본적으로 #pragma omp parallel 앞에 선언 된 변수는 public이므로 모든 스레드 사이에 하나의 공유 인스턴스가 있습니다.

Answer 3

x을 터치하면 원자 적 지시 만 가능합니다.

#pragma omp atomic 
x++; 

이 뮤텍스 또는 다른 동기화 기술을 필요로하지 않고 모든 스레드 x 동일한 값이 표시되도록.