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 traditional approaches 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 the performance 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.
