1. Messages
  2. Sparse Matrix-Vector Multiply (again) and Bit-Vector Compression

Re: Sparse Matrix-Vector Multiply (again) and Bit-Vector Compression

Nick Knight
 

Hi Dawei,

Unfortunately the V-extension does not currently feature block-matrix multiplication instructions, including the bit-masked versions that you're describing. Some of these operations are intended to be addressed by a future (sub-) extension (perhaps EDIV). 

Presently, you can apply your scheme directly to the restricted class of BCSR matrices with 1-dimensional blocks. You can imagine various (nonzero-structure-dependent) tradeoffs between using r-by-1 and 1-by-c blocks.

More generally you can recursively compose (singly or doubly compressed) block-CS{R,C} formats, encoding indices using bitvectors or lists at any level of the recursion.

Best,
Nick


On Tue, Oct 20, 2020 at 2:04 AM lidawei14 via lists.riscv.org <lidawei14=huawei.com@...> wrote:
Hi，

Perhaps instead of using bit vector to encode an entire matrix, we can encode a sub block.
There is a common sparse matrix format called BCSR that blocks the non-zero values of CSR, so that we can reduce col_ind[] storage and reused vector x.
The main disadvantage of BCSR is we have to pad zeros, where we can actually use a bit mask to encode nonzeros of a sub block as Nagendra's bit vector implementation so that the overhead can be avoided.
I could not find good reduction instructions for tiled matrix vector multiplications if we have multiple rows in a block.

One sub block:
A =
a b
0 d 
Corresponding x:
x =
e
f
Bit vector:
1 1 0 1
Computation:
a b 0 d 
e f e f
 
fmul = ae bf 0e df 
accumulate (reduction) ae+bf,0e+df
(Note we can skip that zero computation using bit mask).

Thanks,
Dawei

Join {tech-vector-ext@lists.riscv.org to automatically receive all group messages.