27. Multithreaded Algorithms

지금까지는 직렬 알고리즘을 다루었으나, 이 장에서는 병렬 알고리즘을 다뤄 본다. 단일 칩 멀티프로세서는 단일 멀티코어를 지원한다. 아키텍쳐는 제조사마다 다른데, 공유 메모리를 쓰는 경우도 있고 분산 메모리를 쓰는 경우도 있기 때문이다. 이런 경우에는 여러 스레드를 사용하는 정적 스레딩을 이용해 프로그래밍할 수도 있다. 하지만 이는 어렵기 때문에 동시성 플랫폼이 대두되었다.

Dynamic multithreaded programming

동시성 플랫폼의 중요한 분류는 동적 멀티스레딩으로, 이 장에서 다룰 것이다. 이는 프로그래머에게 부하 분산, 통신 프로토콜 등의 여러 이슈를 신경쓸 필요 없게 해 준다.

27.1. The basics of dynamic multithreading

피보나치는 보통 다음과 같이 계산한다.

FIB(n)
if n ≤ 1
    return n
else
    x = FIB(n - 1)
    y = FIB(n - 2)
    return x + y

이제 다음의 동시성 키워드 spawn과 sync를 도입해 보자.

P-FIB(n)
if n ≤ 1
    return n
else
    x = spawn P-FIB(n - 1)
    y = P-FIB(n - 2)
    sync
    return x + y

이 때 spawn과 sync를 지운 것을 멀티스레딩 알고리즘의 직렬화라 한다. spawn이 프로시져 호출에 선행하면 중첩 병렬화가 발생한다. spawn은 계산의 논리적 병렬화를 의미하며 이는 실제로 스케쥴러에 의해 스레드에 할당된다. 프로시져는 sync 시점에서 다른 스레드가 행동을 마칠 때까지 대기해야 한다.

A model for multithreaded execution

멀티스레드 실행계산 방향비순환그래프로 나타낼 수 있다. 이 때 병렬 제어되지 않는 명령어 블록을 하나의 스트랜드로 묶어 나타낸다. 스트랜드 u에서 v로 경로가 있을 경우 두 스트랜드가 직렬이라 한다. 아니면 병렬이라 한다. 계산 방향비순환그래프에서 간선은 연결 간선산란 간선, 호출 간선 그리고 반환 간선으로 분류된다. 계산은 최초 스트랜드부터 시작되어 마지막 스트랜드로 끝난다. 이 장에서 다룰 멀티스레드 알고리즘은 순차적 일관성을 가진 이상적 병렬 컴퓨터라 가정한다.

Performance measures

멀티스레드 알고리즘의 계산 효율성은 단일 프로세서에서의 동작 수행 시간인 작업과 방향그래프 내 경로 내 스트랜드를 실행하는 최장 시간인 스팬을 기준으로 계산한다. 각 스트랜드가 단위 시간을 가진다면 스팬은 최장 임계 경로의 정점 수와 같다. 이 때 다음이 성립한다.

  • 작업의 법칙 : T_{P} \geq T_{1} / P.
  • 스팬의 법칙 : T_{P} \geq T_{\infty} .

이 때 속도 향상T_{1} / T_{P}이라 한다. 이것이 \Theta(P)일 때 선형 속도 향상이라 하며 P와 같을 때 완벽 선형 속도 향상이라 한다. T_{1} / T_{\infty} 비율을 연산의 병렬화라 한다. T_{1} / (P T_{\infty})을 연산의 느슨함이라 한다.

Scheduling

멀티스레드 스케쥴러는 계산을 사전 지식 없이 온라인으로 스레드에 할당해야 한다. 분석을 간단히 하기 위해, 여기서는 중앙화된 스케쥴러, 그 중에서도 탐욕적 스케쥴러를 이야기하도록 한다. P 스트랜드가 실행 대기 중일 때 완전 단계, P 미만 갯수의 스트랜드가 실행 대기 중일 경우를 불완전 단계라 한다. 다음이 성립한다.

Theorem. 탐욕적 스케쥴러의 수행 시간은 T_{P} \leq T_{1} / P + T_{\infty}이다.

