Boost logo

Ublas :

From: Nico Galoppo (nico_at_[hidden])
Date: 2007-06-29 11:51:48


Also, you hit the nail on the head when you said 'row-major' storage. C = u * M
is basically a bunch of dot products with *columns* of M. So you may run into
cache trashing issues as you are continuously accessing non-coherent memory.

--nico

Ian Fellows wrote:
> Hi Markus,
>
> First off, I think it might be a good idea to turn off debugging by
> defining:
> #define NDEBUG
>
> next, if you can assume no shared memory between the left and right side
> of the equation, then you can use noalias
>
> noalias(v) = prod(u,M);
>
>
>
> What are the time results with these changes?
>
>
> Ian
>
> -----Original Message-----
> *From:* ublas-bounces_at_[hidden]
> [mailto:ublas-bounces_at_[hidden]]*On Behalf Of *Markus Weimer
> *Sent:* Friday, June 29, 2007 3:53 AM
> *To:* ublas mailing list
> *Subject:* [ublas] vector * Matrix is slow compared to hand written code
>
> Hi,
>
> we just did some experiments on the following case, which occurs
> often in our code:
>
> v = prod(u,M)
>
> where v and u are dense vectors and M is a sparse matrix in
> compressed row major format.
>
> We also did an alternative implementatio of prod called ourProd in
> the attached code. It follows the following algorithm:
>
> for i in M.size1():
> v += u[i] * M[i,*]
>
> where M[i,*] equals row i of M.
>
> This version often is 10-20 times faster than the prod in uBLAS on
> sparse M. While this is all good, the implementation in test_fast()
> in the attached source is sometimes 1000 times faster on very sparse
> matrices, for example when running the code with the following
> parameters:
>
> executable 100000 10000 1 0.001
>
> The parameters are as follows:
>
> executable ROWS COLS HOWOFTEN NONZEROPROBABILITY
>
> where HOWOFTEN controls how often the experiments are run.
>
> Do you see any way to achieve better performance within uBLAS for
> prod(u,M) with M being very sparse, as in 1 out of 1000 entries are
> set.
>
> Thanks in advance,
>
> Markus
>
>
> ------------------------------------------------------------------------
>
> _______________________________________________
> ublas mailing list
> ublas_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/ublas

-- 
Nico Galoppo        UNC-CH PhD.student        http://www.ngaloppo.org
                    cell +1-919-360-5056