Sangkon Han(SigmaDream, sd or SD)

"Haskell vs. F# vs. Scala - A High-Level Language Features and Parallelism Support Comparison"을 읽고

Sangkon Han -

본 논문을 연구한 목적은 함수형 언어의 장점을 최대한 활용하기 위해서 lazy와 referential integrity을 활용 한다고 가정 할 때, 1) 함수형 언어는 어떤 모델을 사용해서 병렬처리를 진행하는가? 2) 개별 언어가 서로 다른 병렬처리 모델을 사용하는 이유는 무엇인가? 를 연구하기 위해서 입니다.

이 논문은 Haskell, F# 및 Scala의 병렬 프로그래밍 지원에 대한 성능 및 프로그래밍 가능성(programmability)을 비교합니다. 병렬 계산에 대한 skeleton-based, semi-explicit 및 explicit 접근 방식을 사용하며, 계산(computational) 및 코드의 동등성(coordination aspects)과 최적화(tuning performance)에 중점을 두며 함수의 순수성(purity) 및 언어의 다중 패러다임 디자인(multi-paradigm design)이 프로그램 개발 및 성능에 미치는 영향을 평가합니다.

Introduction

함수형 언어는 내부 상태를 갖지 않는 연산으로 정의됩니다. 1) 불필요한 순차반복을 피할 수 있습니다. 2) 컴파일러 또는 런타임 시스템에서 사용 될 수 있는 병렬 처리를 제공합니다. 이 속성은 명시적 스레드를 생성하거나를 애플리케이션과 통신을 하지 않고도 않고도 병렬 하드웨어를 활용할 수 있는 매력적인 플랫폼을 만들 수 있는 특징입니다. 함수형 언어는 고도의 추상화와 표현력을 제공하므로 병렬 프로그램은 값을 계산하기 보다는 어떻게 계산해야 하는지 지정할 수 있습니다. 병렬 프로그램의 성능을 튜닝하기 위해서는 운영 측면에서 제한적으로 제어하는 것이 바람직합니다.Haskell, F# 및 Scala와 같은 최신 언어에서 제공되는 병렬 처리를 효율적으로 활용하는 방법은 프로그래머에게 충분한 제어 권한을 부여하면서 코드를 최소한으로 수정하는 것을 목표로 합니다.

이 논문은 앞에서 소개한 세 가지 언어에서 제공하는 병렬 메커니즘을 평가하고 여러 수준의 추상화는 물론 선언적 패러다임에서 혼합 패러다임에 이르는 다양한 범위를 다루고 있습니다. 그리고 병렬 성능에 대한 일대일 비교를 결론에 제시합니다. F#과 Scala와 같은 새로운 세대의 프로그래밍 언어는 종종 함수형 패러다임의 장점을 객체 지향 언어에 포함시키는 멀티 패러다임의 접근 방식을 취합니다. 이들은 기존의 최적화 된 VM 기술인 .NET 및 JVM을 사용하여 병렬 처리의 용이성과 효율적인 순차 실행을 결합합니다. 이 논문에서는 순수한 함수형 언어인 Haskell과 다중 패러다임 F# 및 Scala 간의 일대일 프로그래밍 비교를 수행합니다. 스레드를 명시적으로 사용하는 것을 배제합니다. 우리는 언어의 중요한 디자인 문제, 특히 Lazy와 상태 변경 가능한 데이터 구조가 순차적 및 병렬 성능에 미치는 영향을 평가합니다. 마지막으로 서로 다른 기술을 사용하여 Haskell, F# 및 Scala의 일대일 병렬 성능 비교를 통해 다양한 추상화 수준에서 병렬 처리를 비교합니다. Barnes-Hut이 구현한 n-body 알고리즘을 측정 한 모든 언어에서 상당한 속도 향상을 달성 할 수 있었습니다.

