uu.seUppsala universitets publikasjoner
Endre søk
Link to record
Permanent link

Direct link
BETA
Jonsson, Bengt
Alternativa namn
Publikasjoner (10 av 101) Visa alla publikasjoner
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.
Åpne denne publikasjonen i ny fane eller vindu >>Exposing inter-process information for efficient PDES of spatial stochastic systems on multicores
2019 (engelsk)Inngår i: ACM Transactions on Modeling and Computer Simulation, ISSN 1049-3301, E-ISSN 1558-1195, Vol. 29, nr 2, s. 11:1-25, artikkel-id 11Artikkel i tidsskrift (Fagfellevurdert) Published
HSV kategori
Identifikatorer
urn:nbn:se:uu:diva-342180 (URN)10.1145/3301500 (DOI)000468031300004 ()
Prosjekter
UPMARC
Tilgjengelig fra: 2019-04-02 Laget: 2018-02-19 Sist oppdatert: 2019-06-18bibliografisk kontrollert
Abdulla, P., Atig, M. F., Jonsson, B., Lång, M., Ngo, T.-P. & Sagonas, K. (2019). Optimal stateless model checking for reads-from equivalence under sequential consistency. Proceedings of the ACM on programming languages
Åpne denne publikasjonen i ny fane eller vindu >>Optimal stateless model checking for reads-from equivalence under sequential consistency
Vise andre…
2019 (engelsk)Inngår i: Proceedings of the ACM on programming languages, ISSN 2475-1421Artikkel i tidsskrift (Fagfellevurdert) Published
Abstract [en]

We present a new approach for stateless model checking (SMC) of multithreaded programs under Sequential Consistency (SC) semantics.  To combat state-space explosion, SMC is often equipped with a partial-order reduction technique, which defines an equivalence on executions, and only needs to explore one execution in each equivalence class.  Recently, it has been observed that the commonly used equivalence of Mazurkiewicz traces can be coarsened but still cover all program crashes and assertion violations.  However, for this coarser equivalence, which preserves only the reads-from relation from writes to reads, there is no SMC algorithm which is (i) optimal in the sense that it explores precisely one execution in each reads-from equivalence class, and (ii) efficient in the sense that it spends polynomial effort per class.  \end{inparaenum} We present the first SMC algorithm for SC that is both optimal and efficient in practice, meaning that it spends polynomial time per equivalence class on all programs that we have tried.  This is achieved by a novel test that checks whether a given reads-from relation can arise in some execution.  Our experimental results show that Nidhugg/rfsc, although slower than the fastest SMC tools in programs where tools happen to examine the same number of executions, always scales similarly or better than them, and outperforms them by an exponential factor in programs where the reads-from equivalence is coarser than the standard one. We also present two non-trivial use cases where the new equivalence is particularly effective, as well as the significant performance advantage that Nidhugg/rfsc offers compared to state-of-the-art SMC and systematic concurrency testing tools.

