public class MergeSort extends RecursiveAction { final int[] numbers; final int startPos, endPos; final int[] result; private void merge(MergeSort left, MergeSort right) { int i=0, leftPos=0, rightPos=0, leftSize = left.size(), rightSize = right.size(); while (leftPos < leftSize && rightPos < rightSize) result[i++] = (left.result[leftPos] <= right.result[rightPos]) ? left.result[leftPos++] : right.result[rightPos++]; while (leftPos < leftSize) result[i++] = left.result[leftPos++]; while (rightPos < rightSize) result[i++] = right.result[rightPos++]; } public int size() { return endPos-startPos; } protected void compute() { if (size() < SEQUENTIAL_THRESHOLD) { System.arraycopy(numbers, startPos, result, 0, size()); Arrays.sort(result, 0, size()); } else { int midpoint = size() / 2; MergeSort left = new MergeSort(numbers, startPos, startPos+midpoint); MergeSort right = new MergeSort(numbers, startPos+midpoint, endPos); coInvoke(left, right); merge(left, right); } } } |
병합정렬은 병렬 알고리즘으로 고안된 것이 아니며, 순차 처리도 가능하다. 이는 메모리에 수용하기에 너무 큰 데이터 집합을 조각 단위로 정렬해야 할 때 널리 쓰인다. 병합정렬은 최악의 경우에 O(n log n)이며, 보통 평균적인 성능은 낸다. 그러나 원본 데이터를 바로 병합하기 어려워, 그 자리에서 직접 정렬하는 기타 알고리즘 대비 메모리 요구 사항이 높다. 하지만, 부분 문제를 병렬로 정렬할 수 있으므로, 정렬 성능만큼은 빠른정렬(quick-sort)보다도 우수하다.
고정된 수의 프로세서가 주어지더라도, O(n log n) 문제가 병렬 처리로 인해 O(n) 문제로 바뀌지는 않는다. 그러나 문제를 병렬화하기 쉬우면 쉬울수록, 병렬 처리로 얼마나 전체 런타임을 줄이느냐에 따라 ncpus 에 근접할 수도 있다. 전체 런타임을 줄인다는 것은 병렬 처리가 비록 순차 처리 대비 CPU는 더 많이 쓰더라도, 사용자가 결과를 얻는 시간은 단축됨을 의미한다.
포크-조인 기술 사용의 주요 이점은 알고리즘을 병렬 실행하기 위한 간편한 코딩 수단을 제공한다는 데 있다. 프로그래머는 프로그램의 배포 시점에 가용한 CPU 수를 알 필요도 없다. 런타임에서 스스로 일꾼 수에 따라 일을 적절히 분배하므로, 다양한 유형의 하드웨어에 걸쳐 합리적인 결과를 도출할 수 있다.
주요 서버 애플리케이션에서 주로 볼 수 있는 더 세밀하게 세분화한 병렬의 가장 대표적인 예는 데이터 집합의 정렬과 검색, 선택(selection), 요약(summarizing)이다. 이 각 문제는 분할 정복으로 쉽게 병렬 처리할 수 있고, 포크-조인 작업으로도 쉽게 표현할 수 있다. 예를 들어, 큰 데이터 집합의 평균값을 얻는 병렬 처리 단계는 다음과 같다. 먼저, (병합정렬의 경우처럼) 큰 데이터 집합을 더 작은 데이터 집합으로 나눈다. 그리고, 각각 작은 데이터 집합의 평균값을 구한다. 결합 단계에서는 이들 작은 데이터 집합의 평균값에서 가중치를 적용한 평균값을 계산한다.
포크-조인 라이브러리에서는 정렬과 검색의 경우처럼, 병렬 작업을 데이터 집합 단위로 쉽게 표현하기 위해 ParallelArray
클래스도 제공한다. 구조적으로 비슷한 데이터 항목의 집합을 ParallelArray
로 표현하고, 여기에 여러 메서드를 적용하여 데이터 분할 및 처리 정책을 기술한다. 그런 후, 기술된 정책에 따라 집합적 작업(array operation)을 실행한다(이 집합적 작업은 내부적으로 포크-조인 프레임워크를 사용한다). 이 방식의 효과는 프로그래머가 데이터 선택과 변형, 후처리 작업을 선언적으로 명시하기만 하면, 프레임워크가 알아서 합리적인 병렬 처리 방안을 찾는다는 데 있다. 데이터 작업을 SQL로만 기술하면, 그 작업의 구현 메커니즘은 데이터베이스 시스템의 몫인 것과 같은 이치다. 기본 타입 배열 또는 객체 배열을 비롯하여 데이터 타입이나 크기에 따라 다양한 ParallelArray
구현이 있다.
Listing 2는 학생의 성적을 요약하기 위한 ParallelArray
의 사용 예를 보여 준다. 본 예는 선택과 매핑, 요약이라는 기본 작업을 묘사한다. Student
클래스는 (이름, 졸업연도, 평점 등) 학생에 대한 정보를 담고 있다. 도우미 객체 isSenior
는 금년 졸업생만 선택한다. 또 다른 도우미 객체인 getGpa
는 주어진 학생의 평점, 즉 gpa 필드값을 추출한다. 리스트의 첫 코드 블록에서는 학생 집합을 나타내는 ParallelArray
를 생성하여, 금년 졸업생 중 가장 높은 평점을 선택한다.
Listing 2. ParallelArray
를 사용한 데이터의 선택, 처리 및 요약
ParallelArray<Student> students = new ParallelArray<Student>(fjPool, data); double bestGpa = students.withFilter(isSenior) .withMapping(selectGpa) .max(); public class Student { String name; int graduationYear; double gpa; } static final Ops.Predicate<Student> isSenior = new Ops.Predicate<Student>() { public boolean op(Student s) { return s.graduationYear == Student.THIS_YEAR; } }; static final Ops.ObjectToDouble<Student> selectGpa = new Ops.ObjectToDouble<Student>() { public double op(Student student) { return student.gpa; } }; |
집합적 병렬 작업을 기술한 첫 번째 코드 블록은 마치 속임수 코드같다. withFilter()
와 withMapping()
메서드는 정작 데이터를 검색하거나 변형하지 않으며, 대신 "쿼리"의 매개변수만 지정한다. 마지막에 max()
를 호출했듯이, 실질적인 일은 마지막 단계에서 이루어진다.
ParallelArray
가 지원하는 기본 작업은 다음과 같다.
withFilter()
메서드가 필터로 사용된다.apply()
메서드로 임의 동작을 수행할 수 있다.withMapping()
메서드에서 Student
를 학생의 평점으로 변환했다. 선택된 부분 집합에서 필요한 필드값만 모은 ParallelArray
를 결과로 받는다.ParallelArray
를 생성하고 여기서 추가적인 쿼리를 수행한다는 점이 다르다. 대체의 한 예가 바로 정렬이다. 정렬에서는 한 요소가 다른 요소로 대체되어 정렬된 결과 배열을 얻는다(이 동작에서는 내장 sort()
메서드가 제공된다). 또 다른 특별한 예로 cumulate()
메서드가 있다. 이 경우 각 요소를 특정 결합 작업에 따라 실행한 누적값으로 대체한다. 병렬 배열 a
와 b
에서 a[i]+b[i]
값을 요소로 갖는 ParallelArray
를 생성하는 경우와 같이, 대체란 다수의 ParallelArray
를 결합하기 위해 사용되기도 한다.max()
메서드를 사용했다. min()
, sum()
, max()
같은 기본 요약 메서드는 더 일반적인 목적의 reduce()
메서드를 써서 구현했다. Listing 2에서 학생의 최고 평점 계산법을 기술할 수 있었다. 이제 다소 다른 경우, 즉 최고 평점의 학생을 찾는 경우를 보자. 이는 (최고 평점을 찾기 위한 계산과 이 평점을 가진 학생을 찾기 위한 계산의) 두 가지 계산으로 나누어 구현할 수 있다. 그러나 ParallelArray
는 최고값, 최소값, 합계, 평균, 최대 또는 최소값 요소의 인덱스 등 자주 쓰이는 요약 통계를 얻기 위한 더 쉬운 방법을 제시한다. summary()
메서드는 단일 병렬 작업으로 요약 통계를 계산한다.
Listing 3은 요약 통계를 계산하는 summary()
를 보여 준다. 이 예에서는 데이터에 여러 단계를 적용하지 않고 최소와 최대 요소의 인덱스를 구한다.
SummaryStatistics summary = students.withFilter(isSenior) .withMapping(selectGpa) .summary(); System.out.println("Worst student: " + students.get(summary.minIndex()).name; System.out.println("Average GPA: " + summary.getAverage(); |
ParallelArray
는 일반적인 목적의 메모리 데이터베이스 또는 (.NET 3.0의 언어 통합 쿼리(language-integrated query(LinQ) 기능 같은) 데이터 변형이나 추출을 기술하기 위한 메커니즘을 염두에 둔 것이 아니다. 본래 목적은 단지 특정 범위의 데이터 선택과 변형 작업의 표현을 단순화하여, 쉬우면서 동시에 자동으로 병렬을 적용하는 것이다. 따라서, 여기에는 몇 가지 제약이 있다. 예를 들어, 필터 작업은 매핑 작업 전에 기술되어야 한다. (다수의 필터 작업이 허용되지만, 다수의 필터를 단일 복합 필터로 결합하는 편이 더 효율적이다.) 이 클래스의 주요 목적은 병렬 처리 방법에 대한 고민으로부터 개발자를 해방시키는 것이므로, ParallelArray
에서 제공하는 작업으로 변형을 표현할 수만 있으면 특별한 노력을 들이지 않더라도 합리적인 수준의 병렬 효과를 거둘 수 있다.
ParallelArray
의 효과를 얻고자 다양한 크기의 배열과 포크-조인 풀에서 쿼리를 실행하는 단순하고 비과학적인 프로그램을 작성했다. 결과는 Core 2 Quad 기반 MS 윈도우 시스템에서 얻었다. 표 1은 기준(단일 스레드에서 1000명의 학생 정보 사용) 대비 상대 속도를 보여 준다.
Threads | |||||
1 | 2 | 4 | 8 | ||
Students | 1000 | 1.00 | 0.30 | 0.35 | 1.20 |
10000 | 2.11 | 2.31 | 1.02 | 1.62 | |
100000 | 9.99 | 5.28 | 3.63 | 5.53 | |
1000000 | 39.34 | 24.67 | 20.94 | 35.11 | |
10000000 | 340.25 | 180.28 | 160.21 | 190.41 |
(GC 동작을 포함한 여러 요소에 의해 편향되어) 결과는 다소 산만하지만, (시험이 전적으로 CPU 위주 작업인지라) 가용한 코어 수와 동일한 풀 크기에서 최상의 결과를 얻었다는 것과 단일 코어 대비 네 개의 코어에서 두세 배의 속도 증가가 있었다는 점을 확인할 수 있다. 이는 튜닝하지 않고 고수준의 간편한 메커니즘을 써서 합리적으로 병렬 처리할 수 있음을 보여 준다.
ParallelArray
는 자동으로 병렬 처리를 촉진할 뿐 아니라 데이터 집합에 필터 작업, 처리, 집단 작업을 선언적으로 기술하기에도 좋은 방법이다. 포크-조인 라이브러리를 직접 사용하는 것보다 구문(syntax)이 단순해진다. 그러나 각 필터, 매핑 처리자, 감소 처리자를 내부 클래스(inner class)로 기술하는 만큼, 그 구문은 여전히 다소 번거롭다. "금년 졸업생의 최고 평점 찾기"라는 단순한 쿼리조차 수십 줄의 코드가 필요하다. 자바 7의 자바 언어에 포함될 가능성 있는 것 중 하나가 클로저(closure)다. 클로저를 선호하는 이유 중에는 필터, 매핑 처리자, 감소 처리자와 같은 코드 조각 표현이 매우 단순해진다는 점도 있다.
Listing 4는 BGGA 클로저 제안(역자 주, 자바 언어에 클로저 문법을 추가하기 위한 제안. 제안자인 Gilad Bracha, Neal Gafter, James Gosling, Peter von der Ahe의 성씨 첫 알파벳을 각각 따서 붙인 이름)에 따라 작성한, 최고 평점 쿼리다. (이 버전의 ParallelArray
에서는 withFilter()
의 매개변수 타입으로 Ops.Predicate<T>
가 아닌 함수 타입 { T => boolean }
을 썼다.) 클로저 표기법은 내부 클래스와 관련된 상투적인 표현을 제거하여, 동일한 데이터 작업을 좀 더 집약된 (더 중요하면서 더 직접적인) 표현으로 구현할 수 있도록 한다. 이제, 얻고자 하는 결과의 중요한 측면만을 표현하여, 코드를 단 세 줄로 줄였다.
Listing 4. 클로저를 써서 최고 평점을 찾는 코드 작성
double bestGpa = students.withFilter({Student s => (s.graduationYear == THIS_YEAR) }) .withMapping({ Student s => s.gpa }) .max(); |
가용한 프로세서 수가 증가하면서, 프로그램에서 더 세밀하게 세분화된 병렬 요소를 찾을 필요가 생겼다. 병렬 요소의 가장 대표적인 후보로는 정렬, 검색, 요약 등, 집합적 데이터 작업을 들 수 있다. 자바 7에서 소개될 포크-조인 라이브러리는 일부 병렬 알고리즘을 간편하게 표현할 수 있는 수단을 제공하여, 프로그램을 다양한 하드웨어 플랫폼에서 효율적으로 실행하도록 한다. 이 라이브러리의 ParallelArray
는 집합적 병렬 작업을 위한 좀 더 쉬운 수단이다. 프로그래머가 수행할 작업만 선언적으로 기술하면, 나머지 효율적인 실행 방법은 이 클래스가 스스로 선택한다.