Project 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
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
Revision history