이산사건 시스템의 계층적 검증방법론

송해상,이완복,Song, Hae-Sang,Lee, Wan-Bok 한국정보통신학회 2007 한국정보통신학회논문지 Vol.11 No.5

상태폭발문제는 이산사건 시스템 검증과정에서 피하기 어려운 문제로 알려져 있으며, 큰 시스템 해석을 어렵게 만드는 본질적인 요인이다. 본 논문에서는 이산사건 시스템의 무시간 DEVS/DEVS 명세에 대한 계층적인 설계/검증 방법을 제안하여 상태폭발문제를 회피할 수 있는 방법을 보인다. 제안한 방법은 DEVS 상위모델과 DEVS 하위 모델간의 설계/검증 과정을 계층적이면서도 반복적인 방식을 채택하여 검증에 필요한 요소 이외에는 정제 과정을 통하여 없애는 방안이다. 간단한 예제를 통하여 제안된 방법론을 소개하고 있다. State explosion is a well-known problem that impedes analysis md testing of discrete event systems, thus making the verification of large systems intrinsically difficult job. This paper suggests a hierarchical verification methodology of untimed DEVS model which can alleviate the state explosion problem. The method is a repetitive procedure of designing and verifying between the upper level and the lower level models abstracting away the unnecessary information with respect to a given verification task. A small example was employed to show our suggested method in detail.

시뮬레이션 기반 적응형 실시간 작업 제어 프레임워크를 적용한 웨이퍼 제조 공정 DEVS 기반 모델링 시뮬레이션

송해상,이재영,김탁곤,Song, Hae-Sang,Lee, Jae-Young,Kim, Tag-Gon 한국시뮬레이션학회 2010 한국시뮬레이션학회 논문지 Vol.19 No.3

The inherent complexity of semiconductor fabrication processes makes it hard to solve well-known job scheduling problems in analytical ways, which leads us to rely practically on discrete event modeling simulations to learn the effects of changing the system's parameters. Meanwhile, unpredictable disturbances such as machine failures and maintenance diminish the productivity of semiconductor manufacturing processes with fixed scheduling policies; thus, it is necessary to adapt job scheduling policy in a timely manner in reaction to critical environmental changes (disturbances) in order for the fabrication process to perform optimally. This paper proposes an adaptive job control framework for a wafer fabrication process in a control system theoretical approach and implements it based on a DEVS modeling simulation environment. The proposed framework has the advantages in view of the whole systems understanding and flexibility of applying new rules compared to most ad-hoc software approaches in this field. Furthermore, it is flexible enough to incorporate new job scheduling rules into the existing rule set. Experimental results show that this control framework with adaptive rescheduling outperforms fixed job scheduling algorithms.

DEVS 다이어그램 기반 이산사건 시뮬레이션 소프트웨어 구현 및 정적 검증기법: 실용적 접근방법

송해상,Song, Hae Sang 한국시뮬레이션학회 2018 한국시뮬레이션학회 논문지 Vol.27 No.3

Discrete Event System Specification (DEVS) has been used for decades as it provides sound semantics for hierarchical modular specification of discrete event systems. Instead of the mathematical specification, the DEVS diagram, based on the structured DEVS formalism, has provided more intuitive and convenient representation of complex DEVS models. This paper proposes a clean room process for implementation and verification of a DEVS diagram model specification into a simulation software source code. Specifically, it underlies a sequence of transformation steps from conformance and integrity checking of a given diagram model, translation into a corresponding tabular model, and finally conversion to a simulation source code, with each step being inversely verifiable for traceability. A simple example helps developers to understand the proposed process with associated transformation methods; a case study shows that the proposed process is effective for and adaptable to practical simulation software development. 이산사건시스템명세(DEVS) 형식론은 이산사건시스템을 모듈러하고 계층적으로 모델링할 수 있는 잘 정의된 의미론을 제공하고 있어 이산사건시스템 모델링 시뮬레이션 (M&S)에 많이 사용되어 왔다. 이러한 수학적 표현 대신에 DEVS 다이어그램은 복잡한 시스템을 보다 직관적이며 편리한 표현력을 제공한다. 본 논문은 DEVS 다이어그램을 이용하여 표현된 모델을 시뮬레이션 코드로 체계적으로 구현하며 검증하는 DEVS 클린룸 프로세스를 제안하였다. 구체적으로, 주어진 다이어그램 모델의 적합성 검사, 테이블 DEVS 모델로의 변환, 마지막으로 시뮬레이션 소스코드로 변환하는 방법과 역으로 추적성을 기반으로 한 검사기법을 통해 정적 검증하는 구체적인 방법을 제시하였다. 간단한 예제를 통해 제안된 프로세스를 적용하는 구체적인 방법을 설명하였으며, 적용사례 통해 제안된 기법이 실용적으로 적용 가능한 효과적인 프로세스임을 확인하였다.

