하스켈 연구

매니코어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) 구조 분석 및 병렬 아키텍처에 특화된 최적화 연구

연구 결과

본 연구에서는 표절 검사 프로그램을 기반으로 하스켈의 병렬 프로그래밍 모델에 관해 연구를 진행하였다. 첫 번째 연구로 하스켈의 병렬 프로그래밍 모델 중 공유 메모리를 기반으로 하는 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%의 변동 폭이 감소한 것을 확인할 수 있었다.

관련 연구

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

  • 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 등

결과물

논문

소프트웨어