본문 바로가기
  • Home

Parallelization of a Purely Functional Bisimulation Algorithm

  • Journal of The Korea Society of Computer and Information
  • Abbr : JKSCI
  • 2021, 26(1), pp.11-17
  • DOI : 10.9708/jksci.2021.26.01.011
  • Publisher : The Korean Society Of Computer And Information
  • Research Area : Engineering > Computer Science
  • Received : December 22, 2020
  • Accepted : January 4, 2021
  • Published : January 29, 2021

Ki Yung Ahn 1

1한남대학교

Accredited

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.

Citation status

* References for papers published after 2022 are currently being built.

This paper was written with support from the National Research Foundation of Korea.