Efficient implementation of event sets in Time Warp
Efficient implementation of event sets in Time Warp
复制标题
Time Warp 中事件集的高效实现
DOI：
10.1145/158459.158472
复制
发表时间：
1993
期刊：
影响因子：
--
通讯作者：
Samir R Das
中科院分区：
文献类型：
--
作者：
R. Rönngren;R. Ayani;R. Fujimoto;Samir R Das
未决事件集（PES）的实现对离散事件仿真程序的执行速度至关重要。本文研究了PES的实现在并行计算机上使用时间扭曲机制的模拟执行的上下文中。我们提出了一个计划，实现时间Warsp的PES的基础上著名的数据结构的优先级队列。该方案支持对未来和过去事件的有效管理，特别是对于回滚和化石收集操作。几个队列实现的比较研究。时间扭曲系统上执行的肯德尔广场研究多处理器（KSR 1）的实验表明，输入队列的实现可以有一个显着的影响性能，大到一个数量级，这是远远大于可以解释的简单的减少执行时间来访问的数据结构。特别是，它表明，一个有效的输入队列实现也可以显着减少回滚的数量，和效率的内存管理政策，如杰斐逊的cancelback协议。在这项工作的上下文中，我们还提出了一个改进版本的斜堆，允许decreeing的任意元素以低成本。特别是，对任意元素进行去重的可能性将提高内存利用率。这种能力在可能发生频繁重新调度的应用程序中也很重要，例如用于选择下一个要执行的逻辑进程的就绪队列。
The implementation of the pending event set (PES) is crucial to the execution speed of discrete event simulation programs. This paper studies the implementation of the PES in the context of simulations executing on parallel computers using the Time Warp mechanism. We present a scheme for implementing Time Warsp's PES based on well-known data structures for priority queues. This scheme supports efficient management of future and past events, especially for rollback and fossil collection operations. A comparative study of several queue implementations is presented. Experiments with a Time Warp system executing on a Kendall Square Research multiprocessor (KSR1) demonstrate that the implementation of the input queue can have a dramatic impact on performance, as large as an order of magnitude, that is much greater than what can be accounted for by simply the reduced execution time to access the data structure. In particular, it is demonstrated that an efficient input queue implementation can also significantly reduce the number of rollbacks, and the efficiency of memory management policies such as Jefferson's cancelback protocol. In the context of this work we also present an improved version of the skew heap that allows dequeueing of arbitrary elements at low cost. In particular, the possibility of dequeueing arbitrary elements will improve memory utilization. This ability is also important in applications where frequent rescheduling may occur, as in ready queues used to select the next logical process to execute.