하스켈 연구

매니코어OS
이동: 둘러보기, 검색

연구 배경

코어의 수를 늘림으로써 CPU의 성능을 향상시키는 다중코어 구조 시스템에서는 병렬 프로그래밍이 필수적이다. 병렬 프로그래밍은 기존 방법에 비해 훨씬 어렵고 오류를 내포할 가능성이 큰 문제점을 가지고 있다. 이를 해결하는 한 방법으로써, 본 연구에서는 순수 함수형(pure functional) 언어인 Haskell을 이용한 병렬 프로그래밍에 대한 연구를 진행하고 있다. 

하스켈의 특징

하스켈은 지연 계산(lazy evaluation) 방식의 순수 함수형 언어이다. 하스켈은 람다 계산법(the lambda calculus), 타입 이론(type theory) 등의 강력한 이론적 기반으로 갖고 있는 언어로서 소프트웨어의 모듈성(modularity), 무결점성(safety), 생산성(productivity), 가독성(readability) 등에서 탁월한 장점을 갖고 있다. 병렬 프로그래밍의 관점에서 볼 때, 하스켈은 mutable 변수를 사용하지 않으며, 계산 순서에 상관없이 모든 식(expression)은 언제나 유일한 값을 갖는 특징이 있으므로, 계산 할 식(redex)을 병렬처리 할 수 있는 내재적 병렬성을 갖는다. 

연구 목표

본 연구에서는 다음과 같은 문제들을 해결하기 위한 연구를 진행한다. 

  1. 하스켈 고유의 특징인 순수성, 지연계산 등의 특징과 기존의 장점을 유지하면서, 하스켈의 병렬성을 자연스럽게 표현할 수 있는 병렬 프로그래밍 방법 연구 
  2. 본 사업을 통해서 새로 구성되고 있는 매니코어 시스템 구조에 맞는 최적화된 병렬처리 기능의 하스켈 프로그래밍 환경 연구
  3. STM(Software Transaction Memory)을 이용한 병렬화 연구
  4. 공유변수와 메시지 전송을 혼합하여 사용하는 IPC 모델 연구
  5. GHC의 GC(Garbage Collection) 메커니즘 분석 및 튜닝 기법에 대한 연구
  6. GHC의 RTS(Runtime System) 구조 분석 및 병렬 아키텍처에 특화된 최적화 연구
  7. 분할형 운영체제를 위한 하스켈 병렬 프로그래밍 환경 연구

연구 결과

매니코어 환경에서의 병렬 프로그래밍 모델 연구

본 연구에서는 표절 검사 프로그램을 기반으로 하스켈의 병렬 프로그래밍 모델에 관해 연구를 진행하였다. 첫 번째 연구로 하스켈의 병렬 프로그래밍 모델 중 공유 메모리를 기반으로 하는 Eval 모나드를 대상으로 확장성을 실험하였으며 그 결과는 다음 그림 1과 같다.

그림 1. Eval 모나드를 이용한 표절 검사 프로그램의 확장성 실험 결과

그림 1은 Eval 모나드를 이용하여 표절 검사 프로그램을 작성한 뒤 81개의 Java 코드를 대상으로 표절 검사를 수행한 결과이다. 그림 1에서 MUT SpeedUp은 하스켈 프로그램에서 실제 계산에만 사용된 시간만 고려하여 속도 상승을 측정한 결과이며 Total SpeedUp은 초기화 시간과 GC 시간을 포함한 전체 실행 시간을 이용하여 측정한 속도 상승 결과이다. 프로그램 실행 결과를 살펴보면 코어 10개 이후로는 확장성에 병목 현상이 발생하고 있으며 이는 프로그램의 속도 상승 한계 및 GC에 걸리는 시간이 줄어들지 않기 때문에 발생한 것으로 추정된다.

