이름 관리 모나드 라이브러리 기반의 심볼릭 실행기에 결정적 병렬화를 적용하는 연구
Deterministic Parallelism for Symbolic Execution Programs based on a Name-Freshness Monad Library
1
조회
0
다운로드
1
인용
0
참고문헌
키워드
초록
본문에서는 순수 함수형 언어인 하스켈로 작성된 심볼릭 실행의 병렬화를 위한 상태 모나드 기반의 라이브러리에 결정적 병렬화를 적용하기 편리한 API를 설계/구현하고 멀티코어 컴퓨터에서벤치마크를 통해 실제 성능을 향상을 확인해 본다. 일반적으로 순수 함수형 프로그램은 병렬화가쉽다고 알려져 있으나 실제 구현에서 핵심 알고리듬 외적인 부분에서 의도치 않은 순차적 데이터의존성의 발생으로 병렬화가 어려워질 수 있다. 심볼릭 실행 구현에서는 지금껏 사용했던 변수와겹치지 않는 새 이름을 생성함으로써 서로 다른 범위의 이름이 같은 변수끼리 혼동하는 착오를피하는 방식을 종종 활용한다. 그런데 이를 순차적 상태 관리로 구현한 경우가 많아 병렬화에 걸림돌이 된다. 이 논문에서는 하스켈의 범용적 이름 관리 라이브러리인 unbound-generics의 새 이름생성 기능에 순차적 의존성을 회피할 수 있는 확장 기능을 제공함으로써 병렬적 심볼릭 실행 구현을 간소화하는 데 기여하였다. 우리가 구현한 병렬화 확장의 특징은 기존 unbound-generics 라이브러리의 내부 구현을 그대로 유지한 상태의 확장이라는 점으로, 기존에 unbound-generics로 작성된 순차적 심볼릭 실행기의 성능 저하 우려가 전혀 없다는 점이다. 따라서 병렬화가 필요한 부분에만 확장 기능을 적용하는 방식으로 활용하여 성능을 개선할 수 있다.
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.
참고문헌 (15)
- "Unbound-generics: Support for programming with names and binders using GHC Generics"[URL]
- K. Hammond, "Profiling Scheduling Strategies on the GRIP Multiprocessor", Intl. Workshop on the Parallel Implementation of Functional Languages, pp.73~98 (1992)
- P. W. Trinder, "Low level Architecture-independence of Glasgow Parallel Haskell (GpH)", Glasgow Workshop on Functional Programming (1998)
- S. Marlow, "Runtime Support for Multicore Haskell", ICFP 2009, pp.65~78 (2009)
- T. Moto-oka, "Overview of the Fifth Generation Computer System Project", Proceedings of 10th Annual International Symposium on Computer Architecture, (10th ISCA'83), pp.417~422 (1983)
- J. Arora, "Provably Space-efficient Parallel Functional Programming", Proceedings of the ACM on Programming Languages, 5, pp.1~33 (2021), ACM
- L. B. van den Haak, "Accelerating Nested Data Parallelism: Preserving Regularity", LNCS, 12247, pp.426~442 (2020), Springer[DOI]
- Y. Kim, "SSAM: A Haskell Parallel Programming STM Based Simple Actor Model", Journal of Physics: Conference Series, 1566 (2019), IOP Publishing[DOI]
- Elvira Albert, "A Formal, Resource Consumption-Preserving Translation from Actors with Cooperative Scheduling to Haskell*", Fundamenta Informaticae, 177(3-4), pp.203~234 (2020), IOS Press[DOI]
- 김화목, "GC-Tune을 이용한 Haskell 병렬 프로그램의 성능 조정", 정보과학회 컴퓨팅의 실제 논문지, 23(8), pp.459~465 (2017), 한국정보과학회[DOI]
- 안기영, "순수 함수형 언어로 작성된 쌍방시뮬레이션 알고리듬의 성능을 병렬화로 향상시키는 방법 연구", 한국컴퓨터정보학회논문지, 26(1), pp.11~17 (2021), 한국컴퓨터정보학회[DOI]
- S. Weirich, "Binders unbound", Proceeding of the 16th ACM SIGPLAN international conference on Functional Programming, ICFP 2011, pp.333~345 (2011)
- "Unbound-kind-generics: Support for programming with names and binders using kind-generics"[URL]
- A. Rodriguez, "Comparing Libraries for Generic Programming in Haskell", ACM SIGPLAN Notices, 44(2), pp.111~122 (2009)[DOI]
- E. Sebastian, "STCLang: state thread composition as a foundation for monadic dataflow parallelism", Haskell 2019: Proceedings of the 12th ACM SIGPLAN International Symposium on Haskell, pp.146~161 (2019)