멀티코어컴퓨팅 - 7. Divide-and-Conquer for Parallelization

Divide-and-Conquer for Parallelization

총 네개의 쓰레드로 각각 구간의 합을 구해서 마지막에 메인 쓰레드가 결과들을 취합해 ans를 도출했다고하자.

만약 쓰레드가 1000개라면 메인쓰레드는 결과 취합을 위해 1000번의 덧셈을 수행해야 한다. 

그리고 구간을 공평하게 나누는 일도 사실 모든 경우에 쉽지 않다. 설령 구간을 공평하게 나누었더라도 좀 더 쉬운 부분을 할당받은 쓰레드는 쉬는 경우가 생길 수 있다.

 

그래서 divide conquer 알고리즘을 적용해서 더 현실적이고 효율적인 parallel summation을 수행해보자.

메인 쓰레드가 구간을 반으로 쪼갠다 -> 쓰레드 두 개 t1, t2 생성 -> t1, t2가 가져오는 결과를 합산

 

t1이 구간을 반으로 쪼갠다 -> 쓰레드 두개 t11, t12 생성 -> t11, t12가 가져오는 결과를 합산 -> 날 호출한 녀석에게 결과 반환

t2가 구간을 반으로 쪼갠다 -> 쓰레드 두개 t21, t22 생성 -> t21, t22가 가져오는 결과를 합산 -> 날 호출한 녀석에게 결과 반환

 

이렇게 재귀적으로 쓰레드를 생성하고 구간을 나누어 계산을 시킨 다음 결과를 차근차근 반환하도록 한다.

언제까지 구간을 쪼갤 것인지 종료 조건을 잘 설정해야 한다.

 

이렇게 분할정복 알고리즘으로 병렬 처리를 수행하면 전체 시간 복잡도는 O(logn)으로 낮다.

하지만 thread를 너무 많이 생성해버리면 오히려 thread끼리의 communication overhead가 커지기 때문에 cutoff 구간 길이까지만 분할을 수행하도록 하자.