공짜 점심은 끝났다. CPU 클럭 속도 경쟁이 끝나고 본격적인 멀티코어 시대가 시작되었다. CPU 하나가 낼 수 있는 성능은 이미 한계에 도달했기 때문에 프로세서 벤더들은 성능을 향상시키기 위해 여러 개의 코어를 사용하기 시작했다. 멀티 코어 시대는 소프트웨어 개발자에게 큰 변화를 요구한다. 기존의 순차적인 프로그램 작성 방식으로는 코어가 늘어난다고 성능 개선 효과를 기대하기 힘들기 때문이다. 앞으로는 병렬 프로그래밍이 고급 소프트웨어 개발자들의 필수지식이 될 것이다. 이 글은 락/컨디션 변수를 사용한 고전적인 병렬 프로그래밍의 문제점을 짚어보고, 그 대안으로 함수형 언어인 하스켈(Haskell)을 사례로 소프트웨어 트랜잭션 메모리(STM)의 개념을 소개하려 한다.


 2008년 4월 마이크로소프트웨어 기고글입니다.


병렬 프로그래밍

 

병렬 프로그래밍(parallel programming)은 하나의 프로그램이 동시에 여러 일을 수행하게 만드는 방법을 통칭한다. 병렬 프로그래밍이라는 말은 고성능 컴퓨팅(HPC, High Performance Computing)의 한 분야를 지칭하는 좁은 뜻으로도 사용되기 때문에 혼돈을 피하기 위해 동시 프로그래밍(concurrent programming)이라는 말을 쓰기도 한다.

 

병렬 프로그래밍의 가장 일반적인 사례는 자원(보통은 메모리)을 공유하고 락(lock)과 컨디션 변수(conditional variable) 통해 공유 자원의 접근을 통제하는 멀티쓰레드 프로그래밍이다. OS 프로세스를 여러 개 만들고 프로세스 간 통신(IPC, Inter-Process Communication)을 통해 데이터를 처리하는 것도 병렬 프로그래밍의 한 예이다. 함수형 언어인 얼랑(Erlang)처럼 여러 프로세스(process, 여기서 프로세스는 OS 프로세스가 아닌 언어 런타임의 경량 프로세스임)가 메시지 큐(message queue)를 통해 데이터를 주고받는 모델도 병렬 프로그래밍의 한 예이다.

 

병렬 프로그램을 작성하는 일은 순차적인 프로그램 작성에 비해 무척 어렵다. 일례로 데이터 구조의 일종인 데크(double ended queue)를 작성하는 일은 학부생 프로그래밍 숙제 수준에서 해낼 수 있는 일이지만, 규모가변성(scalability) 보장되면서 쓰레드-세이프(thread-safe)한 데크 작성은 논문으로 낼 수 있는 수준이 된다.

 

여기서 규모가변성이란 코어의 수를 늘렸을 때 프로그램의 성능 향상이 일어나는 정도를 말한다. 코어가 2배가 되었을 때 프로그램 성능이 2배가 된다면 규모가변성이 매우 뛰어난 병렬 프로그래밍이고, 코어가 2배가 되었음에도 성능 향상이 미미하다면 규모가변성이 떨어지는 프로그램이다.


락/컨디션 변수의 문제점

 

병렬 프로그래밍의 고전이자 가장 일반적인 모델은 락과 컨디션 변수를 이용한 멀티쓰레드 프로그래밍이다. 멀티쓰레드 프로그래밍은 공유 자원(혹은 공유 메모리)을 가정하고 여러 개의 쓰레드가 동시에 프로그램을 수행하며 같은 자원에 데이터를 읽고 쓰며 통신하는 방법이다. 락과 컨디션 변수는 운영체제를 비롯해 일부 시스템 소프트웨어를 작성하는데 주로 사용되었으나, 자바가 모니터(락과 컨디션 변수)를 프로그래밍 언어에 포함시키면서 일반 개발자들도 널리 사용하게 되었다.

 

