2 ms·
> Place and route is a totally different beast. There is potential for an AlphaGo-like structure to help out here tremendously, where an AI has been trained to
by dragontamer 5y ago
> Place and route is a totally different beast. There is potential for an AlphaGo-like structure to help out here tremendously, where an AI has been trained to produce a cost estimate that aids a decision process and steers the search space.
As far as I can tell, that's just another typical "Damn it, yet ANOTHER NP-complete problem..." that pops up every few minutes when looking through compiler code.
EDIT: Place and route is finite in scope (there's only a finite number of blocks on any FPGA or ASIC design). I haven't though too hard about the problem, but it seems like its similar to knapsack problems. It also seems related to non-NP complete problems like Planar Graphs (https://en.wikipedia.org/wiki/Planar_graph https://en.wikipedia.org/wiki/Planar_graph).
The current state-of-the-art 3SAT solvers are a different branch of AI than deep learning. I'm sure deep learning can have some application somewhere, but... the state of the art is pretty damn good.
There's probably a lot of provably optimal subproblems (ex: Planar) that are simpler than NP-complete. But then the final solution is going to be some complicated beast of a problem that comes down to guess and check (of which, 3SAT solvers are the current state of the art).
- jcranmer 5y agoYour assessment is pretty much correct; it boils down to a constrained optimization problem (a la linear programming or SAT). And this is a family of problem-solving techniques for which we already have decently powerful algorithms. Historically, elements of constrained optimization have been considered AI--most intro to AI courses will probably cover some variant of backtracking solver or various hill-climbing techniques--but it doesn't really mesh with what modern AI tends to focus on. Deep learning isn't likely to provide any wowza-level results in such a space.