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
A Skiplist-Based Concurrent Priority Queue with Minimal Memory Contention
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, Computing Science. Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
2018 (English)Report (Other academic)
Place, publisher, year, edition, pages
2018.
Series
Technical report / Department of Information Technology, Uppsala University, ISSN 1404-3203 ; 2018-003
Keywords [en]
Concurrent Data Structures, Priority Queue, Lock-free, Non-blocking, Skiplist
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:uu:diva-342233OAI: oai:DiVA.org:uu-342233DiVA, id: diva2:1183909
Projects
CoDeR-MPUPMARCAvailable from: 2018-02-19 Created: 2018-02-19 Last updated: 2018-04-06Bibliographically 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

Authority records BETA

Lindén, JonatanJonsson, Bengt

Search in DiVA

By author/editor
Lindén, JonatanJonsson, Bengt
By organisation
Computer SystemsComputing Science
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric score

urn-nbn
Total: 44 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