두 번째 연구로는 병렬 프로그래밍 모델 중 액터 모델에 관해 연구를 진행하였다. 액터 모델은 Erlang에서 이용하고 있는 모델로 각 액터가 고유의 메모리 공간을 가지고 다른 액터와 연결하기 위해서는 메시지를 이용하여 공유 메모리가 존재하지 않는 특징을 지니고 있다. 하스켈에서는 Cloud Haskell을 통해 액터 모델을 제공하고 있으며 본 연구에서는 이를 이용하여 표절 검사 프로그램을 구현하였다. 그리고 두 모델 간의 성능을 비교한 결과는 그림 2, 3과 같다.

그림 2. 두 프로그래밍 모델 사이의 실행 시간 비교 결과
 
그림 3. 두 프로그래밍 모델 사이의 확장성 비교 결과

두 프로그래밍 모델 사이의 실행 시간은 그림 2와 같이 측정되었다. 1개의 코어에서는 Eval 모나드를 이용한 방법이 Cloud Haskell을 이용한 방법보다 약 2배가량 실행 시간의 차이가 나타났지만, 코어 수가 늘어남에 따라 그 차이는 점차 줄어드는 것으로 나타났다. 그리고 두 모델 간의 확장성을 비교한 결과는 그림 3과 같이 나타났다. 그림 3과 같이 Cloud Haskell이 Eval 모나드보다 확장성이 우수한 것으로 나타났으며, 이는 Cloud Haskell이 노드마다 개별 GC를 실행하기 때문에 코어가 늘어남에도 확장성이 유지되는 것으로 추정된다.


위의 실험 결과인 그림 3의 Eval 모나드 SpeedUp 그래프에서 볼 수 있듯이 실행에 사용되는 코어 수가 늘어남에 따라 확장성이 보장되지 않고 성능 증가의 변동성이 크게 요동치는 것으로 나타났다. 이는 하스켈이 GC를 사용하는 가상머신 위에서 동작하기 때문에 GC에 사용되는 시간에 많은 영향을 받기 때문인 것으로 추정된다. 따라서 세 번째 연구로 GHC의 GC 튜닝에 대한 연구를 진행하였다. 먼저 그림 3의 Eval 모나드 실험 결과를 분석한 결과 10, 13, 15, 17, 18, 19, 20, 23개의 코어를 사용한 부분에서 성능 증가의 변동 폭이 크게 요동치는 것으로 나타났다. 따라서 이 8가지의 코어 환경을 바탕으로 GHC에서 제공하는 GC-TUNER를 사용하여 최적의 GC 옵션인 –A, -H를 표 1과 같이 구할 수 있었다.

[표1 GC-TUNE 사용 결과]
코어수 -A -H
10 268435456 268435456
13 134217728 33554432
15 134217728 268435456
17 134217728 1048576
18 134217728 2097152
19 134217728 134217728
20 134217728 536870912
32 268435456 134217728

GHC는 여러 가지 GC 중 세대별 GC을 주로 사용하는데 –A옵션은 가장 어린 세대를 위한 힙 메모리 설정 옵션이고 –H옵션은 GC에 사용되는 전체 힙 메모리 설정 옵션이다. 표 1에서 구한 최적의 GC 옵션을 바탕으로 GHC에서 다시 실행한 결과는 그림 4와 같다.

그림 4. GC-TUNE 사용 전과 사용 후의 실행 결과

그림 4는 GC-TUNE을 사용하기 전과 사용한 후의 초기 SpeedUP을 측정한 결과 이다. 실험결과 어느 정도 변동 폭이 줄어든 그래프를 얻을 수 있었다. 특히 32코어에서 GC-TUNE의 사용 전과 후의 결과 그래프를 비교했을 때 훨씬 좋은 결과를 얻을 수 있었다. 그림 5는 GC-TUNE을 사용하여 얻을 결과를 바탕으로 각각 10번의 반복실행을 통해 평균을 계산한 결과 이다.

그림 5. GC-TUNE 사용 전과 사용 후 10번 반복한 실행 결과

그 결과 전체적인 SpeedUp 기울기는 다소 낮아졌지만 어느 정도 완만한 모양의 그래프를 얻을 수 있었다. 그림 5의 결과를 바탕으로 성능 변동 폭이 생긴 11, 14, 16개의 코어를 사용한 부분은 GC-TUNE을 사용하여 GC 최적화를 통하면 변동 폭이 줄어들 것이라고 예상할 수 있다. 또한 실행 SpeedUp이 감소하는 부분만을 이용하여 변동 폭의 차이를 계산해 본 결과 GC-TUNE을 사용한 그래프다 사용하지 않은 그래프보다 약 34%의 변동 폭이 감소한 것을 확인할 수 있었다.

