OpenMP 중첩 루프 병렬 처리

Question

OpenMP를 사용하고 잘못된 결과에 문제가 있습니다. 왜 wrond 결과를 얻고, 당신은 어떻게 생각하십니까

#pragma omp parallel shared(L,nthreads,chunk) private(tid,i,j){ 
     tid = omp_get_thread_num(); 
     if (tid == 0) 
     { 
      nthreads = omp_get_num_threads(); 
      printf("Starting matrix multiple example with %d threads\n",nthreads); 
      printf("Initializing matrices...\n"); 
     } 

     #pragma omp for schedule (static, chunk) 
     for(i=0; i<SIZE_A;i++){ 
      for(j=0; j<SIZE_B;j++){ 
       if(A[i]==B[j]){ 
        if(i==0 || j==0) 
         L[i][j]=1; 
        else 
         L[i][j] = L[i-1][j-1] + 1; 
       } 
       // or reset the matching score to 0 
       else 
        L[i][j]=0; 
      } 
     } 
    } 

: 여기

코드인가? 무엇을 변경해야합니까?

고마워요!

Answer 1

당신은 루프 데이터 의존성이 있습니다 interations i 및 i-1가 다른 스레드에 할당 된 경우 여기

L[i][j] = L[i-1][j-1] + 1; 

를, 다음 두 번째는 이렇게 시작하기 전에 첫 번째 스레드가 완료 것이라는 보장은 없습니다 두 번째 스레드는 L[i-1][j-1]의 올바르지 않은 (여전히 업데이트되지 않은) 값을 읽습니다. omp for worksharing 지정 문에 ordered 절을 지정하여 실행 순서를 지정할 수는 있지만 병렬 처리가 중단됩니다.

의존성이 대각이기 때문에 행 방식 대신 대각선으로 L을 걷는 알고리즘을 다시 생각해 볼 수 있습니다.