우리는 큰 범위에서 병렬형 언어를 암시적 병렬, 잠재적 병렬, 명시적 생성으로 구분합니다. 이 섹션에서는 Scala의 저수준 구조가 명시적으로 분류 될 수 있지만 잠재적 접근법에 중점을 두고 조사합니다. 또 다른 유용한 분류는 순수한 언어인 Haskell, Clean(<<R. Plasmeijer and M. van Eekelen.Funct. Program and Parallel Graph Rewriting. Addison-Wesley, 1993. ISBN 0-201-41663-8.>>)과 F#, Scala를 대표하는 혼합 된 패러다임 언어를 나타내는 OCaml(<<X. Leroy, D. Doligez, A. Frisch, J. Garrigue, D. R ́emy, and J. Vouillon.The OCaml System. Inst. National de Recherche en Informatique et enAutomatique (INRIA), July 2011. Documentation and User’s Manual.>>)과 같은 대부분의 Lisp와 ML과 유사한 언어을 포함하는 프로그래밍 모델로 나누는 것이다. 선언적 프로그래밍 언어의 일반적인 영역은 <<P. Trinder, K. Hammond, and H.-W. Loidl. Encyclopedia of ParallelComputing, chapter Parallel Functional Languages. Springer Verlag, Sept. 2011. ISBN 978-0387097657.>>에서 깊이있게 조사됩니다. 병렬 하스켈 변형에 대한보다 집중된 비교가 <<P. Trinder, H.W. Loidl, and R. Pointon. Parallel and Distributed Haskells. J. Funct. Program., 12(5):469–510, July 2002.>>에 나와있습니다.

선언적 언어의 고성능 구현에 중요한 것은 적응형 런타임 시스템으로, 병렬 처리 관리에 대한 올바른 결정을 내릴 수 있습니다. 일반적으로 명시적 언어는 프로그래머가 결정합니다. 중요한 개념은 Lisp의 변형된 버전인 Mul-T(<<D. Kranz, R. Halstead Jr., and E. Mohr. Mul-T: A High-PerformanceParallel Lisp. InPLDI’89 — Program. Languages Design and Impl.,pages 81–90, Portland, Oregon, June 21–23, 1989.>>)에 도입된 것으로 성능에 중요한 것은 하나의 태스크가 다른 태스크의 계산을 자동으로 포함 할 수있는 테크니컬 한 기능인 lazy task creation(<<E. Mohr, D. Kranz, and R. Halstead Jr.Lazy Task Creation: ATechnique for Increasing the Granularity of Parallel Programs.IEEETrans. on Parallel and Distributed Systems, 2(3):264–280, July 1991.>>)을 도입함으로써 병렬처리의 세분화를 증가시켰다.

Manticore에서 구현 된 F#, PolyML(<<D. C. J. Matthews and M. Wenzel. Efficient Parallel Programmingin Poly/ML and Isabelle/ML. InDAMP10 — Declarative Aspects ofMulticore Program., pages 53–62, Madrid, Spain, Nov. 2010.>>) 및 병렬 CML(<<J. Reppy, C. Russo, and Y. Xiao.Parallel Concurrent ML.InICFP’09 — Int’l Conf. on Funct. Program., pages 257–268, Edin-burgh, UK, Aug. 2009. ACM Press>>은 언어 수준의 미래를 제공하며, 언어 수준 및 시스템 수준의 기여도는 최근의 병렬 기능 언어 구현에서 나타났습니다. GpH의 런타임 시스템은 잠재적인 병렬성을 "스파크(sparks)"로 표현함으로써 느린 작업 생성을 사용합니다. 추가 병렬 처리가 필요하지 않으면 하나의 스파크로 표시된 작업을 프로세서와 작업간에 자유롭고 저렴하게 실행할 수 있습니다. 또 다른 중요한 런타임 시스템 설계 목표는 경량 쓰레드를 지원하여 병렬 처리를 생성하는 오버 헤드를 줄이고 방대한 양의 병렬 처리를 생성하는 프로그래밍 스타일을 장려하여 런타임 시스템이 병렬 처리를 가장 많이 배열 할 수 있는 유연성을 제공합니다. 기본 하드웨어에 적합합니다. Haskell/GHC는 Computer Language Shootout(<<Shootout. The Computer Language Benchmarks Game, June 2012.>>)의 thread-ring 벤치 마크에서 볼 수 있듯이 경량 쓰레드에서 뛰어납니다. Intel의 Cilk Plus 컴파일러에 통합 된 Filaments(<<D. K. Lowenthal, V. W. Freeh, and G. R. Andrews. Using Fine-grain Threads and Run-time Decision Making in Parallel Computing.J. Parallel and Distributed Computing, 37(1):41–54, 1996>>와 Cilk(<<M. Frigo, C. E. Leiserson, and K. H. Randall. The Implementationof the Cilk-5 Multithreaded Language. InPLDI’98 — Conf. on Pro-gram. Language Design and Impl., pages 212–223, Montreal, Quebec,Canada, June 1998>>는 경량 스레드용 런타임 시스템의 다른 예입니다.

