동시 퀵 소트의 구현이 맞습니까?

Question

OpenMP를 사용하여 C++에서 동시 quicksort를 구현했습니다.

#include <omp.h> 
#include <iostream> 
#include <algorithm> 
using namespace std; 

void sort(int *a, int low, int high); 
int partition(int *a, int low, int high); 

class QuickSort { 
    private: 
     int *arr; 
     int len; 

    public: 
     void init(); 
     void Sort(); 
     void Display(); 
}; 

int main() { 
    cout << "Program implementing Quicksort." << endl; 

    QuickSort a; 

    a.init(); 
    a.Sort(); 
    a.Display(); 
} 

void sort(int *a, int low, int high) { 
    if(high < low || low == high) 
     return; 
    if(high == low+1) { 
     if(a[low] > a[high]) 
      swap(a[low], a[high]); 
     return; 
    } 
    int pivotidx = partition(a, low, high); 
    /*for(int i = 0; i < 5; ++i) 
     cout << a[i] << " "; 
    cout << endl;*/ 
    cout << "Pivot element has been placed at correct position: " << pivotidx << " by thread " << omp_get_thread_num() << endl; 
    #pragma omp parallel sections 
    { 
     #pragma omp section 
     { 
      sort(a, low, pivotidx); 
     } 
     #pragma omp section 
     { 
      sort(a, pivotidx+1, high); 
     } 
    } 
} 

int partition(int *a, int low, int high) { 
    int pivot = low; 
    int pivotval = a[low]; 
    int leftpointer = low; 
    int rightpointer = high; 
    while(leftpointer < rightpointer) { 
     while(a[leftpointer] <= a[pivot] && leftpointer <= high) 
      ++leftpointer; 
     if(leftpointer > high) 
      --leftpointer; 
     while(a[rightpointer] >= a[pivot] && rightpointer >= low) 
      --rightpointer; 
     if(rightpointer < low) 
      ++rightpointer; 
     if(leftpointer < rightpointer) 
      swap(a[leftpointer], a[rightpointer]); 
    } 
    a[low] = a[rightpointer]; 
    a[rightpointer] = pivotval; 
    return rightpointer; 
} 

void QuickSort::init() { 
    cout << "Enter the number of elements in the array: "; 
    cin >> len; 

    cout << "Enter the elements of the array: "; 
    arr = new int[len]; 
    for(int i = 0; i < len; ++i) 
     cin >> arr[i]; 
} 

void QuickSort::Sort() { 
    sort(arr, 0, len-1); 
} 

void QuickSort::Display() { 
    cout << "Sorted array is: " << endl; 
    for(int i = 0; i < len; ++i) 
     cout << arr[i] << " "; 
    cout << endl; 
} 

정확히 정렬되어 있지만 실제로 여러 코어에서 실행 중인지 잘 모르겠습니다. 이것을 어떻게 확인할 수 있습니까? 또한, 내 병렬 코드는 상단 대답 here에있는 것과 매우 유사합니다. 거기에 결국 두 스레드보다 병렬 처리를 추출 할 수 없다는 언급이있다 : 그것은 더 많은 스레드와 함께 실행되면, 다른 스레드가 할 일이 없어 그냥 유휴 앉아있을 것입니다. 왜 그래야만하지?

Answer 1

partition에서 미묘한 오류가 :

while(a[leftpointer] <= a[pivot] && leftpointer <= high) 
    ... 
    while(a[rightpointer] >= a[pivot] && rightpointer >= low) 

두 경우 모두, 당신은 바운드에서 할 수있는 a[leftpointer]leftpointer > high 동안, 그렇지 않으면 당신은 가끔 액세스 순서에게 그 수표를 변경해야합니다. 두 번째 while 조건에서도 마찬가지입니다.

또한

독자에게 거짓말을하지 않습니다 leftpointer는 포인터하지만, 인덱스가 아닙니다! 다른 심각한 스타일 문제가 있지만 CodeReview가 아니기 때문에 병렬 처리에 중점을 둡니다.

여기서 병렬 처리 섹션을 사용하는 것이 이상적입니다. 예를 들어, 중첩 된 병렬 처리를 활성화하여 동시에 두 개 이상의 스레드가 활성화되도록해야합니다. 대신 OpenMP 태스크를 사용해야합니다. sort에 대한 각각의 호출마다 작업을 생성하는 것이 좋지 않습니다. 왜냐하면 많은 작은 작업을 생성하고 오버 헤드/작업 비율이 낮기 때문입니다. 대신, 충분히 큰 데이터 청크에 대해서만 작업을 만들고 재귀에서 런타임 오버 헤드가 발생하지 않도록하십시오. 이를 위해 정교한 두 번째 재귀 함수가 최선의 방법입니다 :

void sort_serial(int* a, int low, int high) 
{ 
    if (high < low || low == high) 
     return; 
    if (high == low + 1) 
    { 
     if (a[low] > a[high]) 
      swap(a[low], a[high]); 
     return; 
    } 
    int pivotidx = partition(a, low, high); 
    sort_serial(a, low, pivotidx); 
    sort_serial(a, pivotidx + 1, high); 
} 

void sort(int* a, int low, int high) 
{ 
    if (high < low || low == high) 
     return; 
    if (high == low + 1) 
    { 
     if (a[low] > a[high]) 
      swap(a[low], a[high]); 
     return; 
    } 
    int pivotidx = partition(a, low, high); 

    // This is an arbitrary threshold. 
    if (high - low > 1000000) 
    { 
#pragma omp task 
     { 
      sort(a, low, pivotidx); 
     } 
#pragma omp task 
     { 
      sort(a, pivotidx + 1, high); 
     } 
    } 
    else 
    { 
     sort_serial(a, low, pivotidx); 
     sort_serial(a, pivotidx + 1, high); 
    } 
} 

이 작업을 진행하려면, 당신은 어딘가 병렬 영역을 작성해야합니다 - 보통 예를 들어, 시작하기위한 하나의 스레드를 좁힐 과 같이 :

void QuickSort::Sort() 
{  
#pragma omp parallel 
    { 
#pragma omp single 
     sort(arr, 0, len - 1); 
    } 
} 

큰만큼 입력의

및 임계 값의 좋은 선택이 병렬로 수행 할 수있는 충분한 일을 노출하지만 큰 오버 헤드를 만들지 않습니다.

이 기능이 병렬로 실행되는 방식을 확인하려면 일반적으로 운영 관련 모니터링 도구 (예 : Linux의 경우 time 또한 스레드가 병렬로 작업을 실행하는 방법을 자세하게 설명 할 수있는 정교한 성능 분석 도구를 사용할 수도 있습니다.