Generative Matrix Computation Library:

Generative Programming (GP) is about designing and implementing software modules which can be combined to generate specialized and highly optimized systems fulfilling specific requirements [Eis97]. The goals are to (a) decrease the conceptual gap between program code and domain concepts (known as achieving high intentionality), (b) achieve high reusability and adaptability, (c) simplify managing many variants of a component, and (d) increase efficiency (both in space and execution time) [CEG+98].
To meet these goals, GP deploys several principles [CEG+98]:

• Separation of concerns: This term, coined by Dijkstra, refers to the importance of dealing with one important issue at a time. To avoid program code which deals with many issues simultaneously, generative programming aims to separate each issue into a distinct set of code. These pieces of code are combined to generate a needed component.
• Parameterization of differences: As in generic programming, parameterization allows us to compactly represent families of components (i.e. components with many commonalities).
• Analysis and modeling of dependencies and interactions: Not all parameter value combinations are usually valid, and the values of some parameters may imply the values of some other parameters. These dependencies are referred to as horizontal configuration knowledge, since they occur between parameters at one level of abstraction.
• Separating problem space from solution space: The problem space consists of the domain-specific abstractions that application programmers would like to interact with, whereas the solution space contains implementation components (e.g. generic components). Both spaces have different structures and thus we map between them with vertical configuration knowledge. The term vertical refers to interaction between parameters of two different abstraction levels. Both horizontal and vertical configuration knowledge are used for automatic configuration.
• Eliminating overhead and performing domain-specific optimizations: By generating components statically (at compile time), much of the overhead due to unused code, run-time checks, and unnecessary levels of indirection may be eliminated. Complicated domain-specific optimizations may also be performed (for example, loop transformations for scientific codes).

The Generative Matrix Computation Library (GMCL) represents a comprehensive and extensively documented case study in Generative Programming. The GMCL makes widespread use of expression templates, generative C++ programming idioms, and many template metaprogramming facilities, e.g. control structures for static metaprogramming. The C++ implementation of the matrix component comprises 7500 lines of C++ code. The matrix configuration DSL covers more than 1840 different kinds of matrices (i.e. with different combinations of features such as dense or sparse, different shapes, different storage formats, dynamic or static memory allocation, different error checking strategies, etc.). Despite the large number of provided matrix variants, the performance of the generated code is comparable with the performance of manually coded variants. This is achieved by the exclusive use of static binding, which is often combined with inlining.

People involved in the GMCL project include Krzysztof Czarnecki, Ulrich Eisenecker, Johannes Knaupp, and Tobias Neubert (past member). This work has been supported in part by Daimler-Benz AG and the German Federal Ministry of Education, Science, Research and Technology (BMBF) through the OSVA project.
 

Documentation and Sources

• “Case Study: Generative Matrix Computation Library (GMCL)” includes a comprehensive description of the analysis, the design, and the implementation of GMCL. The analysis and design method applied here is DEMRAL (see below) and the C++ techniques used in the implementation are described in the document available below. The source code of the demo generative matrix component described in this chapter is also available (compiles with Microsoft Visual C++ 5.0). The source code of the full implementation specified in this document is available below.
• “Domain Engineering Method for Reusable Algorithmic Libraries (DEMRAL)” describes a complete analysis and design method for developing reusable libraries in algorithmic areas such as image processing, numerical computing, containers, etc.
• “Static Metaprogramming in C++” explains some advanced template metaprogramming techniques used in GMCL. A comprehensive tutorial on Static Metaprogramming in C++ will be published in the upcoming book K. Czarnecki and U. Eisenecker. Generative Programming: Methods, Techniques, and Applications. Addison-Wesley, to appear in 1999. Also see Template Metaprogramming

• The full implementation of the matrix component was done by Tobias Neubert. Here is his Masters Thesis:

T. Neubert. Anwendung von generativen Programmiertechniken am Beispiel der Matrixalgebra. Diplomarbeit, Technische Universität Chemnitz, 1998 (in German)
• Here is the source code of the full implementation of the generative matrix component (compiles with Microsoft Visual C++ 5.0). Please note that this code is still experimental and has a number of known problems.

We are currently working on a new version of the matrix component as well as on a generative matrix factorizations component.

Related links

References

[Eis97] U. Eisenecker. Generative Programming (GP) with C++. In Proceedings of Modular Programming Languages (JMLC’97, Linz, Austria, March 1997), H. Mössenböck, (Ed.), Springer-Verlag, Heidelberg 1997, pp. 351-365, see http://home.t-online.de/home/Ulrich.Eisenecker/