Fortress(<<Sun. The Fortress Language. Talks and Posters, June 2012.>>), X10(<<M. Frigo, C. E. Leiserson, and K. H. Randall. The Implementationof the Cilk-5 Multithreaded Language. InPLDI’98 — Conf. on Pro-gram. Language Design and Impl., pages 212–223, Montreal, Quebec,Canada, June 1998>>), Chapel(<<B. L. Chamberlain, D. Callahan, and H. P. Zima.Parallel Pro-grammability and the Chapel Language.Int’l J. of High Perfor-mance Computing Applications, 21(3):291–312, Aug. 2007>>)과 같은 객체 지향 언어에서 고수준 병렬 처리 언어 기능의 사용을 연구 한 여러 실험 언어가 있었습니다. 이 중 Chapel은 현재 대용량 병렬 수퍼 컴퓨터에서 가장 잘 지원됩니다. 이러한 언어는 가상 공유 메모리(X10), 병렬 실행을 위한 구조화 된 프로그래밍 구성 요소(Chapel) 및 소프트웨어 트랜잭션 메모리(Fortress)와 같은 고수준의 구성 요소를 도입하여 소프트웨어 아키텍처의 특성으로 인해 소프트웨어 아키텍처의 재 설계를 방지합니다.

병렬 처리에 대한 높은 수준의 추상화가 점점 더 중요해지는 영역은 병렬 패턴 또는 알고리즘 골격(<<M. Cole.Algorithmic Skeletons: Structured Management of ParallelComputation. MIT Press, Cambridge, MA, 1989.>>)이며 사전 정의 된 병렬 계산 구조가 있는 고차 함수입니다. 라이브러리에서 효율적이고 가능한 하드웨어 종속적 인 병렬 처리의 모든 복잡성을 숨길 수 있기 때문에 고급 병렬 처리 지원 기능이 내장되어 있지 않고 주류 언어로 선택되는 기술로 선택되고 있습니다. 눈에 띄는 사례로는 대규모 분산 아키텍처, Intel Task Building Block(<<J. Reinders.Intel Threading Building Blocks: Outfitting C++ forMulti-core Processor Parallelism. O’Reilly, 2007.>>) 라이브러리 및 Task Parallel Library(<<D. Leijen, W. Schulte, and S. Burckhardt. The Design of a Task Paral-lel Library. InOOPSLA’09 — Int’l Conf. on Object Oriented Program.Systems Languages and Applications, pages 227–242. ACM Press,2009.>>)와 같은 Google의 MapReduce(<<J. Dean and S. Ghemawat. MapReduce: Simplified Data Processingon Large Clusters.Commun. ACM, 51(1):107–113, Jan. 2008.>>) 구현이 있습니다.

Background

Haskell

병렬 계산을 위한 Haskell의 주요 이점은 참조 투명성입니다. 참조 투명성은 Haskell 프로그램에서 병렬 처리에 필요한 개별 하위 표현식을 병렬로 평가할 수 있음을 의미합니다. 그러나 하위 표현식을 너무 세분화 하지 않도록 프로그래머가 병렬로 계산할 가치가 있는 것을 선택하는 것이 바람직합니다.

