[논문]이벤트 지향 DEVS 실행 환경의 설계, 구현 및 성능 비교

권세중; 김탁곤

doi:10.9709/jkss.2011.20.1.087

이벤트 지향 DEVS 실행 환경의 설계, 구현 및 성능 비교
Design, Implementation and Performance Analysis of Event-oriented Execution Environment for DEVS 원문보기

한국시뮬레이션학회논문지 = Journal of the Korea Society for Simulation, v.20 no.1, 2011년, pp.87 - 96

권세중 (KAIST 전기및전자공학과) , 김탁곤 (KAIST 전기및전자공학과)

초록
AI-Helper

DEVS는 이산 사건 시스템을 명세하는 집합론에 근거한 수학적인 틀이다. 이러한 DEVS를 통해 시스템을 시뮬레이션할 때는 명세된 DEVS로부터 구현된 모델과 시뮬레이션 엔진으로 이루어진 실행 환경이 필요하다. 시뮬레이션 엔진은 스케줄링 알고리즘을 통해 모델을 해석하고 실행하는데, 주로 DEVS의 계층적이고 모듈러한 특성을 따라 계층적인 스케줄링 방법을 사용한다. 그러나 이 방법은 계층적인 구조로 인해 시간 관리와 메시지 패싱에 있어서 오버헤드가 존재한다. 본 논문에서는 이러한 오버헤드를 해결하기 위해 이벤트 지향 시뮬레이션을 적용한다. 이벤트 지향의 시뮬레이션은 이벤트에 의해서 모델이 실행되며 이벤트 리스트에 의해 이벤트가 관리된다. 이벤트 리스트에 의해서 시간 관리가 되고 메시지 패싱이 이루어지기 때문에 계층적인 오버헤드를 줄이고 성능 향상을 이룰 수 있다. 본 논문은 이벤트 리스트를 이용한 실행 환경을 제안하고 이러한 실행 환경을 위한 모델 구현 방안에 대해 논하며, 각 실행 환경의 성능을 비교, 분석한다.

Abstract ▼ AI-Helper

DEVS(Discrete Event Systems Specification) is a set theoretic formalism developed for specifying discrete event system. For execution of DEVS, we need an execution environment, which consists of simulation engine and models interpreted by the simulation engine. Common existing environments use hierarchical scheduling algorithm for DEVS execution. This hierarchical scheduling is a proper algorithm for DEVS execution because of hierarchical and modular characteristics. But this algorithm has overheads owing to message passing and time management. To overcome these overheads, we apply event-oriented simulation to DEVS execution and we remove hierarchical overheads. In eventoriented simulation, the scheduling of model execution is performed by events and event list. We propose three event-oriented execution environments for DEVS and experiment about the performance of our proposed environments in comparison with the existing execution environment using the hierarchical scheduling. The experimental results show our environments works better than existing environment using the hierarchical scheduling.

주제어

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

이러한 방법들을 통해 상당부분 성능 향상을 가져올 수 있으나 내부적으로는 계층적 알고리즘을 사용함으로써 계층적 알고리즘이 지니는 한계를 동일하게 가진다. 본 논문에서는 위와는 다르게 실행 환경의 시뮬레이션 알고리즘에 이벤트 지향 시뮬레이션을 적용해서 DEVS 실행의 성능 향상을 가능하게 하는 이벤트 리스트를 사용한 실행 환경을 제시한다.

가설 설정

1. 시뮬레이션 엔진은 가장 상위의 이벤트를 추출한다.
4. 시뮬레이션 엔진은 가장 상위의 이벤트를 추출한다.

제안 방법

