Knowledge-based automatic generation of linear algebra algorithms and code

摘要

This dissertation focuses on the design and the implementation of domain-specific compilers for linear algebra matrix equations. The development of efficient libraries for such equations, which lie at the heart of most software for scientific computing, is a complex process that requires expertise in a variety of areas, including the application domain, algorithms, numerical analysis and high-performance computing. Moreover, the process involves the collaboration of several people for a considerable amount of time. With our compilers, we aim to relieve the developers from both designing algorithms and writing code, and to generate routines that match or even surpass the performance of those written by human experts. We present two compilers, CLAK and CL1CK, that take as input the description of a target equation together with domain-specific knowledge, and generate efficient customized algorithms and routines. CLAK targets high-level matrix equations, possibly encompassing the solution of multiple instances of interdependent problems. This compiler generates algorithms consisting in a sequence of library-supported building blocks. It builds on top of a methodology that combines a model of human expert reasoning with the power of computers; the search for algorithms makes use of the available domain knowledge to prune the search space and to tailor the algorithms to the application. Along the process, clak{} prioritizes the reduction of the computational cost, the elimination of redundant computations, and the selection of the most suitable building blocks. For one target equation, many algorithms, with different properties, are generated. CL1CK, instead, addresses the generation of algorithms for specialized building blocks. To this end, this compiler adopts the FLAME methodology for the derivation of formally correct loop-based algorithms. CL1CK takes a three-stage approach: First, the PME(s) - a recursive definition of the target operation in a divide and conquer fashion - is found; then, the PME is analyzed to identify a family of loop invariants; finally, each loop invariant is transformed into a corresponding loop-based algorithm. CL1CK fully automates the application of this methodology; in this dissertation, we dissect the mechanisms necessary to make it possible. As we show, for our compilers, the exploitation of both linear algebra and application-specific knowledge is crucial to generate efficient customized solvers. In order to facilitate the management of knowledge and to increase productivity, we raise the abstraction level and provide the users with an expressive domain-specific language that allows them to reason at the matrix equation level. The users are thus able to state what needs to be solved, providing as much domain knowledge as possible, and delegating the compilers to find how to efficiently solve it. We illustrate the potential of our compilers by applying them to real world problems. For instance, for a challenging problem arising in computational biology, the exploitation of the available knowledge leads to algorithms that lower the complexity of existing methods by orders of magnitude. Our algorithms, at the heart of the publicly available library OmicABEL, have become the state-of-the-art. We also carry out a thorough study of the application of our compilers to derivative operations, quantifying how much tools used in algorithmic differentiation can benefit from incorporating the techniques discussed in this dissertation. The experiments demonstrate the compilers' potential to produce efficient derivative versions of part of LAPACK and of the entire BLAS, an effort that requires thousands of routines and for which a manual approach is unfeasible. This dissertation provides evidence that a linear algebra compiler, which increases experts' productivity and makes efficiency accessible to non-experts, is within reach.