Haskell의 게으른 의미는 언어가 지원할 수있는 병렬 프로그래밍 모델에 영향을 미친다. 제한되지 않은 지연 평가는 본질적으로 순차적이며 병렬 평가가 어떻게 진행되어야 하는지에 영향을 미칩니다. 열심히 평가하는 정도는 계산을 병렬로 정렬하는 데 필수적입니다. 프로그래머는 다른 표현식이 평행하게 평가를 계속할 수 있도록 충분한 표현식만 평가 되도록 표현의 평가 등급을 지정해야합니다.

Haskell에는 여러 가지 병렬 프로그래밍 모델이 존재하며 이들 사이의 선택은 현재의 문제와 필요한 제어량에 따라 달라집니다. 이것들은 <<P. Totoo and H.-W. Loidl. Parallel Haskell Implementations of the n-body Problem.Conc. and Comp.: Practice and Experience, 2012>에 자세히 설명되어있다. 예를 들어, 동시성 프리미티브를 기반으로하고 라이브러리로서 완전히 개발 된 Par 모나드는 수작업의 작업 포크와 스레드 간의 통신을 요구하는 다소 명시적인 접근 방식을 제공합니다. 반면 DPH는 더 암묵적이며 주로 데이터 병렬 문제에 사용됩니다. 이 논문에서는 최적화 된 변환 기반 컴파일러이자 그래프 축소 기반 런타임 시스템 인 GHC의 확장 인 GpH에 초점을 맞춥니다.

글라스 고 병렬 Haskell[18, 19, 33]은 GHC 컴파일러에 의해 지원되는 Haskell의 최소한의 보수적인 병렬 확장입니다. Haskell은 병렬 처리를 지정하고 제어하기위한 두 가지 기본 프리미티브를 제공함으로써 표준 Haskell을 확장합니다.

−− parallel composition par :: a−>b−>b
−− sequential composition pseq :: a−>b−>b

par를 사용하면 프로그래머가 병렬로 유용하게 계산할 수있는 계산에 주석을 달 수 있습니다. 첫 번째 인수는 시작되고 두 번째 인수의 평가와 병행하여 실행될 수 있습니다. pseq는 병렬 계산을 정렬하는 데 필요한 순차 정렬을 시행합니다.

이러한 프리미티브를 제대로 사용하지 않으면 예기치 않은 병렬 동작이 발생할 수 있습니다 (예 : 이미 평가 된 데이터의 스파크 생성). 평가 전략은 병렬 처리에 대한보다 높은 수준의 제어를 제공하기 위해 프리미티브에 대한 추상화입니다. 평가 전략은 주요 계산에서 조정 측면을 깨끗하게 분리합니다. 예를 들어, parList를 사용하여 목록의 내용을 정의하는 것과는 별도로 각 목록 요소의 병렬 평가를 요구할 수 있습니다. 또한, 평가 방법 및 평가 순서는 평가 전략을 사용하여 지정할 수 있습니다.

다음 예제에서는 parList 전략을 사용하여 parMap 스켈레톤을 정의합니다.

−− definition parallel map using strategies 
parMap str f xs = map f xs `using` parList str
−− usage
parMap rdeepseq f xs

F#

F#(<<D. Syme, A. Granicz, and A. Cisternino.Expert F#. Apress Academic,2007.>>)은 주류 객체 지향 언어의 특징과 함께 ML 스타일의 엄격하고 고차원적이고 불순한 기능 언어의 특징을 결합합니다. 두 패러다임은 프로그래머에게 제공되며, 프로그래머는 응용 프로그램에 대한 패러다임의 적합성과 패러다임에 대한 친숙 함을 기반으로 선택을 할 수 있습니다. F# 구현은 VM으로 .NET으로 컴파일되므로 고도로 최적화 된 VM 구현을 기반으로하고이 중간 플랫폼을 대상으로하는 다른 언어의 라이브러리와 상호 작용할 수 있습니다.

