Cellular automata(CA) modeling is one of modeling paradigms for a complex system. CA represents a system organized as two-dimensional cellular models. Cellular models during CA simulation update their states in every discrete time step, and discrete-time simulation sometimes constrains the precision and the efficiency of CA. To avoid this problem, this thesis simulates cellular models in discrete-event approach.
Improving the CA simulation performance becomes crucial for simulating large-scale cellular models. The parallel simulation is one of the ways to improve the simulation performance. Previously, the parallel simulation has utilized the parallel computing power of multi-core CPU or multiple CPUs. In the thesis, the parallel simulation utilizes GPU which has a powerful parallel computing power with the relatively low-cost compared to CPU.
The thesis proposes a discrete-event and parallel simulation environment for cellular models using GPU. To provide a formal modeling and simulation tool, the Parallel DEVS (PDEVS) formalism is used. The PDEVS formalism is appliable to both discrete-event simulation and parallel simulation. The structure of the proposed simulation environment is designed considering the PDEVS simulation algorithm and the general program flow using GPU.
The thesis performs three experiments using proposed simulation environment. One experiment compares the execution time of PDEVS simulation with DEVS simulation. The second experiment shows the correlated relation between the number of cellular models and the reduced execution time from parallel simulation. The last experiment compares the execution time of PDEVS simulations using the different parallel computing power utilizing GPU and multi-core CPU. With the simulation results, as the number of cellular models is larger, execution time diminishes much more in proposed simulation environment.
복잡한 시스템을 모델링 하기 위한 방법 중 하나로 셀 오토마타 모델링이 있다. 셀 오토마타는 대상 시스템을 이차원의 격자 모델들로 표현하여 시뮬레이션 하는데 사용되어 왔다. 셀 오토마타 시뮬레이션에서 각 셀 모델들은 매 이산 시간 마다 모델 상태를 갱신한다. 이처럼 매 이산 시간 마다 모델 상태 연산을 하기 때문에 효율성 측면에서의 문제가 야기된다. 그러나 효율성 문제를 극복하기 위해 이산 시간 크기를 늘리게 되면 시뮬레이션 정확도 측면에서 문제가 발생한다. 그래서 본 논문에서는 이런 이산 시간 시뮬레이션에서 발생하는 문제를 극복하고자 셀 모델을 이산 이산 사건 시뮬레이션을 하고자 한다.
다수의 셀 모델 시뮬레이션에서는 시뮬레이션 성능이 중요하다. 시뮬레이션 성능을 올리기 위한 방법 중 하나로 병렬 시뮬레이션 방법이 있다. 기존의 병렬 시뮬레이션은 다수의 CPU를 이용하거나 한 CPU 내에 여러 코어를 이용하였다. 그러나 본 논문에서는 이 CPU의 병렬 자원을 사용하는 것이 아니라 가격은 저렴하지만 병렬 연산에서는 더욱 강력한 CPU보다 강력한 GPU를 이용하고자 한다.
본 논문에서는 GPU를 병렬 자원으로 사용하여 셀 모델을 이산 사건, 병렬 시뮬레이션 할 수 있는 환경을 하고자 한다. 시뮬레이션 형식론으로 Parallel DEVS(PDEVS)를 이용하였다. 시뮬레이션 형식론을 이용하면 시뮬레이션을 위한 정형화된 툴이 제공되고 시뮬레이션 테스트, 대화 수단 등의 장점을 얻을 수 있다. 다양한 시뮬레이션 형식론 중 PDEVS는 이산 사건, 병렬 시뮬레이션 둘 모두에 적합하다. 제안한 시뮬레이션 환경은 PDEVS 시뮬레이션 알고리즘과 GPU를 사용하는 일반적인 프로그램 흐름을 고려하여 디자인 되었다.
제안한 환경을 이용하여 3가지 실험을 하였다. 첫 번째 실험은 대상 시스템을 DEVS로 시뮬레이션과 시뮬레이션 시간을 비교하였다. 두 번째는 셀 모델의 수와 제안된 시뮬레이션 환경을 이용함으로써 얻는 병렬 이득과의 관계를 실험하였다. 마지막 실험은 제안된 환경에서 GPU에서 병렬 처리하는 부분을 CPU의 다수의 코어를 이용하였을 때와 성능을 비교하였다. 실험결과를 바탕으로 셀 모델의 수가 많을수록 제안된 시뮬레이션 환경을 이용하면 시뮬레이션 시각이 더욱 감소한다.
