[펌] 자바 이론과 실습: 포크 찌르기, Part 2

[플밍지기]

자바 이론과 실습: 포크 찌르기, Part 2

자바 7의 ParallelArray 클래스를 사용한 정렬과 검색 가속

Brian Goetz, 책임 엔지니어, Sun Microsystems

옮긴이: 오국환 dwkorea@kr.ibm.com

2008 년 6 월 10 일

자바(Java™) 7의 java.util.concurrent 패키지에 포크-조인 스타일의 병렬 분할을 돕는 프레임워크가 포함될 예정입니다. 저자인 Brian Goetz는 본 연재의 1편에서 여러 알고리즘을 분할하여 하드웨어 병렬을 효과적으로 활용하는 자연스러운 메커니즘으로 포크-조인의 원리를 소개했습니다. 이번에는 ParallelArray 클래스를 다룹니다. 이 클래스는 메모리 상의 자료 구조를 대상으로 한 병렬 정렬과 검색 작업을 단순화합니다

지난 '자바 이론과 실습' 1편에서 포크-조인 라이브러리를 살펴 보았다. 이 라이브러리는 자바 7의 java.util.concurrent 패키지에 추가될 예정이다. 포크-조인이란 분할 정복의 병렬 알고리즘을 쉽게 표현하여, 코드 수정 없이 다양한 유형의 하드웨어에서 효율적으로 코드를 실행할 수 있는 방법이다.

프로세서 수가 늘어나면서 가용 하드웨어를 효율적으로 활용하기 위해, 프로그램에서는 세밀하게 세분화된(fine-grained) 병렬 방법을 찾아 적용할 수 밖에 없다. 최근 몇 년 동안에는, (웹 애플리케이션에서의 단일 요구 처리 경우와 같이) 굵직하게 나눠진(coarse-grained) 작업의 경계를 정하고, 이렇게 나눈 작업을 스레드 풀에서 실행하는 병렬 처리만으로도 하드웨어를 충분히 활용할 수 있었다. 앞으로는 하드웨어를 최대한 가동하기 위한 병렬 적용 분야를 더 연구해야 한다. 병렬 적용이 적합한 예로는 대규모 데이터를 대상으로 한 정렬과 검색이 있다. 지난 연재에서 다루었듯이, 포크-조인을 사용하면 이런 문제는 쉽게 표현할 수 있다. 그러나 이것은 워낙 일반적인 문제이므로 ParallelArray라는 더 쉬운 방법을 추가로 제공한다.

포크-조인 분할 다시 보기

분할 정복 기술을 구체화한 것이 포크-조인이다. 포크-조인에서는 한 문제를 다수의 부분 문제로, 순차 처리가 더 효율적일 때까지 충분히 작게 재귀적으로 분할한다. 이러한 재귀적인 단계는 한 문제를 둘 이상의 부분 문제로 나누고, 부분 문제를 처리하고자 큐에 넣고(포크 과정), 부분 문제의 결과를 기다리며(조인 과정), 결과를 합치는 모든 과정을 포괄한다. 이러한 알고리즘의 한 예가 Listing 1에서 포크-조인 라이브러리를 사용하여 예시한 병합정렬(merge sort)이다.

Listing 1. 포크-조인 라이브러리를 이용한 병합정렬

                
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) 문제로 바뀌지는 않는다. 그러나 문제를 병렬화하기 쉬우면 쉬울수록, 병렬 처리로 얼마나 전체 런타임을 줄이느냐에 따라 n_cpus 에 근접할 수도 있다. 전체 런타임을 줄인다는 것은 병렬 처리가 비록 순차 처리 대비 CPU는 더 많이 쓰더라도, 사용자가 결과를 얻는 시간은 단축됨을 의미한다.

포크-조인 기술 사용의 주요 이점은 알고리즘을 병렬 실행하기 위한 간편한 코딩 수단을 제공한다는 데 있다. 프로그래머는 프로그램의 배포 시점에 가용한 CPU 수를 알 필요도 없다. 런타임에서 스스로 일꾼 수에 따라 일을 적절히 분배하므로, 다양한 유형의 하드웨어에 걸쳐 합리적인 결과를 도출할 수 있다.

세밀하게 세분화한 병렬

