병합 정렬 (pthreads) C++

Question

나는 pthreads에 다소 익숙하며 1 백만 개의 무작위로 생성 된 정수를 정렬하는 프로그램을 만들려고합니다. 나는 스레드에 대해 약간의 통제력을 상실한 것 같다. 처음 실행될 때 코드는 단일 스레드 만 생성하지만 이후에 실행될 때 스레드는 스레드를 제어 할 수 없게됩니다. 문제가 어디에 있는지 정확히 알지 못하기 때문에 아래 코드를 제공했습니다.

#include <unistd.h> 
#include <stdio.h> 
#include <stdlib.h> 
#include <pthread.h> 
#include <iostream> 

#define N   8   /* # of thread */ 
#define NUM_INTS 10000  //ideally should be able to sort 1,000,000 

int int_list[NUM_INTS]; 

/* structure for array index 
* used to keep low/high end of sub arrays 
*/ 
typedef struct Arr { 
    int low; 
    int high; 
} ArrayIndex; 

void merge(int low, int high) { 
    int mid = (low+high)/2; 
    int left = low; 
    int right = mid+1; 

    int list_b[high-low+1]; 
    volatile int i, cur = 0; 

    while((left <= mid) && (right <= high)) { 
     if (int_list[left] > int_list[right]) 
      list_b[cur++] = int_list[right++]; 
     else 
      list_b[cur++] = int_list[right++]; 
    } 

    while(left <= mid) 
     list_b[cur++] = int_list[left++]; 

    while(right <= high) 
     list_b[cur++] = int_list[left++]; 

    for (i = 0; i < (high-low+1) ; i++) 
     int_list[low+i] = list_b[i]; 
} 

void * mergesort(void *a){ 
    ArrayIndex *pa = (ArrayIndex *)int_list; 
    int mid = (pa->low + pa->high)/2; 

    ArrayIndex aIndex[N]; 
    pthread_t thread[N]; 

    aIndex[0].low = pa->low; 
    aIndex[0].high = mid; 

    aIndex[1].low = mid+1; 
    aIndex[1].high = pa->high; 

    if (pa->low >= pa->high) 
     return 0; 

    volatile int i; 
    for(i = 0; i < N; i++) 
     pthread_create(&thread[i], NULL, mergesort, &aIndex[i]); 

    for(i = 0; i < N; i++) 
     pthread_join(thread[i], NULL); 

    merge(pa->low, pa->high); 

    pthread_exit(NULL); 
} 

int main(){ 
    volatile int i; 
    struct timeval start_time, end_time; 

    srand(getpid()); 

    for(i=0; i<NUM_INTS; i++) 
     int_list[i] = rand(); 

    ArrayIndex ai; 
    ai.low = 0; 
    ai.high = NUM_INTS/sizeof(int_list[0])-1; 
    pthread_t thread; 

    pthread_create(&thread, NULL, mergesort, &ai); 
    pthread_join(thread, NULL); 

    return 0; 
} 

GDB 출력 :

(gdb) run 
Starting program: /.../sort.o 
[Thread debugging using libthread_db enabled] 
Using host libthread_db library "/lib/x86_64-linux-gnu/libthread_db.so.1". 
[New Thread 0x7ffff6fd5700 (LWP 25801)] 
[Thread 0x7ffff6fd5700 (LWP 25801) exited] 

Computation Time: 38006 micro-seconds. 
[Inferior 1 (process 25797) exited normally] 
(gdb) run 
Starting program: /.../sort.o 
[Thread debugging using libthread_db enabled] 
Using host libthread_db library "/lib/x86_64-linux-gnu/libthread_db.so.1". 
[New Thread 0x7ffff6fd5700 (LWP 25804)] 
[New Thread 0x7ffff67d4700 (LWP 25805)] 
[New Thread 0x7ffff5fd3700 (LWP 25806)] 
[New Thread 0x7ffff57d2700 (LWP 25807)] 
[New Thread 0x7ffff4fd1700 (LWP 25808)] 
[New Thread 0x7fffef7fe700 (LWP 25811)] 
[New Thread 0x7fffeeffd700 (LWP 25810)] 
... 
[New Thread 0x7ffeca6ec700 (LWP 26148)] 

Program received signal SIGINT, Interrupt. 
[Switching to Thread 0x7ffee8728700 (LWP 26088)] 
__GI___nptl_create_event() at events.c:25 
25 events.c: No such file or directory. 

Answer 1

문제는 스레드 지점 때까지 각 하위 문제에 대한 새 스레드를 시작하여 재귀 분할 정복의 병렬 처리를 구현하려고한다는 것입니다 "정렬"할 단일 배열 항목이 제공됩니다. 이 접근법은 여러 가지 이유로 인해 명백히 잘못되었습니다. 하나만 제공하면 100 만 개 항목의 배열을 정렬하려면 리프 호출시 100 만 개의 스레드가 필요하고 위의 모든 재귀 수준에서는 100 만 개의 스레드가 필요합니다. 재귀가 연속되는 임계 값 인 그레인 크기를 도입하더라도 임계 값이 NUM_INTS/N이 아닌 한 스레드의 총량은 여전히 ​​매우 커질 수 있습니다.

은 당신의 구현은 몇 가지 버그를 가지고, 위의 계산하지 :

재귀의 각 수준에서

• , 당신은 N 스레드를 시작, 작업이 단지 절반으로 분할하더라도. aIndex[i]은 i> 1에서 초기화되지 않으므로 해당 스레드는 입력 매개 변수에서 가비지를 수신합니다.
• int에 대한 포인터 인 int_list을 ArrayIndex에 대한 포인터로 캐스팅합니다.

당신이 디자인을 해결할 수 방법 몇 가지 방법이 있습니다 :

• 단순한 하나는 재귀 직렬되고, 그 후에 제가 위에서 말했듯이, 적절한 임계 값을 소개하는 것입니다.
• 더 복잡한 것이지만보다 일반적이며 유연한 것은 스레드 풀과 스레드가 처리하는 풀/큐를 구현하는 것입니다. 주어진 배열을 반으로 나눌 때 각 반을 처리하기위한 두 개의 작업을 생성하고 스레드가 작업을 수행하는 작업 대기열에이 작업을 제출합니다. 좋은 성능을 얻으려면 작업 당 충분한 양의 작업을 수행하기 위해 약간의 입자 크기를 설정해야하지만 스레드 수를 제한하는 데 필요한 것보다 훨씬 작은 임계 값이 필요합니다.
• 오른쪽 코드는 특히 Intel's Threading Building Blocks (tbb) 또는 Microsoft의 병렬 패턴 라이브러리 (ppl)와 같은 재귀 적 병렬성을위한 적절한 기본 요소가있는 라이브러리 또는 병렬 기술을 사용하는 것입니다.

페이지의 일부 링크는 (일반적으로, 구글 "병렬 병합 정렬 C++")

• performance problems in parallel mergesort C++
• https://software.intel.com/en-us/articles/a-parallel-stable-sort-using-c11-for-tbb-cilk-plus-and-openmp
• http://www.drdobbs.com/parallel/parallel-merge-sort/229400239