하지만 결론부터 이야기하면 락을 이용한 멀티쓰레드 프로그래밍 기술이 널리 퍼질수록 전 세계의 개발자들은 더욱 더 많은 버그를 만들어내고 인터넷으로 연결된 우리가 사는 이 세상은 더 나빠진다. 멀티쓰레드 프로그램을 오류 없이 설계하기는 어렵기 때문이다. 또한 비결정적인(nondeterministic)인 프로그램 특성 때문에 테스트가 어렵고, 버그가 발생해도 재현이 힘들기 때문에 멀티쓰레드 프로그램의 디버깅은 불가능에 가깝다.

 

락을 이용한 멀티쓰레드 프로그래밍의 결정적 문제는 안정성과 규모가변성의 충돌이다. 멀티쓰레드 프로그램을 정확하고 안전하게 짜는 방법은 락을 최대한 적게 쓰는 데 있다. 동기화가 필요한 부분에 큰 단위로 락을 잡으면 복잡도가 낮아서 비교적 정확한 프로그램을 짤 수 있다. 하지만 동기화 단위가 큰 만큼 많은 쓰레드가 유용한 일을 수행하기 보다는 다른 쓰레드가 작업 수행을 끝내기를 기다리면서 대부분의 시간을 보내게 된다. 즉, 코어가 2배 4배가 되더라도 성능 향상은 미미할 가능성이 크다. 반대로 락을 잘게 쪼개서 잡으면 규모 가변성이 좋아지지만 데드락(deadlock)과 레이스 컨디션(race condition)이라는 고질적인 병폐에 부딪힐 확률이 그만큼 커진다. 빠르기만 하고 계산 값이 틀린 엉터리 프로그램이 되는 셈이다.

 

락의 문제점을 정리하면 다음과 같다.

 

1) 레이스: 락 잡는 것 잊어먹었을 때 발생한다.

2) 데드락: 락을 정해진 순서와 다르게 획득했을 때 발생한다.

3) 깨어나지 않음: 컨디션 변수를 깨우지(wakeup) 않았을 때 발생한다.

4) 에러 복구: 에러가 발생했을 때 락을 모두 해제하지 못했을 때 발생한다.

 

 

 

 

STM이란?

 

멀티쓰레드 프로그래밍의 병폐는 이미 널리 알려져 있고 이미 수많은 글들이 이런 문제를 극복하는 방법을 다루고 있다. 일례로 데드락을 방지하기 위해서는 시스템의 존재하는 모든 락에 순서를 매기고, 여러 개의 락을 획득할 때는 반드시 정해진 순서를 따르는 것이 한 방법이다. 불필요한 공유 자원 사용을 줄이고 블로킹 큐(blocking queue), 카운트다운 래치(countdown latch) 등 고수준의 유틸리티 클래스를 사용하는 것도 대책이 될 수 있다.

 

이 글에서는 락 기반 멀티쓰레드 프로그래밍의 팁 대신 멀티코어 시대에 새로운 병렬 프로그래밍 모델로 주목받고 있는 소프트웨어 트랜잭션 메모리(이하 STM)를 소개하려 한다.

 

STM은 데이터베이스에서 말하는 트랜잭션(transaction)의 개념을 프로그래밍 언어로 빌려온 것이다. DB 트랜잭션과 마찬가지로 프로그램 내에서 하나의 단위로 수행되어야 하는 일을 묶어주고 그 일을 모두 수행하거나 전혀 수행하지 않는다. 쉽게 말해서 모 아니면 도(all or nothing) 방식이다. STM에서는 중간 상태(inconsistent state)가 노출되는 문제가 존재하지 않는다.

 

