Boost logo

Glas :

[glas] GLAS requirements

From: Toon Knapen (toon.knapen_at_[hidden])
Date: 2004-12-19 16:19:17


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

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.