Recent Talks

  1. Programming languages and linear algebra computations
    Uppsala University, April 2020.
    Matrix computations appear in virtually every domain of science and engineering, and due to the seemingly unstoppable growth of data science, are now as widespread as ever. In response to such a massive demand, the numerical linear algebra community puts tremendous effort in the identification, analysis, and optimization of a reasonably small set of simple operations---such as those included in the BLAS and LAPACK libraries---that serve as building blocks for most users' target computations. However, in a recent investigation, we observed a noticeable disconnect between the developers and the end users of numerical linear algebra libraries: Low-level languages such as C and Fortran and progressively less likely to be used, in favor of high-level programming languages such as Matlab, Julia, and R, make it possible to code matrix computations at the same level of abstraction at which experts reason about them. Unfortunately, our experience suggests that this increase in productivity often comes together with significantly suboptimal algorithms. Under the cover, all such languages face the problem of expressing a target matrix computation in terms of available building blocks; we refer to this problem as the "Linear Algebra Mapping Problem" (LAMP). In this talk, we define the problem, present the challenges it poses, and carefully survey how it is currently solved by the state-of-the-art languages.
    abstracthide
  2. Building blocks: From matrix to tensor operations
    Paolo Bientinesi and Lars Karlsson
    Dagstuhl Seminar 20111, Tensor Computations: Applications and Optimization, March 2020.
    The entire domain of matrix computations is tightly connected to the concept of building blocks, i.e., computational kernels that support one well defined mathematical operation. For almost 50 years, the linear algebra community has been identifying, layering, implementing, and optimizing building blocks. Significant benefits include portable performance, self-documenting quality of code, and robust implementations. Furthermore, standardization of interfaces and wide adoption paved the road towards automated approaches to code generation and performance tuning, and enabled abstraction (via high-level languages). Nowadays there exists a sophisticated and comprehensive hierarchy of libraries for dense and sparse linear algebra (e.g., BLAS, LAPACK, PETSc, etc.); these libraries provide invaluable support for a vast ecosystem of applications. We are convinced that the tensor community could benefit from similar ideas. The need for a better computational infrastructure was publicly recognized already in 2009 (if not earlier) at a workshop organized by Charles Van Loan. Despite many years of development, in 2020 the software landscape for tensor computations is still heavily fragmented and dominated by sophisticated MATLAB toolboxes and niche C++ libraries. Libraries similar to the BLAS and LAPACK are not even on the radar. We believe that it is (still) time for a major community effort to agree on the functionality and possibly the interface of a few low-level tensor operations, to then focus on high performance and parallel scalability.
    abstractPDFhide
  3. How good (or bad) is your favorite language for linear algebra?
    UMIT Research Lab, Umeå University, November 2019.
    Matrix computations appear in virtually every domain of science and engineering, and due to the seemingly unstoppable growth of data science, are now as widespread as ever. Such a massive demand triggered two distinct developments. On the one hand, the numerical linear algebra community has put tremendous effort in the identification, analysis and optimization of a reasonably small set of simple operations---such as those included in the BLAS and LAPACK libraries---that serve as building blocks for most users' target computations. On the other hand, the computer science community delivered several high-level programming languages---such as Matlab, Julia, R---as well as libraries---such as Eigen, Armadillo, NumPy---that make it possible to code matrix computations at the same level of abstraction at which experts reason about them. In this talk we investigate how sophisticated these high-level tools are.
    abstracthide
  4. From Problem to Solution in one Cl1ck
    Umeå University, Annual Celebration 2019, October 2019.
    As computers become increasingly powerful, it becomes more and more challenging to take advantage of their potential. Scientists and engineers alike are constantly facing the dilemma of whether to invest months in the development of sophisticated and efficient code, or to opt for code which is quick to generate, but severely suboptimal in terms of performance. In the first case, computer efficiency comes at the cost of human productivity; in the second case, human productivity comes at the expense of time and energy wasted. Prof. Bientinesi's research focuses on mathematical computations that arise in disciplines such as biology, chemistry, data science and materials science, and aims at achieving simultaneously both human productivity and computer efficiency. The objective is to allow domain experts to easily express their problems with a computer language, and then have computers--and not humans--automatically generate efficient code. Automation lowers computing costs, and at the same time allows scientists to perform more science.
    abstractwebPDFhide
  5. Efficiently Mapping Linear Algebra to High-Performance Code (Poster session)
    TACCSTER 2019.
    September 2019.
  6. The Linear Algebra Mapping Problem
    BLIS Retreat, September 2019.
  7. Model-based Generation of Linear Algebra Software
    IRTG Annual Meeting.
    July 2019.
  8. Programming languages for matrix computations
    Universitat Politècnica de València, July 2019.
    IFIP WG 2.5.
    Matrix computations appear in virtually every domain of science and engineering, and due to the seemingly unstoppable growth of data science, are now as widespread as ever. Such a massive demand triggered two distinct developments. On the one hand, the numerical linear algebra community has put tremendous effort in the identification, analysis and optimization of a reasonably small set of simple operations---such as those included in the BLAS and LAPACK libraries---that serve as building blocks for most users' target computations. On the other hand, the computer science community delivered several high-level programming languages---such as Matlab, Julia, R---that make it possible to code matrix computations at the same level of abstraction at which experts reason about them. Under the cover, all such languages face the problem of expressing a target matrix computation in terms of said building blocks; we refer to this problem as the "Linear Algebra Mapping Problem" (LAMP). In this talk we define the problem, present the challenges it poses, and carefully survey how it is (currently) solved by the state-of-the-art languages. Finally, we introduce Linnea, our compiler for matrix computations.
    abstractPDFhide
  9. Code Generation in Linnea
    6th International Workshop on Libraries, Languages, and Compilers for Array Programming (ARRAY 2019).
    Phoenix, Arizona, 22 June 2019.
    Linnea is a code generator for the translation of high-level linear algebra problems to efficient code. Unlike other languages and libraries for linear algebra, Linnea heavily relies on domain-specific knowledge to rewrite expressions and infer matrix properties. Here we focus on two aspects related to code generation and matrix properties: 1) The automatic generation of code consisting of explicit calls to BLAS and LAPACK kernels, and the corresponding challenge with specialized storage formats. 2) A general notion of banded matrices can be used to simplify the inference of many matrix properties. While it is crucial to make use of matrix properties to achieve high performance, inferring those properties is challenging. We show how matrix bandwidth can be used as a unifying language to reason about many common matrix properties.
    abstractPDFhide
  10. Linnea: Automatic Generation of Efficient Linear Algebra Programs
    Carnegie Mellon University, Pittsburgh, 19 June 2019.
    The evaluation of linear algebra expressions is a central part of both languages for scientific computing such as Julia and Matlab, and libraries such as Eigen, Blaze, and NumPy. However, the existing strategies are still rather primitive. At present, the only way to achieve high performance is by handcoding algorithms using libraries such as BLAS and LAPACK, a task that requires extensive knowledge in linear algebra, numerical linear algebra and high-performance computing. We present Linnea, a synthesis tool that automates the translation of the mathematical description of a linear algebra problem to an efficient sequence of calls to BLAS and LAPACK kernels. The main idea of Linnea is to construct a search graph that represents a large number of programs, taking into account knowledge about linear algebra. The algebraic nature of the domain is used to reduce the size of the search graph, without reducing the size of the search space that is explored. Experiments show that 1) the code generated by Linnea outperforms standard linear algebra languages and libraries, and 2) in contrast to the development time of human experts, the generation takes only few minutes. We present Linnea, the prototype of a compiler that automates the translation of the mathematical description of a linear algebra problem to an efficient sequence of calls to BLAS and LAPACK kernels. The main idea of Linnea is to construct a search graph that represents a large number of programs, taking into account knowledge about linear algebra. The algebraic nature of the domain is used to reduce the size of the search graph, without reducing the size of the search space that is explored. Experiments show that 1) the code generated by Linnea outperforms standard linear algebra languages and libraries, and 2) in contrast to the development time of human experts, the generation takes only few seconds.
    abstractPDFhide