Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The Tensor Algebra Compiler

tensor-compiler.org

Post reply on HN
Print view View original

21–30 of 37 posts

Re: The Tensor Algebra Compiler

#21

Post by throwaway613834 »

surban wrote: post #18

We did some work on computing derivative expressions (goal is application to deep learning) for such tensor algebras. I was going to release it on arXiv in the next few weeks, but now seems to be a good time. Here you go (preliminary version): https://github.com/surban/TensorAlgDiff/raw/master/elemdiff.... Our system takes a tensor algebra (we call it element-wise defined tensor) and outputs expressions for the deriv…

I'm not sure if this is a sensible question, but what is the use of this compared to (say) an autodiff library like FABAD++ [1]? Is performance the main advantage, or expressive power, or something else?

[1] http://www.fadbad.com/fadbad.html

Re: The Tensor Algebra Compiler

#22

Post by lsorber »

comnetxr wrote: post #16

Often (in the scientific computing communities that I am in) large tensor contractions are done by reshaping tensors into matrices, transposing, and using matrix multiplication. The contraction time can change dramatically based on the order one contracts the tensors and the relative sizes of the tensors. It seems this just uses a large nested for loop - how does this strategy compare to using dedicated matrix multip…

An efficient xgemm kernel is probably faster than the code that taco generates if you don't need to permute your tensor. A contraction like B(i,k) = T(i,j,k) * A(j) would require a permutation of T before you could run the matrix multiplication though, while taco can just keep the data in-place.

Re: The Tensor Algebra Compiler

#23

Post by amelius »

surban wrote: post #18

We did some work on computing derivative expressions (goal is application to deep learning) for such tensor algebras. I was going to release it on arXiv in the next few weeks, but now seems to be a good time. Here you go (preliminary version): https://github.com/surban/TensorAlgDiff/raw/master/elemdiff.... Our system takes a tensor algebra (we call it element-wise defined tensor) and outputs expressions for the deriv…

I'm not getting it. If you have a tensor expression, then differentiation gives you another tensor expression. In principle you can then just feed it through a compiler like taco, right? Or is there some optimization you can do, knowing that you are computing a derivative?

Re: The Tensor Algebra Compiler

#24

Post by surban »

throwaway613834 wrote: post #21
surban wrote: post #18

We did some work on computing derivative expressions (goal is application to deep learning) for such tensor algebras. I was going to release it on arXiv in the next few weeks, but now seems to be a good time. Here you go (preliminary version): https://github.com/surban/TensorAlgDiff/raw/master/elemdiff.... Our system takes a tensor algebra (we call it element-wise defined tensor) and outputs expressions for the deriv…

I'm not sure if this is a sensible question, but what is the use of this compared to (say) an autodiff library like FABAD++ [1]? Is performance the main advantage, or expressive power, or something else? [1] http://www.fadbad.com/fadbad.html

If you use autodiff and don't have an 1:1 relationship between function and argument indices you might have to do atomic sums or locking when computing the derivative because multiple elements of the function derivative correspond to one element of the argument derivative. On a CPU this might be okay but on CUDA GPUs this usually has a performance impact. Thus we transform the derivatives so that we have an explicit expression for each derivative element and thus can use one CUDA thread per derivative element.

Re: The Tensor Algebra Compiler

#25

Post by surban »

amelius wrote: post #23
surban wrote: post #18

We did some work on computing derivative expressions (goal is application to deep learning) for such tensor algebras. I was going to release it on arXiv in the next few weeks, but now seems to be a good time. Here you go (preliminary version): https://github.com/surban/TensorAlgDiff/raw/master/elemdiff.... Our system takes a tensor algebra (we call it element-wise defined tensor) and outputs expressions for the deriv…

I'm not getting it. If you have a tensor expression, then differentiation gives you another tensor expression. In principle you can then just feed it through a compiler like taco, right? Or is there some optimization you can do, knowing that you are computing a derivative?

Yes, but you need to take care of the indices of the arguments when calculating the derivative expression. This is what we do.

