Lazy parallel kronecker algebra-operations on heterogeneous multicores

Wasuwee Sodsong, Robert Mittermayr, Yoojin Park, Bernd Burgstaller, Johann Blieberger

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Kronecker algebra is a matrix calculus which allows the generation of thread interleavings from the source-code of a program. Thread interleavings have been shown effective for proving the absence of deadlocks. Because the number of interleavings grows exponentially in the number of threads, deadlock analysis is still a challenging problem. To make the computation of thread interleavings tractable, we propose a lazy, parallel evaluation method for Kronecker algebra. Our method incorporates the constraints induced by synchronization constructs. To reduce problem size, only interleavings legal under the locking behavior of a program are considered. We leverage the data-parallelism of Kronecker sum- and product-operations for multicores and GPUs. Proposed algebraic transformations further improve performance. For one synthetic and two real-world benchmarks, our GPU implementation is up to 5453 X faster than our multi-threaded version. Lazy evaluation significantly reduces memory consumption compared to both the sequential and the multicore versions of the SPIN model-checker.

Original languageEnglish
Title of host publicationEuro-Par 2017
Subtitle of host publicationParallel Processing - 23rd International Conference on Parallel and Distributed Computing, Proceedings
EditorsFrancisco F. Rivera, Tomas F. Pena, Jose C. Cabaleiro
PublisherSpringer Verlag
Number of pages15
ISBN (Print)9783319642024
Publication statusPublished - 2017
Event23rd International Conference on Parallel and Distributed Computing, Euro-Par 2017 - Santiago de Compostela, Spain
Duration: 2017 Aug 282017 Sept 1

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10417 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other23rd International Conference on Parallel and Distributed Computing, Euro-Par 2017
CitySantiago de Compostela

Bibliographical note

Funding Information:
Acknowledgments. This research was supported by the Austrian Science Fund (FWF) project I 1035N23, and by the Next-Generation Information Computing Development Program through the National Research Foundation of Korea (NRF), funded by the Ministry of Science, ICT & Future Planning under grant NRF2015M3C4A-7065522.

Publisher Copyright:
© 2017, Springer International Publishing AG.

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Lazy parallel kronecker algebra-operations on heterogeneous multicores'. Together they form a unique fingerprint.

Cite this