Corollary. 탐욕적 스케쥴러의 수행 시간은 최적 수행 시간의 2배 이하이다.

Corollary. 연산의 느슨함이 클 경우 탐욕적 스케쥴러는 완벽 선형 속도 향상에 가까워진다.

Analyzing multithreaded algorithms

P-FIB(n)의 병렬화는 T_{1}(n) / T_{\infty}(n) = \Theta(\phi^{n}/n)으로, 완벽 선형 속도 향상에 가깝다.

Parallel loops

병렬 루프로 진행되는 행렬과 벡터의 곱을 알아보자.

MAT-VEC(A, x)
n = A.rows
let y be a new vector of length n
parallel for i = 1 to n
    y_i = 0
parallel for i = 1 to n
    for j = 1 to n
        y_i += a_ij * x_j
return y

이 때 컴파일러는 실제로 다음과 같은 코드를 생성한다.

MAT-VEC-MAIN-LOOP(A, x, y, n, i, i')
if i == i'
    for j = 1 to n
        y_i += a_ij * x_j
else
    mid = [(i + i')/2]
    spawn MAT-VEC-MAIN-LOOP(A, x, y, n, i, mid)
    MAT-VEC-MAIN-LOOP(A, x, y, n, mid + 1, i')
    sync

실제로는 동적 멀티스레딩 동시성 플랫폼은 재귀의 리프 노드를 굵게 해서 재귀적 스레드 산란을 줄여 오버헤드를 줄인다. MAT-VEC의 경우 스팬은 \Theta(\lg n)이 되며, 병렬화는 \Theta(n)이다.

Race conditions

멀티스레드 알고리즘은 같은 입력에 대해 항상 같은 출력이 나오면 결정적이고 아니면 비결정적이다. 결정적 알고리즘이 결정적이 되는 것에 실패하면 결정성 경합이라고 한다. 예를 들면 다음과 같다.

RACE-EXAMPLE()
x = 0
parallel for i = 1 to 2
    x = x + 1
print x

이 장에선 병렬로 계산되는 스트랜드가 독립적이라고 가정해서 경합 조건을 상정하지 않는다. 즉, 다음과 같은 구현은 틀렸다.

MAT-VEC-WRONG(A, x)
n = A.rows
let y be a new vector of length n
parallel for i = 1 to n
    y_i = 0
parallel for i = 1 to n
    parallel for j = 1 to n
        y_i = y_i + a_ij * x_j
return y

A chess lesson

작업과 스팬의 관계로 수행 시간을 외삽하면 직접 측정하지 않고도 최적화의 효과를 알 수 있다.

27.2. Multithreaded matrix multiplication

멀티스레드 행렬곱을 알아보자.

Multithreaded matrix multiplication

다음은 멀티스레드 행렬곱을 수행한다.

P-SQUARE-MATRIX-MULTIPLY(A, B)
n = A.rows
let C be a new n x n matrix
parallel for i = 1 to n
    parallel for j = 1 to n
        c_ij = 0
        for k = 1 to n
            c_ij = c_ij + a_ik * b_kj
return C

이 때의 병렬화는 \Theta(n^{2})이다.

A divide-and-conquer multithreaded algorithm for matrix multiplication

행렬곱을 분할 정복으로 멀티스레딩화 해보자.

P-MATRIX-MULTIPLY-RECURSIVE(C, A, B)
n = A.rows
if n == 1
    c_11 = a_11 * b_11
else
    let T be a new n x n matrix
    partition A, B, C and T into n / 2 x n / 2 submatrices A_11, A_12, A_21, A_22, B_11, B_12, B_21, B_22, C_11, C_12, C_21, C_22, and T_11, T_12, T_21, T_22 recursively
    spawn P-MATRIX-MULTIPLY-RECURSIVE(C_11, A_11, B_11) 
    spawn P-MATRIX-MULTIPLY-RECURSIVE(C_12, A_11, B_12)
    spawn P-MATRIX-MULTIPLY-RECURSIVE(C_21, A_21, B_11)
    spawn P-MATRIX-MULTIPLY-RECURSIVE(C_22, A_21, B_12)
    spawn P-MATRIX-MULTIPLY-RECURSIVE(T_11, A_12, B_21)
    spawn P-MATRIX-MULTIPLY-RECURSIVE(T_12, A_12, B_22)
    spawn P-MATRIX-MULTIPLY-RECURSIVE(T_21, A_22, B_21)
    P-MATRIX-MULTIPLY-RECURSIVE(T_22, A_22, B_22)
    sync
    parallel for i = 1 to n
        parallel for j = 1 to n
            c_ij = c_ij + t_ij

이 때 스팬은 M_{\infty}(n) = \Theta(\lg^{2} n)이므로 병렬화는 \Theta(n^{3} / \lg^{2} n)이 된다.

Multithreading Strassen’s method

스트라센 법을 멀티스레딩화 해보자.

  1. A, B, C를 n / 2 x n / 2 부분 행렬로 분할한다.
  2. 행렬 S_{1}, \cdots, S_{10}을 만든다. 작업은 \Theta(n^{2}), 스팬은 \Theta(\lg n)이다.
  3. 이를 통해 재귀적으로 P_{1}, \cdots, P_{7}을 산란한다.
  4. 부분행렬 C_{11}, C_{12}, C_{21}, C_{22}를 구한다.

이 때 스팬은 \Theta(\lg^{2} n)이므로 병렬화는 \Theta(n^{\lg 7} / \lg^{2} n)이 된다.

27.3. Multithreaded merge sort

병합 정렬을 멀티스레딩화 해보자.

MERGE-SORT'(A, p, r)
if p < r
    q = [(p + r) / 2]
    spawn MERGE-SORT'(A, p, q)
    MERGE-SORT'(A, q + 1, r)
    sync
    MERGE(A, p, q, r)

이 때 병렬화는 \Theta(\lg n)밖에 되지 않는다. MERGE가 병목이 되기 때문이다. 더 좋은 방법은 MERGE 자체도 분할 정복하는 것이다.

BINARY-SEARCH(x, T, p, r)
low = p
high = max(p, r + 1)
while low < high
    mid = [(low + high) / 2]
    if x ≤ T[mid]
        high = mid
    else
        low = mid + 1
return high
P-MERGE(T, p_1, r_1, p_2, r_2, A, p_3)
n_1 = r_1 - p_1 + 1
n_2 = r_2 - p_2 + 1
if n_1 < n_2
    exchange p_1 with p_2
    exchange r_1 with r_2
    exchange n_1 with n_2
if n_1 == 0
    return
else
    q_1 = [(p_1 + r_1) / 2]
    q_2 = BINARY-SEARCH(T[q_1], T, p_2, r_2)
    q_3 = p_3 + (q_1 - p_1) + (q_2 - p_2)
    A[q_3] = T[q_1]
    spawn P-MERGE(T, p_1, q_1 - 1, p_2, q_2 - 1, A, p_3)
    P-MERGE(T, q_1 + 1, r_1, q_2, r_2, A, q_3 + 1)
    sync

Analysis of multithreaded merging

P-MERGE의 스팬은 \Theta(\lg^{2} n)이고, 병렬화는 \Theta(n/\lg^{2} n)이다.

Multithreaded merge sort

이제 진짜 멀티스레딩 병합 정렬이 가능해진다.

P-MERGE-SORT(A, p, r, B, s)
n = r - p + 1
if n == 1
    B[s] = A[p]
else
    let T[1, ..., n] be a new array
    q = [(p + r) / 2]
    q' = q - p + 1
    spawn P-MERGE-SORT(A, p, q, T, 1)
    P-MERGE-SORT(A, q + 1, r, T, q' + 1)
    sync
    P-MERGE(T, 1, q', q' + 1, n, B, s)

Analysis of multithreaded merge sort

멀티스레딩 병합 정렬의 스팬은 \Theta(\lg^{3} n), 병렬화는 \Theta(n/\lg^{2}n)이 된다.

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google photo

Google의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중