Search Results for '병렬 프로그래밍'

3 POSTS

  1. 2008.03.28 Parallelism and Concurrency 2 1
  2. 2008.03.26 하스켈과 병렬 프로그래밍
  3. 2008.03.26 멀티 코어 프로그래밍과 헤스켈 2

Parallelism and Concurrency 2

Posted 2008. 3. 28. 03:10
얼마 전에 Parallelism and Concurrency라는 글을 통해 동시성(concurrency)와 병렬(parallelism)의 정확한 정의에 대해서 의문을 제기했었는데 오늘 Simon Peyton Jones가 최근에 정리해서 내놓은 Tackling the Awkward Squad: monadic input/output, concurrency, exceptions, and foreign-language calls in Haskell을 읽다가 보다 명확한 정의를 발견했습니다.

28 페이지 Concurrency에 대한 항목을 보시면 두 용어의 정의가 나옵니다.

A parallel functional program uses multiple processors to gain performance. For example, it may be faster to evaluate e1 + e2 by evaluating e1 and e2 in parallel, and then add the results. Parallelism has no semantic impact at all: the meaning of a program is unchanged whether it is executed sequentially or in parallel. Furthermore, the results are deterministic; there is no possibility that a parallel program will give one result in one run and a different result in a different run.

In contrast, a concurrent program has concurrency as part of its specification. The program must run concurrent threads, each of which can independently perform input/output. The program may be run on many processors, or on one — that is an implementation choice. The behaviour of the program is, necessarily and by design, non-deterministic. Hence, unlike parallelism, concurrency has a substantial semantic impact.


병렬 프로그래밍은 성능 향상을 목적으로 명시적으로 멀티 프로세서를 사용함을 의미합니다. 반대로 동시성 프로그래밍은 동시성 자체가 명세에 포함되는 개념입니다. 프로그램이 여러 개의 동시적인 쓰레드로 실행이 되고 따라서 결과가 비결정적이다라는 사실까지 말입니다. 병렬 프로그래밍과 마찬가지로 멀티 프로세서를 사용할 수도 있지만 이는 필수적인 것이 아니라 구현 세부사항일 뿐입니다.

여기까지는 지난 번에 보여드렸던 설명과 동일합니다. 위 정의에는 여기에 덧붙여 더 중요한 정의가 나오는데, 바로 시멘틱에 관한 부분입니다. 병렬 프로그래밍은 프로그램의 시멘틱에 전혀 영향을 미치지 않습니다. 병렬 프로그래밍에서는 e1 + e2를 계산할 때 e1과 e2를 각각의 프로세서에서 실행을 하던 하나의 프로세서에서 실행을 하던 겉으로 보이는 결과는 반드시 같아야 합니다.

하지만 동시성 프로그래밍에서는 멀티쓰레드 사용 자체가 시멘틱에 포함되어 있기 때문에 쓰레드가 어떻게 수행되느냐에 따라서 결과가 달리나올 수 있음을 내포하고 있습니다. 즉, 시멘틱이 달라질 수 있다는 사실이 깔려있습니다.

앞으로는 이런 사실을 염두에 두고 동시성 프로그래밍과 병렬 프로그래밍 용어를 명확히 구분해서 사용하려고 합니다.

비고: Tackling the Awkaward Squad는 굉장히 읽을 만한 글입니다. 헤스켈에서 가장 어려운 부분이지만, 쓸만한 프로그램을 만들기 위해서는 반드시 알아야 하는 입출력(IO), 동시성(concurrency), 예외 처리(exception), 외부 함수 호출(foreign-language call)을 다루고 있습니다. 특히, IO monad의 operational semantics를 설명하는 부분에 감동했습니다 +_+

하스켈과 병렬 프로그래밍

Posted 2008. 3. 26. 02:25

제가 함수형 언어에 직접적인 관심을 가지게 된 계기는 함수형 언어가 멀티코어 프로그래밍(병렬 프로그래밍)에 대한 가장 활발한 연구 결과를 내어놓고 있기 때문입니다. 부작용(side-effect)이 없고 연산(evaluation) 순서에 제약이 덜하다는 함수 언어 자체의 특징이 병렬화와 잘 어울리는 부분도 있습니다만, 언어 특징과 별개로 병렬 프로그래밍에 대한 최신 생각들이 함수 언어에 가장 먼저 적용되는 부분도 무시할 수 없습니다.