이해를 돕기 위해 병렬 프로그래밍의 고전적인 예인 은행 계좌 이체를 생각해보자 계좌 A에서 돈을 빼내서 계좌 B로 이체하기 위해서는 2가지 일을 해야 한다. 1) 일단 A 계좌에서 돈을 인출하고 2) B 계좌에 돈을 넣는다. (물론 2번, 1번순으로 처리할 수도 있다.) 데이터베이스에서는 이런 상황을 ACID 모델로 해결한다. ACID의 A는 원자성(atomicity)로 1, 2는 하나의 단위로 수행되어야 함을 뜻한다. I는 독립성(isolation)으로 도중에 다른 태스크에 의해 방해받지 않음을 뜻한다. C(consistency)와 D(durability)는 저장 매체와 관련이 있다.

 

STM에 대한 이해를 돕기 위해 하스켈로 작성된 프로그램을 하나 살펴보자. 아래 하스켈 코드는 계좌 from에서 계좌 to로 amount만큼의 돈을 이체하는 간단한 함수이다. ***참고로 대부분의 개발자에게는 낯선 하스켈을 선택한 이유는 하스켈이 STM을 가장 먼저 시작한 프로그래밍 언어이고 하스켈의 강력한 타입 시스템이 STM의 장점을 잘 살려주기 때문이다.


transfer :: Account -> Account -> Int -> IO ()

-- 은행 계좌 'from'에서 'to‘로 amount만큼 이체한다.

transfer from to amount

= atomically ( do { deposit to amount

                           ; withdraw from amount } )

하스켈로 작성된 은행계좌 이체


일단 transfer :: Account -> Account -> Int -> IO ()로 표기된 부분은 transfer 함수의 타입을 선언한다. 각각의 인자는 -> 로 구분되어 있는데, transfer 함수는 첫 번째 인자와 두 번째 인자로 Account 타입을 받고, 세 번째 인자로는 Int(정수)를 받는다. 마지막 IO ()는 transfer 함수의 리턴 타입을 나타내는데 IO를 수행하고 ()를 리턴함을 의미한다. 참고로 ()는 C/C++, 자바의 void와 동일하게 리턴 값이 없을 때 사용한다.


다음은 실제로 함수를 정의하는 부분이다. transfer 함수는 from to amount라는 세 개의 인자를 받으며 amount 만큼을 to 계좌에 입금하고, amount 만큼을 from 계좌에서 인출한다. deposit to amount는 deposit이라는 함수를 to와 amount 2개의 인자로 호출한 함수 호출이다. do 명령은 하스켈에서 IO를 수행하기 위한 블록(반드시 IO만은 아니고 모나드에 적용된다.)으로 do {} 안에 명령은 순차적으로 실행된다. 따라서 일단 to 계좌에서 돈을 인출한 다음에 from 계좌에 돈을 넣게 되는 것이다.

 

여기서 주목할 부분은 atomically이다. do 블록을 감싸고 있는 atomically는 앞서 언급한 원자성(atomicity)과 독립성(isolation)을 보장해준다. atomically 안에 들어있는 STM 액션은 기본적으로 모 아니면 도 스타일로 중간 상태를 허용하지 않는다.

 

이 방식의 장점은 다음과 같다.

 

1) 락을 획득하는 순서 때문에 발생하는 데드락 문제가 사라진다.

2) 또한 에러 발생 시 복구도 자동으로 이루어진다.

3) 규모가변성 측면에서 뛰어나다. 아래 그래프는 사이먼 페이튼 존스(Simon Peyton Jones)가 2007년 OSCON에서 발표한 규모가변성 자료이다. 컴파일러와 통합한 STM의 경우 성능이 인상적이다.



하지만 다음 2가지 문제는 여전히 남아 있는 것처럼 보인다.

 

1) 명시적으로 락을 잡는 것에 비해 성능 향상이 없다.

사실이 아니다. 이 문제는 atomically를 어떻게 구현하느냐에 달려있다. 일반적으로 STM이 취하는 방식은 DB 트랜잭션이 주로 사용하는 낙관적 동시성(optimistic concurrency) 방식과 동일하다. 하스켈에서 atomically 지정된 STM 액션은 아무런 락을 잡지 않고 일단 코드를 수행한다. 코드 수행 도중에 발생하는 메모리 읽기/쓰기는 트랜잭션 로그에 남긴다. 메모리 쓰기는 메모리에 직접 수행하지 않고 로그에만 남긴다. atomically가 끝나면 트랜잭션 로그를 한 번에 커밋한다. 만약 그 사이에 다른 쓰레드가 들어와서 트랜잭션이 읽고 쓴 메모리를 변경했다면, 트랜잭션을 다시 수행한다.


