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

Direct link
BETA
Lindén, Jonatan
Publications (8 of 8) Show all publications
Lindén, J., Bauer, P., Engblom, S. & Jonsson, B. (2019). Exposing inter-process information for efficient PDES of spatial stochastic systems on multicores. ACM Transactions on Modeling and Computer Simulation, 29(2), 11:1-25, Article ID 11.
Open this publication in new window or tab >>Exposing inter-process information for efficient PDES of spatial stochastic systems on multicores
2019 (English)In: ACM Transactions on Modeling and Computer Simulation, ISSN 1049-3301, E-ISSN 1558-1195, Vol. 29, no 2, p. 11:1-25, article id 11Article in journal (Refereed) Published
National Category
Computer Sciences
Identifiers
urn:nbn:se:uu:diva-342180 (URN)10.1145/3301500 (DOI)000468031300004 ()
Projects
UPMARC
Available from: 2019-04-02 Created: 2018-02-19 Last updated: 2019-06-18Bibliographically approved
Lindén, J. & Jonsson, B. (2018). 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
Lindén, J., Bauer, P., Engblom, S. & Jonsson, B. (2018). Fine-grained local dynamic load balancing in PDES. In: Proc. 6th ACM SIGSIM Conference on Principles of Advanced Discrete Simulation: . Paper presented at SIGSIM-PADS 2018 (pp. 201-212). New York: ACM Press
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-11-12Bibliographically approved
Lindén, J. (2018). Synchronization Techniques in Parallel Discrete Event Simulation. (Doctoral dissertation). Uppsala: Acta Universitatis Upsaliensis
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
Projects
UPMARC
Available from: 2018-03-13 Created: 2018-02-19 Last updated: 2019-02-25
Lindén, J., Bauer, P., Engblom, S. & Jonsson, B. (2017). Exposing inter-process information for efficient parallel discrete event simulation of spatial stochastic systems. In: Proc. 5th ACM SIGSIM Conference on Principles of Advanced Discrete Simulation: . Paper presented at SIGSIM-PADS 2017 (pp. 53-64). New York: ACM Press
Open this publication in new window or tab >>Exposing inter-process information for efficient parallel discrete event simulation of spatial stochastic systems
2017 (English)In: Proc. 5th ACM SIGSIM Conference on Principles of Advanced Discrete Simulation, New York: ACM Press, 2017, p. 53-64Conference paper, Published paper (Refereed)
Place, publisher, year, edition, pages
New York: ACM Press, 2017
National Category
Computer Sciences
Identifiers
urn:nbn:se:uu:diva-328367 (URN)10.1145/3064911.3064916 (DOI)978-1-4503-4489-0 (ISBN)
Conference
SIGSIM-PADS 2017
Projects
UPMARC
Available from: 2017-05-16 Created: 2017-08-22 Last updated: 2018-11-12Bibliographically approved
Bauer, P., Lindén, J., Engblom, S. & Jonsson, B. (2015). Efficient inter-process synchronization for parallel discrete event simulation on multicores. In: Proc. 3rd ACM SIGSIM Conference on Principles of Advanced Discrete Simulation: . Paper presented at SIGSIM-PADS 2015 (pp. 183-194). New York: ACM Press
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-11-12Bibliographically approved
Lindén, J. & Jonsson, B. (2013). A Skiplist-based Concurrent Priority Queue with Minimal Memory Contention. In: Roberto Baldoni, Nicolas Nisse, Maarten van Steen (Ed.), OPODIS 2013: 17th International Conference On Principles Of DIstributed Systems: . Paper presented at OPODIS 2013: 17th International Conference On Principles Of DIstributed Systems, Nice, France,December 16-18th, 2013 (pp. 206-220). Berlin: Springer Berlin/Heidelberg
Open this publication in new window or tab >>A Skiplist-based Concurrent Priority Queue with Minimal Memory Contention
2013 (English)In: OPODIS 2013: 17th International Conference On Principles Of DIstributed Systems / [ed] Roberto Baldoni, Nicolas Nisse, Maarten van Steen, Berlin: Springer Berlin/Heidelberg, 2013, p. 206-220Conference paper, Published paper (Refereed)
Abstract [en]

Priority queues are fundamental to many multiprocessor  applications. Several priority queue algorithms based on skiplists  have been proposed, as skiplists allow concurrent accesses to  different parts of the data structure in a simple way. However, for  priority queues on multiprocessors, an inherent bottleneck is the  operation that deletes the minimal element. We present a  linearizable, lock-free, concurrent priority queue algorithm, based  on skiplists, which minimizes the contention for shared memory that  is caused by the DeleteMin operation. The main idea is to  minimize the number of global updates to shared memory that are  performed in one DeleteMin. In comparison with other  skiplist-based priority queue algorithms, our algorithm achieves a  30 - 80% improvement.

Place, publisher, year, edition, pages
Berlin: Springer Berlin/Heidelberg, 2013
Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 8304
Keywords
Concurrent Data Structures, Priority Queue, Lock-free, Non- blocking, Skiplist
National Category
Computer Systems
Research subject
Computer Science
Identifiers
urn:nbn:se:uu:diva-213426 (URN)10.1007/978-3-319-03850-6_15 (DOI)
Conference
OPODIS 2013: 17th International Conference On Principles Of DIstributed Systems, Nice, France,December 16-18th, 2013
Projects
CoDeR-MPUPMARC
Available from: 2013-12-21 Created: 2013-12-21 Last updated: 2014-02-06
Pan, X., Lindén, J. & Jonsson, B. (2012). Predicting the Cost of Lock Contention in Parallel Applications on Multicores using Analytic Modeling. In: Proc. 5th Swedish Workshop on Multi-Core Computing: . Paper presented at MCC12.
Open this publication in new window or tab >>Predicting the Cost of Lock Contention in Parallel Applications on Multicores using Analytic Modeling
2012 (English)In: Proc. 5th Swedish Workshop on Multi-Core Computing, 2012Conference paper, Published paper (Other academic)
National Category
Computer Sciences
Identifiers
urn:nbn:se:uu:diva-270130 (URN)
Conference
MCC12
Projects
UPMARC
Available from: 2012-11-23 Created: 2015-12-21 Last updated: 2018-01-10Bibliographically approved
Organisations

Search in DiVA

Show all publications