C로 작성된 quicksort의 레이싱 조건이 OpenMP와 병렬 처리 됨

이 빠른 구현에서 나는 실행중인 프로그램이 내가 이해할 수없는 근본적인 경쟁 조건에 빠지게된다고 생각합니다. 그래서 나는 지도력을 위해 SO 커뮤니티에 몸을 돌린다.C로 작성된 quicksort의 레이싱 조건이 OpenMP와 병렬 처리 됨

quicksort()에서 for-loop 앞에 "#pragma omp parallel for private (i)"을 제거하면 제대로 정렬됩니다.

다음은 정렬 샘플 및 코드입니다.

Unsorted 
3 6 7 5 3 5 6 2 9 1 

Sorted 
0 1 2 3 3 5 6 7 9 5 



    size_t average (size_t a, size_t b) 
    { 
      return (a + b)/2; 
    } 

    void swap (int *array, size_t x, size_t y) 
    { 
      int tmp; 
      tmp = array[x]; 
      array[x] = array[y]; 
      array[y] = tmp; 
    } 

    void quicksort (int *array, int left, int right) 
    { 
      int i, last; 

      if (left >= right) 
      { 
        return; 
      } 

      swap (array, left, average(left, right)); 
      last = left; 

      #pragma omp parallel for private(i) 
      for (i = left + 1; i <= right; i++) 
      { 
        if (array[i] < array[left]) 
        { 
          #pragma omp critical 
          { 
            last++; 
          } 
          swap(array, last, i); 
        } 
      } 

      swap (array, left, last); 

      #pragma omp parallel sections 
      { 
        #pragma omp section 
        { 
          quicksort(array,left,last-1); 
        } 

        #pragma omp section 
        { 
          quicksort (array, last+1, right); 
        } 
      } 
    }

출처

2012-02-15 Igor Eklund