Emneord
concurrent programs, sequential consistency, program verification, stateless model checking, dynamic partial order reduction
HSV kategori
Forskningsprogram
Datavetenskap
Identifikatorer
urn:nbn:se:uu:diva-396320 (URN)10.1145/3360576 (DOI)
Tilgjengelig fra: 2019-11-03 Laget: 2019-11-03 Sist oppdatert: 2019-11-03
Lindén, J. & Jonsson, B. (2018). A Skiplist-Based Concurrent Priority Queue with Minimal Memory Contention.
Åpne denne publikasjonen i ny fane eller vindu >>A Skiplist-Based Concurrent Priority Queue with Minimal Memory Contention
2018 (engelsk)Rapport (Annet vitenskapelig)
Serie
Technical report / Department of Information Technology, Uppsala University, ISSN 1404-3203 ; 2018-003
Emneord
Concurrent Data Structures, Priority Queue, Lock-free, Non-blocking, Skiplist
HSV kategori
Identifikatorer
urn:nbn:se:uu:diva-342233 (URN)
Prosjekter
CoDeR-MPUPMARC
Tilgjengelig fra: 2018-02-19 Laget: 2018-02-19 Sist oppdatert: 2018-04-06bibliografisk kontrollert
Cassel, S., Howar, F., Jonsson, B. & Steffen, B. (2018). Extending Automata Learning to Extended Finite State Machines. In: Bennaceur, A Hahnle, R Meinke, K (Ed.), Machine Learning for Dynamic Software Analysis: Potentials and Limits. Paper presented at International Dagstuhl Seminar on 16172 - Machine Learning for Dynamic Software Analysis - Potentials and Limits, APR 24-27, 2016, Wadern, GERMANY (pp. 149-177). Springer
Åpne denne publikasjonen i ny fane eller vindu >>Extending Automata Learning to Extended Finite State Machines
2018 (engelsk)Inngår i: Machine Learning for Dynamic Software Analysis: Potentials and Limits / [ed] Bennaceur, A Hahnle, R Meinke, K, Springer, 2018, s. 149-177Konferansepaper, Publicerat paper (Fagfellevurdert)
Abstract [en]

Automata learning is an established class of techniques for inferring automata models by observing how they respond to a sample of input words. Recently, approaches have been presented that extend these techniques to infer extended finite state machines (EFSMs) by dynamic black-box analysis. EFSMs model both data flow and control behavior, and their mutual interaction. Different dialects of EFSMs are widely used in tools for model-based software development, verification, and testing. This survey paper presents general principles behind some of these recent extensions. The goal is to elucidate how the principles behind classic automata learning can be maintained and guide extensions to more general automata models, and to situate some extensions with respect to these principles.

sted, utgiver, år, opplag, sider
Springer, 2018
Serie
Lecture Notes in Computer Science, ISSN 0302-9743, E-ISSN 1611-3349 ; 11026
HSV kategori
Identifikatorer
urn:nbn:se:uu:diva-391442 (URN)10.1007/978-3-319-96562-8_6 (DOI)000476941200006 ()978-3-319-96562-8 (ISBN)978-3-319-96561-1 (ISBN)
Konferanse
International Dagstuhl Seminar on 16172 - Machine Learning for Dynamic Software Analysis - Potentials and Limits, APR 24-27, 2016, Wadern, GERMANY
Forskningsfinansiär
EU, FP7, Seventh Framework Programme, IST 231167Swedish Research Council
Tilgjengelig fra: 2019-08-22 Laget: 2019-08-22 Sist oppdatert: 2019-08-22bibliografisk kontrollert
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
Åpne denne publikasjonen i ny fane eller vindu >>Fine-grained local dynamic load balancing in PDES
2018 (engelsk)Inngår i: Proc. 6th ACM SIGSIM Conference on Principles of Advanced Discrete Simulation, New York: ACM Press, 2018, s. 201-212Konferansepaper, Publicerat paper (Fagfellevurdert)
sted, utgiver, år, opplag, sider
New York: ACM Press, 2018
HSV kategori
Identifikatorer
urn:nbn:se:uu:diva-342174 (URN)10.1145/3200921.3200928 (DOI)000482913900025 ()978-1-4503-5092-1 (ISBN)
Konferanse
SIGSIM-PADS 2018
Prosjekter
UPMARC
Tilgjengelig fra: 2018-05-14 Laget: 2018-02-19 Sist oppdatert: 2019-10-21bibliografisk kontrollert
Abdulla, P. A., Jonsson, B. & Trinh, C. Q. (2018). Fragment abstraction for concurrent shape analysis. In: Programming Languages and Systems: . Paper presented at ESOP 2018 (pp. 442-471). Springer
Åpne denne publikasjonen i ny fane eller vindu >>Fragment abstraction for concurrent shape analysis
2018 (engelsk)Inngår i: Programming Languages and Systems, Springer, 2018, s. 442-471Konferansepaper, Publicerat paper (Fagfellevurdert)
sted, utgiver, år, opplag, sider
Springer, 2018
Serie
Lecture Notes in Computer Science ; 10801
HSV kategori
Identifikatorer
urn:nbn:se:uu:diva-368505 (URN)10.1007/978-3-319-89884-1_16 (DOI)978-3-319-89883-4 (ISBN)
Konferanse
ESOP 2018
Prosjekter
UPMARC
Tilgjengelig fra: 2018-04-14 Laget: 2018-12-05 Sist oppdatert: 2018-12-07bibliografisk kontrollert
Winblad, K., Sagonas, K. & Jonsson, B. (2018). Lock-free Contention Adapting Search Trees. In: The 30th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2018: . Paper presented at The 30th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2018, July 16–18, 2018, Vienna, Austria. New York, NY, USA, 30
Åpne denne publikasjonen i ny fane eller vindu >>Lock-free Contention Adapting Search Trees
2018 (engelsk)Inngår i: The 30th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2018, New York, NY, USA, 2018, Vol. 30Konferansepaper, Publicerat paper (Fagfellevurdert)
sted, utgiver, år, opplag, sider
New York, NY, USA: , 2018
HSV kategori
Forskningsprogram
Datavetenskap
Identifikatorer
urn:nbn:se:uu:diva-354022 (URN)10.1145/3210377.3210413 (DOI)978-1-4503-5799-9 (ISBN)
Konferanse
The 30th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2018, July 16–18, 2018, Vienna, Austria
Forskningsfinansiär
Swedish Research Council
Merknad