DEVS로 명세된 위의 모델을 표2의 실행 환경에 맞게 각각 실행 환경에 맞게 구현하여 비교, 실험 하였다.
성능 측정을 위해서 한 번에 활성화 되는 모델의 개수를 늘리면서 실행 했다. 대조군으로서 깊이가 1이 되도록 계층적 구조를 수정한 모델을 사용하였다. 이벤트 리스트를 사용한 환경에서는 계층적인 구조가 없기 때문에 계층적인 모델을 사용하는 것이 불공평할 수 있다.
DEVSim++은 DEVS 형식론을 C++으로 구현한 실행 환경이다^[8]. 따라서 계층적으로 구현된 DEVS 모델 또한 DEVSim++을 위해 구현된 모델을 사용하였다. 구현의 편의성이라는 측면에서, 명세된 DEVS에 가깝다는면에서 오른쪽으로 갈수록 장점이 있다.
하지만 성능 향상이 있는 대신에 사용자가 모델을 구현하기에 비교적 불편하다는 문제와 DEVS의 모듈러한 특성을 잃어버리는 단점이 있다. 따라서 이벤트 지향의 모델을 구현하는 것과 함께 객체 지향, 기존의 계층적인 모델을 구현하여 이러한 단점을 해결하면서도 여전히 계층적인 오버헤드를 제거하는 방법 또한 제안한다.
둘째로, 실험 결과에는 모델 자체의 실행 시간도 들어있기 때문에 성능 개선이 스케줄링 알고리즘에 따른 것인지 확인하는 것이 필요하다. 따라서 프로파일링(Profiling)을 통해 알고리즘의 개선에 따른 성능 향상의 정도를 확인했다
본 논문에서는 이벤트 리스트를 사용한 실행 환경을 제안하고 계층적인 스케줄링의 실행 환경에 비해 성능 향상이 있다는 것을 보인다. 또한 이벤트 리스트를 사용한 실행 환경을 위한 여러 가지 모델 구현 방법을 살펴보고 장단점을 분석하고 성능을 분석한다.
위의 실행 환경들의 정확성 검증과 성능 테스트를 위해서 각각의 실행 환경을 C++로 구현하고 명세된DEVS를 각각의 실행 환경에 맞는 모델로 구현하였다. 성능 비교를 위해서 각 구현물에서 공유할 수 있는 부분은 최대한 공유하도록 하였으며, 이벤트 리스트를 관리하는 힙 구조 또한 기존의 DEVSim++ 모델이 모델 중에 가장 빠른 tN을 가지는 모델을 결정할 때 사용하는 힙 구조를 그대로 사용하였다.
성능 측정을 위해서 한 번에 활성화 되는 모델의 개수를 늘리면서 실행 했다. 대조군으로서 깊이가 1이 되도록 계층적 구조를 수정한 모델을 사용하였다.
실험에는 표 2와 같이 3개의 실행 환경을 구현하고 대조군으로서 계층적인 스케줄링을 사용한 DEVSim++을 사용하였다. DEVSim++은 DEVS 형식론을 C++으로 구현한 실행 환경이다^[8].
지금까지 이벤트 리스트를 사용하여 스케줄 하는 실행 환경과 그 실행 환경을 위한 3가지 모델 구현 방안을 살펴보았다. 위의 실행 환경들의 정확성 검증과 성능 테스트를 위해서 각각의 실행 환경을 C++로 구현하고 명세된DEVS를 각각의 실행 환경에 맞는 모델로 구현하였다. 성능 비교를 위해서 각 구현물에서 공유할 수 있는 부분은 최대한 공유하도록 하였으며, 이벤트 리스트를 관리하는 힙 구조 또한 기존의 DEVSim++ 모델이 모델 중에 가장 빠른 tN을 가지는 모델을 결정할 때 사용하는 힙 구조를 그대로 사용하였다.
이러한 두 가지 문제를 해결하기 위해 기존의 계층적이고 모듈러하게 구현된 모델을 이벤트 리스트를 이용하여 스케줄 하는 방법을 제안한다.
계층적 스케줄링 알고리즘은 계층적이고 모듈러한 DEVS의 구조를 적용하여 시뮬레이터를 구현한다. 이러한 알고리즘은 DEVS의 원자 모델에 대응되는 시뮬레이터(Simulator)와 결합모델에 대응되는 코디네이터(Coordinator)가 존재하여 구현된 DEVS 모델의 함수를 호출하고 결과를 돌려 받으면서 시뮬레이션을 진행한다. 이때 명세된 DEVS로부터 구현된 모델은 수동적인 형태로 오직 시뮬레이션 엔진의 호출을 받고 결과를 돌려준다
지금까지 DEVS 실행 속도를 개선하기 위한 이벤트 리스트의 실행 환경들을 제안하고 성능을 살펴보았다.
지금까지 이벤트 리스트를 사용하여 스케줄 하는 실행 환경과 그 실행 환경을 위한 3가지 모델 구현 방안을 살펴보았다. 위의 실행 환경들의 정확성 검증과 성능 테스트를 위해서 각각의 실행 환경을 C++로 구현하고 명세된DEVS를 각각의 실행 환경에 맞는 모델로 구현하였다.

