pthreads : Parallel Problems(Bonus)

Overview

다음 섹션은 pthreads들이 충돌했을 때 발생하는 일들을 다루고 있습니다 하지만 만약 각각의 쓰레드가 완전히 다른 일을 해 겹치지 않는다면 어떻게 될까요?

maximum speedup parallel problem을 찾았습니다.

Embarassingly Parallel Problems

평형 알고리즘의 연구는 지난 몇년간 많이 증가했습니다. An embarrasiingly parallel problem은 parallel로 바꾸기 위해 매우 쉬운 문제입니다. 이들 중 대부분이 동기화 개념을 가지고 있지만 항상 그런 것은 아닙니다. 당신이 이미 알고 있는 것 중에 Merge sort가 존재합니다.

void merge_sort(int *arr, size_t len){
     if(len > 1){
     //Mergesort the left half
     //Mergesort the right half
     //Merge the two halves
     }

Thread에 대한 새로운 개념을 가지고 merge sort를 구현하기 위해 해야할 일은 left half를 위한 쓰레드와 right half를 위한 thread를 생성하는 것입니다. CPU가 멀피코어라면 Amdahl's Law에 따라 속도가 증가하는 것을 볼 수 있습니다. Time complexity 분석 또한 흥미롭습니다. Parallel algorithm은 O(log^3(n))을 가집니다(많은 코어를 가지고 있다고 가정하기 때문입니다)

실제 상황에서는, 일반적으로 두가지가 바뀝니다. 하나는 array가 일단 충분히 작아지면, parallel mergesort algorithm 대신에 quick sort나 다른 알고리즘을 사용합니다. 작은 array에 대해서는 이 알고리즘들이 더 빠르기 때문입니다. 또 다른 하나는 CPU는 무한개의 core를 가지고 있을 수없습니다. 이 문제를 해결하기 위해 일반적으로 worker pool을 이용합니다.

Worker Pool

우리는 CPU가 한정된 수의 core를 가지고 있다고 알고 있습니다. startup하는데 많은 시간은 많은 수의 쓰레드를 생산하고 idle인 상태로 작업을 주는데 사용됩니다.

Another problem, Parallel Map

전체 array에 함수를 적용할 때, 한 번에 한개의 원소에만 적용한다고 생각해봅시다.

int *map(int (*func)(int), int *arr, size_t len){
    int *ret = malloc(len*sizeof(*arr));
    for(size_t i = 0; i < len; ++i) 
        ret[i] = func(arr[i]);
    return ret;
}

어떤 원소도 배열의 다른 원소들에게 의존적이지 않으므로, 어떻게 병렬화할 수 있을까요? 쓰레드간에 작업을 나눠주는 최고의 방법은 무엇을까요?

Scheduling

아래에는 작업을 나눠주는 몇가지 방법이 있습니다.

• static scheduling: 미리 정해진 고정된 사이즈의 덩어리로 문제들을 나눕니다. 그러고 각각의 쓰레드는 이 덩어리들에 대해서 작업합니다. 이러한 방식은 subproblem들이 대략 비슷한 시간이 걸린다면 잘 동작합니다(다른 overhead가 필요 없으므로). loop를 작성하고 각각의 subarray에 map function만을 제공하면 끝납니다.
• dynamic scheduling: 새로운 문제가 발생하면 쓰레드가 처리합니다. 이것은 스케쥴링이 얼마나 오래 걸릴지 모를 때 유용합니다.
• guided scheduling: 위의 두가지 방식의 장점과 단점을 조합했습니다. static scheduling으로 시작해서 필요에 의해 천천히 dynamic scheduling으로 이동합니다.
• runtime scheduling: 문제가 해결되는데 얼마나 걸릴지 아무것도 알 수 없을때, 사용자가 결정하는 대신 프로그램이 무엇을 할지 결정하게 합니다.

Few Drawbacks

cache coherency나 scheduling extra threads등과 같은 일 때문에 즉각적인 speedup을 볼 수는 없습니다.