Content deleted Content added
removed link from A to australia |
m Introduce a reference to non-blocking algorithms for the implementation of the pending event set, which is a trend undertaken in the last ~10 years. |
||
Line 31:
[[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.
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}}</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}}</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/
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.
| |||