Vorträge und Posterpräsentationen (mit Tagungsband-Eintrag):
W. Sodsong, R. Mittermayr, Y. Park, B. Burgstaller, J. Blieberger:
"Lazy Parallel Kronecker Algebra-Operations on Heterogeneous Multicores";
Vortrag: Euro-Par 2017 23rd International European Conference on Parallel and Distributed Computing,
Santiago de Compostela, Spain;
28.08.2017
- 01.09.2017; in: "Proceedings of the 23rd International European Conference on Parallel and Distributed Computing (Euro-Par 2017)",
LNCS / Springer Verlag,
10417 / Santiago de Compostela, Spain
(2017),
ISBN: 978-3-319-64202-4;
S. 538
- 552.
Kurzfassung englisch:
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× 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.
Schlagworte:
Kronecker algebra, Lazy evaluation, Deadlock detection, Heterogeneous multicores, GPUs
"Offizielle" elektronische Version der Publikation (entsprechend ihrem Digital Object Identifier - DOI)
http://dx.doi.org/10.1007/978-3-319-64203-1
Zugeordnete Projekte:
Projektleitung Johann Blieberger:
SAJiTcore++
Erstellt aus der Publikationsdatenbank der Technischen Universität Wien.