In press

Tilgjengelig fra: 2018-06-18 Laget: 2018-06-18 Sist oppdatert: 2018-06-27bibliografisk kontrollert
Aronis, S., Jonsson, B., Lång, M. & Sagonas, K. (2018). Optimal dynamic partial order reduction with observers. In: Tools and Algorithms for the Construction and Analysis of Systems: Part II. Paper presented at TACAS 2018, April 14–20, Thessaloniki, Greece. (pp. 229-248). Springer, 10806
Åpne denne publikasjonen i ny fane eller vindu >>Optimal dynamic partial order reduction with observers
2018 (engelsk)Inngår i: Tools and Algorithms for the Construction and Analysis of Systems: Part II, Springer, 2018, Vol. 10806, s. 229-248Konferansepaper, Publicerat paper (Fagfellevurdert)
Abstract [en]

Dynamic partial order reduction (DPOR) algorithms are used in stateless model checking (SMC) to combat the combinatorial explosion in the number of schedulings that need to be explored to guarantee soundness. The most effective of them, the Optimal DPOR algorithm, is optimal in the sense that it explores only one scheduling per Mazurkiewicz trace. In this paper, we enhance DPOR with the notion of observability, which makes dependencies between operations conditional on the existence of future operations, called observers. Observers naturally lead to a lazy construction of dependencies. This requires significant changes in the core of POR algorithms (and Optimal DPOR in particular), but also makes the resulting algorithm, Optimal DPOR with Observers, super-optimal in the sense that it explores exponentially less schedulings than Mazurkiewicz traces in some cases. We argue that observers come naturally in many concurrency models, and demonstrate the performance benefits that Optimal DPOR with Observers achieves in both an SMC tool for shared memory concurrency and a tool for concurrency via message passing, using both synthetic and actual programs as benchmarks.

