Skip to Main Content
 

Global Search Box

 
 
 
 

Files

File List


30512.pdf (7.8 MB)

ETD Abstract Container

Abstract Header

Pending Event Set Management in Parallel Discrete Event Simulation

Gupta, Sounak
http://orcid.org/0000-0001-9368-6205
http://rave.ohiolink.edu/etdc/view?acc_num=ucin1535701778479768

Abstract Details

2018, PhD, University of Cincinnati, Engineering and Applied Science: Computer Science and Engineering.
In Parallel Discrete Event Simulation (PDES), the pending event set refers to the set of events available for execution. These pending events are aggressively scheduled for execution in a Time Warp synchronized parallel simulation without strict enforcement of the causal relationship between events. For most discrete event simulation models, event processing granularity is generally quite small. On many-core and multi-core platforms, this decrease in granularity aggravates contention for the shared data structures which store these pending events. As the number of cores increase, a key challenge lies in providing effective, contention-free event list management for scheduling events. Lock contention, sorting, and scheduling order are the prime contributors to contention for access to the pending events set. Possible solutions to this problem include atomic read-write operations, hardware transactional memory, or synchronization-friendly data structures. The focus is on choosing efficient data structures for the pending event set and optimization of scheduling techniques that can improve the performance of the Time Warp synchronized parallel simulation. The following design concepts for optimizing the pending event set are explored in this dissertation: 1. an exploration of a variety of different data structures that are commonly used in the management of pending event set. In addition, the management of the pending event set using a Ladder Queue data structure is explored. The Ladder Queue forms a self-adjusting hierarchically partitioned priority queue that makes it particularly attractive for managing the pending event set 2. the elimination of sorting within the Ladder Queue partitions. Events are then scheduled from the lowest partition without concerns for their time order and causal independence of these events is assumed 3. an atomic read-write access to the Ladder Queue partition that holds the smallest available events is explored 4. Objects containing groups of events are organized in the pending event set. Each group is dequeued with one access and the collection of events are scheduled. Several different options for the definition of these groups and how these groups are scheduled is explored. Experimental results show that fully-sorted Ladder Queue is over 20% faster than STL MultiSet and Splay Tree. It was also observed that Ladder Queue with unsorted lowest partition is at least 25% faster than fully-sorted Ladder Queue for all discrete event simulation models studied. The atomic read-write access to this lowest partition of the Ladder Queue allows simulation models to run 25-150% faster than the fully-sorted Ladder Queue. Furthermore, studies indicate that scheduling events in groups provides up to 100% gain in performance for some simulation models. The experiments also show that the modularity-based partitioning of LPs makes a simulation run as fast as Ladder Queue with atomic read-write operations for some kernel and model configurations. Overall Ladder Queue with atomic read-write access to its unsorted lowest partition has the best performance among the scheduling data structures studied and multiple schedule queues is the choice for scheduling strategy. Combining the two together results in the most effective scheduling mechanism. There is over 100% boost in performance for some models when this combination is compared to any of the other efficient configurations mentioned above. Each of the aforementioned concepts explored address the contention to the shared data structures that store the pending event set. The work on group and bag-centric scheduling draws inspiration from the study on profile-driven data collected from discrete event simulations. This study helped guide the design and optimization of scheduling strategies for the pending event set in a Time Warp synchronized parallel simulation.
Philip Wilsey, Ph.D. (Committee Chair)
Nael Abu-Ghazaleh, Ph.D. (Committee Member)
Fred Beyette, Ph.D. (Committee Member)
Ali Minai, Ph.D. (Committee Member)
Carla Purdy, Ph.D. (Committee Member)
666 p.
Computer Engineering
Discrete Event Simulation; Parallel Computing; Distributed Computing; Lock-free data structures; Pending Event Set; Time Warp

Recommended Citations

Citations

  • Gupta, S. (2018). Pending Event Set Management in Parallel Discrete Event Simulation [Doctoral dissertation, University of Cincinnati]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=ucin1535701778479768

    APA Style (7th edition)

  • Gupta, Sounak. Pending Event Set Management in Parallel Discrete Event Simulation. 2018. University of Cincinnati, Doctoral dissertation. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=ucin1535701778479768.

    MLA Style (8th edition)

  • Gupta, Sounak. "Pending Event Set Management in Parallel Discrete Event Simulation." Doctoral dissertation, University of Cincinnati, 2018. http://rave.ohiolink.edu/etdc/view?acc_num=ucin1535701778479768

    Chicago Manual of Style (17th edition)

ucin1535701778479768
344
© 2016, some rights reserved.Creative Commons License Pending Event Set Management in Parallel Discrete Event Simulation by Sounak Gupta is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License. Based on a work at etd.ohiolink.edu.
This open access ETD is published by University of Cincinnati and OhioLINK.