mapping expressions to backend

classic Classic list List threaded Threaded
11 messages Options
Reply | Threaded
Open this post in threaded view
|

mapping expressions to backend

Toon Knapen
As stated from the beginning, see
http://glas.sourceforge.net/doc/requirements.html , we plan to support
multiple backends. Thus using the glas-interface, the expressions might
be mapped to the glas-implementation but also to BLAS-calls or any other
optimised backend.

And since we are starting to implement expressions, my question now is:
How will the user have to specify the desired backend?

The first option is that the user asks glas to automatically try to
dispatch all expressions to a specific backend. If the backend does not
provide a corresponding function, the expression will be evaluated by
the fallback (which is the glas implementation itself for instance).
For instance: If the user wishes to use BLAS as backend, writing
'y+=a*x' will automatically result in a call to axpy.

A second option is that the user needs to indicate explicitly the
backend to be used for evaluating a specific expression. For instance by
writing 'y+=mult<blas>(a,x)' or 'y+=blas(a*x)' or 'add_assign<blas>(y,a*x)'

A third option is that the user just calls a high-level binding
directly. For instance 'blas::axpy(y,a,x)'.

The third option is the least ambiguous (in respect to options 1 and 2,
see later) but also the least syntactically transparant. But do we need
syntactic transparancy? And after all, the implementation of 1 and 2
will have to use such a high-level binding anyway.

The first option is syntactically transparant but might result in
ambiguous situations: For instance what if the user writes 'y = a*x +
w'. Should that result in w first being copied to y followed by an axpy
or should that result in an error or should that result in the
expression being evaluated by the fallback implementation?

The main difference between option 1 and 2 is that option 1 requires a
system-wide setting while option 2 requires the backend to be specified
for each and every expression.

What do you prefer?

toon

--
Toon Knapen
Skype Name: toonknapen

============================================
NEW ADDRESS FROM FEBRUARY 1st ONWARD:

Axis Park Louvain-la-Neuve
rue Emile Francqui, 1
B-1435 Mont-Saint Guibert - BELGIUM
Same telephone, same fax, same mail
============================================

------------------------------------------------
Check out our training program on acoustics
and register on-line at http://www.fft.be/?id=35
_______________________________________________
glas mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/glas
Reply | Threaded
Open this post in threaded view
|

Re: mapping expressions to backend

Andreas Pokorny-2
On Tue, Jan 17, 2006 at 12:18:24PM +0100, Toon Knapen <[hidden email]> wrote:
> As stated from the beginning, see
> http://glas.sourceforge.net/doc/requirements.html , we plan to support
> multiple backends. Thus using the glas-interface, the expressions might
> be mapped to the glas-implementation but also to BLAS-calls or any other
> optimised backend.


> And since we are starting to implement expressions, my question now is:
> How will the user have to specify the desired backend?
>
> The first option is that the user asks glas to automatically try to
> dispatch all expressions to a specific backend. If the backend does not
> provide a corresponding function, the expression will be evaluated by
> the fallback (which is the glas implementation itself for instance).
> For instance: If the user wishes to use BLAS as backend, writing
> 'y+=a*x' will automatically result in a call to axpy.
>
> A second option is that the user needs to indicate explicitly the
> backend to be used for evaluating a specific expression. For instance by
> writing 'y+=mult<blas>(a,x)' or 'y+=blas(a*x)' or 'add_assign<blas>(y,a*x)'
>
> A third option is that the user just calls a high-level binding
> directly. For instance 'blas::axpy(y,a,x)'.
>
> The third option is the least ambiguous (in respect to options 1 and 2,
> see later) but also the least syntactically transparant. But do we need
> syntactic transparancy? And after all, the implementation of 1 and 2
> will have to use such a high-level binding anyway.
>
> The first option is syntactically transparant but might result in
> ambiguous situations: For instance what if the user writes 'y = a*x +
> w'. Should that result in w first being copied to y followed by an axpy
> or should that result in an error or should that result in the
> expression being evaluated by the fallback implementation?
>
> The main difference between option 1 and 2 is that option 1 requires a
> system-wide setting while option 2 requires the backend to be specified
> for each and every expression.
>
> What do you prefer?
You could have both, you could attach the info about the backend to your
types. And you could have a kind of override syntax in your expressions.
So for every backend a small backend tag type, and an instance of each
of them.

