The DEVS (Discrete Event Systems Specification) formalism specifies discrete event systems in a hierarchical, modular form. Within the formalism, state transition is specified by internal and external transition functions caused by scheduled internal events and randomly arrived external events, respectively.
This thesis deals with the parallel simulation of DEVS models. The DEVS formalism and the associated abstarct simulator algorithm are implemented in a distributed environment and named as P-DEVSim++. For distributed simulation, two classes, Monitors and ModelIDs, are developed. Monitors acts as the distributed simulation kernel for DEVS simulation and ModelIDs supplies Monitors with mapping information and interfaces of all models and abstract simulators. In P-DEVSim++, internal events as well as external events of abstract simulators associated with DEVS models can be processed in parallel. For such processing, the PARINT algorithm, an optimistic simulation algorithm based on the Time Warp algorithm, is proposed. The proposed algorithm localizes rollbacks of a model within the model itself, not possible in the standard Time Warp approach. An advantage of such localization is simulation speedup.
This thesis also devises mapping of DEVS models to utilize the parallelism of P-DEVSim++ in a hypercube multicomputer environment without multicasting. The coupling relationship between internal and external events is classified into four cases. For each case, a mapping algorithm to reduce the overall simulation finishing time is presented. Especially, task graphs are transformed to reduce the simultaneous external events synchronization overhead by the flattening and deepening methods. Also, when multiple internal events occur simultaneously and each internal event is associated with multiple external events, a hypercube is partitioned into a set of subcubes so that an internal event and the associated external events can be processed in the same subcube.
The performance of our algorithms is measured through the simulation of two benchmark models within the P-DEVSim++ performance simulation environment. For such performance simulation, the runtime behavior of P-DEVSim++ is modeled and implemented. The result shows that the potential parallelism of the PARINT algorithm is very high and the proposed mapping algorithm generates diverse mappings against various combinations of system parameters. With the generated mapping, the significant parallelism of distributed simulation of hierarchical, modular discrete event models is achieved.
DEVS(Discrete Event Systems Specification)형식론은 이산사건 시스템을 계층적이고 모듈화된 형태로 기술한다. DEVS에서 상태전이는 스케쥴링에 의한 내부사건과 불규칙적으로 도착하는 외부사건에 의해서 이루어진다.
본 논문에서는 DEVS 모델의 병렬 시뮬레이션을 다룬다. 우선 DEVS 형식론과 그에 관련된 계층적 시뮬레이션 알고리즘인 추상화 시뮬레이터 알고리즘을 분산환경에서 구현한 P-DEVSim++을 개발하였다. 분산 시뮬레이션을 위해서 Monitors와 ModelIDs 클래스가 구현되었다. Monitors 글래스는 DEVS 시뮬레이션을 위한 분산시뮬레이션 커널의 역할을 하며 ModelIDs 클래스는 Monitors 클래스에게 모델과 추상화 시뮬레이터에 대한 매핑정보와 인터페이스를 제공한다. P-DEVSim++에서 는 모델의 추상화 시뮬레이터들이 외부사건과 내부사건을 병렬처리한다. 그것을 위해서 Time Warp 알고리즘에 기반을 둔 낙관적인 병렬분산 시뮬레이션 알고리즘인 PAR_INT 알고리즘을 고안하였다. 그 알고리즘에서는 어떤 모델의 롤백이 그 모델에 국한되는 성질을 가진다. 이것은 일반적인 Time Warp 알고리즘에서는 불가능한 것으로서 그런 국소화된 롤백의 처리로 인하여 시뮬레이션 속도가 향상되는 장점이 있다.
또 본 논문에서는 P-DEVSim++을 하이퍼큐브 멀티컴퓨터 환경에서 다중통신 없이 수행할 때 그 병렬성을 이용하기 위한 DEVS 모델의 매핑에 대해서도 다룬다. 우선 내부사건과 외부사건 간의 관련성을 네가지의 경우로 분리하였다. 각각의 경우에서 전체 시뮬레이션 수행시간을 줄이는 매핑 알고리즘이 제안되었다. 특히, 동시에 발생되는 외부사건을 동기화하는 오버헤드를 줄이기 위해서 태스크 그래프를 정형적인 방법으로 변환하였다. 또, 여러 내부사건이 동시에 발생되고 각 내부사건이 여러 외부사건을 야기할 경우에는 전체 하이퍼큐브를 서브큐브들의 집합으로 나누어서 하나의 내부사건과 그에 관련된 외부사건들이 같은 서브큐브에서 처리되도록 하였다.
안된 알고리즘들의 성능은 P-DEVSim++ 성능평가 시뮬레이션 환경에서 두가지의 벤치마크 모델을 이용하여 측정되었다. 이때 성능측정 시뮬레이션을 위해서 P-DEVSim++의 수행특성이 모델링되고 구현되었다. 시뮬레이션 결과, PAR_INT 알고리즘의 병렬성이 매우 크며 제안된 매핑 알고리즘은 시스템의 여러 파라미터들의 조합에 대해서 다양한 형태의 매핑을 출력하였다. 또, 그 구해진 매핑을 이용하여 계층적으로 모듈화된 이산사건 모델의 분산 시뮬레이션에서의 병렬성을 얻을 수 있었다.
