http://www.ibm.com/developerworks/kr/library/j-jtp11137.html
" 자바 7에서 선보일 포크-조인(fork-join) 프레임워크를 활용한, 세밀하게 세분화된(fine-grained) 병렬 처리법 탐구 "
자바(Java™) 7에는java.util.concurrent패키지에 포크-조인 스타일의 병렬 작업 분할을 돕는 프레임워크가 포함될 예정입니다. 이 추상화된 포크-조인 프레임워크는 하드웨어 병렬 기능을 효과적으로 활용하여, 알고리즘을 자연스럽게 분해하는 메커니즘입니다.
본 연재의 다음 편에서는ParallelArray클래스를 다룹니다. 이 클래스는 메모리 상의 자료 구조에서 병렬로 정렬하고 검색하는 작업을 단순화합니다.
(역주: 이 글의 원제는 'Stick a fork in it'이다. 여기서 포크는 프로세스나 스레드 분기를 뜻하는 포크와 식탁용 포크의 중의적 의미로 쓰였다.)
언어나 라이브러리, 프레임워크는 우리의 프로그램 작성 방식에 영향을 준다. 1934년도에 Alonzo Church는 모든 알려진 계산 프레임워크는 곧 이로써 표현할 수 있는 프로그램의 집합과 동등하다고 입증했다. 그렇더라도, 현실 세계의 프로그래머가 작성하는 프로그램 집합은 프로그래밍 모델에서 표현하기 쉬운 관용어로 형상화하고, 이러한 프로그래밍 모델은 언어나 라이브러리, 프레임워크가 주도한다.
바꾸어 말하면, 그 시대의 지배적인 하드웨어 플랫폼이 언어나 라이브러리, 프레임워크를 개발하는 방식을 형성한다. 자바 언어는 태동부터 스레드와 동시 처리를 지원했다. 이 언어는 synchronized나 volatile 같은 동기화 요소를 포함하며, 클래스 라이브러리에는 Thread 같은 클래스가 있다. 그러나 1995년에 인지한 동시적 요소에는 그 시대의 하드웨어 수준을 반영하였을 뿐이다. 당시 상용 시스템은 대부분 병렬 처리를 전혀 지원하지 않았다. 심지어 최고가 시스템조차 제한된 병렬 처리만을 지원했다. 스레드는 주로 동시성보다는 비동기를 표현하기 위해 사용되었다. 결과적으로 이는 그 시절의 요구에 충분한 메커니즘이었다.
멀티프로세서 시스템이 저렴해짐에 따라, 시스템이 제공하는 하드웨어 병렬 기능을 더 많은 애플리케이션에서 활용할 필요가 생겼다. 프로그래머는 언어나 클래스 라이브러리에서 제공하는 저수준 동기화 요소만으로 동시 동작하는 코드를 작성하기 어렵고 잦은 오류도 유발한다는 사실을 깨달았다. 자바 5에서는 java.util.concurrent 패키지가 추가되어, 동시 동작하는 애플리케이션 코드 작성에 유용한 여러 컴포넌트를 제공했다. 이러한 컴포넌트에는 동시 동작하는 컬렉션(collection), 큐(queue), 세마포어(semaphore), 래치(latch), 스레드 풀 등이 있다. 이러한 컴포넌트는 합리적인 선에서 굵직한 작업 단위를 가진 프로그램에 적합하다. 이런 프로그램에서 필요한 것은 가용한 프로세서 수 이상으로 동시 실행할 수 있도록 작업을 일관성 있게 나누는 것이다. 웹 서버나 메일 서버, 데이터베이스 서버에서 하나의 요청을 작업 단위로 처리할 때, 애플리케이션은 보통 이러한 요구를 충족한다. 따라서 이러한 메커니즘은 그저 그런 병렬 하드웨어를 활용하기에 충분했다.
이제 하드웨어 변화 추세는 명백하다. 무어의 법칙은 더 이상 더 높은 클럭 주파수를 제공하는 대신 칩 당 더 많은 코어를 제공할 것이다. 십여 개의 프로세서가 쉬게 하지 않고, 사용자 요청 처리 같은 굵직하게 나눠진(coarse-grained) 작업 간에 조율하는 일이란 어렵지 않다. 그러나 이런 기술을 수천 개의 프로세서로 확장할 수는 없다. 단시간 내에 프로세서간 신호 흐름이 기하급수적으로 증폭될 수 있기 때문이다. 그러나 하드웨어 변화 추세는 알려진 한계를 점차 극복하게 된다. 다수의 코어를 다루는 시대로 진입함에 따라 더 세밀하게 세분화된(fine-grained) 병렬 방식을 찾거나, 수행할 작업이 많더라도 프로세서를 쉬게 하는 손실을 감수할 필요가 있다. 지배적인 하드웨어 플랫폼이 바뀜에 따라, 우리가 따르려는 소프트웨어 플랫폼 역시 바뀌어야 한다. 자바 7에서는 포크-조인 프레임워크를 포함할 예정이다. 이는 더 세밀하게 세분화된 병렬 알고리즘을 표현하기 위한 프레임워크다.
오늘날 대부분의 서버 애플리케이션은 사용자 요청-반응 처리를 하나의 작업 단위로 사용한다. 전형적으로 서버 애플리케이션은 가용한 프로세서보다 훨씬 더 많은 스레드 또는 요청을 동시 실행한다. 그 이유는 대부분의 서버 애플리케이션에서 요청 처리에 상당한 양의 I/O를 포함하기 때문이다. I/O 작업은 프로세서를 그다지 많이 사용하지 않는다. (모든 네트워크 서버 애플리케이션은 소켓으로 요청을 받으므로 다수의 소켓 I/O를 처리한다. 또한, 다수의 서버 애플리케이션은 꽤 많은 양의 디스크(또는 데이터베이스) I/O를 처리한다.) 각 작업이 전체 소요 시간의 90퍼센트를 I/O 작업 종료를 기다리면서 소모한다면, 최대한 프로세서를 활용하기 위해 10배 많은 작업을 동시 실행해야 한다. 프로세서 수가 늘어나면서, 동시 요청이 모든 프로세서를 최대한 활용하기에 충분하지 않을 수도 있다. 대신, 사용자의 응답 대기 시간을 줄이는 예와 같이 요청 하나의 처리 성능을 향상시키기 위해, 병렬 처리를 활용할 수도 있다.
전형적인 네트워크 애플리케이션의 예로 데이터베이스 서버를 살펴 보자. 데이터베이스 서버가 받은 요청은 다음의 여러 단계를 거친다. 첫째, SQL 구문을 파싱하고 검증한다. 그리고 질의 계획(query plan)을 선택한다. 데이터베이스 서버는 최소 I/O 작업으로 복잡한 질의를 처리하기 위해, 여러 후보 질의 계획을 검사한다. 이러한 질의 계획 검색에 CPU를 과도하게 사용할 수 있다. 따라서 어느 시점에는 더 많은 수의 후보 질의 계획을 확인하는 것이 오히려 손해가 될 수도 있다. 그러나 너무 적은 수의 후보 질의 계획을 검사하면, 필요 이상으로 많은 I/O 작업을 필요할 수 있다. 게다가, 데이터를 디스크에서 읽은 이후, 결과로 얻은 데이터 집합을 다시 처리하는 일이 더 클 수도 있다. 질의에 SUM이나 AVERAGE 같은 집합 작업이 포함될 수도 있고, 데이터 집합의 정렬을 요구할 수도 있기 때문이다. 또한, 결과는 반드시 인코딩하여 요청한 곳으로 돌려 주어야 한다.
대부분의 서버 요청과 같이, SQL 질의 처리에는 계산과 I/O가 혼합되어 있다. 그런데 추가적인 CPU 전력량으로는 I/O 종료 소요 시간을 줄일 수 없다(이전 I/O 작업을 캐시하여 I/O 수를 줄이기 위한 목적으로 추가 메모리를 사용할 수 있기는 하다). 그러나 (질의 계획 평가 또는 정렬과 같은) CPU 집약적인 요청 처리 부분은 병렬 처리로 소요 시간을 줄일 수 있다. 질의 계획 평가에서는, 다수의 서로 다른 질의 계획을 동시에 평가할 수 있다. 데이터 집합 정렬에서는, 큰 데이터 집합을 작은 데이터 집합으로 분할하여,각각을 동시에 정렬하고 합칠 수 있다. 이런 식으로 (요청을 처리하기 위해 수행할 전체 작업이 늘어날 수는 있지만) 결과를 더 빨리 얻게 되므로 사용자 관점에서 성능을 향상시킬 수 있다.
병합정렬(merge sort)은 분할 정복 알고리즘의 한 예다. 이 알고리즘에서는 한 문제를 여러 작은 문제로 나누고, 이 작은 문제들의 해법을 모아 최종 결론을 도출한다. 분할 정복 알고리즘은 종종 순차적인 환경에서도 유용하지만, 작은 문제를 동시에 해결할 수 있어 병렬 환경에서 더욱 효과적이다.
Listing 1에 전형적인 분할 정복의 병렬 알고리즘의 예 하나를 소개한다.
Listing 1. 일반적인 분할 정복의 병렬 알고리즘의 유사 코드(pseudo-code)
// PSEUDOCODE
Result solve(Problem problem) {
if (problem.size < SEQUENTIAL_THRESHOLD)
return solveSequentially(problem);
else {
Result left, right;
INVOKE-IN-PARALLEL {
left = solve(extractLeftHalf(problem));
right = solve(extractRightHalf(problem));
}
return combine(left, right);
}
}
|
분할 정복의 병렬 알고리즘에서 가장 먼저 할 일은 문제가 너무 단순해 순차적 접근이 더 빠른지를 판단하는 것이다. 이것은 대개 문제의 크기를 스레시홀드(threshold)와 비교하는 것이다. 문제가 충분히 커서 세분화한 병렬 처리가 득이 된다면, 이를 둘 이상의 작은 문제로 분할하여 이 알고리즘을 다시 재귀적으로 병렬 적용한다. 그런 후, 각 작은 문제의 결과를 기다렸다가 이들을 합친다. 병렬 처리 조율에 드는 비용 함수를 써서, 순차 처리와 병렬 처리 사이의 선택 기준이 되는 스레시홀드를 정한다. 이상적으로 조율 비용이 0이면, 수없이 세밀하게 세분화된 작업으로 더 좋은 병렬 처리 효과를 얻는다. 즉 조율 비용이 적을수록, 더 세밀하게 세분화하여 병렬 처리 후 순차 접근으로 마무리할 수 있다.
Listing 1의 예에서 존재하지 않는 가상의 INVOKE-IN-PARALLEL 동작을 사용했다. 이 동작에서는 현 작업을 일시 중단하고, 두 보조 작업을 병렬로 수행한다. 현 작업은 보조 작업의 종료 때까지 대기하였다가, 보조 작업의 결과를 합친다. 한 작업이 여러 보조 작업을 분기(fork)했다가 보조 작업을 종료하면 결과를 결합(join)하므로 이런 식의 병렬 분할을 두고 포크-조인(fork-join)이라고 부른다.
Listing 2에서는 포크-조인 해법에 적합한 문제, 즉 거대 배열에서 최대값 검색의 예를 보인다. 물론 이는 매우 단순한 예일 뿐, 포크-조인 기술은 검색, 정렬, 데이터 분석 문제에 다양하게 쓰일 수 있다.
public class SelectMaxProblem {
private final int[] numbers;
private final int start;
private final int end;
public final int size;
// constructors elided
public int solveSequentially() {
int max = Integer.MIN_VALUE;
for (int i=start; i<end; i++) {
int n = numbers[i];
if (n > max)
max = n;
}
return max;
}
public SelectMaxProblem subproblem(int subStart, int subEnd) {
return new SelectMaxProblem(numbers, start + subStart,
start + subEnd);
}
}
|
subproblem() 메서드는 엘리먼트를 복사하지 않는다. 단지 배열의 참조(reference)와 기존 자료 구조 대비 참조의 오프셋만 복사한다. 이는 포크-조인 문제를 구현하는 전형적인 방식이다. 문제를 재귀적으로 나눌 때 잠재적으로 수많은 새로운 Problem 객체가 생성되기 때문이다. 더구나, 검색 작업은 검색 자료 구조를 수정하지 않는다. 즉 부분 작업마다 개별적인 데이터 집합 사본을 유지할 필요가 없다. 따라서 복사에 따른 추가 오버헤드를 감수할 필요도 없다.
Listing 3은 자바 7에 포함 예정된 포크-조인 패키지를 사용하여 SelectMaxProblem을 구현하는 예를 보인다. 이 패키지는 JSR 166 Expert Group을 통해 jsr166y라는 코드 네임으로 공개하여 개발 중이다. 독자들도 이 패키지를 별도로 다운로드하여, 자바 6 이상에서 함께 사용할 수 있다(java.util.concurrent.forkjoin 패키지를 사용한다). invoke-in-parallel 작업은 coInvoke() 메서드로 구현한다. 이 메서드는 동시에 다수의 작업을 수행하고 모두 종료하기를 기다린다. ForkJoinExecutor는 일반적인 작업을 수행하기 위한 Executor 같은 것이다. 다만, ForkJoinExecutor는 연산 집약적인 작업을 위해 특별히 고안되어, 같은 ForkJoinExecutor가 다른 작업을 처리하려고 대기하는 상황을 제외하면 동작을 멈추지 않는다는 점이 다를 뿐이다.
포크-조인 프레임워크는 명시적인 종료가 필요한 작업과 반복 수행되는 작업을 포함한 몇 가지 유형의 ForkJoinTasks를 지원한다. 여기에서 사용된 RecursiveAction 클래스는 결과를 품지 않는 작업(non-result-bearing task)을, RecursiveTask는 결과를 품는 작업을 재귀적으로 병렬 분할하는 유형을 지원한다. (그 외 포크-조인 작업 클래스에는 CyclicAction과 AsyncAction, LinkedAsyncAction이 있다. 사용법에 대한 더 상세한 설명은 Javadoc을 참고하라.)
Listing 3. 포크-조인 프레임워크를 사용한 최대값 검색 해법
public class MaxWithFJ extends RecursiveAction {
private final int threshold;
private final SelectMaxProblem problem;
public int result;
public MaxWithFJ(SelectMaxProblem problem, int threshold) {
this.problem = problem;
this.threshold = threshold;
}
protected void compute() {
if (problem.size < threshold)
result = problem.solveSequentially();
else {
int midpoint = problem.size / 2;
MaxWithFJ left = new MaxWithFJ(problem.subproblem(0, midpoint), threshold);
MaxWithFJ right = new MaxWithFJ(problem.subproblem(midpoint +
1, problem.size), threshold);
coInvoke(left, right);
result = Math.max(left.result, right.result);
}
}
public static void main(String[] args) {
SelectMaxProblem problem = ...
int threshold = ...
int nThreads = ...
MaxWithFJ mfj = new MaxWithFJ(problem, threshold);
ForkJoinExecutor fjPool = new ForkJoinPool(nThreads);
fjPool.invoke(mfj);
int result = mfj.result;
}
}
|
표 1은 다양한 시스템에서 병렬 수행 대신 순차 수행하는 스레시홀드를 달리하여, 한 배열의 50만 개의 엘리먼트 중 최대값을 구한 결과를 보여 준다. 대개의 실행 결과에서 포크-조인 풀에서 쓰인 스레드 수는 하드웨어가 지원하는 스레드의 수(코어 수 X 코어 당 스레드 수)와 같았다. 여기 제시된 속도 수치는 해당 시스템에서 순차적 수행 결과 대비 상대값이다.
표 1. 다양한 시스템에서 50만 개 엘리먼트를 가진 배열에서 최대값을 구한 결과
| Threshold=500k | Threshold=50k | Threshold=5k | Threshold=500 | Threshold=-50 | |
|---|---|---|---|---|---|
| 펜티엄-4 HT(2 쓰레드) | 1.0 | 1.07 | 1.02 | .82 | .2 |
| 듀얼-제온 HT(4 쓰레드) | .88 | 3.02 | 3.2 | 2.22 | .43 |
| 8-웨이 옵테론(8 쓰레드) | 1.0 | 5.29 | 5.73 | 4.53 | 2.03 |
| 8-코어 나이아가라 (32 쓰레드) | .98 | 10.46 | 17.21 | 15.34 | 6.49 |
다양한 범위의 매개변수에서 좋은 성능 향상 결과를 보여 준다. 주어진 문제나 하드웨어에는 비합리적인 매개변수만 제외하면, 별다른 튜닝 없이 좋은 결과를 얻을 수 있다. 칩-멀티쓰레딩(chip-multithreading)에서 최적 속도가 얼마인지는 확실하지 않다. 단, 하이퍼쓰레딩 같은 CMT 접근법이 동일한 수의 하드웨어 코어보다 성능이 떨어진다는 점은 분명하다. 물론, 실행 코드의 캐시 실패율 등 다양한 요소에 따라 상대적으로 성능 차가 날 수는 있다.
순차 스레시홀드는 500K(배열의 크기, 병렬 처리를 전혀 하지 않는 것을 의미)에서 50 사이에서 선택했다. 순차 스레시홀드 값으로 50을 사용한 것은 극단적으로 작은 값을 의미한다. 결과 역시 극단적으로 낮은 순차 스레시홀드에서 포크-조인 작업 관리에 오버헤드를 보여 준다. 반면, 극단적으로 높거나 낮은 매개변수 값만 피하면, 별도로 튜닝하지 않더라도 좋은 결과를 얻을 수 있다. 일꾼(worker) 스레드의 최적값으로 Runtime.availableProcessors()를 선택하면 된다. 포크-조인 풀에서는 CPU 처리 위주 작업을 수행하게 되어 있다. 풀 크기가 너무 크거나 작지 않으면, 매개변수는 결과에 크게 영향을 주지 않는다.
MaxWithFJ 클래스에는 명시적인 동기화가 필요없다. 처리할 데이터는 문제 처리 과정 내내 일정하여, 부분 작업이 데이터를 읽거나 조인할 부분 작업 결과를 읽을 때에도 ForkJoinExecutor 내부 동기화만으로 충분하다.
Listing 3에서 보듯이, 포크-조인 프레임워크의 구현 방식은 다양하다. Thread.start()와 Thread.join()에는 필요한 기능이 모두 있으므로, 스레드를 직접 사용하는 것도 한 가지 방법이다. 그러나 이 방법으로는 VM이 지원할 수 있는 스레드로 부족할 수 있다. (순차적 처리를 위한 스레시홀드가 매우 작다고 가정할 경우) 크기 N의 문제를 해결하려면, O(N) 스레드가 필요하다. (문제 트리의 깊이는 log2N이며, 깊이 k의 바이너리 트리의 노드 수는 2k 이다.) 그리고 이 스레드들 중 절반은 보조 작업이 끝나기를 기다리면서 대부분의 시간을 보낸다. 스레드는 생성 비용이 비싸고 소비 메모리 양도 많다. 따라서 이런 접근법은 권장하지 않는다. (이 방법을 제대로 쓰려면, 코드는 복잡해지고 문제 크기와 하드웨어에 따라 세밀한 매개변수 튜닝도 요구한다.)
포크-조인 작업은 다른 작업의 종료를 기다리면서 대부분의 시간을 보내므로, 포크-조인을 재래식 스레드 풀을 써서 구현하는 것도 괜찮다. 이는 스레드 부족으로 인한 데드락을 막는 방법이다. 물론 스레드 풀에서 생성 가능한 스레드 수가 충분하거나 무제한인 경우에만 해당한다. 재래식 스레드 풀은 서로 독립적이고 굵직하게 나눠진 작업의 중단없는 수행을 고려해 설계된 것이다. 포크-조인은 이러한 재래식 스레드의 주요 설계 목적과 무관하다. 재래식 스레드 풀에서 세분화된 작업을 수행하면, 여러 일꾼이 큐 하나를 공유하면서 과도한 경합을 벌일 수 있다.
포크-조인 프레임워크는 '일 훔치기'로 알려진 기술을 써서 '일 큐(work queue)'를 사이에 둔 경합을 줄인다. 각 일꾼 스레드는 각각 자신의 '일 큐'를 가진다. 이 '일 큐'는 삽입과 삭제가 양 끝에서 모두 가능한 큐(double-ended queue), 즉 디큐(deque)를 써서 구현한다(자바 6에서 클래스 라이브러리에 ArrayDeque와 LinkedBlockingDeque를 포함하여 몇 가지 디큐 구현을 추가했다). 한 작업이 새 스레드를 분기할 때면, 디큐의 머리에 자신을 추가한다. 아직 종료하지 않은 다른 작업과 조인할 때, (Thread.join()이 하듯이) 이 작업은 그 조인할 작업이 종료할 때까지 잠자는 대신 디큐의 머리에서 다른 작업을 꺼내어 실행한다. 본 스레드의 디큐가 비었으면, 다른 스레드 디큐의 꼬리에서 남은 작업을 훔친다.
일 훔치기는 표준 큐로도 구현할 수 있다. 그러나 디큐를 사용하면 표준 큐와 대비하여 경합하거나 훔칠 일이 감소하는 두 가지 주요 이점이 있다. 일꾼 스레드만이 디큐의 머리에 접근할 수 있으므로, 디큐의 머리를 놓고 경합을 벌일 일은 없다. 스레드가 할 일이 없을 경우에만 디큐의 꼬리에 접근하므로 디큐를 두고 간혹 경합을 벌이게 된다(포크-조인 프레임워크에서는 이러한 접근 패턴에 디큐를 써서 경합을 조율하는 비용을 줄인다). 경합이 줄면, 전통적인 스레드 풀 기반 접근법에 비해 동기화 비용도 극적으로 준다. 나아가, 이같이 후입선출(LIFO) 방식으로 작업을 나열하면, 디큐의 꼬리에 가장 큰 작업이 남는다. 이는 다른 스레드가 작업을 훔칠 때, 그 스레드는 더 작은 것으로 분할할 수 있는 큰 작업을 훔친다는 것을 의미한다. 즉 조만간에 다시 훔칠 일이 줄어든다. 일 훔치기는 이런 식으로 중앙 조율 없이 합리적으로 작업량을 분배하고 동기화 비용을 절감한다.
포크-조인 방식은 타겟 시스템의 동시 병렬 처리 능력에 대한 사전 정보가 없더라도 유연한 병렬 처리 수단을 제공한다. 모든 유형의 정렬, 검색, 수치 알고리즘에서 병렬 분할을 적용할 수 있다. (미래에는 Arrays.sort() 같은 표준 라이브러리 메커니즘이 포크-조인 프레임워크의 수요처가 될지 모른다. 그 때는, 애플리케이션에서 무료로 병렬 분할의 이점을 누릴 수 있을 것이다.) 갈수록 수가 늘어나는 프로세서를 프로그램에서 효율적으로 사용하려면 병렬을 자주 검토할 필요가 있다. 정렬 같은 연산 집약적인 작업을 병렬 분할하면, 오늘날 하드웨어의 강점을 간편하게 활용할 수 있다.
교육
- "Java theory and practice: Stick a fork in it, Part 2"(developerWorks 2008년 5월):
ParallelArray클래스를 탐구한다. 이 클래스는 내부 메모리 상의 자료 구조에서 병렬 정렬과 검색을 단순화한다.
- 처치-튜링(Church-Turing) 가설: 알려진 모든 주요 문제의 표현력이 동등하다고 밝힌다.
- 병합정렬(Merge sort): 분할 정복 알고리즘의 또 다른 예다.
- Concurrent Programming in Java의 4.4장(Doug Lea, Prentice Hall PTR, 1999년 11월): 병열 분할에 대해 상세히 다룬다.
- Doug Lea의 동시성에 대한 웹 사이트: jsr166y 패키지의 일부인 포크-조인 프레임워크를 다운로드하거나 그 디자인에 대한 논문을 읽어보라.
- Java Concurrency in Practice의 8.1장(Brian Goetz, Addison-Wesley Professional, 2006년 5월): 스레드 부족으로 인한 데드락을 다룬다.
- 기술 주제를 다루는 책을 서점에서 찾아 보라.
- 한국 developerWorks의 자바 코너: 자바 프로그래밍의 여러 관점에 대한 수백 가지의 자료가 있다.
토론
- developerWorks 블로그를 확인하여, developerWorks 커뮤니티에 참여해 보라.
 | ||
|
|
|
Brian Goetz는 지난 20년간 전문 소프트웨어 개발자로 일했다. 현재는 썬 마이크로시스템즈의 책임 엔지니어로 있으며, 다수의 JCP Expert Group에서 일하고 있다. 그의 책 Java Concurrency In Practice 는 2006년 5월에 Addison-Wesley에서 발간되었다. 업계의 유명한 출판물로, Brian이 출간하였거나 발행할 저서도 읽어 보라. |
