Reliable generation of high-performance matrix algebra

DOI10.1145/2629698zbMATH Open1347.68066arXiv1205.1098OpenAlexW1877620707WikidataQ113310287 ScholiaQ113310287MaRDI QIDQ2828141FDOQ2828141

Authors: Thomas Nelson, Geoffrey Belter, Jeremy G. Siek, Elizabeth Jessup, Boyana Norris 

Publication date: 24 October 2016

Published in: ACM Transactions on Mathematical Software (Search for Journal in Brave)

Abstract: Scientific programmers often turn to vendor-tuned Basic Linear Algebra Subprograms (BLAS) to obtain portable high performance. However, many numerical algorithms require several BLAS calls in sequence, and those successive calls result in suboptimal performance. The entire sequence needs to be optimized in concert. Instead of vendor-tuned BLAS, a programmer could start with source code in Fortran or C (e.g., based on the Netlib BLAS) and use a state-of-the-art optimizing compiler. However, our experiments show that optimizing compilers often attain only one-quarter the performance of hand-optimized code. In this paper we present a domain-specific compiler for matrix algebra, the Build to Order BLAS (BTO), that reliably achieves high performance using a scalable search algorithm for choosing the best combination of loop fusion, array contraction, and multithreading for data parallelism. The BTO compiler generates code that is between 16% slower and 39% faster than hand-optimized code.

Full work available at URL: https://arxiv.org/abs/1205.1098

Recommendations

• Anatomy of high-performance matrix multiplication
• Compiler blockability of dense matrix factorizations
• Exploiting fast matrix multiplication within the level 3 BLAS
• Publication:4945557
• GEMM-based level 3 BLAS

zbMATH Keywords

genetic algorithmslinear algebradomain-specific languagesautotuning

Mathematics Subject Classification ID

Complexity and performance of numerical algorithms (65Y20) Packaged methods for numerical algorithms (65Y15) Theory of compilers and interpreters (68N20) Software, source code, etc. for problems pertaining to numerical analysis (65-04) Numerical linear algebra (65Fxx)

Cites Work

• Title not available (Why is that?)
• An extended set of FORTRAN basic linear algebra subprograms
• Basic Linear Algebra Subprograms for Fortran Usage
• A set of level 3 basic linear algebra subprograms
• An updated set of basic linear algebra subprograms (BLAS)
• FLAME
• Title not available (Why is that?)
• Title not available (Why is that?)
• Families of Algorithms for Reducing a Matrix to Condensed Form
• Cache efficient bidiagonalization using BLAS 2.5 operators
• Title not available (Why is that?)
• Languages and Compilers for Parallel Computing

Cited In (6)

• Title not available (Why is that?)
• Automatic generation of fast algorithms for matrix–vector multiplication
• BLASFEO: Basic linear algebra subroutines for embedded optimization
• The BLAS API of BLASFEO: optimizing performance for small matrices
• Analytical modeling is enough for high-performance BLIS
• TTC: a high-performance compiler for tensor transpositions

Uses Software

• ATLAS
• FLAME
• SPIRAL
• BLAS
• PHiPAC
• PLuTo
• pthreads

This page was built for publication: Reliable generation of high-performance matrix algebra

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2828141)