C-DEVS형식론을 이용한 실시간 이산사건 제어시스템의 논리 해석 기법

송해상,김탁곤,Song, Hae Sang,Kim, Tag Gon 한국시뮬레이션학회 2012 한국시뮬레이션학회 논문지 Vol.21 No.4

실시간 시스템의 복잡도가 증가함에 따라 임시방편적 시스템 해석 방법은 시스템 동작 영역 전체를 완전하게 분석하는 데는 한계가 있다. 모델링을 기반으로 한 정형 기법은 그러한 한계점을 극복 할 수 있다. 본 논문은 모델 기반 정형 기법을 이용하여 실시간 시스템의 안전성 및 필연성 등과 같은 논리적 타당성을 이산 사건 모델 수준에서 분석하는 방법을 제안한다. 먼저, 분석 대상 실시간 시스템은 이산사건 수준에서 계층적으로 모듈화하여 모델을 명세하는 수학적 형식론인 DEVS (Discrete Event Systems Specification) 형식론으로 기술된다. 다음으로, 기술된 DEVS 모델은 시간 명세가 포함된 전역 상태 공간을 표현하는 C-DEVS (Communicating DEVS) 형식론으로 표현한 후 C-DEVS 형식론의 해석 알고리즘을 통해 시스템 동작을 분석된다. 제안된 C-DEVS 형식론 및 해석 알고리즘은 주어진 시스템의 동작 특성을 분석하는 과정에서 시스템의 상태 공간을 완전하게 빠짐없이 탐색하는 것을 보장한다. 간단한 건널목 제어 시스템의 안전성 분석 사례 연구를 통하여 제안된 모델 기반 해석 기법의 효율성을 예시 하였다. As complexity of real-time systems is being increased ad hoc approaches to analysis of such systems would have limitations in completeness and coverability for states space search. Formal means using a model-based approach would solve such limitations. This paper proposes a model-based formal method for logical analysis, such as safety and liveness, of real-time systems at a discrete event system level. A discrete event model for real-time systems to be analyzed is specified by DEVS(Discrete Event Systems Specification) formalism, which specifies a discrete event system in hierarchical, modular manner. Analysis of such DEVS models is performed by Communicating DEVS (C-DEVS) formalism of a timed global state transition specification and an associated analysis algorithm. The C-DEVS formalism and an associated analysis algorithm guarantees that all possible states for a given system are visited in an analysis phase. A case study of a safety analysis for a rail road crossing system illustrates the effectiveness of the proposed method of the model-based approach.

Structured DEVS Formalism: A Structural Modelling Method of Discrete Event Systems

송해상,Song, Hae-Sang The Korea Society for Simulation 2012 한국시뮬레이션학회 논문지 Vol.21 No.2

최근 몇 십년간 이산사건시스템명세(DEVS) 형식론은 이산사건시스템을 모듈러하고 계층적으로 모델링할 수 있는 잘 정의된 의미론을 제공하여 왔다. 그럼에도 불구하고 실용 엔지니어들은 실세계의 시스템을 모델링에 적용하는데 어려움을 겪기도 하는데 이는 DEVS가 많은 상태와 사건들을 구조화되지 않은 형태로 명세해야 하는 것 때문이다. 본 논문은 집합 이론을 바탕으로 그러한 사건 및 상태집합들을 구조화된 형태로 표현하는 Structured DEVS 형식론과 이와 연관된 DEVS 다이어그램을 제안하고자 한다. 위상, 변수, 포트 등의 개념을 사용하여 집합들을 명세한 구조적 DEVS 형식론은 원래의 DEVS 형식론과 동등함을 증명하였다. DEVS 다이어그램을 이용하여 구조적 DEVS 형식론으로 표현된 예시 모델이 쉽게 객체지향 시뮬레이션 환경에서 구현될 수 있음을 보임으로써 제안된 형식론이 효과적임을 보였다. In recent decades, it has been known that the Discrete Event System Specification, or DEVS, formalism provides sound semantics to design a modular and hierarchical model of a discrete event system. In spite of this benefit, practitioners have difficulties in applying the semantics to real-world systems modeling because DEVS needs to specify a large size of sets of events and/or states in an unstructured form. To resolve the difficulties, this paper proposes an extension of the DEVS formalism, called the Structured DEVS formalism, with an associated graphical representation, called the DEVS diagram, by means of structural representation of such sets based on closure property of set theory. The proposed formalism is proved to be equivalent to the original DEVS formalism in their model specification, yet the new formalism specifies sets in a structured form with a concept of phases, variables and ports. A simplified example of the structured DEVS with the DEVS diagram shows the effectiveness of the proposed formalism which can be easily implemented in an objected-oriented simulation environment.

