이산 이벤트 시뮬레이션

Discrete-event simulation

이산 이벤트 시뮬레이션(DES)은 시간 내에 이벤트의 (구체적) 시퀀스로 시스템 작동을 모델링한다. 각 이벤트는 특정 순간에 발생하며 시스템의 상태 변화를 나타낸다.[1] 연속적인 사건들 사이에서는 시스템의 어떤 변화도 일어나지 않는다고 가정하므로 시뮬레이션 시간은 다음 사건의 발생 시간으로 바로 점프할 수 있으며, 이를 다음 사건 시간 진행이라고 한다.

다음 이벤트 시간 진행 외에도, 고정 증가 시간 진행이라고 하는 대안적 접근법이 있는데, 여기서 시간은 작은 시간 조각으로 분할되고 시간 조각에서 일어나는 사건/활동 집합에 따라 시스템 상태가 업데이트된다.[2] 모든 슬라이스를 시뮬레이션할 필요는 없기 때문에, 다음 이벤트 시간 시뮬레이션은 일반적으로 해당 고정 증가 시간 시뮬레이션보다 훨씬 더 빨리 실행될 수 있다.

두 형태의 DES는 상태 변수의 변화 속도를 정의하는 일련의 미분 방정식에 기초하여 시간이 지남에 따라 지속적으로 시스템 상태가 변경되는 연속 시뮬레이션과 대비된다.

예

개별 이벤트 시뮬레이션을 구축하는 방법을 배우는 데 있어 일반적인 연습은 은행에 도착하는 고객들과 같은 대기열을 모델링하는 것이다. 이 예에서 시스템 실체는 고객 큐와 텔러다. 시스템 이벤트는 Customer-Aright 및 Customer-Departure 입니다. (텔러-베긴스-서비스(Teller-Beins-Service) 이벤트는 도착 및 출발 이벤트의 논리의 일부가 될 수 있다.) 이러한 이벤트에 의해 변경되는 시스템 상태는 Queue 내 사용자 수(0부터 n까지의 정수) 및 Teller-Status(바쁨 또는 유휴)이다. 이 시스템을 확률적으로 모델링하기 위해 특성화해야 하는 랜덤 변수는 Customer-Intertainer-Time과 Teller-Service-Time이다. 낙관적 병렬 이산 이벤트 시뮬레이터의 성능 모델링을 위한 에이전트 기반 프레임워크도 이산 이벤트 시뮬레이션의 또 다른 예다.[3]

구성 요소들

시스템 이벤트가 발생할 때 발생하는 것에 대한 논리 외에도 이산 이벤트 시뮬레이션에는 다음이 포함된다.

  • 우선 순위 대기열,
  • 애니메이션 이벤트 핸들러 및
  • 시간 재정규화 핸들러(시뮬레이션이 실행되면 시간 변수의 정밀도가 저하됨) 잠시 후 모든 시간 변수는 마지막으로 처리된 이벤트 시간을 빼서 다시 정규화해야 한다.

주

시스템 상태는 연구할 시스템의 두드러진 특성을 포착하는 변수 집합이다. 시간 경과에 따른 상태 궤적은 사건이 발생할 때마다 값이 변할 수 있는 단계 함수로 수학적으로 나타낼 수 있다.

시계

시뮬레이션은 모델링되는 시스템에 적합한 측정 단위가 무엇이든 현재 시뮬레이션 시간을 추적해야 한다. 이산 이벤트 시뮬레이션에서는, 지속적인 시뮬레이션과는 반대로, 이벤트가 즉각적이기 때문에 시간이 '홉'된다 – 시계는 시뮬레이션이 진행됨에 따라 다음 이벤트 시작 시간으로 미끄러진다.

이벤트 리스트

시뮬레이션은 적어도 하나의 시뮬레이션 이벤트 리스트를 유지한다. 이전에 시뮬레이션된 이벤트의 결과로 보류 중이지만 자체적으로 아직 시뮬레이션되지 않은 이벤트를 나열하기 때문에 보류 중인 이벤트 집합이라고도 한다. 이벤트는 발생한 시간과 유형으로 설명되며, 해당 이벤트를 시뮬레이션하는 데 사용될 코드를 나타낸다. 이벤트 코드는 파라메터링되는 것이 일반적이며, 이 경우 이벤트 설명에는 이벤트 코드에 대한 파라미터도 포함되어 있다.

