Content deleted Content added
Importing Wikidata short description: "Type of simulation" (Shortdesc helper) |
→Events list: Add with refs |
||
Line 25:
===Events list===
The simulation maintains at least one list of simulation events. This is sometimes called the ''pending event set'' because it lists events that are pending as a result of previously simulated event but have yet to be simulated themselves. An event is described by the time at which it occurs and a type, indicating the code that will be used to simulate that event. It is common for the event code to be parametrized, in which case, the event description also contains parameters to the event code.{{cn}} The event list is also referred to as the ''future event list'' (FEL) or ''future event set'' (FES).<ref>{{Cite journal |last=Park |first=Hyungwook |last2=Fishwick |first2=Paul A. |date=2010|title=A GPU-Based Application Framework Supporting Fast Discrete-Event Simulation |url=http://journals.sagepub.com/doi/10.1177/0037549709340781 |journal=SIMULATION |language=en |volume=86 |issue=10 |pages=613–628 |doi=10.1177/0037549709340781 |issn=0037-5497}}</ref><ref>{{Cite web |last=Dannenberg |first=Roger |title=An Introduction to Discrete-Event Simulation |url=https://www.cs.cmu.edu/~music/cmsip/readings/intro-discrete-event-sim.html |access-date=2022-03-11 |website=[[Carnegie Mellon School of Computer Science]]}}</ref><ref>{{Cite web |last=Güneş |first=Mesut |title=Chapter 3: General Principles |url=https://www.mi.fu-berlin.de/inf/groups/ag-tech/teaching/2012_SS/L_19540_Modeling_and_Performance_Analysis_with_Simulation/03.pdf |access-date=2022-03-11 |website=[[Freie Universität Berlin]]}}</ref><ref>{{Cite journal |last=Damerdji |first=Halim |last2=Glynn |first2=Peter W. |date=1998 |title=Limit Theory for Performance Modeling of Future Event Set Algorithms |url=https://www.jstor.org/stable/2634704 |journal=Management Science |volume=44 |issue=12 |pages=1709–1722 |issn=0025-1909}}</ref>
When events are instantaneous, activities that extend over time are modeled as sequences of events. Some simulation frameworks allow the time of an event to be specified as an interval, giving the start time and the end time of each event.{{cn}}
[[Single-threaded]] simulation engines based on instantaneous events have just one current event. In contrast, [[Thread (computing)|multi-threaded]] simulation engines and simulation engines supporting an interval-based event model may have multiple current events. In both cases, there are significant problems with synchronization between current events.{{cn}}
The pending event set is typically organized as a [[priority queue]], [[Sorting|sorted]] by event time.<ref>[[Douglas W. Jones]], ed. [http://portal.acm.org/citation.cfm?id=318242.318467 Implementations of Time], Proceedings of the 18th Winter Simulation Conference, 1986.</ref> That is, regardless of the order in which events are added to the event set, they are removed in strictly chronological order. Various priority queue implementations have been studied in the context of discrete event simulation;<ref>[[Douglas W. Jones]], [http://doi.acm.org/10.1145/5684.5686 Empirical Comparison of Priority Queue and Event Set Implementations], ''Communications of the ACM, 29,'' April 1986, pages 300–311.</ref> alternatives studied have included [[splay tree]]s, [[skip list]]s, [[calendar queue]]s,<ref>Kah Leong Tan and Li-Jin Thng, [http://portal.acm.org/citation.cfm?id=510378.510453 SNOOPy Calendar Queue], Proceedings of the 32nd Winter Simulation Conference, 2000</ref> and ladder queues.<ref>{{Cite book |doi = 10.1145/2486092.2486106|chapter = Event pool structures for PDES on many-core Beowulf clusters|title = Proceedings of the 2013 ACM SIGSIM conference on Principles of advanced discrete simulation - SIGSIM-PADS '13|pages = 103|year = 2013|last1 = Dickman|first1 = Tom|last2 = Gupta|first2 = Sounak|last3 = Wilsey|first3 = Philip A.|isbn = 9781450319201|s2cid = 17572839}}</ref><ref>{{Cite book |doi = 10.1145/3200921.3200925|chapter = Adaptive Ladder Queue|title = Proceedings of the 2018 ACM SIGSIM Conference on Principles of Advanced Discrete Simulation - SIGSIM-PADS '18|pages = 101–104|year = 2018|last1 = Furfaro|first1 = Angelo|last2 = Sacco|first2 = Ludovica|isbn = 9781450350921|s2cid = 21699926}}</ref>
On [[Massively parallel processor array|massively-parallel machines]], such as [[Multi-core processor|multi-core]] or [[Manycore processor|many-core]] CPUs, the pending event set can be implemented by relying on [[Non-blocking algorithm|non-blocking algorithms]], in order to reduce the cost of synchronization among the concurrent threads.<ref>{{Cite book |doi = 10.1145/3064911.3064926|chapter = A Conflict-Resilient Lock-Free Calendar Queue for Scalable Share-Everything PDES Platforms|title = Proceedings of the 2017 ACM SIGSIM Conference on Principles of Advanced Discrete Simulation - SIGSIM-PADS '17|pages = 15–26|year = 2017|last1 = Marotta|first1 = Romolo|last2 = Ianni|first2 = Mauro|last3 = Pellegrini|first3 = Alessandro|last4 = Quaglia|first4 = Francesco|hdl = 11573/974295|isbn = 9781450344890|s2cid = 30460497}}</ref><ref>{{Cite book |doi = 10.1007/978-3-319-03850-6_15|chapter = A Skiplist-Based Concurrent Priority Queue with Minimal Memory Contention|title = Proceedings of the 2013 Conference on Principles of Distributed Systems - OPODIS 2013|pages = 206–220|year = 2013|last1 = Lindén|first1 = Jonatan|last2 = Jonsson|first2 = Bengt|isbn = 9783319038490}}</ref>
Typically, events are scheduled dynamically as the simulation proceeds. For example, in the bank example noted above, the event CUSTOMER-ARRIVAL at time t would, if the CUSTOMER_QUEUE was empty and TELLER was idle, include the creation of the subsequent event CUSTOMER-DEPARTURE to occur at time t+s, where s is a number generated from the SERVICE-TIME distribution.{{cn}}
===Random-number generators===
| |||