2) atomically를 선언하지 않고 같은 메모리에 접근하는 경우가 생기면 레이스 컨디션의 문제가 있다.

이 문제는 락 기반 멀티쓰레드 프로그램의 고질적인 문제점이다. 락은 기본적으로 모든 참여자가 룰을 지킬 것이라는 믿음 하에 출발한다. 특정 메모리 영역에 접근하기 위해서는 특정 락을 잡겠다는 규칙을 모두가 지켜야만 레이스 컨디션이 없는 프로그램을 작성할 수 있다. 단 하나라도 이 규칙을 깨뜨리는 경우가 생기면 그대로 버그가 되기 때문이다.

 

얼핏 보면 atomically도 같은 문제점을 안고 있는 것처럼 보인다. 하나라도 atomically를 사용하지 않고 메모리에 접근하면 레이스 컨디션이 생기기 때문이다. 하스켈은 이 문제를 타입 시스템을 통해 풀었다. atomically는 얼핏 보기에 프로그래밍 언어의 고유 기능으로 보이지만 실제로는 다음 타입을 갖는 함수이다.


atomically: STM a -> IO a

atomically의 타입

 

STM 액션은 IO 액션과 마찬가지로 사이드 이펙트를 가지지만 그 범위가 훨씬 좁다. STM 액션에서 할 수 있는 일은 (TVar a) 타입의 트랜잭션 변수를 읽고 쓰는 것만 가능하다. 반대로 IO 액션에서는 IO 변수만 읽고 쓸 수 있으며 직접 트랜잭션 변수에 접근하지 못한다. IO 액션에서 트랜잭션 변수에 접근하는 유일한 방법이 atomically이다. atomically를 사용하지 않고는 트랜잭션 변수에 접근할 수 없게 타입 시스템에서 강제한 것이다.

 

 

 

STM 액션

 

앞서 atomically로 지정된 STM 액션들은 자동으로 원자성과 독립성을 보장받는다고 말했다. 이제는 실제로 STM 변수를 어떻게 사용하는지 살펴보자.


type Account = TVar Int

 

withdraw :: Account -> Int -> STM()

withdraw acc amount

     = do { bal <- readTVar acc

             ;writeTVar acc (bal - amount) }

withdraw 함수

 

위 예제는 withdraw 함수를 STM을 통해 구현한 것이다. STM 변수는 TVar(TArray, TChan, TMVar 등도 있다) 타입으로 위 예제에서는 Account를 TVar Int로 정의했다. STM 변수는 2가지 기능이 있다. readTVar는 변수의 값을 읽는 것이고, writeTVar는 변수의 값을 쓴다. 앞서 말한 것처럼 이때 STM 액션은 공유 메모리에 쓰기 전에 임시로 다른 장소에 저장을 했다가 다른 태스크의 방해 없이 수행에 성공하면 한 번에 커밋한다.


deposit :: Account -> Int -> STM()

deposit acc amount = withdraw acc ( - amount)

deposit 함수


이 두 함수를 보고 다시 앞서 transfer 함수를 떠 올려보면 STM 또 다른 장점을 볼 수 있다. 이 예제에서 withdraw와 deposit 함수는 각각 STM 액션으로 트랜잭션으로 처리할 수 있는 구조를 가지고 있다. 개발자가 transfer 함수처럼 이 두 함수를 하나의 트랜잭션으로 호출하고 싶으면 단순히 이 둘을 do {} 블록에 묶고 atomically만 붙여주면 된다. 이처럼 STM으로 작성된 루틴은 필요에 따라 얼마든지 합성이 가능하다는 장점이 있다.

 