사건이 즉각적일 때, 시간이 지남에 따라 확장되는 활동은 사건의 순서에 따라 모델링된다. 일부 시뮬레이션 프레임워크는 각 이벤트의 시작 시간과 종료 시간을 제공하면서 이벤트의 시간을 구간으로 지정할 수 있다.

순간 이벤트에 기반한 단일 스레드 시뮬레이션 엔진은 현재 이벤트가 하나만 있다. 대조적으로, 간격 기반 이벤트 모델을 지원하는 다중 스레드 시뮬레이션 엔진과 시뮬레이션 엔진은 여러 개의 전류 이벤트를 가질 수 있다. 두 경우 모두 현재 이벤트 간 동기화에 상당한 문제가 있다.

대기 중인 이벤트 세트는 일반적으로 이벤트 시간별로 정렬된 우선순위 대기열로 구성된다.[4] 즉, 이벤트 집합에 이벤트가 추가되는 순서에 관계없이 엄격히 시간순으로 제거된다. 다양한 우선 순위 대기열 구현이 이산 이벤트 시뮬레이션의 맥락에서 연구되었다.[5] 연구된 대안에는 재생 트리, 건너뛰기 목록, 달력 대기열 [6]및 래더 대기열이 포함되었다.[7][8] 멀티 코어 또는 다코어 CPU와 같은 대규모 병렬 머신에서는 동시 스레드 간 동기화 비용을 줄이기 위해 비차단 알고리즘에 의존하여 대기 중인 이벤트 세트를 구현할 수 있다.[9][10]

일반적으로 이벤트는 시뮬레이션이 진행됨에 따라 동적으로 스케줄링된다. 예를 들어, 위에서 언급한 은행 예에서, CUSTER_QUE가 비어 있고 TALER가 유휴 상태라면, CUSTER_QUE의 CUSTER-ARTALLER 이벤트가 t+s에 발생하는 후속 CUSTER-DEPARTure 이벤트의 생성을 포함할 것이다. 여기서 s는 SERVICE-TIME 배포에서 생성된 숫자다.

임의 번호 생성기

시뮬레이션은 시스템 모델에 따라 다양한 종류의 랜덤 변수를 생성해야 한다. 이것은 하나 이상의 유사 숫자 생성기에 의해 달성된다. 실제 무작위 숫자와 반대로 의사 난수를 사용하는 것은 시뮬레이션에서 정확히 동일한 동작으로 재실행해야 하는 경우에 유익하다.

이산 사건 시뮬레이션에 사용되는 난수 분포의 문제 중 하나는 사건 시간의 정상 상태 분포를 사전에 알 수 없다는 것이다. 결과적으로, 보류 중인 이벤트 세트에 배치된 초기 이벤트 세트는 정상 상태 분포를 대표하는 도착 시간을 갖지 못할 것이다. 이 문제는 전형적으로 시뮬레이션 모델의 부팅스트래핑을 통해 해결할 수 있다. 미결 이벤트의 초기 집합에 현실적인 시간을 할당하기 위한 제한적인 노력만 행해진다. 그러나 이러한 이벤트는 추가 이벤트를 스케줄링하며, 시간이 지남에 따라 이벤트 시간 분포가 안정 상태에 근접한다. 이것을 시뮬레이션 모델을 부트스트래핑이라고 한다. 실행 모델에서 통계를 수집하려면 안정 상태에 도달하기 전에 발생하는 이벤트를 무시하거나 부트스트래핑 동작이 안정 상태 동작에 의해 압도될 정도로 오랫동안 시뮬레이션을 실행하는 것이 중요하다. (부스트스트래핑이라는 용어의 사용은 통계와 컴퓨팅 모두에서 그 용어와 대조될 수 있다.)

통계

시뮬레이션은 일반적으로 시스템의 통계를 추적하여 관심 있는 측면을 정량화한다. 은행 예제에서 평균 대기 시간을 추적하는 것이 관심사다. 시뮬레이션 모델에서 성능 지표는 확률 분포에서 분석적으로 도출되는 것이 아니라, 모델의 다른 런인 복제에 대한 평균으로 도출된다. 신뢰 구간은 대개 출력의 품질을 평가하는 데 도움이 되도록 구성된다.

