luminal
luminal copied to clipboard
jafioti
Cost model
Hi @jafoti, nice project!
I did something somewhat similar a few years ago in Scala.
I skimmed a little bit through the project, so I only have a superficial understanding.
What I'm wondering is if there is or should be a cost model that guides the optimizations?
From what I see the optimizations are more heuristic based, i.e. if they can be applied, they are.
There might be occasions though, where it makes a difference in which order optimizations are applied, and sometimes it could be even be beneficial to take a longer route with worse intermediate states. Not sure how realistic this is, but one could imagine a case where (A + B) * C could benefit from being expanded into A*C + B*C because A*C and B*C can be reused in another step of the computation.
That was at least the case for me sometimes in my Scala project.
I imagine that by having an explicit cost model, one could apply search algorithms (A*, Genetic Algorithms, Simulated Annealing, ...) to the problem and cover a much wider range of possible solutions than by using heuristics.
Hi Martin,
Yes cost models can certainly make more optimal plans than just heuristics. Long term I'd like to have an RL model take in a hardware representation and predict the op graph. I've found that cost models add a ton of complexity though and clever heuristics can get you 90% of the way there, so for now I don't think cost models are worth working on
Actually I'll leave this issue open for discussion since we'll eventually implement a cost model. Feel free to post thoughts and ideas here