Discrete-event simulation: Difference between revisions

Revision as of 05:35, 19 September 2020

Revision as of 07:59, 26 October 2020

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|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>