고른 표본 추출을 통한 병렬 정렬

고른 표본 추출을 통한 병렬 정렬(Parallel Sorting by Regular Sampling, PSRS) 알고리즘은 병렬 정렬 알고리즘의 일종으로 hyper quick sort 알고리즘에 비하여 세 가지 장점이 있다.

• 각각의 프로세스가 갖고 있는 수들의 목록의 길이가 더 비슷하다. 균형이 잘 잡혀 있다.
• 여러 번 반복적으로 키 값을 주고 받지 않는다.
• 프로세스의 수가 $2^{n}$ 꼴이 되지 않아도 동작한다.

알고리즘의 동작

전체적으로 해야 할 일은 n개의 원소들을 p개의 프로세스들이 나누어서 빠른 시간에 정렬하는 것이다. 이것을 하기 위한 PSRS 알고리즘은 다음과 같은 네 단계를 거친다.

각자 순차 빠른 정렬을 하는 단계

만일 $n$개의 원소들을 $p$개의 프로세스들이 서로 나누어 갖고 있지 않다면 각자가 원소들을 나누어 갖는다. 각각의 프로세스는 각자가 갖고 있는 $\lceil n/p\rceil$개 이하의 원소들을 순차(즉, 병렬화 되지 않은) 빠른 정렬을 수행한다. 정렬이 끝나면 각자는 일정하게 $0,{n \over p^{2}},{2n \over p^{2}},\cdots ,{(p-1)n \over p^{2}}$번째 원소들을 표본으로 추출한다.

일정한 표본을 정렬하는 단계

한 프로세스가 각자의 표본을 모아서 정렬한다. 정렬한 후에 $p-1$개의 피봇(pivot)을 추출하는데, $p+\lfloor p/2\rfloor -1,2p+\lfloor p/2\rfloor -1,\cdots ,(p-1)p+\lfloor p/2\rfloor -1$번째 값들을 피봇으로 정한다. 이제 각각의 프로세스들이 $p-1$개의 피봇을 기준으로 원소들을 분리한다.

원소 교환 단계

프로세스들이 서로간에 원소들을 교환한다. i번째 프로세스는 i번째 영역에 있는 원소들을 제외한 나머지 j번째 영역들의 원소들을 각각 j번째 프로세스에 넘겨준다. 교환이 끝나면, 0번 프로세스는 0번째 피봇 이하의 값들을 모두 모아서 갖고, 1번 프로세스는 0번째 피봇 초과, 1번째 피봇 이하의 값들을 갖는다. 그리고 각각의 프로세스는 각자 정렬된 $p$개의 원소 목록을 갖게 된다. $p$개의 영역 중에서 하나는 자신이 원래부터 갖고 있던 것이고 $p-1$개의 영역은 다른 프로세스로부터 받은 것들이다. 한 프로세스가 갖는 원소는 $2n \over p$개를 넘지 않는다. (단, $n$은 모든 프로세스가 가지고 있는 원소 개수들의 합이다.)

합병 단계

각각의 프로세스는 p개의 이미 정렬되어 있는 목록들을 하나로 합병한다. 이제 각각의 프로세스는 전체 원소들이 정렬된 것을 순서대로 나누어 갖고 있는 상태가 된다.

동형효율 분석

동형효율 분석을 하면 확장성 함수는 $p^{C-1}$이 되고 이것은 초월 빠른 정렬 알고리즘의 확장성 함수와 같다. 그러나 PSRS 알고리즘은 프로세스당 담당하는 키의 수가 더 비슷하기 때문에 다 빠르게 수행된다.

같이 보기

• 병렬 컴퓨팅

참고 문헌

• Michael J. Quinn, Parallel Programming in C with MPI and OpenMP, International Edition, McGraw-Hill, 2003, pp 346-349.

외부 링크

• 머리를 내밀어 봅시다: 고른 표본 추출을 통한 빠른 정렬 - C언어와 MPI를 활용한 PSRS 소스 코드