struct glas_lib_tag {};
struct atlas_lib_tag {};
struct example_library_tag {};

const glas_tag glas_lib;
const atlas_tag atlas_lib;
const example_library_tag example_library;

is required. These tags then can be attached to types. E.g:

  matrix<float,atlas_lib_tag> mat;
  matrix<float> some_other_matrix; // glas_lib_tag could be the default

  mat *= some_other_matrix;

and this expression will be evaluated using atlas. And to override that
setting, the user could write:
   
  mat[example_library] *= some_other_matrix;

and a different implementation will be used.

Picking the backend using a tag type can also be used for algorithms and
functions, which is what you do in two of your examples above.  

I am proposing that syntax because I currently work on a
diploma thesis with that topic. Currently there are these so
called strategy tags:

struct basic_system{}; // default implementation
struct doubled_accuracy{}; // doubles accuracy inside of expressions then
                           // casts back to target type during
                           // assignment
struct system_3dnow{}; // tries to make use of 3dnow instructions,
struct gmp_system{}; // uses the gnu multiple precision arithmetic library

template<size_t K>
struct kfold_dot_product{}; // all dot products are evaluated using
                            // kfold working precision

Some strategies only change certain poritions of the expression
evaluation. Since it is possible to simply reuse existing backends, only
the modified parts have to be implemented, e.g. for gmp_system and
doubled_accuracy only those nodes that handle assignment and accessing
data structures had to be implemented.
That way "basic_system" does impose a certain structure requirement, for
all derived backends, but it is also possible to implement a backend not
fitting into that layout, by not extending basic_system.
So other backends, like using a blas interface of a third party library is
still possible, but involves writing more backend code, well at least once.

I would like to explain more details if you are interested in the
backend layout imposed by basic_system.

Regards,
Andreas Pokorny
 

_______________________________________________
glas mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/glas

