|
Glas :
[glas] GLAS requirements |
Hi all,
To start the technical discussion, I attached a short document with some
requirements about what exactly we would like to accomplish in this
project. Once we have detailed requirements we can outline the
description of work.
But thus first the 'requirements'. Attached is thus a first set of
requirements but we should discuss each of them in detail so I already
would like to have your feedback on the current description. Please also
don't hesitate to give your view on requirements that did not make it on
my list yet.
Next it might also be interesting to discuss how these requirements
differ from existing libraries (developed by yourself or others).
I will try to update this document constantly with the conclusions that
are reached on the ml.
toon
Generic Linear Algebra Software
Requirements
Containers
Generic support for dense and sparse vectors and matrices
Sparse and dense containers should mainly implement the same concepts.
Sparse and dense containers only differ in the definition of the structure
(i.e. location of non-zeros) which is implicit for dense while for sparse
containers the structure needs to be defined by the user.
Handling the structure of sparse containers
Multiple ways to define the structure of a sparse type are supported:
- The structure can be defined on the fly:
By assigning a value to a specific element of a sparse type,
the corresponding coordinates are automatically added to the structure.
- The structure can be defined seperatly:
The user can create the structure first and than create a sparse object that uses the given
structure. By creating multiple sparse objects that use the same
structure, the memory footprint will be reduced. Additionally many
operations involving sparse objects which are guaranteed to have the
same structure can be optimised.
Both ways can be mixed of course. A sparse object might be created from
a predefined structure and afterwards it might change its structure
whenever the user assigns a value to a previously zero element. From this
point onward however, this object will not be able to share its
structure anymore with other objects that were defined on top of the
same structure originally.
Memory management
Total abstraction should be made of where the object is stored. This
might be on the stack, on the heap, on disk or ...Every storage type
induces it own performance and size limitations.
To handle such a diverse number of storage types, containers
should make abstraction of the storage type they are using.
For instance a vector might use an underlying std::vector to store its
elements or a B-tree for handling very large vectors that must
(partially) be stored on disk.
Views
A wide range of different views should be supported:
- slices
- ranges
- indirect
- rows
- columns
Support for structured types
Structured types are special cases which define specific relations
between the different elements in the matrix. For structured types a
clear distinction must be made between the storage format (e.g. packed)
and the user-interface.
For instance, if the upper and lower part of a symmetric matrix are
stored, would changing an element in the upper part induce the
corresponding element in the lower to be changed. In case the symmetric
matrix is stored using the packed format this will be the case
automatically. But what happens if a row-view on a symmetric matrix is
taken and the values are changed via this view ?
Parallelism
Parallelism should be supported but what kind of distribution modes do
we allow ? And which mechanisms to use (both OpenMP and MPI)?
Performance
Performance is of utmost importance for an LA library. However first I
think we need to focus on the requirements and on defining a generic
interface. Performance is generally a consideration during the
implementation. However we need to make sure that the interface does not
imply performance constraints.
Reference implementation
In addition to the interface definition, this project also aims at implementing
a reference implementation. The focus of this reference implementation
is to implement the interface and provide optimal performance.
Support for multiple backends
This project is about (an interface for) a generic linear algebra
library and to provide a reference implementation. To attain optimal
performance with this reference implementation, the generics should
certainly allow to plugin multiple optimised backends such as Netlib-BLAS, ATLAS etc.
Whenever such a backend is plugged in, the library should be able to map (parts of) expressions
to these backends and request to calculate them. Of course, the (parts of) expressions that
can not be mapped must be calculated by the library itself.
Bindings
Users of the libraries might want to communicate containers to third-party
libraries such as SuperLU, UMFPACK etc.
The library should allow to define containers that can be easily exchanged
with these third-party libraries.
Expression templates
I think it's clear we need expression templates. But having expression
templates is not a goal in itself. It's more a means to achieve the goal
of performance. So I think that during the specification of requirements
we don't need to go deep into this.
Minimising abstraction penalty
During the implementation we should constantly evaluate the abstraction penalty
of the implementation. However minimising the abstraction penalty may never criple
the design.
Multi-platform
We should provide a reference implementation that can be compiled on reasoneably
conforming compilers. Again trying to be compatible with a non-conforming compiler
might not cripple the design.