대용량 데이터를 처리해야 하는 툴을 만들다 보니 데이터 처리 관련 알고리즘이나 성능 좋은 방법 등을 많이 고민하고 공부하게 된다. 이 방법들 중 데이터 처리에 있어 많은 비용을 지불해야 하는 정렬에 대하여 이야기 하고 싶다.
우리나라 사람들 성질이 급해서 그런지 뭐든 빨리 나오길 바란다. 정렬도 예외가 아니다. 얼마 안 되는 데이터를 정렬한다면 로직이 좋던 나쁘던 별반 차이나지 않지만 데이터가 커지면 이 차이는 무시 못 할 정도로 벌어진다. 그리고 데이터 처리에 있어 정렬은 아주 큰 부분은 차지하기 때문에 할 수 있다면 할 수 있는 만큼은 개선을 해야 할 부분이다. (어떤 사람은 십수년이 넘는 기간동안 정렬만 연구해 솔루션을 내 놓는 경우도 있으며, 난 이 사람 마음을 십분 이해한다. 정렬은 그럴 만한 가치가 충분히 있다.)
(앞으로의 내용은 개인적으로 분석하여 나온 것임을 미리 밝힌다.)
프로세스 하나만 쓸 경우 가장 빠른 정렬 알고리즘은 Quick Sort이다. Bubble Sort, Insertion Sort, Selection Sort 등등등 여러 가지 정렬 방법이 있지만 내가 해본 것 중 제일 빠른 것은 Quick Sort이다. Quick Sort는 Unstable한 정렬 방법이여서 이론상 수행 시간이 같고 Stable한 방법인 Merge Sort가 나을 것 같았는데 실제 구현해 보면 Quick Sort만큼 속도가 나오지 않는다. 참고로 Unstable하다는 것은 같은 값의 데이터들이 있을 경우 이들의 순서가 원래 순서대로 보장되지 않는다는 뜻이다.
프로세스를 여러 개 사용하여 정렬할 수 있는 알고리즘으로 Sheer Sort, Merge Sort 등 여러 방법들이 있다. 이 중 괜찮다는 것들을 구현해서 테스트 해 봤는데 구현을 잘못했는지 생각만큼 성능이 나오지 않았다. 여러 프로세스가 한 작업을 같이 수행할 때 처리해야 할 데이터 공유 방법이라든지 각 프로세스의 작업이 고루 분배되게 하는 방법 등을 잘 고려해서 해야 하는데 이런 점에서 실패했던 것 같다.
Quick Sort를 기본으로 한 병렬 소팅 방법도 있다. Quick Sort가 Pivot Value를 하나 잡은 다음 이 값보다 큰 그룹, 작은 그룹을 나눠 각 그룹마다 또 Pivot Value를 잡아 비교하여 그룹지어 나가는 방법이므로 그룹 지어진 부분을 여러 프로세스가 나누어 작업을 하게 되면 병렬로 정렬을 수행할 수 있다. 싱글 프로세싱 환경에서 보통의 경우 가장 빠른 정렬 알고리즘이므로 이를 병렬로 처리하게 되면 다른 병렬 알고리즘 보다 더 좋은 성능을 보이지 않을까 생각해 본다.
Parallel QuickSort
다음과 같은 데이터가 있다고 해보자.
원본데이터: 23 65 13 02 07 99 47 26 10 13 85 18 90 96 95 78 70 73 59 38
1. 각 데이터를 프로세스 개수만큼 나눈다.
프로세스 4개라고 가정하면 다음과 같이 나눌 수 있다.
P1: 23 65 13 02 07
P2: 99 47 26 10 13
p3: 85 18 90 96 95
p4: 78 70 73 59 38
2. P1에서 Pivot value를 선택하여 다른 프로세스에 알려준다. 랜덤하게 선택하는 것이 일반적임.
23를 pivot value로 선택했다고 하자.
3. 프로세스를 짝으로 묶고 지정된 pivot value 보다 작거나 같은 값은 앞쪽, 큰 값은 뒤쪽으로 이동한다.
(P1, P3), (P2, P4)를 짝으로 묶고 지정된 pivot value 23비교하여 작거나 같은 값은 P1, P2 쪽으로 큰값은 P3, P4로 이동 시킨다. 그러면 다음과 같이 그룹핑된 값이 변한다.
P1: 23 13 02 07 18
P2: 10 13
P3: 65 85 90 96 95
P4: 99 47 26 78 70 73 59 38
4. 작은 쪽의 값을 가지고 있는 P1, P2 중 P1에서 새로운 Pivot value를 구하고 큰 값을 가지고 있는 P3, P4 중 P3에서도 새로운 Pivot value를 구한다.
P1에서 13, P3에서 90의 값을 pivot value로 선택하였다고 하자.
5. 선택된 pivot value를 다른 프로세스에 알려준다.
P2에 새로운 pivot value 13을, P4에 90을 알려준다.
6. 3에서와 마찬가지로 새로 지정된 pivot value보다 작거나 같은 값은 앞쪽, 큰 값은 뒤쪽으로 이동한다.
(P1, P2), (P3, P4)가 짝이 되고 각각 13, 90을 기준으로 값을 이동한다.
P1: 13 02 07 10 13
P2: 23 18
P3: 65 85 90 47 26 78 70 73 59 38
P4: 96 95 99
7. 각 프로세스는 자신에게 할당된 값을 정렬한다.
최종 할당된 값을 정렬하면 다음과 같이 된다.
P1: 02 07 10 13 13
P2: 18 23
P3: 26 38 47 59 65 70 73 78 85 90
P4: 95 96 99
8. 정렬된 결과를 하나로 합치면 정렬 완료!!
한 프로세스에서 QuickSort를 수행하는 것 보다는 빠르겠지만 정렬해야 할 대상 값이 골고루 분배되지 않는 문제가 있다. 그리고 수행해야 할 프로세스 개수가 2^n 이여야 하는 단점이 있다. 이를 보완하기 위한 알고리즘이 있는데 HyperQuickSort와 Parallel Sorting by Regular Sampling (PSRS) 등이 있다. 이 알고리즘에 대해서는 다음에....
참고자료:
1. Parallel Quick Sort로 검색한 결과
2. Parallel Programming in C with MPI and OpenMP
'Programming > Algorithm' 카테고리의 다른 글
| [Algorithm]동기화 기법(Synchronization) (0) | 2012.11.19 |
|---|