F#은 비동기 워크 플로와 메시지 전달을 통한 동시성과 작업 병렬 라이브러리를 통한 병렬 처리를 잘 지원합니다. 이 라이브러리를 결합하여 응용 프로그램에서 잠재적 인 병렬 처리를 이용할 수 있습니다.

비동기 워크 플로는 스레드를 차단하지 않아도되는 비동기 I/O를 수행하는 동시 및 반응 프로그램을 작성하기위한 것입니다. 그러나 기본 병렬 처리에 사용할 수 있습니다. 그것은 주 스레드를 차단하지 않고 독립적으로 실행할 수있는 비동기 블록 안에 코드 섹션을 래핑하여 작동합니다. 예를 들어, 웹 서버는 요청을 동시에 처리 할 수 있습니다. 병렬 시스템에서는 이러한 요청이 병렬로 실행되므로 성능이 향상됩니다.

let handleRq rq = async { (* some code here *) } 
Async.RunSynchronously(handleRq request)

비동기식 인프라 구조를 기반으로 Mailbox Processor 유형은 Erlang[2]에서와 유사한 에이전트 기반 동시성 구현을 캡슐화합니다. 이 모델에서 에이전트는 병렬로 실행되며 서로에게 메시지를 보내 통신합니다. 공유 가변 상태가 없으면 응용 프로그램을 확장하고 이해를 단순화합니다. 상당히 다른 응용 프로그램 구조가 필요하지만 공통 패턴을 사용하여 에이전트 기반 응용 프로그램을 구현할 수 있습니다.

Task Parallel Library [<<C. Campbell, R. Johnson, A. Miller, and S. Toub.Parallel Pro-gram. with Microsoft .NET — Design Patterns for Decompositionand Coordination on Multicore Architectures. Microsoft Press, Aug.2010.>>, <<D. Leijen, W. Schulte, and S. Burckhardt. The Design of a Task Paral-lel Library. InOOPSLA’09 — Int’l Conf. on Object Oriented Program.Systems Languages and Applications, pages 227–242. ACM Press,>>]는 응용 프로그램에 병렬 처리를 추가하는 프로세스를 단순화하는 API를 제공합니다. TPL은 작업 분할, 스레드 풀에서의 스레드 스케줄링 및 동시성 정도를 동적으로 조정하여 사용 가능한 모든 프로세서를 가장 효율적으로 활용하는 것과 같은 많은 세부 사항을 처리합니다.

프로그래머의 관점에서 보면 스레드에 대한 명확한 개념은 없습니다. 태스크 병렬 처리의 기본 구성은 병렬로 실행되는 독립적인 작업 단위를 나타내는 태스크 개념을 기반으로합니다. 작업은 로드 균형을 조정하기 위해 작업 도용을 사용하는 스레드 풀에 대기합니다. 스레드의 수는 작업량 및 사용 가능한 프로세서를 기반으로 런타임 중에 조정됩니다. 여러 작업을 단일 스레드에 매핑 할 수 있기 때문에 비교적 경량이됩니다. 작업은 여러 가지 기본 제공 방법을 통해 제어 할 수 있습니다. 아래 코드 샘플은 시퀀스의 각 항목을 동시에 처리하고 끝에 동기화하는 작업을 만듭니다.

let tasks ts = 
  [| for t in ts
    Task.Factory.StartNew ( fun () −> 
      process t) |]
Task . WaitAll tasks

