(sparse) operations and temporary storage

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

(sparse) operations and temporary storage

Gunter Winkler
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
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/glas

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

Re: (sparse) operations and temporary storage

Karl Meerbergen-2
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
>[hidden email]
>http://lists.boost.org/mailman/listinfo.cgi/glas
>

Disclaimer: http://www.kuleuven.be/cwis/email_disclaimer.htm

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

Karl.Meerbergen.vcf (344 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: (sparse) operations and temporary storage

Karl Meerbergen-2
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
>> [hidden email]
>> http://lists.boost.org/mailman/listinfo.cgi/glas
>>
>
>
> Disclaimer: http://www.kuleuven.be/cwis/email_disclaimer.htm
>
>_______________________________________________
>glas mailing list
>[hidden email]
>http://lists.boost.org/mailman/listinfo.cgi/glas
>

Disclaimer: http://www.kuleuven.be/cwis/email_disclaimer.htm

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

Karl.Meerbergen.vcf (344 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: (sparse) operations and temporary storage

Gunter Winkler
In reply to this post by Karl Meerbergen-2
Karl Meerbergen schrieb:
> 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
I can open the gzipped xml file, but I don't see anything useful. What
program should I use?

mfg
Gunter

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

Re: (sparse) operations and temporary storage

Karl Meerbergen-2
I use dia.

Karl


Gunter Winkler wrote:

>Karl Meerbergen schrieb:
>  
>
>>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
>>    
>>
>I can open the gzipped xml file, but I don't see anything useful. What
>program should I use?
>
>mfg
>Gunter
>
>_______________________________________________
>glas mailing list
>[hidden email]
>http://lists.boost.org/mailman/listinfo.cgi/glas
>  
>

Disclaimer: http://www.kuleuven.be/cwis/email_disclaimer.htm

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

Karl.Meerbergen.vcf (344 bytes) Download Attachment
Loading...