병렬 프로그래밍하면 주로 얼랑(Erlang)이 많이 주목받고 있습니다. 함수 언어 중 거의 유일하게 상업적인 용도로 이용된 적이 있다는 사실 때문에 근래에 관심을 가지게 되신 분이 많이 있는것 같습니다. 하지만 경량 프로세스(lightweight process)와 메시지 패싱 방식은 순차적 프로그래밍에 익숙한 기존 개발자들이 쉽게 적응할 수 있는 모델이 아니라 굉장히 큰 진입 장벽이 존재합니다. 자바 개발자가 파이썬으로 코딩해도 여전히 자바 스타일인 것처럼 락 기반 멀티쓰레드 프로그래밍에 익숙한 개발자가 태스크를 잘게 쪼개고 수많은 경량 프로세스를 통해 메시지를 주고 받는 모델로 개발하기란 쉽지 않습니다.

더불어 얼랑은 함수 언어 연구와 깊은 상관관계를 맺고 있는 정적 타입 시스템의 장점을 전혀 살리지 못하는 동적인 언어라는 사실도 약점입니다. 얼랑이 주로 통신 장비 등 상당한 안정성이 요구되는 분야에 사용된 언어임에도 불구하고, 버그를 일찍 쉽게 발견할 수 있게 도와주는 정적 타입 시스템의 도움을 전혀 못 받고 있다는 사실을 조금 의외입니다. 런타임에 쉽게 오류에서 회복되는 것도 중요하지만 애당초 버그를 줄일 수 있었다는 더 좋았을 텐데 말이죠.

하스켈은 병렬 프로그래밍과 관련해서는 가장 많은 옵션을 제공하는 언어입니다. 일단 가장 유명한 세 가지는 다음과 같습니다.



1) Concurrent Haskell

forkIO 등의 함수를 이용해 쓰레드를 생성하고 죽일 수 있으며 MVar 등 공유 메모리를 이용해 동기화하는 모델입니다.

2) Parallel Haskell

Paralle Haskell은 `par`와 `seq` 등을 이용해 순차적인 프로그램에 병렬화할 수 있는 단서를 달아주는 방법입니다. 어떤 부분이 동시에 수행될 수 있는지만 알려주면 하스켈이 알아서 쓰레드를 생성하고 동기화를 해줍니다. 아래 글을 참고하세요.

3) Software Transaction Memory

1) 번 모델을 발전시킨 것으로 데이터베이스의 트랜잭션처럼 특정 코드를 모 아니면 도(all or nothing)로 실행시켜주는 방법입니다. 직접 메모리에 쓰는 대신에 트랜잭션 로그를 만들고 한 번에 커밋하는 방식입니다. 도중에 누가 방해하면 처음부터 다시 실행하면 됩니다. retry를 이용해 컨디션 변수를 대신해 블로킹을 할 수도 있습니다.

락 기반 멀티쓰레드 프로그래밍의 문제점인 데드락, 레이스컨디션 등이 불가능하고, 규모 가변성(scalability)이 뛰어난 편이라 병렬 프로그래밍 계의 총아로 떠오르고 있는 분야입니다.


멀티 코어 프로그래밍과 헤스켈

Posted 2008. 3. 26. 02:01
멀티코어 시대가 오면서 병렬 프로그래밍이 성능 향상의 중요 방법으로 떠오르고 있습니다. 하지만 실제 개발 환경에서 개발자가 멀티 코어를 효율적으로 활용하기는 쉽지 않습니다.

다음은 0에서 40까지 피보나치 수열을 계산하는 간단한 C 프로그램입니다.

long long fib(long long n) {
  if (n < 2) {
    return 1;
  }
  return fib(n - 2) + fib(n - 1);
}

int main(int argc, char ** argv) {
  long long n = 0;

  for (n = 0; n <= 40; n++) {
      printf("fib(%lld) = %lld\n", n, fib(n));
  }

  return 0;
}

좀 더 효율적으로 짤 수도 있겠지만 계산량이 많은 프로그램의 예를 들기 위해 의도적으로 비효율적인 방식으로 작성했습니다. 이 프로그램을 GCC에서 최적화 옵션을 최고로 주고 컴파일한 후 실행하면 제 컴퓨터(1.66GHZ 코어 2 듀오 1GB 램)에서 대략 12.94초가 걸렸습니다.

gcc -O3 fib.c -o fib.exe
$ time ./fib.exe
real    0m12.940s
user    0m12.921s
sys     0m0.015s


같은 프로그램을 헤스켈로 작성하면 다음과 같습니다.

import Control.Monad
import Text.Printf

fib :: Int -> Int
fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

main = forM_ [0..40] $ \i ->
        printf "fib(%d) = %d\n" i (fib i)


ghc -O2 fib.hs -o fib.exe --make
$ time ./fib.exe
real    0m12.454s
user    0m0.031s
sys     0m0.015s


위 프로그램을 컴파일해서 실행하면 12.45초가 걸립니다. 약간이긴 하지만 오히려 C 보다 빠릅니다. 성능을 논하기에는 너무 간단한 예이긴 하지만 함수형 언어가 느리다고 생각하는 것과는 상반된 결과입니다.