종료조건

이벤트가 부트스트랩되기 때문에 이론적으로 개별 이벤트 시뮬레이션은 영원히 실행될 수 있다. 따라서 시뮬레이션 설계자는 시뮬레이션이 언제 끝날지 결정해야 한다. 대표적인 선택은 "time t" 또는 "n개의 사건 수를 처리한 후" 또는 더 일반적으로 "통계 측정 X가 x 값에 도달할 때"이다.

삼면접근법

Pidd(1998)는 이산형 이벤트 시뮬레이션에 대한 3단계 접근방식을 제안했다. 이 접근법에서 첫 번째 단계는 다음 연대기적 사건으로 점프하는 것이다. 두 번째 단계는 그 시간에 무조건 발생하는 모든 이벤트(이를 B-이벤트라고 한다)를 실행하는 것이다. 세 번째 단계는 그 시간에 조건부로 발생하는 모든 사건(이를 C-이벤트라고 한다)을 실행하는 것이다. 3단계 접근방식은 컴퓨터 자원을 가장 효율적으로 사용할 수 있도록 동시 이벤트를 주문하는 이벤트 기반 접근방식의 개선이다. 3상접근법은 여러 상업용 시뮬레이션 소프트웨어 패키지에 의해 이용되지만, 이용자 입장에서는 기본 시뮬레이션 방법의 구체성이 일반적으로 숨겨져 있다.

공통 용법

프로세스 문제 진단

시뮬레이션 접근방식은 사용자가 복잡한 환경에서 문제를 진단할 수 있도록 특히 잘 갖춰져 있다. 제약조건 이론은 시스템의 병목현상을 이해하는 것의 중요성을 보여준다. 병목 현상을 식별하고 제거하면 프로세스와 전체 시스템을 개선할 수 있다. 예를 들어 제조업에서 병목현상은 재고 과잉, 과잉생산, 공정의 변동성, 라우팅 또는 시퀀싱의 변동성에 의해 발생할 수 있다. 시뮬레이션 모델의 도움을 받아 시스템을 정확하게 문서화함으로써 시스템 전체를 조감할 수 있다.

시스템의 작동 모델을 통해 경영진은 성능 동인을 이해할 수 있다. 시뮬레이션을 구축하면 근로자 활용률, 정시 납품율, 스크랩 레이트, 현금 주기 등 성과 지표가 얼마든지 포함될 수 있다.

병원 신청서

수술 극장은 일반적으로 여러 수술 분야 간에 공유된다. 이러한 절차의 성격을 더 잘 이해함으로써 환자의 처리량을 증가시킬 수 있을 것이다. 예: 심장수술에 평균 4시간이 걸리는 경우 수술실 일정을 8시간에서 9시간으로 변경해도 환자의 처리량은 증가하지 않는다. 반면에 탈장 시술이 평균 20분 정도 걸리는 경우 추가 시간을 제공하는 것도 회복실에서 소비되는 용량과 평균 시간을 고려하지 않을 경우 처리량이 증가하지 않을 수 있다.

랩 테스트 성능 개선 아이디어

많은 시스템 개선 아이디어가 건전한 원리, 입증된 방법론(Lean, Six Sigma, TQM 등)에 기초하고 있지만 전체 시스템을 개선하지 못하고 있다. 시뮬레이션 모델은 사용자가 전체 시스템의 맥락에서 성능 개선 아이디어를 이해하고 시험할 수 있도록 한다.

자본 투자 결정 평가

참고 항목: 몬테카를로 금융, 기업 금융 § 자본 투자 결정 및 기업 금융 § 불확실성 수량화 방법

시뮬레이션 모델링은 일반적으로 잠재적 투자를 모델링하는 데 사용된다. 투자 모델링을 통해 의사결정자는 정보에 입각한 의사결정을 내리고 잠재적 대안을 평가할 수 있다.

네트워크 시뮬레이터

주요 기사: 네트워크 시뮬레이션

