4 ms·

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 statica

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.

pstoll 2y ago
> 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.
gaze 2y ago
I am. Why would you assume otherwise?
llm_trw 2y ago
Anyone working on deep learning for one.
- almostgotcaught 2y ago
  if you can explain to me the relevance of this paper for your stack i'll paypal you $50.
  - saagarjha 2y ago
    The people who are in a position to respond to you are also unlikely to be moved by an offer of $50.
saagarjha 2y ago
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.
- almostgotcaught 2y ago
  > 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.pdf#page=18.00 https://llvm.org/devmtg/2018-04/slides/Absar-ScalarEvolution... specifically pages 16-18
  - saagarjha 2y ago
    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?
    - almostgotcaught 2y ago
      > 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_classes https://en.wikipedia.org/wiki/PSPACE#Relation_among_other_cl...
      - saagarjha 2y ago
        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-geometric-sums.html 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.

pstoll 2y ago

> 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.

gaze 2y ago

I am. Why would you assume otherwise?

llm_trw 2y ago

Anyone working on deep learning for one.

almostgotcaught 2y ago
if you can explain to me the relevance of this paper for your stack i'll paypal you $50.
- saagarjha 2y ago
  The people who are in a position to respond to you are also unlikely to be moved by an offer of $50.

saagarjha 2y ago

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.

almostgotcaught 2y ago
> 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.pdf#page=18.00 https://llvm.org/devmtg/2018-04/slides/Absar-ScalarEvolution... specifically pages 16-18
- saagarjha 2y ago
  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?
  - almostgotcaught 2y ago
    > 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_classes https://en.wikipedia.org/wiki/PSPACE#Relation_among_other_cl...
    - saagarjha 2y ago
      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-geometric-sums.html 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.