Skip to Main Content
 

Global Search Box

 
 
 
 

Files

File List


matt-depero-masters-final.pdf (2.12 MB)

ETD Abstract Container

Abstract Header

Thread Safe Multi-Tier Priority Queue for Managing Pending Events in Multi-Threaded Discrete Event Simulations

DePero, Matthew Michael
http://orcid.org/0000-0003-1929-8348
http://rave.ohiolink.edu/etdc/view?acc_num=miami1535426621614915

Abstract Details

2018, Master of Computer Science, Miami University, Computer Science and Software Engineering.
Parallel Discrete Event Simulation (PDES) conducted using emerging shared memory many-core CPUs presents capacity for even greater performance by 1) eliminating the need for message passing and associated serialization/deserialization overheads, and 2) reducing memory requirements by allowing a single copy of an event to be shared between multiple threads. However, the overall performance of a PDES is highly contingent on the speed and capacity of its pending event set data structure. Accordingly, we present a simple, thread-safe priority queue called 3tSkip for managing pending events. Our design takes advantage of contemporary synchronization primitives, including atomics and lock-free data structures to ensure good performance. The priority queue has been incorporated into a redesigned version of a parallel simulator called MUSE, to enable PDES on shared memory platforms. The effectiveness of the proposed solution has been assessed using standard PDES benchmarks. Our analysis identifies many critical design obstacles to multi-threaded design and presents novel solutions to those design obstacles. Our solution achieves significant speedup in high granularity scenarios, when compared to existing MUSE simulator, though more work is required before multithreaded design becomes effective in a broad range of scenarios.
Dhananjai Rao, Dr. (Advisor)
Mike Zmuda, Dr. (Committee Member)
Karen Davis, Dr. (Committee Member)
61 p.
Computer Science
PDES, parallel discrete event simulation, DES, discrete event simulation, simulation, data structure, thread-safe, priority queue

Recommended Citations

Citations

  • DePero, M. M. (2018). Thread Safe Multi-Tier Priority Queue for Managing Pending Events in Multi-Threaded Discrete Event Simulations [Master's thesis, Miami University]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=miami1535426621614915

    APA Style (7th edition)

  • DePero, Matthew. Thread Safe Multi-Tier Priority Queue for Managing Pending Events in Multi-Threaded Discrete Event Simulations. 2018. Miami University, Master's thesis. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=miami1535426621614915.

    MLA Style (8th edition)

  • DePero, Matthew. "Thread Safe Multi-Tier Priority Queue for Managing Pending Events in Multi-Threaded Discrete Event Simulations." Master's thesis, Miami University, 2018. http://rave.ohiolink.edu/etdc/view?acc_num=miami1535426621614915

    Chicago Manual of Style (17th edition)

miami1535426621614915
248
© 2018, all rights reserved.
This open access ETD is published by Miami University and OhioLINK.