attachment0 (196 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: mapping expressions to backend

Wolfgang Bangerth-3
In reply to this post by Toon Knapen

> The first option is that the user asks glas to automatically try to
> dispatch all expressions to a specific backend. If the backend does not
> provide a corresponding function, the expression will be evaluated by
> the fallback (which is the glas implementation itself for instance).
> For instance: If the user wishes to use BLAS as backend, writing
> 'y+=a*x' will automatically result in a call to axpy.

I can't imagine why someone would want to use different backends in the same
program. I would therefore proposed to take option 1. The way this is
typically done is to give a switch at configure time:

  ./configure --with-backend=blas
  ./configure --with-backend=generic
  etc

W.

-------------------------------------------------------------------------
Wolfgang Bangerth                email:            [hidden email]
                                 www: http://www.math.tamu.edu/~bangerth/

_______________________________________________
glas mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/glas
Reply | Threaded
Open this post in threaded view
|

Re: mapping expressions to backend

Toon Knapen
In reply to this post by Andreas Pokorny-2
Andreas Pokorny wrote:

>
> You could have both, you could attach the info about the backend to your
> types. And you could have a kind of override syntax in your expressions.
> So for every backend a small backend tag type, and an instance of each
> of them.
>
> struct glas_lib_tag {};
> struct atlas_lib_tag {};
> struct example_library_tag {};
>
> const glas_tag glas_lib;
> const atlas_tag atlas_lib;
> const example_library_tag example_library;
>
> is required. These tags then can be attached to types. E.g:
>
>   matrix<float,atlas_lib_tag> mat;


Great. Currently we have provided this functionality already (but we
always used the term 'attribute' instead of 'tag').


>   matrix<float> some_other_matrix; // glas_lib_tag could be the default
>
>   mat *= some_other_matrix;
>
> and this expression will be evaluated using atlas.


Indeed, here you could say that the expression needs to be evaluated
using atlas because one container clearly preferred atlas while the
other had no preference. The situation can easily get ambiguous for
instance like in the following


matrix<float,some_other_backend_tag> mat_other ;
mat_other *= mat


What backend should be used now: atlas or the 'other_backend'?
This ambiguity is a consequence of attaching the attribute describing
the preferred-backend to the container instead of the operation. Because
it's actually the operation/expression that needs to be mapped to a
backend. Attaching an attribute to an operator however is syntactically
very difficult and thus resolving in option 2 (unless you have a better
idea) in my initial mail.

> And to override that
> setting, the user could write:
>    
>   mat[example_library] *= some_other_matrix;
>
> and a different implementation will be used.


This is indeed another alternative for the possible syntaxes I described
for option 2. I'm not sure which syntax is the easiest and clearest.

[snip]

>
> I would like to explain more details if you are interested in the
> backend layout imposed by basic_system.

If you have some document describing the design, you can always mail it
to me privately.

toon
_______________________________________________
glas mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/glas
Reply | Threaded
Open this post in threaded view
|

Re: mapping expressions to backend

Toon Knapen
In reply to this post by Wolfgang Bangerth-3
Wolfgang Bangerth wrote:

>>The first option is that the user asks glas to automatically try to
>>dispatch all expressions to a specific backend. If the backend does not
>>provide a corresponding function, the expression will be evaluated by
>>the fallback (which is the glas implementation itself for instance).
>>For instance: If the user wishes to use BLAS as backend, writing
>>'y+=a*x' will automatically result in a call to axpy.
>
>
> I can't imagine why someone would want to use different backends in the same
> program. I would therefore proposed to take option 1. The way this is
> typically done is to give a switch at configure time:
>
>   ./configure --with-backend=blas
>   ./configure --with-backend=generic


It is not unthinkable that the generic/glas backend outperforms an
optimised BLAS library for instance on e.g. compile-time-fixed-size
vectors.

So even though an operation is available in a BLAS library, the
developer might have some additional information which tells him that
the BLAS backend is not the fastest on evaluating a specific expression.

toon
_______________________________________________
glas mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/glas
Reply | Threaded
Open this post in threaded view
|

Re: mapping expressions to backend

Toon Knapen
In reply to this post by Wolfgang Bangerth-3
Wolfgang Bangerth wrote:

>
> I can't imagine why someone would want to use different backends in the same
> program. I would therefore proposed to take option 1.

And after specifying to use BLAS as a backend, would you like to be
informed by the library, whenever it is unable to dispatch an expression
to BLAS (because there is no equivalent in BLAS), that it is falling
back on the internal glas implementation ?
_______________________________________________
glas mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/glas
Reply | Threaded
Open this post in threaded view
|

Re: mapping expressions to backend

Andreas Pokorny-2
In reply to this post by Toon Knapen
On Wed, Jan 18, 2006 at 01:11:09PM +0100, Toon Knapen <[hidden email]> wrote:

> Andreas Pokorny wrote:
> >
> > You could have both, you could attach the info about the backend to your
> > types. And you could have a kind of override syntax in your expressions.
> > So for every backend a small backend tag type, and an instance of each
> > of them.
> >
> > struct glas_lib_tag {};
> > struct atlas_lib_tag {};
> > struct example_library_tag {};
> >
> > const glas_tag glas_lib;
> > const atlas_tag atlas_lib;
> > const example_library_tag example_library;
> >
> > is required. These tags then can be attached to types. E.g:
> >
> >   matrix<float,atlas_lib_tag> mat;
>
>
> Great. Currently we have provided this functionality already (but we
> always used the term 'attribute' instead of 'tag').

Yes, i just saw that. In my clean rewrite I do use boost::fusion-2 maps
to store meta information like that inside of expressions. And containers
are value expression in the terms of the frontend, so these also carry
attributes.

>
> >   matrix<float> some_other_matrix; // glas_lib_tag could be the default
> >
> >   mat *= some_other_matrix;
> >
> > and this expression will be evaluated using atlas.
>
>
> Indeed, here you could say that the expression needs to be evaluated
> using atlas because one container clearly preferred atlas while the
> other had no preference. The situation can easily get ambiguous for
> instance like in the following
>
>
> matrix<float,some_other_backend_tag> mat_other ;
> mat_other *= mat
>
>
> What backend should be used now: atlas or the 'other_backend'?
> This ambiguity is a consequence of attaching the attribute describing
> the preferred-backend to the container instead of the operation. Because
> it's actually the operation/expression that needs to be mapped to a
> backend. Attaching an attribute to an operator however is syntactically
> very difficult and thus resolving in option 2 (unless you have a better
> idea) in my initial mail.

In my case the left side of the assignment operator defines what backend
has to be used. In fact attaching the backend information to a type was a
feature not planed at the beginning. So the default was always basic_system,
if no other was given using the []-syntax. So the general rule for
picking the backend is always: let the left side of the assignment
decide.

One could also gather all backend info used inside of one expression and
store that in a type sequence while processing towards the '='. Then
one could ask some meta function which backend dominates the others.
But I think thats not verbose enough for the user to understand, what
backend is used.

That leads me to the possibility of combining backends. Which is
currently not yet supported by my code, but possible provided that all
backends follow the structure imposed by basic_system.

The current default backend defines a set of node structures, for all
kinds of binary and unary nodes in a linear algebra expressions. Each
of them has at least an operator() to evaluate the given node type.
These nodes are assembled during the different assignment operators.

Currently a depth-first search using the backend tag is done to find
the most specific partial or full specialization of a requested node
types. I think it would be possible to replace the depth search with
a breadth-first search, using all given backend tags. The syntax
proposed by Dave Abrahams will then look like that:

 mat[some_lib,another_feature,atlas_lib] += a*t;


>
> > And to override that
> > setting, the user could write:
> >    
> >   mat[example_library] *= some_other_matrix;
> >
> > and a different implementation will be used.
>
>
> This is indeed another alternative for the possible syntaxes I described
> for option 2. I'm not sure which syntax is the easiest and clearest.

I cannot tell either, I am already biassed by my solution :).


