A Theoretical Model for Global Optimization of Parallel Algorithms

Julian Miller, Lukas Trümper, Christian Terboven and Matthias S. Müller
Additional contact information
Julian Miller: Chair for High Performance Computing, IT Center, RWTH Aachen University, 52074 Aachen, Germany
Lukas Trümper: Chair for High Performance Computing, IT Center, RWTH Aachen University, 52074 Aachen, Germany
Christian Terboven: Chair for High Performance Computing, IT Center, RWTH Aachen University, 52074 Aachen, Germany
Matthias S. Müller: Chair for High Performance Computing, IT Center, RWTH Aachen University, 52074 Aachen, Germany

Mathematics, 2021, vol. 9, issue 14, 1-14

Abstract: With the quickly evolving hardware landscape of high-performance computing (HPC) and its increasing specialization, the implementation of efficient software applications becomes more challenging. This is especially prevalent for domain scientists and may hinder the advances in large-scale simulation software. One idea to overcome these challenges is through software abstraction. We present a parallel algorithm model that allows for global optimization of their synchronization and dataflow and optimal mapping to complex and heterogeneous architectures. The presented model strictly separates the structure of an algorithm from its executed functions. It utilizes a hierarchical decomposition of parallel design patterns as well-established building blocks for algorithmic structures and captures them in an abstract pattern tree (APT) . A data-centric flow graph is constructed based on the APT, which acts as an intermediate representation for rich and automated structural transformations. We demonstrate the applicability of this model to three representative algorithms and show runtime speedups between 1.83 and 2.45 on a typical heterogeneous CPU/GPU architecture.

Keywords: parallel programming; parallel patterns; program optimization; optimizing framework; dependence analysis (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2021
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://www.mdpi.com/2227-7390/9/14/1685/pdf (application/pdf)
https://www.mdpi.com/2227-7390/9/14/1685/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:9:y:2021:i:14:p:1685-:d:596252

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().