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
Efficient inter-process synchronization for parallel discrete event simulation on multicores
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.
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.ORCID iD: 0000-0002-3614-1732
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
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. p. 183-194
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:uu:diva-260199DOI: 10.1145/2769458.2769476ISBN: 978-1-4503-3583-6 (print)OAI: oai:DiVA.org:uu-260199DiVA, id: diva2:846638
Conference
SIGSIM-PADS 2015
Projects
UPMARCAvailable from: 2015-06-10 Created: 2015-08-17 Last updated: 2018-11-12Bibliographically approved
In thesis
1. Parallelism and efficiency in discrete-event simulation
Open this publication in new window or tab >>Parallelism and efficiency in discrete-event simulation
2015 (English)Licentiate thesis, comprehensive summary (Other academic)
Abstract [en]

Discrete-event models depict systems where a discrete state is repeatedly altered by instantaneous changes in time, the events of the model. Such models have gained popularity in fields such as Computational Systems Biology or Computational Epidemiology due to the high modeling flexibility and the possibility to easily combine stochastic and deterministic dynamics. However, the system size of modern discrete-event models is growing and/or they need to be simulated at long time periods. Thus, efficient simulation algorithms are required, as well as the possibility to harness the compute potential of modern multicore computers. Due to the sequential design of simulators, parallelization of discrete event simulations is not trivial. This thesis discusses event-based modeling and sensitivity analysis and also examines ways to increase the efficiency of discrete-event simulations and to scale models involving deterministic and stochastic spatial dynamics on a large number of processor cores.

Place, publisher, year, edition, pages
Uppsala University, 2015
Series
Information technology licentiate theses: Licentiate theses from the Department of Information Technology, ISSN 1404-5117 ; 2015-004
National Category
Computational Mathematics Computer Sciences
Research subject
Scientific Computing
Identifiers
urn:nbn:se:uu:diva-264756 (URN)
Supervisors
Projects
UPMARCeSSENCE
Available from: 2015-10-14 Created: 2015-10-16 Last updated: 2018-11-12Bibliographically approved
2. Parallelism in Event-Based Computations with Applications in Biology
Open this publication in new window or tab >>Parallelism in Event-Based Computations with Applications in Biology
2017 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

Event-based models find frequent usage in fields such as computational physics and biology as they may contain both continuous and discrete state variables and may incorporate both deterministic and stochastic state transitions. If the state transitions are stochastic, computer-generated random numbers are used to obtain the model solution. This type of event-based computations is also known as Monte-Carlo simulation.

In this thesis, I study different approaches to execute event-based computations on parallel computers. This ultimately allows users to retrieve their simulation results in a fraction of the original computation time. As system sizes grow continuously or models have to be simulated at longer time scales, this is a necessary approach for current computational tasks.

More specifically, I propose several ways to asynchronously simulate such models on parallel shared-memory computers, for example using parallel discrete-event simulation or task-based computing. The particular event-based models studied herein find applications in systems biology, computational epidemiology and computational neuroscience.

In the presented studies, the proposed methods allow for high efficiency of the parallel simulation, typically scaling well with the number of used computer cores. As the scaling typically depends on individual model properties, the studies also investigate which quantities have the greatest impact on the simulation performance.

Finally, the presented studies include other insights into event-based computations, such as methods how to estimate parameter sensitivity in stochastic models and how to simulate models that include both deterministic and stochastic state transitions.

Place, publisher, year, edition, pages
Uppsala: Acta Universitatis Upsaliensis, 2017. p. 48
Series
Digital Comprehensive Summaries of Uppsala Dissertations from the Faculty of Science and Technology, ISSN 1651-6214 ; 1586
Keywords
Event-based computations, Parallel algorithms, Discrete-event simulation, Monte-Carlo methods, Systems biology.
National Category
Other Computer and Information Science Computational Mathematics
Research subject
Scientific Computing
Identifiers
urn:nbn:se:uu:diva-332009 (URN)978-91-513-0125-9 (ISBN)
Public defence
2017-12-11, 2347, ITC, Lägerhyddsvägen 2, Uppsala, 10:15 (English)
Opponent
Supervisors
Projects
UPMARC
Available from: 2017-11-30 Created: 2017-10-22 Last updated: 2018-03-07
3. 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

Bauer, PavolLindén, JonatanEngblom, StefanJonsson, Bengt

Search in DiVA

By author/editor
Bauer, PavolLindén, JonatanEngblom, StefanJonsson, Bengt
By organisation
Division of Scientific ComputingComputational ScienceComputer Systems
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

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