More sparse format support?

[jermainewang]

Hi Tacoers,

I am from MXNet team. We are working on sparse tensor operation support and we found that your project is really interesting. I really like your idea that can unify all different kinds of sparse formats in one representation. I can see this lays a foundation for easy extension to different sparse formats and even code generation like what you guys try to solve. We've also been discussing about using your representation as our sparse format (https://github.com/apache/incubator-mxnet/pull/7082). Here, we have some questions:

• How do you support coordinate format? In the future work of your paper, you also talked about ellpack and dia format. How are they supported?

• Is there any format that cannot be converted to your representation?

• It seems to me that the representation is a fixed-length vector (depends on the ranks of the tensor). Is there a way to represent arbitrary-rank-tensor?

Look forward to your reply and I'd like to appreciate your cool project once again!

-Minjie

[fredrikbk]

Hi! Great to hear!

We have a new and much improved version of that paper that will appear at OOPSLA (assuming they accept some changes). One of the new things in that paper is parallelism. I'll look into sharing a preprint.

Have you considered using our library in your project instead of re-creating it? For example, @peterahrens in the Julia research group is currently working on building tensor support in Julia on top of taco and we're working on integrating with tensorflow. If you take that route we'd certainly work with you on taco-related problems you encounter. For example, we are considering C (and Python) bindings to make taco easier to use from other languages.

As to your questions:

• We are working on coordinates at the moment, spear-headed by @stephenchouca, and should have a paper describing how this works as well as support in the library in one to three months. The main benefit of coordinates is that you don't have to take the cost to pack tensors if they are already stored in coordinates. @stephenchouca is also working on a plugin system that will make it easier for us to add other formats such as dia and ell, and we know more or less how to do it so this should also eventually get into master.

• Our formats can represent any tensor, so there is in principle no format that cannot be converted to our formats.

• I'm not sure I understand, but we do support tensors of any rank/order. Each mode of the tensor would have separate arrays. Did I misunderstand you?

Finally, a question from me: what are the driving applications that caused you to work on sparse tensor operations in MXNet?

-Fred

[fredrikbk]

I looked through the discussion at https://github.com/apache/incubator-mxnet/pull/7082 and I think I understand now. You can express, at runtime, tensors of any rank/order. For example, a kRowSparseStorage for a 3-order tensor in your notation is [<0, sparse>, <1, dense>, <2, dense>], a 4-order kRowSparseStorage is [<0, sparse>, <1, dense>, <2, dense>, <2, dense>], etc. In our C++ library you can provide these descriptors as dynamic (not fixed size) std::vectors so it's not a compile time thing.

[jermainewang]

CC @tqchen @mli @piiswrong

Thanks for the quick reply! It is great to know that you are looking into DL frameworks. I think the reason why MXNet needs sparse operations is the same as Tensorflow. From my bare understandings, they are quite useful for data pre-processings and result post-processings for speech and NLP tasks. @piiswrong @eric-haibin-lin should know more about this.

I'd love to see using taco as the sparse tensor library in MXNet. I think what we can think about is adding taco's sparse tensor format in DLPack project. This is the proposed tensor data structure and tensor operator interface shared by DL frameworks. Currently, it is only for dense tensors. By adapting to this interface, it will also benefit taco to be adopted by other DL frameworks like Caffe2 and Pytorch.

[eric-haibin-lin]

To add some context, we're using sparse tensor feature in mxnet for machine learning models for search/computational ads/recommender system/factorization machine/nlp problems.

[fredrikbk]

I have made a preprint of the rewritten paper available at http://people.csail.mit.edu/fred/tensor-compiler-preprint.pdf. It is clearer, more complete, and includes parallelism.

[fredrikbk]

@jermainewang @eric-haibin-lin Thanks for the information! We're happy to learn as much as we can about sparse tensor use cases in ml as we're coming from compilers.

There's also documentation for our library on our webpage http://tensor-compiler.org/docs, and a demo if you want to play with it http://tensor-compiler.org/codegen.

[stephenchouca]

As @fredrikbk mentioned, I'm currently working on extending taco to support additional formats like the coordinate format and DIA. It is still very much a work in progress (and unsupported for now), but if you'd like feel free to check out the prototype on this branch and play around with it. (As an example for reference, the following taco tool command generates code that computes the tensor-times-vector operation with an order-3 COO tensor as input and an order-2 COO tensor as output: taco "A(i,j) = B(i,j,k) * c(k)" -f=B:ucq -f=A:uq -c)

[jermainewang]

@stephenchouca that's really cool! Another question from our side, have you guys thought about generating GPU codes?

[fredrikbk]

@jermainewang yes that is something we're interested in. In fact, @Lugatod is looking into generating code for distributed machines/supercomputers and we believe some of those ideas may apply to GPU code generation too.