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

Show HN: Luminal – Open-source, search-based GPU compiler

github.com

Post reply on HN
Print view View original

31–40 of 70 posts

Re: Show HN: Luminal – Open-source, search-based GPU compiler

#31

Post by helltone »

jafioti wrote: post #29
helltone wrote: post #28

I have a background in program analysis, but I'm less familiar with the kind of kernels you are optimising. - Can you give some more insight on why 12 ops suffice for representing your input program? - With such a small number of ops, isn't your search space full of repeat patterns? I understand the will to have no predefined heuristics, but it seems that learning some heuristics/patterns would massively help reduce…

we're just optimizing linear algebra, which is mostly made up of patterns of simple ops. for instance, matmul is just broadcasted multiply -> sum reduce. the search does common subexpression elimination by default. if two patterns are unioned in the search space, it applies that union to every occurrence of that pattern at the same time, so using e-graphs it helps keep the search space smaller.

Right I think I see it.

This is insanely cool.

But then there are performance tradeoffs in reusing intermediates vs recomputing that I think you can't represent.

Some of these may affect numerical stability btw. See eg https://herbie.uwplse.org/

There is so much potential in this project.

Re: Show HN: Luminal – Open-source, search-based GPU compiler

#33

Post by matthewjgunton »

fancyfredbot wrote: post #32

This is a good idea. Do you use a cost model for the search or are you actually executing kernels? What kind of heuristics do you use to avoid search space becoming intractabl

our cost function right now is just the latency of the kernel. we execute on the hardware as is it really the only accurate way to see how fast the kernel will run

Re: Show HN: Luminal – Open-source, search-based GPU compiler

#35

Post by pilooch »

jakestevens2 wrote: post #14
Alifatisk wrote: post #11

So wait, am I understanding this correctly? Instead of applying just predetermined optimization rules or patterns, the compiler formulates the problem as searching through many possible configurations or versions of the code. Each possible version can have different arrangements, tiling sizes, thread block configurations, memory access patterns, and instruction sequences, right? And from my understanding, the “search…

Your description is exactly right. We create a search space of all possible kernels and find the best ones based on runtime. The best heuristic is no heuristic. This obviously creates a combinatorial problem that we mitigate with smarter search. The kernels are run on the computer the compiler is running on. Since runtime is our gold standard it will search for the best configuration for your hardware target. As long…

Is this a bit similar to what tensorrt does, but in a more opened manner ?

Re: Show HN: Luminal – Open-source, search-based GPU compiler

#37

Post by jafioti »

GregarianChild wrote: post #36

How is this different from superoptimisation? Also, how do you ensure that newly generated kernels are correct w.r.t. the original naive kernel that you use as specification?

very similar to superoptimisation, but most superoptimisers try to tackle turing-complete code. by just doing a very limited space of computation (linear algebra with 12 primitive ops) the search remains tractable.

the search space is designed to remain logically equivalent at all times, by virtue of how its built (applying rewrite rules we know dont change the logical equivalence).

Re: Show HN: Luminal – Open-source, search-based GPU compiler

#38

Post by jafioti »

helltone wrote: post #31
jafioti wrote: post #29

Earlier quoted context omitted.

we're just optimizing linear algebra, which is mostly made up of patterns of simple ops. for instance, matmul is just broadcasted multiply -> sum reduce. the search does common subexpression elimination by default. if two patterns are unioned in the search space, it applies that union to every occurrence of that pattern at the same time, so using e-graphs it helps keep the search space smaller.

Right I think I see it. This is insanely cool. But then there are performance tradeoffs in reusing intermediates vs recomputing that I think you can't represent. Some of these may affect numerical stability btw. See eg https://herbie.uwplse.org/ There is so much potential in this project.

ah i see the confusion. we do common subexpression elimination of the terms in the search space (which allows single application of rewrites to apply to many repeat patterns) but the search can choose to re-use patterns of terms when we extract dags after the search space is built. so various levels of recomputation are searched.

right now since we're profiling kernels, and we have a reference output of the unoptimised version, we can directly measure deviation of profiled outputs "for free" since we're already computing them for runtime. tbh this isn't what i want long term, i want to bake numerical stability natively into the search space to only extract dags that would produce stable outputs. hopefully that'll be solved soon.

Re: Show HN: Luminal – Open-source, search-based GPU compiler

#39

Post by jafioti »

fancyfredbot wrote: post #32

This is a good idea. Do you use a cost model for the search or are you actually executing kernels? What kind of heuristics do you use to avoid search space becoming intractabl

we're working on techniques like mcts and RL (e.g. AlphaGo) to manage the search space, but you'd be suprised how far you can get if you carefully design the search space to prevent explosions.

Re: Show HN: Luminal – Open-source, search-based GPU compiler

#40

Post by jafioti »

PoignardAzur wrote: post #30
sakras wrote: post #24

I see you guys are using Egg/Egglog! I've been mildly interested in egraphs for quite a while, glad to see they're gaining traction!

Right, my first thought when reading the blurb was "kinda sounds like e-graphs?"

e-graphs are awesome! none of this would be possible without them.
Post reply on HN