위 두 예제는 멀티코어를 전혀 활용하지 못하는 프로그램입니다. fib.exe 실행시켜 놓고 윈도 작업 관리자로 확인해보면 CPU 점유율이 50%에 머물고 있는 것을 볼 수 있습니다. 두 개의 코어 중에서 하나만 죽어라고 쓰고, 나머지 하나는 놀고 있기 때문입니다. 이런 식이면 1.66GHZ 짜리 코어를 10개를 갖다 붙여도 위 프로그램은 성능은 전혀 개선되지 않게 되겠죠.

소프트웨어 성격에 따라 차이는 있겠지만 과거와 달리 멀티 코어 시대에는 소프트웨어 성능 향상을 위해 개발자의 명시적인 개입이 필요하다는 이야기가 여기서 나옵니다.

C로 작성된 프로그램을 멀티 코어를 이용하도록 개선하기 위해서는 pthread 같은 쓰레드 라이브러리를 이용해 명시적으로 쓰레드를 만들고 일을 쪼개서 데이터를 처리하고 공유 메모리를 통해 동기화를 해야할 것입니다. 간단한 예제이지만 제대로 짜기가 무척 어려우므로 실제로 코드를 작성하지 않고 넘어가겠습니다.


대신에 헤스켈은 순차적으로 작성된 프로그램을 병렬화하는 것이 상대적으로 매우 쉽습니다. fib2.hs는 fib.hs에 병렬화(parallelism)을 위한 어노테이션(`par`와 `seq`)을 덧붙인 코드입니다.

import Control.Parallel
import Control.Monad
import Text.Printf

cutoff = 30

fib' :: Int -> Integer
fib' 0 = 0
fib' 1 = 1
fib' n = fib' (n-1) + fib' (n-2)

fib :: Int -> Integer
fib n | n < cutoff = fib' n
      | otherwise  = r `par` (l `pseq` l + r)
 where
    l = fib (n-1)
    r = fib (n-2)

main = forM_ [0..40] $ \i ->
            printf "fib(%d) = %d\n" i (fib i)


헤스켈이 병렬 프로그래밍을 하는 방법에는 Control.Concurrent 모듈을 이용해 명시적으로 쓰레드를 생성하고 MVar나 STM을 이용해 공유 메모리를 제어하는 방법도 있지만, 위 예제처럼 Control.Parallel 모듈의 par와 seq 함수를 이용하는 방법도 있습니다.

위 예제는 특정 cutoff보다 작은 숫자는 쓰레드를 생성하지 않고 직접 계산을 하되, cutoff보다 크면 쓰레드를 만들라는 힌트를 줍니다. a `par` b는 a를 계산(evaluation)할 때 CPU가 놀고 있으면 쓰레드를 만들어서 작업하라고 런타임에 힌트를 줍니다. a `seq` b는 b을 계산하기 전에 a를 먼저 계산(순차적)하라는 뜻으로 이해하시면 됩니다. 따라서 위 예제는 fib (n - 2)는 별도의 쓰레드로 계산하고 동시에 부모 쓰레드에서 fib (n - 1)을 계산해 두 결과를 합쳐서 리턴하게 됩니다.

GHC에 -threaded 옵션만 주면 자동으로 멀티 코어를 활용하는 런타임이 생성됩니다. 실행할 때는 명시적으로 +RTS -N2로 코어가 2개임을 지정해주면 됩니다.

ghc -O2 fib2.hs -o fib2.exe --make -threaded
time ./fib2.exe +RTS -N2
real    0m10.171s
user    0m0.015s
sys     0m0.031s


위 프로그램은 명시적으로 쓰레드를 생성하지 않았고 락을 잡지도 않았지만 멀티 코어를 활용하게 됩니다. 수행 결과 싱글 코어일 때보다 조금 더 빠른 10.17초가 걸렸습니다. 프로그램이 작다보니 쓰레드를 생성하는데 오버헤드가 있어서 성능이 2배가 되지는 않는 걸로 보입니다. 대신에 작업 관리자를 보시면 이번에는 CPU를 거의 100% 쓰고 있다는 사실을 확인하실 수 있습니다.

제 컴퓨터에서는 테스트해볼 수 없었지만 위 프로그램은 코어 수가 2배 4배가 되면 그에 따라 성능이 증가하게 됩니다. 즉, 멀티 코어가 대세가 되면 코어를 제대로 활용하지 못하는 C 프로그램보다 여러 코어를 잘 활용할 수 있는 함수 언어가 더 빠른 세상도 올 수 있는 것입니다.


참고: 헤스켈 컴파일러인 GHC는 공유 메모리 멀티프로세서만 지원합니다. 클러스터나 싱글 멀티프로세서 등은 GHC에서 파생된 GPH(Glasgow Parallel Haskell) 프로젝트를 사용하시면 됩니다.