반대로 이 두 함수를 락으로 구현했다고 생각해보자. withdraw도 락을 잡고 deposit도 락을 잡았다고 하더라도 이 둘을 합성한 transfer는 여전히 문제가 있다. 락을 잡는 순서에 따라서 데드락이 발생할 수도 있고, 별도의 락을 잡아주지 않는 이상 withdraw와 deposit 사이에는 레이스도 존재하기 때문이다. 락 기반 멀티쓰레드 프로그래밍은 작성하기도 어려울 뿐만 아니라 프로그램을 재활용하는 모듈화가 힘들다는 또 다른 숨은 문제점이 있다.

 

STM 블로킹

 

지금까지는 주로 락을 대체할 수 있는 STM 액션과 atomically에 대해서만 이야기했다. 여기서 또 하나 특정 조건이 만족될 때까지 블로킹할 수 있는 컨디션 변수의 역할을 해줄 수 있는 무엇인가가 필요하다. 이 역할은 하스켈 STM에서 retry가 맡는다.

limitedWithdraw :: Account -> Int -> STM ()

limitedWithdraw acc amount

= do { bal <- readTVar acc

                  ; if amount > 0 && amount > bal

                  then retry

                  else writeTVar acc (bal - amount) }

limitedWithdraw 함수

 

위 예제는 인출 금액이 잔고보다 많을 경우 잔고가 생길 때까지 대기하는 limitedWithdraw 함수이다. 여기서 주의 깊게 봐야할 부분은 retry이다. retry는 현재 트랜잭션을 취소하고 새로 트랜잭션을 시작하라는 의미이다. 이때 트랜잭션을 즉시 다시 시작할 수도 있겠지만 은행 잔고가 바뀔 가능성이 낮기 때문에 이렇게 폴링(polling)할 경우 굉장히 비효율적인 코드가 된다. 하스켈 STM은 if 문에서 체크한 변수(이 경우 bal)를 검사해 해당 변수가 변경되었을 때 새로 트랜잭션을 시작해준다. retry는 조건이 바뀌면 자동으로 retry가 되는 것을 보장해 주기 때문에 컨디션 변수처럼 영원히 깨어나지 않거나 잘못된 상황에서 깨어나는 버그를 걱정할 필요가 없다.

 

예제: Buffer

 

지금까지 알아본 내용을 토대로 간단한 버퍼를 만들어보자.

> module STM where

>

> import Random

> import Control.Monad

> import Control.Concurrent

> import Control.Concurrent.STM

>

> type Buffer a = TVar [a]

>

> newBuffer :: IO (Buffer a)

> newBuffer = newTVarIO []

>

> put :: Buffer a -> a -> STM ()

> put buffer item = do ls <- readTVar buffer

>                                     writeTVar buffer (ls ++ [item])

>

> get :: Buffer a -> STM a

> get buffer = do ls <- readTVar buffer

>                      case ls of

>                          [] -> retry

>                          (item:rest) -> do writeTVar buffer rest

>                                                  return item

  buffer.lhs STM을 이용한 버퍼 구현


위 코드는 여러 태스크가 동시에 사용할 수 있는 동시 버퍼(concurrent buffer)를 STM을 이용해 구현한 것이다. 여기서 newBuffer를 newTVarIO []로 선언했는데 newTVarIO는 atomically . newTVar과 동일하다. put은 STM 액션으로 버퍼의 끝에 원소를 하나 더 한다. ++는 리스트 두 개를 더해서 새로운 리스트를 만드는 함수이다. 여기서 buffer는 크기 제한이 없는 큐이므로 put은 블로킹하지 않는다.


get의 경우 리스트에서 첫 번째 원소를 빼고 나머지를 다시 저장한다. 이 때 buffer가 비어있을 경우가 있으므로 buffer가 비어있으면 retry한다. retry는 ls <- readTVar buffer의 ls에 의존적이므로 다른 태스크가 buffer에 새로운 원소를 put하는 순간에 깨어나서 다시 트랜잭션을 시도하게 된다.

 

 