Regards
Andreas Pokorny

_______________________________________________
glas mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/glas
Reply | Threaded
Open this post in threaded view
|

Re: mapping expressions to backend

C J Kenneth Tan -- OptimaNumerics
In reply to this post by Toon Knapen
Toon,

> It is not unthinkable that the generic/glas backend outperforms an
> optimised BLAS library for instance on e.g. compile-time-fixed-size
> vectors.

How do you see this being possible when some implementations of BLAS
can deliver 98% to 99% of peak chip performance?


Kenneth Tan
-----------------------------------------------------------------------
C J Kenneth Tan, PhD
OptimaNumerics Ltd                    Telephone: +44 798 941 7838
E-mail: [hidden email]      Telephone: +44 207 099 4428
Web: http://www.OptimaNumerics.com    Facsimile: +44 207 100 4572
-----------------------------------------------------------------------
_______________________________________________
glas mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/glas
Reply | Threaded
Open this post in threaded view
|

Re: mapping expressions to backend

Andrew Lumsdaine
This can happen in a couple of ways.

One obvious way is for expressions / operations that do not have a  
corresponding BLAS realization.  Adding three vectors together and  
putting them into a third, for example.  Doing this with successive  
axpy calls is going to take many more trips through memory than the  
single fused loop you would get with an expression template approach.

Second, Toon didn't say that generic/blas would always outperform  
every optimized BLAS out there.  BLAS contains a number of functions  
(level 1, level 2, level 3).  Level-1 and level-2 BLAS are  
straightforward to match in performance (on microprocessor based  
systems) because the computation isn't typically the limiting factor  
on problems of any scale. It is only level 3 that can really reach  
close to peak performance (because of the favorable ratio of compute  
to memory access).  Even in that case, the optimizations to get that  
level of performance are well known and done at a high level (loop  
unrolling, tiling, blocking) -- and can be included in a glas  
equivalent to level-3 BLAS.  With MTL we were able to match or beat  
several vendor-tuned BLAS on gemm -- including ESSL.  And even if  
there are BLAS out there that are faster than glas for gemm -- some  
won't be -- hence, it is to be expected that there will be cases  
(CPU, problem size, compiler, vendor) where generic/blas backed  
outperforms BLAS.


On Jan 19, 2006, at 6:26 AM, C J Kenneth Tan -- OptimaNumerics wrote:

