jafioti
commented
4 months ago 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
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) * Ccould benefit from being expanded intoA*C + B*CbecauseA*CandB*Ccan 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.