맺음말

 

정리하자면 STM의 가장 큰 장점은 기존 락/컨디션 변수 기반의 멀티쓰레드 프로그래밍보다 훨씬 프로그래밍 하기가 용이하다는 데 있다. 또한 STM은 근본적으로 데드락이나 컨디션 변수의 잘못된 깨어남 등의 가능성을 차단해 주고, 코어가 늘어났을 때 규모가변성을 어느 정도 보장해준다.


STM은 아직 많은 개발자들이 사용하는 일반적인 방법은 아니다. 하지만 오랜 시간 여러 연구자들이 검증해온 아이디어이고 현재 기존 프로그래밍 언어에 접목하려는 시도가 활발히 이루어지고 있다. 특히 하스켈 커뮤니티에서 가장 먼저 그 시도가 이루어졌고, 이 글 역시 하스켈과 STM에 깊은 기여를 한 마이크로소프트 리서치의 사이먼 페이튼 존스(Simon Peyton Jones) 글과 강연에서 많은 도움을 받았다.


앞으로 다가올 멀티코어 시대를 맞을 준비는 STM으로 시작해보자.


참고문헌

[1] Beautify concurrency, Simon Peyton Jones

http://research.microsoft.com/~simonpj/papers/stm/beautiful.pdf

[2] Lock -Free Data Structures using STMs in Haskell, FLOPS'06

http://research.microsoft.com/Users/simonpj/papers/stm/lock-free-flops06.pdf

[3] Composable memory transactions, PPOPP'05

http://research.microsoft.com/Users/simonpj/papers/stm/stm.pdf

[4] stm-2.1.1.0: Software Transactional Memory

http://www.haskell.org/ghc/docs/latest/html/libraries/stm/Control-Concurrent-STM.html

신고

Parallelism and Concurrency 2

Posted 2008.03.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를 설명하는 부분에 감동했습니다 +_+

신고

Parallelism and Concurrency 1

Posted 2008.03.26 02:36
여러분은 Paralleism과 Concurrency를 구분해서 쓰시나요? 저는 그동안 Parallel Programming과 Concurrent Programming을 구분하지 않고 그냥 병렬 프로그래밍이라고 번역해왔는데 Parallelism과 Concurrency의 의미를 구분해서 쓰는 경우도 있더군요. 헤스켈 컴파일러인 GHC 매뉴얼 Cocurrent and Parall Haskell에 보면 두 용어를 다음과 같이 정의해 놨습니다.


Paralleism

헤스켈 프로그램을 성능 향상을 목적으로 여러 프로세서에 돌리는 것을 의미한다. 이 과정은 의미 변화 없이 눈에 보지이 않게(자동으로) 이루어지는 것이 이상적이다.


Concurrency

프로그램을 I/O를 수행하는 여러 개의 쓰레드를 구현하는 것을 의미한다. Concurrent 헤스켈 또한 병렬 머신에서 실행될 수 있으나, Concurrency의 주 목적은 성능 향상이 아니라 이 방법이 프로그램을 작성하고 가장 쉽고 직접적인 방법이기 때문이다. 쓰레드가 I/O를 수행하기 때문에 프로그램의 의미는 비결정적(non-deterministic)이다.

저는 여전히 두 용어를 혼용해서 쓰는 편이고 웹에 있는 상당수의 글들도 마찬가지인 것 같은데 정확한 가이드라인이 있는 것인지 궁금하군요. 더불어 Concurrency는 뭐라고 번역하면 좋을까요? 동시성은 영 어색한 단어 같고, 병렬로 하자니 Parallelism과 구분이 안 되는 것 같고 고민이네요.


신고

하스켈과 병렬 프로그래밍

Posted 2008.03.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)이 뛰어난 편이라 병렬 프로그래밍 계의 총아로 떠오르고 있는 분야입니다.


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

다음은 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) 프로젝트를 사용하시면 됩니다.

신고

티스토리 툴바