종합적으로 본다면 매니코어 환경에는 Eval 모나드보다 Cloud Haskell을 사용하는 것이 유리하다. 즉 확장성 측면의 성능만을 논하자면 Cloud Haskell을 사용해야 하지만 코딩 편의성까지 고려한다면 Eval 모나드가 유리할 수 있다. 이는 Cloud Haskell이 병렬 코딩을 위해 별도의 코드를 작성해야 하기에 발생하는 문제이다.

본 연구에서는 코딩 편의성이 떨어지는 Cloud Haskell을 개선하여 Eval 모나드와 Cloud Haskell의 장점을 합친 Cloud Haskell 기반 병렬 모델을 개발하였다. 이 병렬 모델은 Eval 모나드와 유사하게 손쉽게 병렬 코딩을 할 수 있으면서 Cloud Haskell의 확장성을 확보한 것이다. Cloud Haskell 기반 병렬 모델의 병렬화 개념은 그림 6과 같다.

그림 6. Cloud Haskell 기반 병렬 모델 개념도 

Cloud Haskell 기반 병렬 모델은 그림 6의 (c)와 같이 병렬 프로그래밍을 하는 것을 목표로 한다. 기존 Eval 모나드의 경우 병렬 고차 함수인 parMap을 이용하여 간단하게 병렬 프로그래밍을 할 수 있다. 반면에 Cloud Haskell의 경우 병렬로 동작할 함수를 별도의 마스터/슬레이브 방식의 함수로 새로 작성하여야 병렬로 동작할 수 있다. 두 경우를 비교해보면 Eval 모나드가 Cloud Haskell보다 새로 프로그램을 작성할 때나 기존 프로그램을 병렬 프로그램으로 변경할 때 유리하다. 즉 본 연구에서 개발하고자 하는 Cloud Haskell 기반 병렬 모델은 매니코어 환경에서 Eval 모나드와 같이 Cloud Haskell을 사용할 수 있도록 하고자 한다.

Cloud Haskell은 분산 컴퓨팅 환경에 초점이 맞춰져 있으므로 매니코어 환경에서는 코딩 편의성 이외에도 몇 가지 문제점이 존재하는데 이는 아래와 같다.

· 마스터/슬레이브 실행 함수(ex. startMaster)로 인해 프로그램의 부분 병렬화가 어려움

· 프로그램을 별도로 실행해야 함 (ex. 슬레이브 별도 실행 -> 마스터 실행)

Cloud Haskell 기반 병렬 모델에서는 코딩 편의성과 함께 위 두 가지 문제점도 아울러 개선하였다. 이를 이용해 프로그램을 개발한 코드를 비교하면 그림 7과 같다.

그림 7의 코드는 Haskell을 이용하여 1에서 100 사이의 배열에 1을 더하고 총합을 출력하는 프로그램이다. 그림 7의 (a)와 같이 Eval 모나드로 작성한 프로그램의 경우 LoC가 9이며 기본 로직을 제외한 병렬화 부분도 보통의 Haskell 프로그램과 거의 유사한 것을 알 수 있다. 그리고 그림 7의 (c)와 같이 Cloud Haskell을 이용하여 작성한 프로그램의 경우 LoC가 43으로 slaveJob을 통해 슬레이브가 어떻게 동작하고 masterJob을 통해 마스터가 어떻게 동작하는지를 작성해야 된다. 하지만 그림 7의 (b)와 같이 Cloud Haskell 기반 병렬 모델을 이용해 프로그램의 경우 LoC가 15로 슬레이브에서 동작할 함수를 넘겨주는 작업과 실행할 함수를 remotetable을 통해 정의하는 부분 이외에는 Eval 모나드 프로그램과 거의 유사한 것을 확인할 수 있다.

