A Theoretical Model for Global Optimization of Parallel Algorithms

Mathematics, vol. 9, pp. 1685

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.

Authors 3

1. Julian Miller corresponding Aachen IT centre Chair for High Performance Computing

   RWTH Aachen University

   Affiliation as printed

   Chair for High Performance Computing, IT Center, RWTH Aachen University, 52074 Aachen, Germany

2. Lukas Trümper Aachen IT centre Chair for High Performance Computing

   RWTH Aachen University

   Affiliation as printed

   Chair for High Performance Computing, IT Center, RWTH Aachen University, 52074 Aachen, Germany

   Huddly AS, Karenslyst Allé 51, 0279 Oslo, Norway

3. Christian Terboven Aachen IT centre Chair for High Performance Computing

   RWTH Aachen University

   Affiliation as printed

   Chair for High Performance Computing, IT Center, RWTH Aachen University, 52074 Aachen, Germany