데이터 병렬 처리는 Parallel 클래스와 PLINQ를 통해 지원됩니다. Parallel 클래스는 기본 루프 병렬화를 위해 Parallel.For 및 Parallel.ForEach와 같은 정적 메서드를 구현합니다. 이 메소드는 루프를 병렬 처리하는 쉬운 for을 제공합니다. PLINQ는 LANGAGE 통합 쿼리를 기반으로 데이터 병렬성에 대한 더 많은 선언적 모델을 제공합니다. 이것은 일반적인 목적의 호스트 언어 (이 경우 F#)에 SQL과 유사한 쿼리 언어를 직접 임베드하여 표준 데이터 컬렉션에서 XML 데이터, 데이터베이스 또는 객체를 쿼리 할 수있게 해줍니다. 후자는 PLINQ를 사용하는 방법입니다. 이 구현은 효율적인 구현을 위해 내부적으로 TPL을 사용하며 F#에서 상응하는 최고 수준의 언어 메커니즘입니다.

Scala

스칼라는 정적으로 유형화되고 엄격하며 다중 패러다임 프로그래밍 언어이며 기능적 객체 지향 기능을 결합합니다 [22]. 이 언어를 사용하면 일반 프로그래밍 패턴을 간결하고 우아하며 유형 안전 방식으로 표현할 수 있습니다. Scala의 컴파일러는 JVM 플랫폼을 대상으로하므로 Java와 완벽하게 상호 운용되므로 프로그래머가 모든 Java 라이브러리 및 프레임 워크를 사용할 수 있습니다. 또한 언어는 확장 성을 염두에두고 설계되었으므로 언어의 구문을 변경할 필요없이 새로운 기능을 새로운 라이브러리 형태로 쉽게 추가 할 수 있습니다.

스칼라의 주요 초점은 동시 프로그래밍에 대한 최첨단 고수준의 구조와 추상화, 대규모 배포, 확장 성 및 결함 허용 기능을 제공하는 것입니다. 이 목표를 달성하기 위해 많은 프로그래밍 프레임 워크를 제공합니다. 특히 Scala Actors[11]는 동시성을, Scala Parallel Collections[25]는 암시적 병렬 처리를 제공합니다.

스칼라는 액터를 기반으로하는 명시적인 메시지 전달 프로그래밍 모델을 제공함으로써 동시성을 지원합니다. 액터는 비동기식 메시지를 교환하여 서로 통신하는 일류의 경량 프로세스입니다[1]. 이러한 메시지는 수신자의 사서함에 수집됩니다. 액터는 기능적 프로그래밍에서 주요 접근법 인 패턴 매칭을 사용하여 사서함을 반복하고 수집 한 다양한 메시지에 응답 할 수 있습니다. 메시지에 대한 응답에는 다음과 같은 작업이 포함됩니다. 1) Actor 생성, 2) 발신자에게 새로운 메시지를 보내는 단계, 3) 그리고 Actor의 근본적인 행동을 바꾸는 것. 이 설계는 Erlang[2]에 의해 수행된다.

a ! msg // actor sending a message
// receiving msgs and responding with actions
receive {
case msg pattern 1 => action 1 case msg pattern 2 => action 2 case msg pattern n => action n
}

Scala Parallel Collections Framework은 시퀀스, 맵, 세트에 대한 병렬 구현을 일반적인 병렬 연산[25]과 함께 정의하는 병렬 수집 서브 패키지를 제공합니다. 프로그래머는 순차 콜렉션에서 par 메소드를 사용하여 해당 병렬 구현을 호출 할 수 있습니다. seq메소드를 사용하면 병렬 수집이 순차적으로 다시 작동합니다. 이 접근법의 이점은 병렬 연산이 순차 버전과 동일한 이름을 가질 수 있다는 것입니다. 즉 프로그래머는 아래에 표시된 것처럼 올바른 위치에 메소드를 제공함으로써 병렬 처리를 쉽게 도입 할 수 있습니다.

xs.map( (x: Int) => x + 1 ) // sequential xs.par.map( (x: Int) => x + 1 ).seq // parallel

병렬 수집 라이브러리의 구현은 Java Fork/Join 프레임 워크[13] 위에 구축됩니다. 이것은 기본적으로 사용 가능한 프로세서간에 fork/join 작업을 효율적으로 스케줄하는 것을 목표로하는 스레드 풀 구현입니다. Divide-and-conquer 및 병렬 처리에 대한 재귀 적 접근 방식에 영감을 받아 fork/join 작업은 새 작업을 스폰(포크)하고 실행이 진행되기 전에 완료(조인) 할 때까지 기다릴 수 있습니다. 현재 fork/join 구현은 작업 세분화를 효율적으로 제어하기 위해 적응 작업 도용 [8, 13]과 지수 적 작업 분할[8]이라는 두 가지 핵심 기술을 사용합니다. 프로그래머가 프레임 워크에서 제공하는 병렬 처리 수준을 제대로 제어하지는 못하지만 병렬 성능을 높이기 위해 구현을 신중하게 조정했습니다.

