Clak: An Automatic Environment for Linear Algebra Equations

• Applicant: Professor Paolo Bientinesi, Ph.D.
• Subject Area: Software Engineering and Programming Languages
• Term: from 2015 to 2020
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 266457877

This proposal centers around the development of CLAK, a domain-specificcompiler targeting linear algebra problems. In a nutshell, given thedescription of a matrix equation expressed in the standard mathematicalnotation of vectors, matrices and tensors, CLAK will automatically producealgorithms and high-performance routines for both sequential and shared-memoryarchitectures. The ultimate goal is a dramatic increase in productivity forengineers and computational scientists.The main concept behind CLAK is the idea that users possessmore information about the specific application than what traditionalenvironments allow them to express, and that if properly exploited, thisknowledge leads to remarkable speedups. Presently, users can choose between a"low-level" approach, entailing a manual development and implementation ofalgorithms with languages such as C or Fortran, or a "high-level" approach,based on user-friendly environments such as Matlab or Eigen. Both approacheshave merits and shortcomings: the former might lead to efficient solutions,but at the expense of long development times; the latter instead allows rapiddevelopment, but with severe performance cuts. With CLAK, we aim at aninterface more expressive than what offered by environments such as Matlab, andat performance levels equivalent to or even superior than Fortran codebuilt on top of optimized black-box libraries such as LAPACK. Specifically, the distinguishing features of CLAK are a) the expressiveness of the input language, b) the knowledge-based generation of algorithms, andc) the generation of code based on high-performance kernels provided by (existing) numerical libraries.CLAK will incorporate a language that allows users to express equationstogether with a wide range of properties which will then be automaticallytreated and exploited. Similarly to general-purpose compilers---which take asinput a computer program, and return optimized code to be executed on aspecific architecture---the idea behind the generation of algorithms in CLAKis the decomposition of the input equation onto a given set of kernelsprovided by high-performance libraries. At the heart of the process there is a "knowledge engine" and multiplelanguages (internal representations). The engine---based on a database ofidentities, properties and theorems---makes it possible to infer properties ofcomplex expressions from those of subexpressions. The internal representationsmake it possible to decompose the input equation---expressed in mathematicalterms---into efficient code while applying different types of algorithmicoptimizations. In all cases, instead of applying exhaustive search, thedecisions are steered by knowledge.

• DFG Programme: Research Grants