For example if you have f_{i,j} = (x_i)^2, then the derivative (of some loss) w.r.t. x will be: dx_i = \sum_j df_{i,j} 2 x_i. The sum is needed because the argument x does not depend on the index j and thus x_i is affected by all j elements of df_{i,j}.

Another example would be: f_i = (x_ii)^2, i.e. taking the squares of the diagonal of the matrix x. Here the derivative is x_{i,j} = kronecker_{i=j} 2 df_i x_ii because off-diagonal elements have zero derivatives.

For such simple expressions it's trivial, but for complex expressions it's error-prone when you do it by hand.

Re: The Tensor Algebra Compiler

#26

Post by fredrikbk »

scottlegrand2 wrote: post #13
110011 wrote: post #12

Earlier quoted context omitted.

Just saw your talk. Man you are one hell of a speaker. Great slides, animations and presentation. I enjoyed it. It seems like a strange thing that no one thought of doing this before! Nice that you identified a cool problem and solved it :)

Not entirely true. Sparse x Dense Matrix is an important component of the DSSTNE deep learning framework: https://github.com/amzn/amazon-dsstne But this library is clearly more thorough.

For sure, as you point out, many such kernels have been written, going at least as far back as 1967.

We believe our contribution is being able to generate kernels for all the expressions.

Thanks for the reference though! We’re trying to learn where sparsity may be important in neural networks.

Re: The Tensor Algebra Compiler

#27

Post by fredrikbk »

110011 wrote: post #12
fredrikbk wrote: post #2

Hi Hacker News! I’m one of the developers. This project was also featured in MIT News yesterday: http://news.mit.edu/2017/faster-big-data-analysis-tensor-alg... The code is available at: https://github.com/tensor-compiler/taco/issues I’m happy to discuss the project and to answer any questions :)

Just saw your talk. Man you are one hell of a speaker. Great slides, animations and presentation. I enjoyed it. It seems like a strange thing that no one thought of doing this before! Nice that you identified a cool problem and solved it :)

Thanks, that is really nice of you :)

Re: The Tensor Algebra Compiler

#28

Post by fredrikbk »

amelius wrote: post #20
fredrikbk wrote: post #2

Hi Hacker News! I’m one of the developers. This project was also featured in MIT News yesterday: http://news.mit.edu/2017/faster-big-data-analysis-tensor-alg... The code is available at: https://github.com/tensor-compiler/taco/issues I’m happy to discuss the project and to answer any questions :)

Hi, I just saw the presentation too, and it looks impressive. I'm hoping that you can (at some point) write a language-agnostic library, so that your work can be used in many other development tools (which are not using C++). I suppose it would amount to publishing the documentation of the intermediate code you are already using. This would also save you the trouble of writing and maintaining a GPU back-end because o…

That is a good idea, but we are only so many. One student in the Julia group is developing Julia bindings though, and we hope to make C/python bindings. The inner workings are published in the paper “The Tensor Algebra Compiler”, so it can be implemented in other languages. We like the idea of bindings because then our future work can benefit more users.

Re: The Tensor Algebra Compiler

#29

Post by gugagore »

Conventional wisdom has that dense matrix-matrix multiply is generally faster if you use some cache-aware scheme instead of the textbook 3 nested for loops.

Is there a similar story for sparse matrices ever?

Re: The Tensor Algebra Compiler

#30

Post by fredrikbk »

mattnewton wrote: post #17
fredrikbk wrote: post #2

Hi Hacker News! I’m one of the developers. This project was also featured in MIT News yesterday: http://news.mit.edu/2017/faster-big-data-analysis-tensor-alg... The code is available at: https://github.com/tensor-compiler/taco/issues I’m happy to discuss the project and to answer any questions :)

Skimming it quickly I didn’t see anything about gpu or vector instruction support as compilation targets. Is this planned? Did I miss something and this is at a higher layer? Ps: excellent name

We currently compile to C code and use the system Compiler to compile it further. For dense loop nests it does a good job of auto-vectorizing, but we believe there’s good opportunities for doing something custom, knowing the high-level algebraic structure.

taco does not target GPUs yet, and we want to work on it this spring. It’s clearly needed, for example for neural networks

Post reply on HN