그림 7. Eval 모나드 vs. Cloud Haskell 기반 병렬 모델 프로그램 비교 

즉 그림 7과 같은 코드의 경우 기존 Cloud Haskell 대비 코드 사이즈를 65% 축약한 것을 확인할 수 있다. 그리고 본 연구에서는 4종의 병렬 프로그램을 대상으로 Cloud Haskell 기반 병렬 모델을 적용한 결과, 표 2와 같은 결과를 얻을 수 있었다.

[표2 Cloud Haskell 기반 병렬 프로그램 성능 비교]
구분 Eval 모나드 Cloud Haskell 제안방법 Cloud Haskell 대비 축약 비율
소수 세기 전체 27 60 32 46.667
병렬 2 38 7 81.579
최빈 단어 세기 전체 42 82 47 42.683
병렬 2 49 7 85.714
스도쿠 전체 100 140 15 25.000
병렬 2 39 7 82.051
표절 검사 전체 515 602 529 12.126
병렬 4 51 14 72.549
평균 전체 171 221 178 19.344
병렬 3 44 9 80.226


SAM 모델 개선을 위한 연구

본 연구에서는 SAM 성능향상을 위한 연구를 위해 하스켈 STM(software transactional memory) 구조에 대한 연구를 진행하였다. SAM은 노드 간의 통신을 위해 소켓 통신을 사용하기 때문에 공유 메모리 환경에서 오버헤드가 존재한다. 이를 해결하기 위해 노드 간 통신 채널을 개선해야 하는데 본 연구에서 선택한 방법은 하스켈의 lock free 구조인 STM을 통신 채널로 사용하는 방법이다.

STM은 병렬 컴퓨팅을 위한 모델로 DB에서 사용되고 있던 트랜잭션(transaction) 개념을 공유 메모리상의 동시성 프로그램 작성에 적용한 것이다. STM은 기본적으로 각 병렬 단위마다 개별적 메모리 공간을 가지고 내용을 작성하게 된다. 그리고 작성된 내용을 공유된 공간에 업데이트하는 경우 버전 검사를 통해 업데이트 가능 여부를 확인하고 업데이트를 수행하는 방법이다. 만약 충돌이 발생하거나 업데이트가 불가능한 경우 처음부터 다시 시도하는 방법을 채택하고 있다. 그리고 현재 STM은 다양한 언어에서 라이브러리 형태로 제공하고 있지만 가장 널리 알려지고 범용적으로 사용되고 있는 언어는 하스켈이다.

하스켈 STM이 가장 널리 사용되는 이유는 몇 가지 장점이 있기 때문이다. 우선 하스켈 STM은 모나드를 이용하여 작성되었는데, 모나드를 이용한 경우 하스켈의 강력한 타입 시스템으로 쓰레드가 트렌잭션 안에서만 공유 자원에 접근할 수 있게 된다. 그리고 하스켈은 GHC 컴파일러 런타임 시스템 차원에서 STM을 지원하기 때문에 다른 언어보다 효과적으로 STM을 사용할 수 있다. 또한 하스켈 STM은 처음 설계 시 operational semantics를 정의하여 구현하였기 때문에 의미가 명확하게 구현되어 있다. 이외에도 하스켈은 다른 언어보다 런타임 시스템 규모가 작기 때문에 STM을 쉽게 수정해볼 수 있어 연구에 적합하다.

하지만 기존 연구에 의하면 하스켈 STM이 매니코어 환경에서 한계점이 있다는 보고가 존재한다. 해당 연구에서 언급한 문제점 중 본 연구와 관련이 있는 문제점은 아래와 같다.


· 하스켈 TM 문제

· 하스켈 GC 문제

· 아키텍처의 문제


