Performance modeling and prediction for dense linear algebra

  • Performance-Modellierung und -Vorhersage für Dichtbesetzte Lineare Algebra

Peise, Elmar Hans; Bientinesi, Paolo (Thesis advisor); Müller, Matthias Stefan (Thesis advisor); Gunnels, John (Thesis advisor)

Aachen (2017, 2018)
Dissertation / PhD Thesis

Dissertation, RWTH Aachen University, 2017

Abstract

This dissertation introduces measurement-based performance modeling and prediction techniques for dense linear algebra algorithms. As a core principle, these techniques avoid executions of such algorithms entirely, and instead predict their performance through runtime estimates for the underlying compute kernels. For a variety of operations, these predictions allow to quickly select the fastest algorithm configurations from available alternatives. We consider two scenarios that cover a wide range of computations: To predict the performance of blocked algorithms, we design algorithm-independent performance models for kernel operations that are generated automatically once per platform. For various matrix operations, instantaneous predictions based on such models both accurately identify the fastest algorithm, and select a near-optimal block size. For performance predictions of BLAS-based tensor contractions, we propose cache-aware micro-benchmarks that take advantage of the highly regular structure inherent to contraction algorithms. At merely a fraction of a contraction's runtime, predictions based on such micro-benchmarks identify the fastest combination of tensor traversal and compute kernel.

Institutions

  • Aachen Institute for Advanced Study in Computational Engineering Science [080003]
  • Department of Computer Science [120000]
  • [123620]

Identifier

Downloads