> Toon,
>
>> It is not unthinkable that the generic/glas backend outperforms an
>> optimised BLAS library for instance on e.g. compile-time-fixed-size
>> vectors.
>
> How do you see this being possible when some implementations of BLAS
> can deliver 98% to 99% of peak chip performance?
>
>
> Kenneth Tan
> ----------------------------------------------------------------------
> -
> C J Kenneth Tan, PhD
> OptimaNumerics Ltd                    Telephone: +44 798 941 7838
> E-mail: [hidden email]      Telephone: +44 207 099 4428
> Web: http://www.OptimaNumerics.com    Facsimile: +44 207 100 4572
> ----------------------------------------------------------------------
> -
> _______________________________________________
> glas mailing list
> [hidden email]
> http://lists.boost.org/mailman/listinfo.cgi/glas

_______________________________________________
glas mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/glas
Reply | Threaded
Open this post in threaded view
|

Re: policy of mapping expressions to backend

Toon Knapen
In reply to this post by Wolfgang Bangerth-3
Thus in case the backend to be used is configurable, what policies
should we envision to dispatch expressions to backend?

Suppose we have a BLAS backend, the expression `y+=a*x` will logically
be dispatched to an axpy. But what about the expression `y+=a*x+w` ? Do
we evaluate it with BLAS in two step (`y+=w;y+=a*x`) or do we evaluate
it with the generic backend since there's no _direct_ match with the
BLAS backend.

So which policy should we provide (or both)?

1) Only dispatch to a backend if the whole expressions matches exactly
one expression that is implemented by the backend

2) or should we try to match the whole expression with one or multiple
expressions that are implemented by the backend and thus trying to use
the preferred backend as much as possible.


Policy 1 works fine if we assume that a backend is only good at
evaluating the expressions that it directly supports while policy 2
assumes that one backend is in all cases far superior to another.

On the other hand when using policy 1, the interface to the backend
could be extended with expressions that are not _directly_ implemented
by the backend in case we know that it is nevertheless very good at
evaluating specific expressions. E.g. suppose we now that `y+=a*x+w` is
best evaluated with BLAS in two steps (instead of evaluating the
expression using a generic algo), we might list this expression to be
directly supported by the BLAS backend and thus force the dispatch of
the expression to the BLAS backend. The BLAS backend will on its turn
dispatch it to two BLAS calls.



Wolfgang Bangerth wrote:

>>The first option is that the user asks glas to automatically try to
>>dispatch all expressions to a specific backend. If the backend does not
>>provide a corresponding function, the expression will be evaluated by
>>the fallback (which is the glas implementation itself for instance).
>>For instance: If the user wishes to use BLAS as backend, writing
>>'y+=a*x' will automatically result in a call to axpy.
>
>
> I can't imagine why someone would want to use different backends in the same
> program. I would therefore proposed to take option 1. The way this is
> typically done is to give a switch at configure time:
>
>   ./configure --with-backend=blas
>   ./configure --with-backend=generic
>   etc
>
> W.
>
> -------------------------------------------------------------------------
> Wolfgang Bangerth                email:            [hidden email]
>                                  www: http://www.math.tamu.edu/~bangerth/
>
> _______________________________________________
> glas mailing list
> [hidden email]
> http://lists.boost.org/mailman/listinfo.cgi/glas
>

_______________________________________________
glas mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/glas
Reply | Threaded
Open this post in threaded view
|

assignment policy

Karl Meerbergen
Hi,


Next to the evaluation of expressions by some backend, there might also
be need for different assigment policies: e.g.
1) left hand side and right hand side must have the same size.
2) left hand side resizes before the assignment if sizes do not match.

For sparse collections, there are more choices:
3) the sparse structure on left and right hand sides must be the same
4) the sparse left hand side takes the structure of the right hand side
(it does no look at the numerical values)
5) the sparse left hand side only creates a structural non-zero when the
corresponding element in the right-hand side has a non-zero value (the
numerical values are checked).

Etc.

There can also be user defined policies.

The syntax to get this assignment behaviour can happen in the same way
as the dispatching to a back_end.

For example, we can have
assign<my_policy,my_back_end>(v, e);
which is by default:
v = e;

and also

add_assign<policy,backend>(v,e) or by default: v+=e
subtract_assign<policy,backend>(v,e)  or by default v-=e;

Alternatively, we can provide adaptors: e.g.

keep_sparse_structure(v) += e ;
fixed_size(v) = e ;

etc.

In addition, containers (and views) may have a tag or attribute that
decides which is the default assignment policy.


Karl

_______________________________________________
glas mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/glas