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
Fine-grained local dynamic load balancing in PDES
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Division of Scientific Computing. Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computational Science.
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Division of Scientific Computing. Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computational Science.
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
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. p. 201-212
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:uu:diva-342174DOI: 10.1145/3200921.3200928ISBN: 978-1-4503-5092-1 OAI: oai:DiVA.org:uu-342174DiVA, id: diva2:1183821
Conference
SIGSIM-PADS 2018
Projects
UPMARCAvailable from: 2018-05-14 Created: 2018-02-19 Last updated: 2018-06-08Bibliographically approved
In thesis
1. Synchronization Techniques in Parallel Discrete Event Simulation
Open this publication in new window or tab >>Synchronization Techniques in Parallel Discrete Event Simulation
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
Parallel discrete event simulation, Discrete event simulation, PDES, Optimism control
National Category
Computer Sciences
Research subject
Computer Science
Identifiers
urn:nbn:se:uu:diva-342270 (URN)978-91-513-0241-6 (ISBN)
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

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full text

Authority records BETA

Lindén, JonatanBauer, PavolEngblom, StefanJonsson, Bengt

Search in DiVA

By author/editor
Lindén, JonatanBauer, PavolEngblom, StefanJonsson, Bengt
By organisation
Computer SystemsDivision of Scientific ComputingComputational Science
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 70 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