// TODO

하스켈은 객체 지향 프로그래밍과 명령형 프로그래밍을위한 기능을 포함하지 않는 순전히 기능적인 언어로 설계되었습니다. 그러나 외국어 통합을 지원합니다. C를 통해 IO 모나드 내부의 안전하지 않은 작업을 수행 할 수 있습니다. F #은 대부분 기능적이지만 디자인은 오프셋의 다른 패러다임과의 통합을 목표로합니다. 스칼라는 주로 Java의 영향을받으며 많은 언어 개념이 객체에 묶여 있습니다. 그러나 구문이 더 많은 전통적인 함수형 언어와 약간 다르긴하지만 상당히 훌륭한 기능적 지원을 제공합니다.

세 가지 언어 모두 자동 형식 유추를 사용하는 고급 형식 시스템을 제공하며 다중 코어 병렬성에 대한 높은 수준의 접근 방식을 지원합니다. Haskell은 플랫폼 기반으로 자체적 인 그래프 기반 런타임 시스템 (STGM)을 가지고 있으며 FIL #을 CIL (Common Intermediate Language)로 컴파일 한 다음 CLR (Common Language Runtime)에서 실행하고 Scala는 Java Byte 코드를 작성하고 JVM (Java Virtual Machine)에서 실행됩니다.

데이터 구조 측면에서 모든 언어에서 가장 일반적으로 사용되는 것은 Haskell에서 기본적으로 게으르고 다른 두 언어에서는 엄격한 목록과 가변 배열입니다. F #에는 평가가 수요 중심 인 순서와 Powersepack의 LazyList가 있는데, 하스켈 목록과 유사합니다. LazyList는 캐싱을 사용하고 시퀀스와 달리 패턴 일치를 허용합니다.

Implementation

N-Body Problem(다체 문제)

다체 문제(N-Body Problem)은 여러 개(N >= 3)의 입자들 간의 상호작용을 계산하는 것으로, N이 3을 넘어가면 대수적인 해법은 존재하지 않고 컴퓨터 시뮬레이션에 의존해야 합니다. 대표적인 다체 문제는 은하 충돌, 우주 거대 구조 모델링 등에 사용되고 있는 중력 시뮬레이션등이 있습니다.

다체 문제는 계산량이 복잡한 것으로 유명합니다. 예를 들면 10개의 입자가 있다고 가정했을ㄷ 때, 각각의 입자는 나머지 9개의 다른 입자로부터 받는 중력을 계산한다면 총 계산은 9*10=90번 이루어집니다. 입자 개수가 적을 때는 상관이 없지만 입자가 수천, 수만 개로 많아질 경우 예를 들어, 10,000개의 입자가 있을 경우 필요한 계산의 양은 1억 번이 되고, 이 1억 번의 계산을 시뮬레이션이 진행되는 동안 매 프레임마다 수행해야 하기 때문에 알고리즘이 매우 복잡합니다. 그리고 다체 문제 알고리즘의 복잡도는 N^2 입니다.

Barnes-Hut(DEMO)알고리즘은 충분히 가까운 몸체를 그룹화하여 계산을 진행합니다. 해당 입자를 쿼드-트리(quad-tree)에 저장함으로써 입자의 집합을 반복적인 그룹으로 나눕니다. 쿼드-트리는 이진 트리와 비슷하지만 각 노드에 4개의 자식이 있습니다(일부는 비어있을 수 있음). 이 알고리즘을 사용하면 N*logN으로 계산량을 줄일 수 있습니다.

Conclusion

