Collaborative Research: A Systematic Approach to the Derivation, Representation, Analysis, and Correctness of Dense and Banded Linear Algebra Algorithms for HPC Architectures

尽管人们普遍认为密集线性代数库的研究已经耗尽，但历史表明，随着用于科学应用的高性能计算机中出现新的体系结构特征，重新研究广泛使用的密集线性代数软件包的必要性重新浮出水面。 当向量超级计算机在20世纪70年代首次出现时，当基于微处理器的工作站在20世纪80年代出现时，以及当分布式存储器并行架构在20世纪90年代出现时，情况就是如此。 现在，随着多级存储器在顺序和并行架构中的出现，重新设计再次得到保证，因为当前一代密集线性代数软件包所获得的性能与单个操作的最佳优化算法不匹配。 与此密切相关的一个问题是，现有的库并不总是具有科学计算社区所需的功能和性能，传统的方法从以前的库开发一个新的密集线性代数库的根本问题是，它固有的进化。 一直以来，人们都非常强调最大限度的代码重用，因为他们相信新的库会继承前一个库的“正确性”（主要是通过详尽的测试建立的），从而减少产生新库所需的工作量。 不幸的是，进化方法在过去失败并在未来注定失败的原因是可以确定的。 这个项目背后的基本前提是，必须制定一个革命性的方法，如果要避免重复投资的努力，最近的研究已经发现了一个系统的方法来推导可证明正确的稠密线性代数算法，通过应用经典的推导技术从计算机科学。现在可能触手可及的实际解决方案包括高性能密集带状线性代数库的（部分）自动开发（推导、实现、成本和稳定性分析）。 这与传统的实现这些库的方法相反，因为这些库的复杂性，开发，调试和维护是繁琐和容易出错的过程。 建议的工作承诺提供图书馆，需要很少或根本没有维护，通过系统和直接翻译系统派生的，可证明正确的算法到一个命令式的编程language.The建议的工作将奠定基础，这样的自动化系统，通过集中精力开发上述系统的方法，还没有冒险到自动化。 此外，将开发使用最新软件工程技术编码的原型库，以展示这些方法的潜力。 特别是，通过使用C++技术（如模板元编程和表达式模板）来克服驱动系统方法的抽象的明显成本的能力将是这项研究的核心。 成功将通过系统方法实现自动化的程度、使用该方法发现的新算法以及由此产生的原型库（在顺序和并行架构上）可以证明的性能来衡量。 其他项目目前使用的自动化方法在性能和灵活性方面被认为与拟议的图书馆没有竞争力。

Despite the general belief that research in dense linear algebra libraries has been exhausted, history shows that as new architectural features appear in high-performance computers used for scientific applications, the need for the renewed investigation of widely used dense linear algebra packages resurfaces. This has been the case when vector supercomputers first appeared in the 1970s, when microprocessor based workstations appeared in the 1980s, and when distributed memory parallel architectures appeared in the 1990s. Now, with the emergence of multi-level memories in both sequential and parallel architectures, a redesign is once again warranted, as the performance attained by the current generation of dense linear algebra packages does not match that of the best optimizations of algorithms for individual operations. A closely related concern is that the existing libraries do not always have the functionality nor the performance required by the scientific computing community.The fundamental problem with the traditional approach to developing a new dense linear algebra library from a previous library is that it has been inherently evolutionary. There has been a heavy emphasis on maximal code-reuse in the belief that the ``correctness'' (established largely through exhaustive testing) of the previous library is then inherited by the new library, thus reducing the effort required to produce that new library. Unfortunately, there are identifiable reasons why the evolutionary approach has failed in the past and is doomed to failure in the future. The fundamental premise behind this proposed project is that a revolutionary approach must be developed if the repeated investment of effort is to be avoided.Recent research has uncovered a systematic approach to the derivation of provably correct dense linear algebra algorithms via the application of classic derivation techniques from computer science. The practical solutions that may now be within reach include the (partially) automatic development (derivation, implementation, and cost and stability analysis) of high-performance dense and banded linear algebra libraries. This is in contrast to the traditionalapproaches for implementation of such libraries for which the development, debugging, and maintenance are tedious and error-prone processes because of their complexity. The proposed work promises to deliver libraries that require little or no maintenance through the systematic and direct translation of systematically derived, provably correct algorithms to an imperative programming language.The proposed work will lay the foundation for such automated systems by concentrating on developing the systematic approaches mentioned above, without yet venturing into automation. In addition, prototype libraries, coded using the latest software engineering techniques, will be developed to demonstrate the potential of the approaches. In particular, the ability to overcome the apparent cost of the abstractions that drive the systematic approaches by using C++ techniques like template meta-programming and expression templates will be central to the study. Success will be measured by the degree to which the systematic approaches will enable automation, by the new algorithms that will be uncovered using the methodology, and by theperformance that can be demonstrated (on sequential and parallel architectures) by the resulting prototype libraries. Automated methods currently used by other projects are not deemed to be competitive, in terms of performance and flexibility, with the proposed libraries.