|
|
Glas :Re: [glas] (sparse) operations and temporary storage |
From: Karl Meerbergen (Karl.Meerbergen_at_[hidden])
Date: 2006-12-20 03:35:36
Gunter,
I'd like to add that backends may introduce concepts. Additional
conceptual requirements may have to be added, e.g. the BLAS backend
should always be able to get a pointer to the data.
Karl
Karl Meerbergen wrote:
> Hi Gunter,
>
> I am currently writing a proposal for the first GLAS concepts.
>
> The concepts are very minimal and make a distinction between dense and
> sparse. The common concepts are VectorExpression and VectorCollection.
> See the dia file in http://www.cs.kuleuven.be/~karlm/glas/expression.dia
>
> Details about temporary storage, I would personally keep in the
> backend since they are most likely implementation dependent.
>
> Again, this is my view. We haven't really discussed these issues yet.
>
> Concerning your example, I haven't really thought about this in detail
> yet, but my first bet would be to split
>
> z = alpha x + beta y
> into
> z = alpha x
> z += beta y
>
> when x or y are a SparseExpression with different sparse structure.
>
>
> Karl
>
>
> Gunter Winkler wrote:
>
>> Hallo,
>>
>> will the glas-concepts consider the need for temporary storage or is
>> this only interesting for the backends?
>>
>> Lets for example consider a linear combination of two sparse vectors:
>>
>> z = alpha x + beta y
>>
>> in the case x and y being conformant (the pairs (index,value) are
>> sorted by index) the result can be computed in order by a parallel
>> run through both vectors. The index sequence of z is just a merge of
>> two sorted sequences.
>> However, if x or y are not conformant one could either use
>> z = alpha x; z += beta y; or utilize a temporary dense vector "temp"
>> known to be zero everywhere:
>> temp = alpha x; // sparse assign because temp is zero ("scatter")
>> temp += beta y; // sparse update of a dense vector
>> for each index i in x do {
>> z(i) = temp(i); temp(i) = 0;
>> } // "gather and clear"
>> for each index i in y do {
>> if temp(i)!=0 { z(i) = temp(i);
>> temp(i) = 0;
>> }
>> } // "gather if nonzero and clear"
>>
>> One important point is, that the vector "temp" has to be reused many
>> times in order to amortize is allocation cost. Thus it has to be a
>> parameter of the assign operation.
>>
>> (This algorithm is expected to be even faster than the conformant
>> merge, especially when more vectors are combined - but I never tried
>> it.)
>>
>> The question is now, should this be considered in the general
>> concepts, or could this be hidden inside backend functions, or should
>> these optimizations left to the enduser by only providing some
>> building blocks?
>>
>> Another question is, whether to have concepts (and implementations)
>> which are independent of the actual implementation and provide
>> refinements for dense and sparse types (which might be quite
>> different) or to have concepts (and models) mainly for dense types
>> and refine these for sparse types.
>>
>> What do you think?
>>
>> mfg
>> Gunter
>>
>>
>> ------------------------------------------------------------------------
>>
>> _______________________________________________
>> glas mailing list
>> glas_at_[hidden]
>> http://lists.boost.org/mailman/listinfo.cgi/glas
>>
>
>
> Disclaimer: http://www.kuleuven.be/cwis/email_disclaimer.htm
>
>_______________________________________________
>glas mailing list
>glas_at_[hidden]
>http://lists.boost.org/mailman/listinfo.cgi/glas
>
Disclaimer: http://www.kuleuven.be/cwis/email_disclaimer.htm