이론/모형

하지만 성능은 왼쪽으로 갈수록 빠른 성능을 보일 것으로 예상된다. 실험에는 단일 서버 큐잉 모델을 사용했으며 그림 7과 같다.

성능/효과

계층적 구조에 따른 문제점을 가지고 있는 계층적 알고리즘 대신에 이벤트 리스트를 사용하여 이벤트 관점으로 스케줄링 함으로써 성능 향상을 얻을 수 있었다. 실행 환경의 모델은 3가지 방법으로 구현 할 수 있는데 이벤트 지향 - 객체 지향 - 기존의 계층적인 모델 순으로 속도가빠르지만 그만큼 모델 구현에 있어서 단점이 있다.
또한 계층적인 구조를 통해 실행 시간을 수집하던 시간 관리가 오직 이벤트를 등록하고 이벤트를 추출하는 작업으로 대신 된다. 계층적인 알고리즘의 많은 부분이 삭제되어, 이벤트 리스트를 사용한 실행 환경이 계층적인 스케줄링 알고리즘보다 좋은 성능을 가진다는 결론을 얻을 수 있다.
둘째로, 계층적인 스케줄링의 실행 환경에서는 모델이 수동적이고 독립적으로 구현되는 반면에 이벤트 리스트를 사용한 실행 환경에서는 구현된 모델이 직접 다른 모델을 호출하는 이벤트를 스케줄 해야 하기 때문에 시뮬레이션 엔진과 구현된 모델 사이에, 또한 모델과 모델 사이에 완벽한 독립성을 이룰 수 없다
본 논문에서는 이벤트 리스트를 사용한 실행 환경을 제안하고 계층적인 스케줄링의 실행 환경에 비해 성능 향상이 있다는 것을 보인다. 또한 이벤트 리스트를 사용한 실행 환경을 위한 여러 가지 모델 구현 방법을 살펴보고 장단점을 분석하고 성능을 분석한다.
표 4를 통해서 이벤트 리스트를 사용한 실행 환경들이 모두 빠른 성능을 보였으며 그 성능은 이벤트 지향의 모델 - 객체 지향 모델 - DEVSim++ 모델 순이라는 것을 확인할 수 있다. 이 결과는 구현 편의성과 정 반대되는 결과로서 장단점이 있다는 것을 확인할 수 있다.

후속연구

둘째로, 실험 결과에는 모델 자체의 실행 시간도 들어있기 때문에 성능 개선이 스케줄링 알고리즘에 따른 것인지 확인하는 것이 필요하다. 따라서 프로파일링(Profiling)을 통해 알고리즘의 개선에 따른 성능 향상의 정도를 확인했다
좀 더 원시적인 방법으로 구현하는 이벤트 지향의 모델이 성능에 있어서 조금 더 빠른 성능을 보일 것이다. 클래스의 멤버 함수를 실행하는 것보다 함수를 실행하는 것이 더 빠르고, 이벤트에 대응하는 함수들이 다 분리되어 있기 때문이다.
첫째로, 성능은 공간을 비효율적으로 더 사용함으로써 좋아질 수 있기 때문에 효율적인 공간 사용이 이루어졌는지 확인이 필요하다. 크게 봤을 때, 대조군에 비해서 이벤트 지향 실행 환경은 이벤트를 저장하기 위한 공간을 더 사용한다.

질의응답

