순수 함수형 언어로 작성된 쌍방시뮬레이션 알고리듬의 성능을 병렬화로 향상시키는 방법 연구
Parallelization of a Purely Functional Bisimulation Algorithm
2
조회
0
다운로드
1
인용
0
참고문헌
키워드
초록
본 논문에서는 순수 함수형 언어로 작성된 쌍방시뮬레이션 알고리듬의 성능을 멀티코어 프로세서 컴퓨터에서 병렬화로 향상시키는 방법을 연구한다. 이 병렬화에 있어 핵심 아이디어는 순수함수형 프로그램의 참조 투명성을 십분 활용하면 병렬화가 전혀 고려되지 않고 작성된 초기 구현으로부터 최소한의 수정만으로 성능 개선 효과를 기대할 수 있다는 것이다. 초기 구현과 병렬화구현 둘 다 순수 함수형 언어인 하스켈로 작성되었다. 초기 구현을 병렬화할 때 변화는 아주 적어서 병렬화된 구현에서도 초기 구현의 프로그램 구조가 거의 그대로 유지되었다. 벤치마크를 통해 제시된 간단한 병렬화만으로도 초기 구현과 비교해 두 배 이상의 성능 개선을 확인했다. 또한, 병렬화와는 별개의 최적화 기법인 메모이제이션이 적용된 버전의 쌍방시뮬레이션 구현에도 같은방식의 병렬화를 적용함으로써 마찬가지로 성능을 개선할 수 있음을 확인하였다.
Abstract
In this paper, we demonstrate a performance boost by parallelizing a purely functional bisimulation algorithm on a multicore processor machine. The key idea of this parallelization is exploiting the referential transparency of purely functional programs to minimize refactoring of the original implementation without any parallel constructs. Both original and parallel implementations are written in Haskell, a purely functional programming language. The change from the original program to the parallel program is minuscule, maintaining almost original structure of the program. Through benchmark, we show that the proposed parallelization doubles the performance of the bisimulation test compared to the original non-parallel implementation. We also shaw that similar performance boost is also possible for a memoized version of the bisimulation implementation.
참고문헌 (12)
- D. Michie, "Memo Functions: a Language Feature with “Rote-Learning" Properties", Edinburgh University, Dept. of Machine Intelligence and Perception, ~ (1967)
- J. Huges, "Functional Programming languages and Computer Architecture", pp.129~148 (1985), Springer-Verlag
- 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)
- J. S. Conery, "Parallel Interpretation of Logic Programs", Proc. of the 1981 Conference on Functional Programming languages and Computer Architecture, pp.163~170 (1981)
- 김연어, "Haskell Eval 모나드와 Cloud Haskell 간의 성능 비교", 정보과학회논문지, 44(8), pp.791~802 (2017), 한국정보과학회
- R. Milner, "Communication and Concurrency" (1989), Prentice Hall
- D. Sangiorgi, "A theory of bisimulation for pi-calculus", Acta Informatica, 3, pp.69~97 (1996), Springer
- A. Tiu, "SPEC : an equivalence checker for security protocols", APLAS ‘16 : Asian Symposium on Programming Languages and System, pp.87~95 (2016)
- R. Horne, "Quasi-Open Bisimilarity with Mismatch is Intuitionistic", LICS '18:Proceedings of the 33rd Annual ACM, 2018, 26~35
- R. Clifton-Everest, "Streaming Irregular Arrays", Haskell 2017: Proceedings of the 10th ACM SIGPLAN International Symposium on Haskell, pp.174~185 (2017)