Star-Mesh NoC 반도체칩 설계를 위한 트랜잭션 수준 DEVS 형식론 기반 모델링 기법

송해상(Hae Sang Song),김원종(Won Jong Kim) 대한전자공학회 2010 대한전자공학회 학술대회 Vol.2010 No.6

This paper introduces a new modeling simulation methodology for NoC(Network-on-Chip) design in a transaction level based on a mathematical formalism called the DEVS (Discrete Event Systems Specification) formalism. This methodology can be used to verify architectural design prior to CAD engineering design to determine desirable parameters such as buffer size and latency of Star-mesh NoC topology as well as performance evaluation. The transaction level model of NoC in DEVS formalism can be simulated by using the simulation engine DEVSim++. This can be useful for architectural exploration of NoC before costly engineering design and fabrication.

가설적 모델의 기계학습을 이용한 연속시간 동적시스템 모델링 프레임워크

송해상(Hae Sang Song),김탁곤(Tag Gon Kim) 한국시뮬레이션학회 2023 한국시뮬레이션학회 논문지 Vol.32 No.1

본 논문은 실제 시스템의 빅데이터가 확보되었고 시스템에 대한 정보를 일부 알고 있을 때 파라미터를 가진 그레이박스 혹은 블랙박스 형태의 가설모델을 설정하고 기계학습을 통해 모델을 자동 생성하는 기법을 제안하였다. 제안된 프레임워크를 구현하고 다양한 가설모델에 대한 실험을 통해 학습된 모델의 정합도와 가설모델의 학습에 소요되는 비용에 대해 분석하였다. 실험결과 제안된 가설모델 기반 기계학습 기법으로 상미분방정식으로 기술될 수 있은 연속시스템의 그레이박스 혹은 화이트박스 가설모델과 주어진 빅데이터를 이용하여 모델링을 했을 때 상당히 좋은 성능과 정확도를 보인 모델을 찾아낼 수 있음을 확인하였다. 이 기법은 최근 생성된 빅데이터를 이용하여 디지털트윈 모델의 일치성을 자동 갱신하거나 새로운 입력에 대한 출력을 예측하는 목적으로도 잘 활용될 수 있을 것으로 기대된다. This paper proposes a method of automatically generating a model through a machine learning technique by setting a hypothetical model in the form of a gray box or black box with unknown parameters, when the big data of the actual system is given. We implements the proposed framework and conducts experiments to find an appropriate model among various hypothesis models and compares the cost and fitness of them. As a result we find that the proposed framework works well with continuous systems that could be modeled with ordinary differential equation. This technique is expected to be used well for the purpose of automatically updating the consistency of the digital twin model or predicting the output for new inputs using recently generated big data.

BlockSim++: 연속시스템의 계층적 모델링 및 시뮬레이션을 위한 블록기반 경량 프레임워크

송해상(Hae-Sang Song),서정만(Jeong-Man Se) 한국컴퓨터정보학회 2012 韓國컴퓨터情報學會論文誌 Vol.17 No.12