핵심어	질문	논문에서 추출한 답변
	이산 사건 시스템이란 무엇인가?	이산 사건 시스템이란 시스템 내부 혹은 외부 요인으로 인하여 불규칙적으로 실수 시간에 일어나는 이벤트에 의해서 상태가 변화하는 시스템이다. 이러한 이산 사건 시스템은 통신 모델, 물류 시스템, 생산 시스템, 교통 시스템, 워 게임 등에서 찾아 볼 수 있다.
	이산 사건 시스템은 어디에서 찾아 볼 수 있는가?	이산 사건 시스템이란 시스템 내부 혹은 외부 요인으로 인하여 불규칙적으로 실수 시간에 일어나는 이벤트에 의해서 상태가 변화하는 시스템이다. 이러한 이산 사건 시스템은 통신 모델, 물류 시스템, 생산 시스템, 교통 시스템, 워 게임 등에서 찾아 볼 수 있다.
	계층적인 스케줄링의 단점은 무엇인가?	계층적인 스케줄링에서 시간 관리는 하위 모델로부터 상위 모델로 정보가 모아지는 형태로 일어나고 메시지 패싱은 계층적인 구조를 따라 상위 모델을 거쳐서 전달되는 구조를 가진다. 따라서 계층적 구조가 깊어지고 복잡해질수록 중간 과정이 늘어나게 되고 성능이 느려지게 된다.

참고문헌 (8)

Bernard P. Zeigler, Herbert Praehofer, and Tag Gon Kim, Theory of modeling and simulation. ACADEMIC PRESS, 2001.
Y.G. Kim and T.G. Kim, "Optimization of model execution time in the DEVSim++ environment," In proc. of 1997 european simulation symposium, Passau, Germany, pp. 215-219, Oct., 1997.
Wan Bok LEE and Tag Gon KIM, "Performance evaluation of concurrent system using formal model: simulation speedup," IEICE Transactions on fundamentals of electronics, Communications and computer sciences, Vol. E86-A, No. 11, pp. 2755-2766, 2003.
Tag Gon KIM, IE801 Lecture Note, EE, KAIST, 2009, http://smslab.kaist.ac.kr/
Tag Gon KIM, DEVSim++ v3.0 Developer's manual, 2006, http://smslab.kaist.ac.kr/
권세중, 김탁곤, "Event-oriented 기반의 DEVS 모델 실행 환경," 한국군사과학기술학회 '10종합학술대회 , pp. 380-383, 2010년 6월.
권세중, 김탁곤, "계층적인 DEVS 모델의 이벤트 기반 실행 환경," 한국시뮬레이션학회 '10추계학술대회, pp. 117-122, 2010년 10월.
Tag Gon Kim and Sung Bong Park, "The DEVS formalism: hierarchical modular systems specification in C++," 1992 European simulation multiconference, York, United Kingdom, pp. 152-156, June, 1992.

저자의 다른 논문 :

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증

이벤트 지향 DEVS 실행 환경의 설계, 구현 및 성능 비교
Design, Implementation and Performance Analysis of Event-oriented Execution Environment for DEVS 원문보기

초록
AI-Helper

Abstract ▼ AI-Helper

주제어

AI 본문요약
AI-Helper

문제 정의

가설 설정

제안 방법

이론/모형

성능/효과

후속연구

질의응답

참고문헌 (8)

이 논문을 인용한 문헌

저자의 다른 논문 :

관련 콘텐츠

원문 보기

원문 URL 링크

오픈액세스(OA) 유형

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

연합인증

이벤트 지향 DEVS 실행 환경의 설계, 구현 및 성능 비교 Design, Implementation and Performance Analysis of Event-oriented Execution Environment for DEVS 원문보기

초록 용어보기논문에서 용어와 풀이말을 자동 추출한 결과로, 시범 서비스 중입니다. AI-Helper

Abstract ▼ AI-Helper

주제어

AI 본문요약 엑셀 다운로드 AI-Helper

문제 정의

가설 설정

제안 방법

이론/모형

성능/효과

후속연구

질의응답

참고문헌 (8)

이 논문을 인용한 문헌

저자의 다른 논문 :

권세중 (3) 김탁곤 (52)

관련 콘텐츠

원문 보기

원문 URL 링크

오픈액세스(OA) 유형

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

이벤트 지향 DEVS 실행 환경의 설계, 구현 및 성능 비교
Design, Implementation and Performance Analysis of Event-oriented Execution Environment for DEVS 원문보기

초록
AI-Helper

AI 본문요약
AI-Helper