3 ms·

> If you're going down into FPGA routing, then maybe we also call that synthesis (slightly different than compilers, but very very similar in problem scope).

> If you're going down into FPGA routing, then maybe we also call that synthesis (slightly different than compilers, but very very similar in problem scope). Synthesis is the process of taking constructs in a high-level language (SystemVerilog, VHDL, etc) and translating the code into the primitives provided by the target architecture (LUT, blockram, DSP, distributed RAM, muxes, etc). I agree that this looks like an ordinary compiler pipeline. 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.

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

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