Lock-free pending event set management in time warp
Lock-free pending event set management in time warp
复制标题
时间扭曲中的无锁挂起事件集管理
DOI：
10.1145/2601381.2601393
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Wilsey, Philip A.
中科院分区：
文献类型：
--
作者：
Gupta, Sounak;Wilsey, Philip A.
多核处理器并行性的快速增长为并行仿真离散事件仿真(PDES)开辟了新的机遇和挑战。PDES模拟器尝试在挂起事件集中找到并行性，以实现加速。通常，对未决事件集进行排序以保留所包含事件的因果顺序。排序是放大对共享事件调度器的独占访问的争用的关键方面，并且事件通常被调度为遵循挂起事件的基于时间的顺序。在这项工作中，我们利用梯形队列数据结构将未决事件划分为按相邻和较短时间区域排列的组(称为桶)。我们假设任何一个存储桶中的挂起事件是因果独立的，并且不排序也不考虑它们的总的基于时间的顺序来调度它们的执行。当实际依赖关系出现时，我们使用时间扭曲机制进行恢复。由于不需要排序，我们进一步扩展了挂起事件数据结构，以便可以将其组织为无锁访问。实验结果表明，所有研究的配置和仿真模型都具有一致的加速比。加速比从1.1到1.49不等，线程数量越多，加速比越高，传统的互斥锁机制对共享事件集的争用变得更加困难。
The rapid growth in the parallelism of multi-core processors has opened up new opportunities and challenges for parallel simulation discrete event simulation (PDES). PDES simulators attempt to find parallelism within the pending event set to achieve speedup. Typically the pending event set is sorted to preserve the causal orders of the contained events. Sorting is a key aspect that amplifies contention for exclusive access to the shared event scheduler and events are generally scheduled to follow the time-based order of the pending events. In this work we leverage a Ladder Queue data structure to partition the pending events into groups (called buckets) arranged by adjacent and short regions of time. We assume that the pending events within any one bucket are causally independent and schedule them for execution without sorting and without consideration of their total time-based order. We use the Time Warp mechanism to recover whenever actual dependencies arise. Due to the lack of need for sorting, we further extend our pending event data structure so that it can be organized for lock-free access. Experimental results show consistent speedup for all studied configurations and simulation models. The speedups range from 1.1 to 1.49 with higher speedups occurring with higher thread counts where contention for the shared event set becomes more problematic with a conventional mutex locking mechanism.
登录
查看更多内容
集群时间扭曲和逻辑模拟
DOI：
10.1109/pads.1995.404310
发表时间：
1995
期刊：
Proceedings 9th Workshop on Parallel and Distributed Simulation (ACM/IEEE)
影响因子：
--
作者：
Hervé Avril;C. Tropper
通讯作者：
C. Tropper
面向对象的时间扭曲模拟内核
DOI：
10.1007/3-540-49372-7_2
发表时间：
1998
期刊：
2012 ACM/IEEE/SCS 26th Workshop on Principles of Advanced and Distributed Simulation
影响因子：
--
作者：
R. Radhakrishnan;D. E. Martin;Malolan Chetlur;D. Rao;P. Wilsey
通讯作者：
P. Wilsey
DOI：
--
发表时间：
1995-12
期刊：
--
影响因子：
--
作者：
Maged M. Michael;M. Scott
通讯作者：
Maged M. Michael;M. Scott
多核 Beowulf 集群上 PDES 的事件池结构
DOI：
10.1145/2486092.2486106
发表时间：
2013
期刊：
ACM SIGSIM Conference on Principles of Advanced Discrete Simulation
影响因子：
--
作者：
Dickman, Tom;Gupta, Sounak;Wilsey, Philip A.
通讯作者：
Wilsey, Philip A.
用于乐观仿真系统的低开销恒定时间 LTF 调度程序
DOI：
10.1109/iscc.2010.5546544
发表时间：
2010
期刊：
The IEEE symposium on Computers and Communications
影响因子：
--
作者：
Tiziano Santoro;F. Quaglia
通讯作者：
F. Quaglia