Boost logo

Glas :

[glas] the glas-charter

From: Toon Knapen (toon.knapen_at_[hidden])
Date: 2004-12-10 04:45:31


If you receive this mail that means that you have been subscribed (by
me) to the glas mailinglist. Welcome again.

As promised in the mail you received about your subscription to the ml,
I'm sending the latest edition of the charter to the ml (in attachment).

Please don't hesitate to discuss the project setup or other issues that
you have on your mind. And then somewhere next week I hope we can start
with the technical discussions.

toon


GLAS

Project charter:

Generic Linear Algebra Software (GLAS)

version 0.05

Goal of the project

This project aims to investigate a generic interface for matrix and vector operations that allows for good performance and provides a multi-platform reference implementation.

Importance of numerical simulation for industry

Numerical simulation has become an important tool for the design of modern products. Its major contribution lies in the reduction of the number of prototypes that have to be built for the optimal design, since numerical simulation of particular aspects of the design may help the decision of important process parameters at a lower cost and higher speed. Typical simulations are crash tests for the automotive industry, structural dynamics tests for vehicles and buildings, acoustic analysis of engines and tyres, simulation of electronic circuits. Tests with prototypes are often hard to carry out, for example in the aerospace industries. industry

Motivation

For many software applications such as CAD/CAE/CAM, visualisation, simulation, game-development, robotics, statistics, machine-steering, quantum mechanics, medical imaging, etc, linear algebra operations on vectors and matrices reside in core modules, performing time consuming computations.

The introduction of the BLAS (Basic Linear Algebra Software) has been a revolution in scientific computing. The advantages for the industry were manifold: Since machine vendors provided optimised BLAS implementations for their platforms and since the above mentioned applications mainly spent their time doing linear algebra operations, application developers could obtain maximal performance by using this standard library. Additionally, the widespread use of BLAS made it easy to exchange/port high-level libraries that were implemented using BLAS, again offering optimal performance.

The interface for BLAS has been defined in FORTRAN, traditionally the language of choice for numerical software. The BLAS[1] are a collection of subroutines that only provide a small set of linear algebra operations. Nevertheless, the lack of support for object-orientation, generics[2] and meta-programming[3] in FORTRAN makes BLAS hard to extend. The lack of these techniques also complicated the interface of sparse matrix BLAS which might explain its limited success.

Therefor this project aims mainly on defining a generic[1] interface for matrix and vector operations. Although the interface must be generic, the flexibility of the interface might not constrain the performance. In addition to specifying the concepts, this project will also provide a multi-platform reference implementation. Because of its support for O.O., generics, meta-programming along with its wide-acceptance in the scientific community, the interface and reference implementation will be defined using C++.

Impact

More and more numerical software is no longer written in FORTRAN, but using C++, because of the availability of generics, meta-programming and polymorphism. Linking C++ with FORTRAN and C codes is fairly easy. Unfortunately, numerics has never been well supported by the C++ community. There is no C++ standard for vectors and matrices. As a consequence, application software developers have to write their own linear algebra libraries or rely on public domain libraries. The development of a library that satisfies a high quality standard in user friendliness, performance, and portability is a time consuming job. Public domain libraries are usually not complete, not well documented and contain a large number of bugs and inconsistencies.

The availability of such a generic library would improve the time-to-market for applications in the above mentioned industries as well as allow for more complex calculations.

If, in addition, this library would be accepted as an ad-hoc standard for linear algebra operations, application developers will be able to share and exchange/port algorithms and machine-vendors can concentrate on this one library to boost the performance for a large number of different applications. Hence, we expect the same impact as the BLAS and LAPACK have had many years ago and still have on the community of scientific computing worldwide.

Research objectives and challenges

This project aims to define an interface and a reference implementation. The main focus will be on defining the interface because this is most important to the users whereas a good interface provides plenty of room for improving the implementation. The timeframe does not allow for finding an optimal implemenation.

Generic data types

Although interfaces to dense generic vectors and matrices are straightforward (which are generic in respect to value_type, memory layout, memory allocation etc.) we also plan to define structured matrices (i.e. symmetric, Hermitian, skew-symmatric, etc.). Next, we plan to define various types of sparse matrices for which currently multiple memory layouts are documented but no generic interfaces nor (efficient) reference implementations are available.

Efficient evaluation of expressions

Within this project we focus on evaluating expressions containing operations on vectors, matrices and other expressions in a minimal amount of time. An example of such and expression is y = a*x + b. These expressions should be evaluated as efficiently as possible taking into account possible memory-footprint constraints. Therefore it needs to minimise the necessary amount of floating point operations and the data access patterns. Additionally, the expression might be best evaluated without or using some strategically placed temporaries. Again these temporaries need an optimal layout to reduce the required number of flops and optimise the data-access patterns. For instance D=(A+B)*(C+D) is best evaluated using a temporaries.