이 논문에서는 순수 함수형 언어인 Haskell과 다중 패러다임 언어인 F#와 Scala에서 구현된 n-body 문제를 해결하기 위한 Barnes-Hut 알고리즘의 병렬 구현을 비교했습니다. 멀티 코어를 기반으로 한 컴퓨터에서 병렬 처리 성능을 평가합니다. 각 언어는 여러 가지 병렬 프로그래밍 구조를 사용합니다. 특히 Haskell의 GpH, F#의 비동기 워크플로와 TPL, 스칼라의 병렬 컬렉션과 Actor를 사용합니다. 우리는 Haskell(최대 8 코어)에서 최대 5.62, F# (코어 4)에서 2.28, Scala에서 4.51(코어 8)의 속도 향상을 달성했습니다.

병렬처리로 코드를 변경할 때 주의 사항은 다음과 같습니다.

  • 모든 언어에서 가장 높은 추상화 수준을 사용하는 버전이 (거의)가장 좋은 성능을 보여주었습니다.

  • annotations이나 라이브러리가 아닌 프리미티브를 통해 언어에서 병렬 처리를 first-class로 지원 및 제공하는 것은 Haskell에서 중요합니다. 예를 들어 chunking parMap에서 고차 함수를 사용하여 스레드 세부 사항을 명시적으로 조정할 수 있습니다.

  • lazy Haskell버전에서 조심스럽게 최적화하면 엄격한(strict) F# 및 Scala를 능가하는 성능을 얻을 수 있습니다.

  • 순수한 언어가 아닌 기능(side-effect가 발생하는)을 초기에 사용하여 순차 코드 최적화는 코드의 병렬 처리를 심각하게 방해합니다. 그러나 병렬 프로세스가 끝날 때 순수한 언어가 아닌 기능을 선택적으로 사용하면 성능이 현저히 향상 될 수 있습니다.

  • Mono에서 제공하는 상당히 낮은 성능의 .NET 구현으로 인해 Linux에서 F#의 성능이 좋지 않아서 F#이 현재 Linux에서의 병렬 처리에 대한 실용적인 선택이 되지 못합니다.

  • 스칼라의 저수준 Actor 기반 코드가 제공하는 기능은 성능을 크게 향상시키지 못하므로 추가 프로그래밍 작업은 정당화되지 않습니다.

다른 언어와 비교할 때, 우리는 모든 언어가 상당히 고수준의 구조를 제공한다는 것을 알았지만 제공된 제어의 정도는 다릅니다.

  • 예를 들어 Haskell은 잘 알려진 고차 함수의 병렬 버전으로 초기 병렬 처리를 쉽게 지정할 수 있습니다. 주석 또는 라이브러리가 아닌 프리미티브를 통해 제공되므로 언어의 모든 기능을 사용할 수 있으므로 사용자가 사용자 정의 할 수있는 청킹(chunking)을 통해 병렬 성능을 조정할 수 있습니다.

  • 반면에 F#과 Scala는 프로그래머가 입력하지 않아도 자동 관리를 목표로 런타임 시스템 구현 내에서 병렬 처리에 대한 대부분의 제어를 제한합니다. 그러므로 튜닝은 더 어렵습니다.

  • Haskell은 풍부한 라이브러리와 공격적인 최적화에서 우위를 점하고 있습니다. 지연연산을 통해 병렬 처리를 모듈 방식으로 지정 할 수 있으므로 구성 요소를 수정 할 필요가 없으며 명시적 스레드를 회피할 수 있습니다. 따라서, Haskell은 최소한의 기능으로 병렬 처리를 할 수 있는 언어입니다.

  • F#과 Scala는 병렬화를 위한 몇가지 메커니즘을 제공합니다. 일부는 하스켈만큼 높은 수준이며 성능을 튜닝하기 위해서 저수준의 기능도 함께 제공됩니다. 따라서 이러한 언어는 저수준의 측면에서 직접적인 방법을 제공하며 객체 지향 및 절차지향적인 언어의 기능을 사용할 수 있습니다.