이름 관리 모나드 라이브러리 기반의 심볼릭 실행기에 결정적 병렬화를 적용하는 연구

국문 초록 (Abstract)

본문에서는 순수 함수형 언어인 하스켈로 작성된 심볼릭 실행의 병렬화를 위한 상태 모나드 기반의 라이브러리에 결정적 병렬화를 적용하기 편리한 API를 설계/구현하고 멀티코어 컴퓨터에서 벤치마크를 통해 실제 성능을 향상을 확인해 본다. 일반적으로 순수 함수형 프로그램은 병렬화가 쉽다고 알려져 있으나 실제 구현에서 핵심 알고리듬 외적인 부분에서 의도치 않은 순차적 데이터 의존성의 발생으로 병렬화가 어려워질 수 있다. 심볼릭 실행 구현에서는 지금껏 사용했던 변수와 겹치지 않는 새 이름을 생성함으로써 서로 다른 범위의 이름이 같은 변수끼리 혼동하는 착오를 피하는 방식을 종종 활용한다. 그런데 이를 순차적 상태 관리로 구현한 경우가 많아 병렬화에 걸림돌이 된다. 이 논문에서는 하스켈의 범용적 이름 관리 라이브러리인 unbound-generics의 새 이름 생성 기능에 순차적 의존성을 회피할 수 있는 확장 기능을 제공함으로써 병렬적 심볼릭 실행 구현을 간소화하는 데 기여하였다. 우리가 구현한 병렬화 확장의 특징은 기존 unbound-generics 라이브러리의 내부 구현을 그대로 유지한 상태의 확장이라는 점으로, 기존에 unbound-generics로 작성된 순차적 심볼릭 실행기의 성능 저하 우려가 전혀 없다는 점이다. 따라서 병렬화가 필요한 부분에만 확장 기능을 적용하는 방식으로 활용하여 성능을 개선할 수 있다.

다국어 초록 (Multilingual Abstract)

In this paper, we extend a generic library framework based on the state monad to exploit deterministic parallelism in a purely functional language Haskell and provide benchmarks for the extended features on a multicore machine. Although purely functional programs are known to be well-suited to exploit parallelism, unintended squential data dependencies could prohibit effective parallelism. Symbolic execution programs usually implement fresh name generation in order to prevent confusion between variables in different scope with the same name. Such implementations are often based on squential state management, working against parallelism. We provide reusable primitives to help developing parallel symbolic execution programs with unbound-genercis, a generic name-binding library for Haskell, avoiding sequential dependencies in fresh name generation. Our parallel extension does not modify the internal implementation of the unbound-generics library, having zero possibility of degrading existing serial implementations of symbolic execution based on unbound-genecrics. Therefore, our extension can be applied only to the parts of source code that need parallel speedup.

목차 (Table of Contents)

• [Abstract]
• [요약]
• Ⅰ. Introduction
• Ⅱ. Preliminaries
• Ⅲ. Supporting parallelism in a name-freshness monad
• Ⅳ. Benchmark
• Ⅴ. Related work
• Ⅵ. Conclusions
• REFERENCES

참고문헌 (Reference)

1 안기영, "순수 함수형 언어로 작성된 쌍방시뮬레이션 알고리듬의 성능을 병렬화로 향상시키는 방법 연구" 한국컴퓨터정보학회 26 (26): 11-17, 2021

2 "Unbound-kind-generics: Support for programming with names and binders using kind-generics"

3 "Unbound-generics: Support for programming with names and binders using GHC Generics"

4 E. Sebastian, "STCLang: state thread composition as a foundation for monadic dataflow parallelism" 146-161, 2019

5 Y. Kim, "SSAM: A Haskell Parallel Programming STM Based Simple Actor Model" IOP Publishing 1566 : 2019

6 S. Marlow, "Runtime Support for Multicore Haskell" 65-78, 2009

7 J. Arora, "Provably Space-efficient Parallel Functional Programming" ACM 5 : 1-33, 2021

8 K. Hammond, "Profiling Scheduling Strategies on the GRIP Multiprocessor" 73-98, 1992

9 T. Moto-oka, "Overview of the Fifth Generation Computer System Project" 417-422, 1983

10 P. W. Trinder, "Low level Architecture-independence of Glasgow Parallel Haskell (GpH)" 1998

11 김화목, "GC-Tune을 이용한 Haskell 병렬 프로그램의 성능 조정" 한국정보과학회 23 (23): 459-465, 2017

12 A. Rodriguez, "Comparing Libraries for Generic Programming in Haskell" 44 (44): 111-122, 2009

13 S. Weirich, "Binders unbound" 333-345, 2011

14 L. B. van den Haak, "Accelerating Nested Data Parallelism: Preserving Regularity" Springer 12247 : 426-442, 2020

15 Elvira Albert, "A Formal, Resource Consumption-Preserving Translation from Actors with Cooperative Scheduling to Haskell*" IOS Press 177 (177): 203-234, 2020