DEVS (Discrete Event Systems Specification) is one of the most frequently utilized system specifications to model discrete event systems in the real world. Recently, large DEVS models are designed and implements, so the execution time of the DEVS models has become an important issue in this community. The execution of a DEVS model requires an execution environment which consists of a simulation engine for DEVS and implemented models utilizing the engine. To speed up the execution, this thesis hypothesizes that accelerating the scheduling algorithm of the engine is critical.
One of the most frequently used scheduling algorithms is a hierarchical algorithm proposed by B.P. Zeigler. The algorithm utilizes the hierarchical structure of a running DEVS model to select the next call of a function of a sub-model. Due to this hierarchical approach, as the depth of the structure increases, the path of the message routing gets longer, and the execution time consequently gets larger. Unlike the scheduling algorithm of DEVS, the scheduling algorithm of the execution of event-based models is unrelated to the hierarchy increase. This independence between the scheduling and the hierarchy is achieved by managing events from models with an event list. This thesis finds a chance to adopt this event list to the scheduling algorithm of DEVS.
Hence, this thesis proposes three event-based execution environments for DEVS. Two environments consist of redesigned DEVS models and new simulation engines with the scheduling algorithm of the event-based approach. Another environment consists of existing DEVS models with no changes and a new simulation engine with the event-based scheduling algorithm. The scheduling algorithm shared by the three execution environments is that 1) the DEVS model generates events of specifying which functions to call and puts the events in the event list, 2) the simulation engine calls the function specified by the right next event in the event list. This event list management is the key of detaching the execution environment from the hierarchy, eventually the source of the execution performance increase.
To verify the performance improvement, this thesis compares the existing DEVS execution environment with the hierarchy to the three proposed environments. The comparison shows that the new environments requiring model redesigns have the first and the second shortest execution times. Also, the new environment with no model change has significantly shorter execution time than the existing environment. This thesis expects that this performance improvement will be applicable to the DEVS modeling practices as well as the DEVS simulation engine development.
DEVS(Discrete Event Systems Specification)는 이산 사건 시스템을 모델링하는 시스템 명세로서, 집합론에 근거하여 수학적인 틀을 제공한다. DEVS는 크고 복잡한 시스템을 설계하고 구현하기에 적합하여 최근에 복잡한 시스템, 특히 워 게임 등에 많이 쓰이고 있다. 시뮬레이션할 시스템의 단위가 커짐에 따라 DEVS 모델을 실행하여 결과를 얻는 것까지의 실행 속도가 중요한 문제가 되고 있다. DEVS 모델의 실행은 실행 환경에 의해서 이루어지는데, 이것은 시뮬레이션 엔진과 엔진이 해석 가능하도록 구현된 모델로 이루어진다. 이 논문은 시뮬레이션 엔진이 모델을 실행하는데 쓰이는 스케줄링 알고리즘이 실행 속도를 높이는 것에 있어서 중요한 역할을 한다고 가정한다.
스케줄링 알고리즘 중에 가장 많이 쓰이는 것은 B.P Zeiger에 의해서 제안된 계층적인 스케줄링 알고리즘이다. 이것은 다음 실행될 하위 모델을 결정하기 위해 DEVS 모델의 계층적인 구조를 활용한다. 이러한 계층적인 접근으로 인해 구조가 깊어질수록 메시지가 이동하는 경로가 길어지고 실행 시간이 증가하게 된다. 하지만 이것과 다르게 이벤트 기반의 시뮬레이션은 계층적인 오버헤드를 제거 할 수 있다. 이벤트 기반의 시뮬레이션은 이벤트 리스트에 의해서 관리되는 이벤트에 의해서 이루어지는데, 계층적인 구조와 독립적으로 모델의 실행을 결정한다.
따라서 이 논문은 이벤트 기반 시뮬레이션을 적용하여 DEVS 모델을 실행 할 수 있도록 세 가지 이벤트 기반 실행 환경을 제안한다. 먼저 그 중 두 가지는 이벤트 지향 시뮬레이션 엔진에 맞도록 재설계된 DEVS 모델과 이벤트 기반 시뮬레이션 엔진을 사용하는 것이고. 나머지 하나는 기존의 DEVS 모델을 그대로 사용하면서 이벤트 기반 시뮬레이션을 적용하도록 하여 모델 구현의 편의성과 재사용성을 높이는 것이다.
성능 향상을 확인하기 위해서 이 논문은 기존의 DEVS 실행 환경과 제안하는 실행 환경을 비교한다. 그 결과는 모델을 새롭게 디자인하는 두 가지 경우가 성능이 가장 좋음을 볼 수 있고 그 다음으로 모델의 변화 없는 이벤트 기반 실행 환경의 성능으로, 3가지 실행 환경 모두 기존의 실행 환경보다 좋은 성능을 보인다. 이 논문은 이러한 성능 향상이 DEVS 모델링과 DEVS 시뮬레이션 엔진 개발에 적용될 수 있을 것이라고 기대한다.