sted, utgiver, år, opplag, sider
Springer, 2018
Serie
Lecture Notes in Computer Science, ISSN 0302-9743, E-ISSN 1611-3349 ; 10806
HSV kategori
Identifikatorer
urn:nbn:se:uu:diva-333508 (URN)10.1007/978-3-319-89963-3 _ 14 (DOI)000445822600014 ()978-3-319-89962-6 (ISBN)978-3-319-89963-3 (ISBN)
Konferanse
TACAS 2018, April 14–20, Thessaloniki, Greece.
Prosjekter
UPMARC
Forskningsfinansiär
Swedish Research Council
Tilgjengelig fra: 2018-04-14 Laget: 2017-11-21 Sist oppdatert: 2019-01-07bibliografisk kontrollert
Ngo, T.-P., Abdulla, P., Jonsson, B. & Atig, M. F. (2018). Optimal Stateless Model Checking under the Release-Acquire Semantics. In: SPLASH OOPSLA 2018, Boston, Nov 4-9, 2018: . Paper presented at SPLASH OOPSLA 2018. ACM Digital Library
Åpne denne publikasjonen i ny fane eller vindu >>Optimal Stateless Model Checking under the Release-Acquire Semantics
2018 (engelsk)Inngår i: SPLASH OOPSLA 2018, Boston, Nov 4-9, 2018, ACM Digital Library, 2018Konferansepaper, Publicerat paper (Fagfellevurdert)
Abstract [en]

We present a framework for efficient application of stateless model checking (SMC) to concurrent programs running under the Release-Acquire (RA) fragment of the C/C++11 memory model. Our approach is based on exploring the possible program orders, which define the order in which instructions of a thread are executed, and read-from relations, which define how reads obtain their values from writes. This is in contrast to previous approaches, which in addition explore the possible coherence orders, i.e., orderings between conflicting writes. Since unexpected test results such as program crashes or assertion violations depend only on the read-from relation, we avoid a potentially large source of redundancy. Our framework is based on a novel technique for determining whether a particular read-from relation is feasible under the RA semantics. We define an SMC algorithm which is provably optimal in the sense that it explores each program order and read-from relation exactly once. This optimality result is strictly stronger than previous analogous optimality results, which also take coherence order into account. We have implemented our framework in the tool Tracer. Experiments show that Tracer can be significantly faster than state-of-the-art tools that can handle the RA semantics.

sted, utgiver, år, opplag, sider
ACM Digital Library, 2018
Emneord
Software model checking, C/C++11, Release-Acquire, Concurrent program
HSV kategori
Forskningsprogram
Datavetenskap
Identifikatorer
urn:nbn:se:uu:diva-358241 (URN)
Konferanse
SPLASH OOPSLA 2018
Prosjekter
UPMARC
Tilgjengelig fra: 2018-08-26 Laget: 2018-08-26 Sist oppdatert: 2019-01-09bibliografisk kontrollert
Jonsson, B. (2018). The Quest for Optimality in Stateless Model Checking of Concurrent Programs. In: Howar, F Barnat, J (Ed.), Formal Methods For Industrial Critical Systems, FMICS 2018: . Paper presented at 23rd International Conference on Formal Methods for Industrial Critical Systems (FMICS), SEP 03-04, 2018, Natl Univ Ireland Maynooth, Maynooth, IRELAND (pp. XI-XII). Springer
Åpne denne publikasjonen i ny fane eller vindu >>The Quest for Optimality in Stateless Model Checking of Concurrent Programs
2018 (engelsk)Inngår i: Formal Methods For Industrial Critical Systems, FMICS 2018 / [ed] Howar, F Barnat, J, Springer, 2018, s. XI-XIIKonferansepaper, Publicerat paper (Fagfellevurdert)
sted, utgiver, år, opplag, sider
Springer, 2018
Serie
Lecture Notes in Computer Science, ISSN 0302-9743, E-ISSN 1611-3349 ; 11119
HSV kategori
Identifikatorer
urn:nbn:se:uu:diva-391437 (URN)000477763200001 ()978-3-030-00244-2 (ISBN)978-3-030-00243-5 (ISBN)
Konferanse
23rd International Conference on Formal Methods for Industrial Critical Systems (FMICS), SEP 03-04, 2018, Natl Univ Ireland Maynooth, Maynooth, IRELAND
Tilgjengelig fra: 2019-09-25 Laget: 2019-09-25 Sist oppdatert: 2019-09-25bibliografisk kontrollert
Organisasjoner