## Glas :## [glas] the glas-charter |

**From:** Toon Knapen (*toon.knapen_at_[hidden]*)

**Date:** 2004-12-10 04:45:31

**Next message:**David Abrahams: "[glas] Re: Welcome to the "glas" mailing list"**Previous message:**Toon Knapen: "[glas] testing the new ml"

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

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.

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++.

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.

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.

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).

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.

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.

- 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.

- 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:

- 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.

- [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

- the value_type: being able to mix for instance real and complex vectors (but integers, UDT's and others are supported too),
- the structure: algorithms should be able to make abstraction of the matrix type they are working on which can be symmetrix, hermitian etc, ranges or strides on containers should be interchangeable with the basic containers etc.
- the memory management: the containers might be allocated on the heap or the stack using different mechanisms.

- [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

- 0.01: Initial draft
- 0.02: Cleanup using HTML tidy and added the 'goal of the project' to the beginning of the document
- 0.03: Documented that only reasonably conforming compiler will be supported and only the most conforming per platform.
- 0.04: Corrected example in 'efficient evaluation of expression' section. Also modified footnote 2 to state that we are not only considering real and complex value types.
- 0.05: Added partner section, 'project proposal' has become 'project charter' because it is not the sole intent of this text anymore to be proposed to the E.U.

**Next message:**David Abrahams: "[glas] Re: Welcome to the "glas" mailing list"**Previous message:**Toon Knapen: "[glas] testing the new ml"