주요 서버 애플리케이션에서 주로 볼 수 있는 더 세밀하게 세분화한 병렬의 가장 대표적인 예는 데이터 집합의 정렬과 검색, 선택(selection), 요약(summarizing)이다. 이 각 문제는 분할 정복으로 쉽게 병렬 처리할 수 있고, 포크-조인 작업으로도 쉽게 표현할 수 있다. 예를 들어, 큰 데이터 집합의 평균값을 얻는 병렬 처리 단계는 다음과 같다. 먼저, (병합정렬의 경우처럼) 큰 데이터 집합을 더 작은 데이터 집합으로 나눈다. 그리고, 각각 작은 데이터 집합의 평균값을 구한다. 결합 단계에서는 이들 작은 데이터 집합의 평균값에서 가중치를 적용한 평균값을 계산한다.

ParallelArray

포크-조인 라이브러리에서는 정렬과 검색의 경우처럼, 병렬 작업을 데이터 집합 단위로 쉽게 표현하기 위해 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가 지원하는 기본 작업은 다음과 같다.

• 필터 작업: 계산의 대상이 될 부분 집합을 선택하는 일. Listing 2에서는 withFilter() 메서드가 필터로 사용된다.
  
  
• 적용: 선택된 각 요소마다 프로시저를 적용한다. Listing 2에서는 이 기술을 선보이지 않았다. 그러나 각 선택된 요소마다 apply() 메서드로 임의 동작을 수행할 수 있다.
  
  
• 매핑: (요소에서 데이터 필드를 추출하는 식의) 선택된 요소를 다른 형태로 변환한다. 본 예에서는 withMapping() 메서드에서 Student를 학생의 평점으로 변환했다. 선택된 부분 집합에서 필요한 필드값만 모은 ParallelArray를 결과로 받는다.
  
  
• 대체: 각 요소를 여기에서 파생된 다른 요소로 대체하여 새로운 병렬 배열을 생성한다. 이 기술은 매핑과 비슷하나, 먼저 새로운 ParallelArray를 생성하고 여기서 추가적인 쿼리를 수행한다는 점이 다르다. 대체의 한 예가 바로 정렬이다. 정렬에서는 한 요소가 다른 요소로 대체되어 정렬된 결과 배열을 얻는다(이 동작에서는 내장 sort() 메서드가 제공된다). 또 다른 특별한 예로 cumulate() 메서드가 있다. 이 경우 각 요소를 특정 결합 작업에 따라 실행한 누적값으로 대체한다. 병렬 배열 a와 b에서 a[i]+b[i] 값을 요소로 갖는 ParallelArray를 생성하는 경우와 같이, 대체란 다수의 ParallelArray를 결합하기 위해 사용되기도 한다.
  
  
• 요약: 합계, 평균, 최소값, 최대값 등을 계산하듯이, 값의 집합에서 단일 값을 얻는다. Listing 2에서는 max() 메서드를 사용했다. min(), sum(), max() 같은 기본 요약 메서드는 더 일반적인 목적의 reduce() 메서드를 써서 구현했다.

공통적인 요약 작업

Listing 2에서 학생의 최고 평점 계산법을 기술할 수 있었다. 이제 다소 다른 경우, 즉 최고 평점의 학생을 찾는 경우를 보자. 이는 (최고 평점을 찾기 위한 계산과 이 평점을 가진 학생을 찾기 위한 계산의) 두 가지 계산으로 나누어 구현할 수 있다. 그러나 ParallelArray는 최고값, 최소값, 합계, 평균, 최대 또는 최소값 요소의 인덱스 등 자주 쓰이는 요약 통계를 얻기 위한 더 쉬운 방법을 제시한다. summary() 메서드는 단일 병렬 작업으로 요약 통계를 계산한다.

Listing 3은 요약 통계를 계산하는 summary()를 보여 준다. 이 예에서는 데이터에 여러 단계를 적용하지 않고 최소와 최대 요소의 인덱스를 구한다.

Listing 3. 최고 평점의 학생 찾기

                
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명의 학생 정보 사용) 대비 상대 속도를 보여 준다.

표 1. 최고 평점 쿼리에 대한 성능 측정 결과

		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 위주 작업인지라) 가용한 코어 수와 동일한 풀 크기에서 최상의 결과를 얻었다는 것과 단일 코어 대비 네 개의 코어에서 두세 배의 속도 증가가 있었다는 점을 확인할 수 있다. 이는 튜닝하지 않고 고수준의 간편한 메커니즘을 써서 합리적으로 병렬 처리할 수 있음을 보여 준다.

클로저(closure)와의 연결

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는 집합적 병렬 작업을 위한 좀 더 쉬운 수단이다. 프로그래머가 수행할 작업만 선언적으로 기술하면, 나머지 효율적인 실행 방법은 이 클래스가 스스로 선택한다.