> Brad Lucier writes:
> > It seems to be fairly fast; e.g., my second generation sparse
> > matrix--vector multiply with a single right hand side takes 17 cycles
> > per flop on my Alpha 21264.
>
> A lot depends on the size of the matrix for whether this really is
> fast. The Alpha is a darn fast chip overall, so even at 17 cycles per
> flop it is pretty quick.
>
> But if memory serves it ought to be able to do 0.5 cycles per flop if
> the data fits in cache. Or 1 cycle per flop, I forget. Either way,
> more than an order of magnitude, and you would see close the machine
> speed in either C or Fortran.
It's a sparse matrix with 16641 rows; most rows have 7 nonzero entries,
for which I store 7 indices and 7 coefficients; thus the matrix storage
required is roughly
16641 * (7 + 7 + 2) * 8 = 2,130,048 bytes
(the +2 is for the links to the coefficient and index vectors for each
row), which does not fit in the L1 cache, but does fit in the L2 cache.
The L1 cache has an 11 cycle delay, I seem to remember (and multiple loads
can be outstanding at one time); I don't know what delay the L2 cache has.
And (I'm not trying to back-peddle here) this is a work in progress.
The elements are not exactly ordered randomly, but no particular
attention is paid to how they're ordered. One student is working
on a space-filling-curve ordering in an attempt to improve locality.
And gcc-2.95.1 schedules the main loop in 68 cycles; the development
version of gcc, called with a switch to transform the code to SSA
canonical form (which seems to be buggy, unfortunately), schedules it in
40 bytes, which may (or may not) bring it down to 10 cycles per flop.
When I asked one of the parallel programming guys here at Purdue how
fast you could expect this type of code to go in C on an SGI, he said he
didn't remember precisely, but it was about 10 cycles/flop with multiple
argument vectors. So unless someone has better data, I'll continue to
believe that I'm in the right performance ballpark ;-).
Brad
--------------------- Object Oriented Numerics List --------------------------
* To subscribe/unsubscribe: use the handy web form at
http://oonumerics.org/oon/
* If this doesn't work, please send a note to owner-oon-list@oonumerics.org
This archive was generated by hypermail 2b29 : Wed Feb 20 2002 - 03:20:10 EST