하스켈 TM 문제는 로컬 자원의 내용을 공유 자원으로 commit 단계에서 성능 저하가 발생하는 문제이다. 이는 예전 GHC에서는 commit 단계에서 coarse-grained 락을 이용하여 충돌이 발생하지 않는 부분에서도 병렬 처리가 불가능하였던 문제점이다. 하지만 최근 GHC에서는 이를 fine-grained 락 기반으로 변경하여 일정 부분 해결된 것으로 알려져 있다. 다음으로 GC 문제는 코어가 늘어남에 따라 높은 메모리 사용으로 인해 힙과 스택 사이에 불필요한 전송이 늘어나게 되는 문제와 STM 연산 재시도 시 점프 대상 주소가 자주 변경되어 분기 예측 실패로 인한 GC 성능 저하 문제이다. 마지막으로 아키텍처 문제는 NUMA 환경에서 STM 이용 시 쓰레드 위치에 따른 스케줄링 이슈를 의미하는 것으로 NUMA 환경의 특성상 다양한 위치에서 쓰레드가 발생할 수 있기 때문에 나타나는 문제이다.

본 연구에서는 최근 GHC STM이 매니코어에서 성능 확보 문제가 많은지를 판단하기 위한 실험을 진행하였다. 실험에 사용된 프로그램 STM 벤치 마크 프로그램으로 연결 리스트 프로그램과 레드-블랙 트리를 실험에 사용하였다. 실험환경은 인텔 KNL 64코어 단일 노드 환경에서 진행하였다. 그리고 실험 결과는 그림 8, 9와 같이 나타났다.

그림 8. STM을 이용하여 구현된 연결 리스트 확장성 실험 결과 
그림 9. STM을 이용하여 구현된 레드-블랙 트리 확장성 실험 결과 

실험 결과 연결 리스트는 매니코어 환경에서 확장성이 확보되는 것을 알 수 있다. 하지만 레드-블랙 트리는 확장성이 거의 보이지 않으며, 심지어 작은 코어에서는 단일 코어 환경보다 느리게 동작하는 것을 확인할 수 있었다. 이는 레드-블랙 트리의 특징 때문으로 노드를 이동 시 발생하는 밸런싱 작업으로 인해 트랜잭션이 지속적으로 충돌하기 때문에 발생하는 문제점으로 판단된다. 즉 매니코어 환경에서 STM은 확장성은 보이지만 응용 선택이 중요한 것을 알 수 있다. 그리고 향후 SAM에서 STM을 사용 시 채널의 역할로 이용할 것이며, 이는 연결 리스트에 가까운 형태로 예상된다. 그렇기 때문에 SAM에 STM을 사용하여도 확장성이 확보될 것으로 판단된다.


분할형 운영체제를 위한 하스켈 프로그래밍 환경 분석

본 연구에서는 분할형 운영체제의 일종인 유니커널에서 하스켈 병렬 프로그램이 잘 동작하는지를 확인하고 그 성능을 알아보기 위한 연구를 진행하였다. 이를 위해 사용한 유니커널은 HaLVM(Haskell Lightweight Virtual Machine)은 Galois에서 개발한 유니커널로, 수정된 Xen 위에서 동작하는 커널이다. HaLVM은 기존 마이크로커널 기반 시스템의 한계점을 극복하기 위해 개발된 것으로 소규모 단일 용도 프로그램에 적합하며, 특히 클라우드 서비스에 유용하다고 알려져 있다.

HaLVM은 OS 프로그래밍을 순수 하스켈을 이용하여 작성하였기 때문에 POSIX와 같은 인터페이스를 제공하지 않는다. 그렇기 때문에 기존 하스켈 컴파일러를 사용하지 못하고 HaLVM에서 제공하는 halvm-ghc와 외부 패키지 설치를 위한 halvm-cabal을 이용하여 프로그램을 개발해야 한다. 그리고 HaLVM 간의 통신은 순수 하스켈로 구현된 네트워크 통신을 이용하거나 IVC(inter virtual machine communication)을 이용하여 OS 간의 통신이 이루어진다. 본 연구에서는 이러한 HaLVM의 병렬 프로그래밍 성능을 알아보기 위한 실험을 진행하였으며, 연구에 사용된 하스켈 병렬 프로그래밍 모델은 아래와 같다.


· Eval 모나드

· forkIO

· forkOS

· IVC

· Cloud Haskell

· SAM