본 논문은 실용 엔지니어를 위해서 일반미분방정식으로 표현될 수 있는 연속시스템의 계층적인 모델 개발을 위한 모델링 기법 및 객체지향언어 기반의 경량 시뮬레이션 구축 환경을 제안하였다. 제안된 블록 기반 모델링 형식론은 단위 모델의 동적인 행위를 나타내는 기본블록 모델과 모델들의 계층적인 구조를 나타내는 결합블록 모델 형식론으로 이루어져 있다. 이러한 수학적 모델의 시뮬레이터를 객체지향 언어로 구현하기 위한 시뮬레이션구축 프레임워크인 BlockSim++를 제안하였다. 제안된 프레임워크는 재사용성을 제공하며, 수학적 모델을 쉽게 구현할 수 있게 하고, 또한 외부 응용 소프트웨어와도 쉽게 결합할 수 있는 인터페이스를 제공한다. 간단한 하이브리드 모델링 시뮬레이션 예시를 통해 제안된 모델링 형식론과 시뮬레이션 프레임워크를 이용하여 그 유용성을 입증하였다. This paper proposes for practical engineers a lightweight modeling and simulation environment for continuous system models specified in ordinary differential equations, which are time-domain specification of such systems. We propose a block-oriented specification formalism that has two levels: one for atomic behavior and the other the structure of models. Also we provide with a simulation framework, called BlockSim++, which make models specified in the block-oriented formalism be easily translated in object-oriented program that runs with the proposed simulation framework. The proposed formalism and framework has advantage of reuse such that it can be easily integrated into application programs and heterogeneous simulators. We illustrates the usefulness of the proposed framework by a simple hybrid modeling simulation example.

시스템수준 시뮬레이션과 디스크 I/O수준 시뮬레이션 연동을 위한 DEVSim++과 DiskSim 사이의 인터페이스 설계 및 구현

송해상(Hae Sang Song),이순주(Sun Ju Lee) 한국컴퓨터정보학회 2013 韓國컴퓨터情報學會論文誌 Vol.18 No.4

본 논문은 분산 스토리지 시스템과 같이 디스크를 내장하고 있는 다수의 컴퓨터 노드로 구성되어 있는 스토리지 시스템에서 개개의 디스크 스펙 변화에 따른 전체 성능을 분석하고자 할 때 잘 알려져 있는 블록 I/O 수준의 디스크 시뮬레이터인 DiskSim과 시스템수준의 시뮬레이터와의 연동을 위한 인터페이스의 설계 및 구현에 관한 기법을 제안하였다. 본 연구에서 시스템수준 시뮬레이션 엔진으로는 계층적이고 모듈러한 모델링 기법을 지원하는 DEVS 형식론을 지원하는 범용 이산사건시스템 시뮬레이션 엔진인 DEVSim++을 목표로 하였고 이식성을 위해 DiskSim과 DEVSim++ 시뮬레이션 엔진의 내부는 수정하지 않는 것을 가정하였다. 이를 만족하기 위해 I/O 수준의 DiskSim 시뮬레이터와 시스템 수준의 DEVSim++ 기반 시뮬레이터 사이의 연동 인터페이스 구조를 제안하였다. 이 구조에서는 여러 인스턴스의 DiskSim을 관리하는 DiskSimManager의 개념을 도입하여 I/O 수준 시뮬레이션과 시스템 수준 시뮬레이션 간의 시간과 사건(데이터) 동기화를 담당하도록 설계하였고, 시스템 수준의 DEVS 모델에서 간편하게DiskSim을 접근할 수있도록 감싸는 DEVS wrapper 모델을 제안하였다. 벤치마크 실험결과 설계 구현된 연동 인터페이스를 사용한 시뮬레이션 결과는 DiskSim만의 단독 시뮬레이션 결과와 정확히 일치함을 확인함으로써 설계 구현된 연동 인터페이스가 목적에 맞게 잘 동작함을 입증하였다. This paper deals with the design and implementation of an interface for interoperation between DiskSim, a well-known disk simulator, and a system-level simulator based on DEVSim++. Such inter-operational simulation aims at evaluation of an overall performance of storage systems which consist of multiple computer nodes with a variety of I/O level specifications. A well-known system-level simulation framework, DEVSim++ environment is based on the DEVS formalism, which provides a sound semantics of modular and hierarchical modeling methodology at the discrete event systems level such as multi-node computer systems. For maintainability we assume that there is no change of the source codes for two heterogeneous simulation engines. Thus, we adopt a notion of simulators interoperation in which there should be a means to synchronize simulation times as well as to exchange messages between simulators. As an interface for such interoperation DiskSimManager is designed and implemented. Various experiments, comparing the results of the standalone DiskSim simulation and the interoperation simulation using the proposed interface of DiskSimManager, proved that DiskSimManager works correctly as an interface for interoperation between DEVSim++ and DiskSim.

역 DEVS의 개념과 이산사건 시스템의 감시제어

송해상(Hae Sang Song),김탁곤(Tag Gon Kim) 제어로봇시스템학회 1994 제어로봇시스템학회 국내학술대회 논문집 Vol.1 No.1