이산 이벤트 시뮬레이션은 컴퓨터 네트워크에서 실제 배치 전에 새로운 프로토콜, 서로 다른 시스템 아키텍처(분산, 계층, 중앙 집중, P2P)를 시뮬레이션하기 위해 사용된다. 서비스 시간, 대역폭, 손실된 패킷, 리소스 소비 등 서로 다른 평가 지표를 정의할 수 있다.

참고 항목

시스템 모델링 접근 방식:

계산 기법:

소프트웨어:

분야:

참조

  1. ^ Stewart Robinson (2004). Simulation – The practice of model development and use. Wiley.
  2. ^ Matloff, Norm. "Introduction to Discrete-Event Simulation and the SimPy Language" (PDF). Retrieved 24 January 2013.
  3. ^ Aditya Kurve; Khashayar Kotobi; George Kesidis (2013). "An agent-based framework for performance modeling of an optimistic parallel discrete event simulator". Complex Adaptive Systems Modeling. 1: 12. doi:10.1186/2194-3206-1-12.
  4. ^ 더글러스 W. 존스, 에드 시간의 구현, 제18회 동계 시뮬레이션 컨퍼런스의 진행, 1986.
  5. ^ Douglas W. Jones, 우선순위 큐와 이벤트 세트 구현의 경험적 비교, ACM의 통신, 1986년 4월 29일 페이지 300~311.
  6. ^ Kah Leong Tan과 Li-Jin Thng, SNOOPy 캘린더 큐, 제32회 동계 시뮬레이션 컨퍼런스 진행, 2000년
  7. ^ Dickman, Tom; Gupta, Sounak; Wilsey, Philip A. (2013). "Event pool structures for PDES on many-core Beowulf clusters". Proceedings of the 2013 ACM SIGSIM conference on Principles of advanced discrete simulation - SIGSIM-PADS '13. p. 103. doi:10.1145/2486092.2486106. ISBN 9781450319201. S2CID 17572839.
  8. ^ Furfaro, Angelo; Sacco, Ludovica (2018). "Adaptive Ladder Queue". Proceedings of the 2018 ACM SIGSIM Conference on Principles of Advanced Discrete Simulation - SIGSIM-PADS '18. pp. 101–104. doi:10.1145/3200921.3200925. ISBN 9781450350921. S2CID 21699926.
  9. ^ Marotta, Romolo; Ianni, Mauro; Pellegrini, Alessandro; Quaglia, Francesco (2017). "A Conflict-Resilient Lock-Free Calendar Queue for Scalable Share-Everything PDES Platforms". Proceedings of the 2017 ACM SIGSIM Conference on Principles of Advanced Discrete Simulation - SIGSIM-PADS '17. pp. 15–26. doi:10.1145/3064911.3064926. hdl:11573/974295. ISBN 9781450344890. S2CID 30460497.
  10. ^ Lindén, Jonatan; Jonsson, Bengt (2013). "A Skiplist-Based Concurrent Priority Queue with Minimal Memory Contention". Proceedings of the 2013 Conference on Principles of Distributed Systems - OPODIS 2013. pp. 206–220. doi:10.1007/978-3-319-03850-6_15. ISBN 9783319038490.

추가 읽기

  • Myron H. MacDougall (1987). Simulating Computer Systems: Techniques and Tools. MIT Press.
  • William Delaney; Erminia Vaccari (1988). Dynamic Models and Discrete Event Simulation. Dekker INC.
  • Roger W. McHaney (1991). Computer Simulation: A Practical Perspective. Academic Press.
  • Michael Pidd (1998). Computer simulation in management science – fourth edition. Wiley.
  • A, Alan Pritsker, Jean J. O'Reilly (1999). Simulation with Visual SLAM and AweSim. Wiley.{{cite book}}: CS1 maint : 복수이름 : 작성자 목록(링크)
  • Averill M. Law; W. David Kelton (2000). Simulation modeling and analysis – third edition. McGraw–Hill.
  • Bernard P. Zeigler; Herbert Praehofer; Tag Gon Kim (2000). Theory of modeling and simulation: Integrating discrete event and continuous complex dynamic systems – second edition. Academic Press.
  • Jerry Banks; John Carson; Barry Nelson; David Nicol (2005). Discrete-event system simulation – fourth edition. Pearson.
  • James J. Nutaro (2010). Building software for simulation: theory and algorithms, with applications in C++. Wiley.