The goal of the project is to analyse the order of the evaluation of elements of an expression depending on the data in this expression. Generics should also support mixing different data types (e.g. multiplication of real matrix with complex vector).

Flexible interface allowing multiple implementations

This project aims at defining an interface and a complete reference (or native) implementation. However it should be possible to plugin different 'backends' into the native implementation. This would for instance allow expressions (can also be temporaries) that map onto a BLAS funtion to be routed to an optimised BLAS-kernel.

Parallel computing

Due to the increased popularity of clustered and numa machines in the scientific community, parallel data types and algorithms will be supported exploiting a combination of MPI and OpenMP.

Reduction of the abstraction penalty

Since the project aims for flexible interfaces as well as optimal performance, the code should be structured to avoid any abstraction penalty. The abstraction penalty might certainly be significant on proxies (such as matrix-stride's, indirect matrices etc.). This objective can be achieved in collaboration with compiler-vendors. This is a major research theme in this project.

Machine performance

Not only algorithms should be optimised for performance, but all available machine resources should be exploited such as vector-processing units, block-organise algorithms for cache-optimisation etc.

Partners

Types

Three types of project-partners can be distinguished
Developers
Any of the members could participate in the research, definition and implementation of the library as it is open-source.
Tool-specialists
Tool-specialists (tool-vendor but not necessarily) will specifically focus on portability and performance to their supported platforms. The involvement of tool-specialists is necessary to optimise data-access patterns (see efficient evaluation of expressions), OpenMP (see parallel computing) and the reduction of the abstraction penalty.
End-users
End-users try the library in a real (industrial) environment.

People

Note that because the organisations for which following people are working for are mentioned does not imply that these organisations endorse the project.
David Abrahams, Boost consulting
Achim Basermann, NEC Europe Ltd, C&C Research Laboratories:
Education: MSc and PhD in Electrical Engineering Achim Basermann, Principal Researcher and Team Leader for applications, support environments and libraries, obtained a PhD in Electrical Engineering from RWTH Aachen in 1995 followed by a postdoctoral position in Computer Science at Research Centre Juelich GmbH, Central Institute for Applied Mathematics. In 1997 Dr. Basermann joined CCRLE. Current research is focused on parallel sparse linear algebra algorithms (developed libraries: PILUTS for systems of linear equations and JADA for eigenproblems) and circuit simulation. Contributions to EC projects were within the ESPRIT EC-DGIII Basic Research Project APPARC, the ESPRIT LTR project DRAMA, the ESPRIT project SEP-Tools and the IST project SimBio. In the current FP6 IST project NextGRID, Dr. Basermann is workpackage leader of the activity Applications.
Guntram Berti, NEC Europe Ltd, C&C Research Laboratories:
Education: MSc and PhD in Mathematics Guntram Berti, Principal Researcher, obtained a MSc in mathematics at the University of Dortmund and a PhD in mathematics at the University of Cottbus. In 2001 Dr. Berti joined CCRLE. His current research is focused on bio-medical applications, including mesh generation (VGrid mesh generator) and parallel FEM solvers as well as on the development of mesh tools and algorithms (GrAL: Grid Algorithms Library) using generic programming in C++. He participated in the EC-funded project SimBio and is contributing to the current EC projects PRISM and GEMSS.
Harold C. Edwards, Sandia National Laboratories:
Sven Hammerling, Numeric Algorithms Group Ltd.:
Toon Knapen, Free Field Technologies S.A.:
After obtaining an MSc in physics from the University of Ghent, Toon shortly worked inside a team of 1K engineers on telecommunication software. Next he started working on simulation software and in August 2000 started the development of the parallel finite element framework called FEMTown.
Patrick Kowalzick:
Kresimir Fresl, Faculty of Civil Engineering, University of Zagreb:
Born in 1962 in Zagreb, Croatia, Kresimir Fresl graduated in 1988 at the Faculty of Civil Engineering, University of Zagreb, obtained MSc in 1993 at the Technical Faculty, University of Maribor, Slovenia, and PhD in 1998 at the Faculty of Civil Engineering, University of Zagreb. Since 1988 Kresimir Fresl works at the Faculty of Civil Engineering, University of Zagreb, first as assistant, then as research assistant and currently as associated professor (course: Structural Analysis). His current research interest is the application of the Partition of Unity Methods in numerical modelling of building structures, in particular historical and monumental structures. Kresimir Fresl has been using C++ for his research for a long time and reviewed the initial revision of the valarray proposal of David Vandevoorde. Currently he uses uBLAS and contributed bug-fixes, vector_indirect and matrix_indirect and improved the compressed and coordinate vectors and matrices. Additionally he also codeveloped the bindings libraries that provide generic bindings to LAPACK, UMFPACK, Netlib BLAS and ATLAS.
Andrew Lumsdaine, Indiana University:
John Maddock
John Maddock is a PhD Chemist (Nottingham 1992) and now an independent programmer / consultant from the UK with an interest in generic programming and library design. He is the author of the Regular Expression and Type Traits chapters from the forthcoming Technical Report 1, for the ISO C++ Standard.
Karl Meerbergen, Free Field Technologies S.A.:
He obtained a PhD in March 1996 from the Faculty of Applied Sciences of the Katholieke Universiteit Leuven. His expertise on the solution of large scale eigenvalue problems and more recently algebraic model reduction has been recognized by the international community on numerical linear algebra. His professional experience is partly academic (K.U. Leuven, U. Utrecht, Rutherford Appleton Laboratory) and partly industrial (LMS and Free Field Technologies), with research interests in numerical linear algebra, parallel and scientific computing. He has had long term visits to the European Space Operation Centre (ESA-ESOC), Bath University, and Stanford University. Karl Meerbergen has used computer languages (FORTRAN, C, Fortran 90, C++) for scientific computing over many years. Currently, he is responsible for linear algebra research and development at Free Field Technologies. The Krylov method software developed by him is used by Msc.Nastran to speed up the computation of frequency response functions. Together with Kresimir Fresl and Toon Knapen he contributed to the development of C++ bindings to LAPACK and dense BLAS.
Vladimir Prus,
Vladimir was born in 1979, graduated from CS department of the Moscow State University in 2001 and is currently working on a PhD thesis about static program analysis. While PhD student, he was also developing a simulation tool for a multi-processor system, including efficient processor emulation, time estimation and whole-system modelling. He's also lead developer of the Boost.Build V2 project and a contributor to C++ Boost. His primary experience include C++, Python and software engineering tools.
Alan B. Williams, Sandia National Laboratories:

Organisations

The organisations that support the project are:
Faculty of Civil Engineering, University of Zagreb:
Free Field Technologies S.A.:
Free Field Technologies (FFT) occupies a leading position in the small world of computational acoustics. Founded in 1998, this belgian SME has managed to convince several large industrial groups of the value of its software developments and engineering services. To name but a few Airbus, Rolls-Royce, Aermacchi, Honda, Renault, Peugeot Citroën Automobile, Fiat, BMW, Daimler-Chrysler, Solvay, Rieter, Hutchinson, Glaverbel, Alstom and Goodyear are for instance among its customers. FFT has two major activities : development of a general purpose acoustics, vibro-acoustics and aero-acoustics simulation tool (ACTRAN) and provision of consulting services based on this and related software products. FFT has a staff of 17 engineers, half of them holding PhDs. A subsidiary was opened in France in 2000 and a representation office opened in the US in March 2003. FFT received an award from the Fondation Roi Baudouin in 1999 for its innovative economical activity and reached the second place in the European Trophy for the Spirit of Entreprise 2000 Contest. FFT is the project coordinator of the AROMA project (FP5, Growth, KA Aeronautics and space) and a partner in SMILE and RATIN (FP5, Growth, KA Surface Transport)
Indiana University:
NEC C&C Research Laboratories:
C&C Research Laboratories, NEC Europe Ltd. (CCRLE), Sankt Augustin, Germany, is one of two laboratories belonging to NEC’s corporate R&D group (the other being the Network Laboratory in Heidelberg, Germany). Its main activities lie in the area of parallel and distributed computing, including High Performance Computing (HPC) for both support environments and applications on a range of hardware architectures from PC clusters to vector supercomputers.

Description of work

First the requirements need to be set out: concept definitions of dense, sparse and structured and matrices and vertices. Also (collaboration with) existing libraries (uBLAS, MTL[4],SparseBLAS,PETSc,Trilinos,...) will be investigated. Finally the reference library will also be contributed to boost[5] The definitive work-program will be defined in collaboratin with the project partners. This reference library will be made available for all platforms with a reasonably conformant C++ compiler. And for every platform with a reasonable conformant compiler, only the most conformant compiler will be supported.

References

[1] BLAS
BLAS has had a great effect on the software industry. Therefore machine vendors also provide vendor-tuned BLAS libraries: IBM ESSL,Intel MKL,....
[2] Generic
For the definition of generic programming, see wikipedia.

The interfaces defined in this project aim to be generic in respect to

[3] Meta-programming
short definition of meta-programming will come here
[4] MTL
MTL is a development of Notre Dame university.
[5] boost
See http://www.boost.org

Revision history