[Sparse] Support sparse matrix computation

[liangfu]

Objective

• To reduce unnecessary work load in computing convolution over large amount of zeros.
• To reduce memory/cache footprint

TODOs

• Step 0 : Summarize the design decision
• Step 1 : Update the PR ([Sparse] add sparse tensor computation support #1289) to support the following features
• Create tvm.contrib.sparse.CSRNDArray and tvm.contrib.sparse.placeholder for creating sparse tensor.
• Provide conversion between numpy.ndarray and tvm.contrib.sparse.CSRNDArray
• Implement topi.sparse.csrmv and topi.sparse.csrmm as SpMV and SpMM, and check correctness with dense tensor operations
• Support some other sparse tensor computation (e.g. relu, batch_norm, flatten)
• Demonstrate sparse approximation based on MobileNetV2, and compare performance with dense matrix computation baseline.
• Write a blogpost introducing this feature.

Proposed API Changes

• There will no change to original Tensor object.

[tqchen]

It is great to introduce sparse computations. However, directly introducing the sparse tensor into Tensor object seems to be a big change.

How about we still keep the original tensor data structure, but implement sparse operation using two tensors(index, data). Benchmark the end to end speed, then work on proposals to bring formal sparse storage in once we have a good idea about what is needed.

[liangfu]

In this case, we shall introduce tvm.tensor.SparseTensor and adopt it into ComputeOp for a quick benchmark implementation. The sparse tensor would only support indexed data structure, so that it would be easier to maintain.

[tqchen]

we could start with a tvm.contrib.SparseTensor for this. The only thing that I am not so sure so far is how much code generation trick need to be included.

[tqchen]

One of the design consideration we need to think here is that whether the sparse storage specification should sit inside the Operation object, or should it be specified via memory layout, in which case it should be the Buffer object. Having a SparseBuffer might be better in such case

[liangfu]

In my observation, if sparse storage is designed to sit inside a Operation object, there is a need to create a sparse buffer object. However, there would be too much work, and I think it is unnecessary to make sparse storage inside operation object at current stage.

Also, I think the main problem right now is that the output shape of data, indices and indptr are sometimes undetermined (e.g. adding two sparse matrix and expecting sparse matrix as the output). Therefore, it is difficult to allocate output buffers for sparse operations. Is there any idea?

[tqchen]

I think @eric-haibin-lin might have more ideas. Dynamic memory allocation could be necessary for sparse computations.
Also, taco contains a lot of great ideas on sparse code generation(by @fredrikbk) and we should adopt it in some way

[fredrikbk]

Hi @liangfu and @tqchen,

Sparse matrix computations require dynamic memory allocation when the results are sparse, such as in e.g. sparse matrix addition, multiplication and element-wise multiplication. For examples, you can use the code generator at http://tensor-compiler.org/codegen.html. Just select matrix addition from the dropdown menu (three vertical dots), press general kernel, and select the ASSEMBLY or COMPLETE tab.

Code generation for sparse computations is a significant effort (see e.g. http://tensor-compiler.org/publications.html). One option is to adopt taco as a code generation backend.

[liangfu]

Hi @fredrikbk , thanks for your explanation. I think we should refer to taco for the code generation part in tvm, especially for the unified sparse tensor structure. However, we would very likely to support the runtime for cuda, opencl and many other backends, therefore I think it is necessary to implement code generation in tvm.

In my observation, there are two categories of algorithms that extensively use sparse tensor operations to speed up convolution. First, people depends on high sparsity of weight tensor to speed up 2D image convolution, which requires retraining the network weights to increase the sparsity. Second, sparse tensors are used to represent point cloud dataset and its processing steps, where sparse tensors are used to represent features instead of weights in a convolution operator. In many cases, we might need to implement direct sparse convolution as well.

[tqchen]

partly closed by #1289 let us open new thread for further updates