uu.seUppsala University Publications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Synchronization Techniques in Parallel Discrete Event Simulation
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Division of Computer Systems. Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
2018 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

Discrete event simulation is an important tool for evaluating system models in many fields of science and engineering. To improve the performance of large-scale discrete event simulations, several techniques to parallelize discrete event simulation have been developed.

In parallel discrete event simulation, the work of a single discrete event simulation is distributed over multiple processing elements. A key challenge in parallel discrete event simulation is to ensure that causally dependent events are processed in the correct order, so that the same simulation trajectory is produced as in a sequential simulation. To preserve chronology between events processed in parallel, different synchronization protocols have been devised, each carrying a cost in performance.

This thesis presents techniques for reducing synchronization costs in two approaches to parallel discrete event simulation, viz., optimistic space-parallel and share-everything parallel discrete event simulation.

Firstly, we develop a concurrent priority queue, to be used as, e.g., a central event queue in the share-everything approach to parallel discrete event simulation. The priority queue is based on skiplists. It improves over previous queues by incurring fewer global synchronization operations, thereby inducing less contention and improving scalability.

Secondly, we study how to improve the performance of optimistic parallel discrete event simulation by disseminating accurate estimates of timestamps of future events. We present techniques for obtaining the estimates in two different methods for simulation of spatial stochastic models. The estimates allow processing elements to determine when to pause simulation with high precision, thereby reducing the amount of performed useless work.

Finally, we observe that in the applications that we have studied, the phenomena of interest are often non-homogeneous and migrate over time. Due to this, the work distribution tends to become unbalanced among the processing elements. A solution is to rebalance the work dynamically. We propose a fine-grained local dynamic load balancing algorithm for parallel discrete event simulation. The load balancing algorithm reduces the number of events arriving out-of-order, thereby reducing the amount of time spent on corrective actions.

Place, publisher, year, edition, pages
Uppsala: Acta Universitatis Upsaliensis, 2018. , p. 57
Series
Digital Comprehensive Summaries of Uppsala Dissertations from the Faculty of Science and Technology, ISSN 1651-6214 ; 1634
Keywords [en]
Parallel discrete event simulation, Discrete event simulation, PDES, Optimism control
National Category
Computer Sciences
Research subject
Computer Science
Identifiers
URN: urn:nbn:se:uu:diva-342270ISBN: 978-91-513-0241-6 (print)OAI: oai:DiVA.org:uu-342270DiVA, id: diva2:1183933
Public defence
2018-04-10, 2446, ITC, Lägerhyddsvägen 2, Uppsala, 13:15 (English)
Opponent
Supervisors
Available from: 2018-03-13 Created: 2018-02-19 Last updated: 2018-04-24
List of papers
1. A Skiplist-Based Concurrent Priority Queue with Minimal Memory Contention
Open this publication in new window or tab >>A Skiplist-Based Concurrent Priority Queue with Minimal Memory Contention
2018 (English)Report (Other academic)
Series
Technical report / Department of Information Technology, Uppsala University, ISSN 1404-3203 ; 2018-003
Keywords
Concurrent Data Structures, Priority Queue, Lock-free, Non-blocking, Skiplist
National Category
Computer Sciences
Identifiers
urn:nbn:se:uu:diva-342233 (URN)
Projects
CoDeR-MPUPMARC
Available from: 2018-02-19 Created: 2018-02-19 Last updated: 2018-04-06Bibliographically approved
2. Efficient inter-process synchronization for parallel discrete event simulation on multicores
Open this publication in new window or tab >>Efficient inter-process synchronization for parallel discrete event simulation on multicores
2015 (English)In: Proc. 3rd ACM SIGSIM Conference on Principles of Advanced Discrete Simulation, New York: ACM Press, 2015, p. 183-194Conference paper, Published paper (Refereed)
Place, publisher, year, edition, pages
New York: ACM Press, 2015
National Category
Computer Sciences
Identifiers
urn:nbn:se:uu:diva-260199 (URN)10.1145/2769458.2769476 (DOI)978-1-4503-3583-6 (ISBN)
Conference
SIGSIM-PADS 2015
Projects
UPMARC
Available from: 2015-06-10 Created: 2015-08-17 Last updated: 2018-02-19Bibliographically approved
3. Exposing inter-process information for efficient PDES of spatial stochastic systems
Open this publication in new window or tab >>Exposing inter-process information for efficient PDES of spatial stochastic systems
(English)Manuscript (preprint) (Other academic)
National Category
Computer Sciences
Identifiers
urn:nbn:se:uu:diva-342180 (URN)
Projects
UPMARC
Available from: 2018-02-19 Created: 2018-02-19 Last updated: 2018-04-09Bibliographically approved
4. Fine-grained local dynamic load balancing in PDES
Open this publication in new window or tab >>Fine-grained local dynamic load balancing in PDES
2018 (English)In: Proc. 6th ACM SIGSIM Conference on Principles of Advanced Discrete Simulation, New York: ACM Press, 2018, p. 201-212Conference paper, Published paper (Refereed)
Place, publisher, year, edition, pages
New York: ACM Press, 2018
National Category
Computer Sciences
Identifiers
urn:nbn:se:uu:diva-342174 (URN)10.1145/3200921.3200928 (DOI)978-1-4503-5092-1 (ISBN)
Conference
SIGSIM-PADS 2018
Projects
UPMARC
Available from: 2018-05-14 Created: 2018-02-19 Last updated: 2018-06-08Bibliographically approved

Open Access in DiVA

fulltext(516 kB)79 downloads
File information
File name FULLTEXT01.pdfFile size 516 kBChecksum SHA-512
fc8b52c95e09d2db50b80b5d8c06a0218dd1a608e42cb526820ee917f65894c27746c4d4efea38d18256cb147b317058c44033610e1e0d119c6ad653a7f6148a
Type fulltextMimetype application/pdf
Buy this publication >>

Authority records BETA

Lindén, Jonatan

Search in DiVA

By author/editor
Lindén, Jonatan
By organisation
Division of Computer SystemsComputer Systems
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 79 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 463 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf