Tensor evolution: A framework for fast tensor computations using recurrences | Hacker News Reader

Tensor evolution: A framework for fast tensor computations using recurrences

arxiv.org

53 pointsmatt_d18 comments

> Tensor Evolution (TeV)

Oh no, I'm never not going to read this as "tera-electron Volts". I wish they picked a different acronym!

This is neat! I've been thinking about how to best express recursion with diagrams for tensorgrad (https://github.com/thomasahle/tensorgrad) and this might just be it.

So much computation these days are done on tensors, mostly for easy parallelism reasons. But we can't get completely rid of recursion. Great to have work like this making them more computationally compatible!

I don't see a lot of use for this since it only extends element-wise operations and not things like multiplication which are the more interesting operations on tensors. Yeah you can model tensors in the compiler with this but no loops in the compiler are actually doing this. Unlike SCEV which is used for almost every loop.

> not things like multiplication

in order to perform that kind of canonicalization/folding/cse you effectively need to embed a whole-ass tensor ops interpreter into your compiler. note this isn't so far-fetched

https://github.com/openxla/stablehlo/blob/main/docs/interpre...

the problem is it needs to be performant as well. so what some people do is jit these canonicalizations using the compiler (yo dawg i heard you like compiling...).

lol who is interested in this on hn? this has nothing to do with frameworks or training or inference or whatever. this is purely about "when can i infer statically XYZ property about tensor constants in a program". mind you, small tensor constants, because this thing is effectively performing actual tensor arithmetic and you don't want slow tensor arithmetic in your compiler.

also FYI they're not magically calculating closed form solutions to recurrence relations here (that's not possible) - they're basically just iterating the loop arithmetic.

> lol who is interested in this on hn?

I’m guessing lots of people who are on HN. I’ll go with - me for one. Guessing I’m not alone.

Remember - it’s a big world. Lots of POVs.

I am. Why would you assume otherwise?

Anyone working on deep learning for one.

if you can explain to me the relevance of this paper for your stack i'll paypal you $50.

The people who are in a position to respond to you are also unlikely to be moved by an offer of $50.

This kind of thing is quite useful for people implementing block-level compilers; in particular spending time on optimizations for “small” tensors that are being operated on in a block are very worthwhile because the generated code is then reused across all blocks and multiple invocations of the kernel.

For this case, you can actually calculate a closed form for many recurrences, in the same way that SCEV works. You don’t need to interpret the loop to do this. If you mark your induction variables and put the loop in the right form then it’s possible to do recurrence analysis in constant time. This isn’t particularly complex or novel (and, to be fair, the paper doesn’t do much other than go “hmm what if we did this for tensors”) so I suggest you look up how it’s done in traditional compilers.

> closed form for many recurrences, in the same way that SCEV works ... so I suggest you look up how it’s done in traditional compilers.

SCEV does not compute closed forms ... because that's impossible. if you don't understand why it's impossible you can consult this same team's slides on SCEV in LLVM, a "traditional compiler":

https://llvm.org/devmtg/2018-04/slides/Absar-ScalarEvolution...

specifically pages 16-18

I feel like we must be talking about different things, because I don't see how any of this follows, and the slides just seem to explain how LLVM does its SCEV? Consider the following program (in C and not LLVM IR because I am very lazy):

  int foo = 0;
  for (int i = 0; i < n; ++i) {
   foo += 1;
  }

Both foo and i have an addrec of {0, +, 1}. Given the loop iteration count n it is pretty clear that you can calculate the value at exit to be n without actually running the loop n times. In fact you don't even know n and can still convert it to a closed form at compile time. So what's the point of disagreement here?

> In fact you don't even know n and can still convert it to a closed form at compile time.

1. you have to prove monotonicity to make the inference you're implying is "pretty clear". recall that "prove" really does mean prove in compilers

2. even if you did prove motonicity, it's the simplest category of loop body behavior. recall control flow.

> without actually running the loop n times

this is not possible without an oracle because PSPACE \subseteq EXPTIME

https://en.wikipedia.org/wiki/PSPACE#Relation_among_other_cl...

Put the theory aside and look at the loop I showed you. Surely you can see that its CFG is trivial? You can track all the variables across the basic block and it's really easy to prove (yes, prove) what I claimed. And compilers can of course do more advanced forms of this, here are some more examples: https://kristerw.blogspot.com/2019/04/how-llvm-optimizes-geo.... I'm confused why you think this is hard because major compilers have been doing it for decades now. I assure you they can do this efficiently.

I feel like you have poor reading comprehension. I literally said yes for simple cases it works.

> https://kristerw.blogspot.com/2019/04/how-llvm-optimizes-geo...

Literally not a single loop on that page has a conditional in it. They're all the same stupid "polynomial" example. Hint: how often do you think people are trying to optimize loops that compute polynomials....

> I assure you they can do this efficiently.

It's amazing you think your assurances mean anything. So let me assure you: I know exactly what I'm talking about. In the last month I landed basically SCEV in a production compiler. Except since our programs are real and not just goofy polynomial examples, my SCEV is actually an abstract interpreter.

Uh, no? You literally said “that’s not possible” and then “that’s impossible”, then as I repeatedly showed you SCEV can actually be used to solve recurrences you retreated to “uh but you have to prove they’re monotonic” (which is easy) and now we’re at “lol your examples are simple and easy, not like the real world problems I, the compiler expert™, deal with every day”.

Now, I will admit I don’t work on compilers like you do. But I have a great respect for them, as I work adjacent to them and have done so for each of the career switches I’ve done, and all of those have been far more different from each other than they were from your field. So I think you being smug about your day job doing like “halp my kernel no hit roofline bandwidth pls fix” support or whatever your employer has you do is actually incredibly rude and uncalled for. You can express your views like a normal person without assuming everyone else you talk to is an idiot with no knowledge of how compilers work. I honestly feel like you started down this path at the very start of this thread where assumed everyone here is like “wow AI cool” and when I actually tried to engage with you on something you tried to show you had some knowledge on and you continued to do this so now I’m really just upset because you were deeply unpleasant while I got nothing out of this.

> then as I repeatedly showed you SCEV can actually be used to solve recurrences you retreated to “uh but you have to prove they’re monotonic” (which is easy) and now we’re at “lol your examples are simple and easy, not like the real world problems I, the compiler expert™, deal with every day”.

friend we're not here now, we were here the entire time; in my literal first comment:

> they're basically just iterating the loop arithmetic.

then in my second response to you, in crystal clear, bulleted text:

> 2. even if you did prove motonicity, it's the simplest category of loop body behavior. recall control flow.

do you understand "if X then Y"? so again, i believe this is simply an issue of reading comprehension.

> “halp my kernel no hit roofline bandwidth pls fix” support or whatever your employer has you do

lol my guy - people that implement things like SCEV are not doing customer support. to wit: i know javed personally and my employer pays me to do literally the same exact things he does. but nice try trying to throw shade based on a weird misinformed notion of what compiler work is like.

> I’m really just upset because you were deeply unpleasant while I got nothing out of this.

well you could've gotten something out of it but you certainly worked really hard to insist on your misinformed notions so i guess i'm not surprised? but i'm definitely "sorry not sorry" because i definitely tried to explain something to you.

Reply on news.ycombinator.com