사용자:Only2sea/작업/작업장2

일정한 표본 추출을 통한 병렬 정렬(Parallel Sorting by Regular Sampling, a.k.a PSRS) 알고리즘은 X. Li 등이 개발한 병렬 정렬 알고리즘의 일종으로 초월 빠른 정렬 알고리즘에 비하여 세 가지 장점이 있다.

• 각각의 프로세스가 갖고 있는 수들의 목록의 길이가 더 비슷하게 된다.
• 여러 번 반복적으로 키 값을 주고 받지 않는다.
• 프로세스의 수가 2의 n 승 꼴이 되지 않아도 동작한다.

알고리즘의 동작

PSRS 알고리즘은 4가지 단계를 거친다.

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

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

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

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

원소 교환 단계

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

합병 단계

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

동형효율 분석

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

같이 보기

• 병렬 컴퓨팅

참고 문헌

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