SHF: Small:Transforming Linear Algebra Libraries

自从第一个FORmula TRANslator出现以来，编译器就声称可以采用人类语言制定的算法，并将其编译为有效的可执行文件。实践显然不能达到这种理想，因为编程语言迫使程序员做出面向执行的设计决策，而编译器的缺陷需要进一步的手动优化。虽然普通程序员可以通过使用库来忽略这个问题，但库开发人员却不能。这个问题现在看起来比以往任何时候都更加令人绝望，因为不知道未来的体系结构会采取什么形式，再加上将复杂性从体系结构（例如降低功耗）推到程序和编译器上的趋势。FLAME项目已经允许在更高的抽象层次上开发和编码线性代数库，从而更好地捕获底层算法。已经证明，这些技术极大地简化了库到不同平台的移植，从传统的顺序计算机到新奇的多gpu加速器。然而，用于高层次抽象编码的api会对每一步执行相对较少计算的操作（例如，2级blas操作和“无阻塞”算法）产生相当大的性能损失。因此，libflame的非平凡部分（由该项目产生的库）仍然需要低级别的编码。该项目将开发一个源到源的翻译器，该翻译器将采用高层次抽象表达的算法，并将其转换为一系列表示形式，包括高性能的低级代码。这将克服最终对FLAME方法的合理反对，因为在高抽象级别上编码将不再带来性能损失。该方法将被一般化，以便专家为了针对不同的平台而手工应用的代码转换将变得机械。总之，这些都代表了对图书馆发展的传统方法的重大背离。

Ever since the first FORmula TRANslator, compilers have purported totake an algorithm, formulated in human terms, and compile it to anefficient executable. Practice clearly does not live up to thisideal, as programming languages force execution-oriented designdecisions on the programmer, and compiler imperfections necessitatefurther manual optimizations. While the ordinary programmer canignore this problem by using libraries, the library developer cannot.The problem appears more desperate now than ever, since it is notknown what form future architectures will take, combined with a trendtowards pushing complexity away from the architecture (for example tolower power consumption) and onto the program and compiler.The FLAME project already allows linear algebra libraries to bedeveloped and coded at a high level of abstraction that bettercaptures the underlying algorithms. It has already been shown thatthese technique greatly simplify the porting of libraries to differentplatforms ranging from conventional sequential computers to exoticmultiGPU accelerators. However, the APIs for coding at a high levelof abstraction incur a considerable performance penalty for operationsthat in each step perform relatively little computation (e.g., level-2BLAS operations and ``unblocked'' algorithms). As a result, anontrivial part of libflame, the library that has resulted from theproject, still requires coding at a low level.The project will develop a source-to-source translator will takealgorithms expressed at a high level of abstraction and will transformthese into a range of representations, including high-performancelow-level code. This will overcome the final legitimate objection tothe FLAME methodology since coding at a high level of abstraction willno longer carry a performance penalty. The approach will begeneralized so that code transformations that an expert applies byhand in order to target different platforms will be made mechanical.Together, these represent a major departure from traditionalapproaches to library development.