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.
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
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.
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":
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?
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.
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.
> 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.
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):
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.
> 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.
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.
I am. Why would you assume otherwise?