Eval 모나드는 병렬 전략을 이용하여 병렬 프로그래밍을 하는 모델이다. 해당 모델의 병렬 단위는 GHC에서 제공하는 병렬 단위 중 가장 작은 스파크(spark)이며, 이를 기반으로 병렬 작업이 수행된다. forkIO는 하스켈 언어에서 제공하는 쓰레드를 이용하여 병렬 프로그래밍을 하는 모델이다. 이 모델의 병렬 단위는 그린 쓰레드이며, 이는 언어 수준에서 제공하는 쓰레드로 통상적으로 사용하는 운영체제 수준의 쓰레드보다 작은 단위이다. forkOS는 하스켈에서 운영체제의 쓰레드를 이용하여 병렬 프로그래밍을 하는 모델이다. 이 모델의 병렬 단위는 쓰레드이며, 사용 방법은 forkIO와 유사하지만 운영체제 쓰레드를 사용하기 때문에 큰 단위의 쓰레드가 실행된다. Cloud Haskell은 메시지 전달 기반의 병렬 프로그래밍 모델이다. 해당 모델의 병렬 단위는 프로세스이며, 노드간 메시지는 소켓을 통해 이루어진다. SAM은 맵 스타일 프로그래밍을 이용한 메시지 전달 기반의 병렬 프로그래밍 모델이다. 해당 모델의 병렬 단위는 프로세스이며, Cloud Haskell과 마찬가지로 소켓을 통해 메시지가 전달된다. 마지막으로 IVC는 HaLVM에서 제공하고 있는 유니커널간의 통신 채널로 이를 이용하여 병렬 프로그래밍을 하는 모델이다. 해당 모델의 병렬 단위는 프로세스로 Xen의 dom0를 통해 데이터를 주고받는다.

본 연구에서는 1에서 40까지의 피보나치 수를 구하는 프로그램을 기준으로 실험을 진행하였다. 즉, 위 6종의 병렬 프로그래밍 모델을 이용하여 피보나치 수를 구하는 프로그램을 병렬로 작성하였으며 실험환경은 인텔 KNL 64코어 단일 노드 환경에서 진행하였다. 실험 결과는 표 3과 같다.


[표3 HaLVM 병렬 프로그래밍 모델 성능 비교 결과]
병렬 모델 병렬 단위 실행 여부 확장성 비고
Eval 모나드 스파크 가능 없음 spark 생성 후 실행 시간 변화 없음
forkIO 그린 쓰레드 가능 없음 Task 생성 후 실행 시간 변화 없음
forkOS OS 쓰레드 불가 - 실행 후 프로그램이 정지됨
IVC 프로세스 가능 있음
Cloud Haskell 프로세스 불가 - 소켓 문제로 실행 불가
SAM 프로세스 불가 - 소켓 문제로 실행 불가


위 표의 결과를 살펴보면 현재 HaLVM에서 병렬성이 있는 것으로 나타나는 것은 IVC 뿐이다. 이는 병렬 단위가 프로세스 단위보다 작은 병렬 모델의 경우 병렬화가 제대로 이루어지지 않는 것으로 판단된다. 이 문제는 HaLVM의 구조적 문제로 판단되며 이를 해결하기 위해서는 HaLVM 구조에 대한 자세한 분석이 필요하다. 이외에 Cloud Haskell과 SAM의 경우 내부적으로 소켓 통신에서 유니캐스트 통신을 사용하는데, HaLVM의 네트워크 스택에서는 이를 지원하지 않는다. 이 문제를 해결하기 위해서는 유니캐스트 기능을 구현하거나 소켓 통신부를 IVC와 같은 내부 통신 구조로 변경할 필요가 있다.



관련 연구

다음과 같은 내용들을 기반으로 새로운 병렬 프로그래밍 모델을 추구한다. 

  • GHC(Glasgow Haskell Compiler)의 RTS(runtime system). 특히 Haskell의 lightweight process 및 IPC 통신 속도. 
  • Cloud-Haskell 및 HdpH의 구현 기술 및 응용 프로그래밍.
  • 동시성 이론(concurrent theory)을 응용한 구현 방법 (Actor 및 Erlang, CSP, Pi-calculus 등)
  • Function serialization 및 process migration 등

결과물

논문

소프트웨어

시연 영상