4 ms·

Everything you are saying makes good sense, but I wanted to ask: Is taking a computer program and then re-configuring for some exotic and complex CPU a great pr

Everything you are saying makes good sense, but I wanted to ask: Is taking a computer program and then re-configuring for some exotic and complex CPU a great problem for AI? I bet people on this forum know why that is / isn't true and I am curious.

dragontamer 5y ago
If you consider "compiler theory" an AI problem, then sure. But most of us just call that compiler theory. 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). Today's compilers have an idea of how modern CPUs execute instructions, and optimize accordingly. (Intel's ICC compiler is pretty famous for doing this specifically for Intel chips). Any FPGA synthesis will similarly be written to optimize for resources on the FPGA. ------------ EDIT: Just so that you know... compiler theory and optimization is largely the study of graphs turning into other, provably equivalent but more efficient, graphs. All computer programs can be described as a graph traversal. Reconfiguring the graph to be shorter / smaller / more parallel (more instruction-level parallelism for the CPU to discover), etc. etc. leads to faster execution. You don't really need deep-learning or an AI to do a lot of these graph operations. There's a few NP-complete problems (knapsack problem: minimizing memory moves by optimizing register allocation) along the way that maybe an AI could try to solve. But I have my doubts that throwing a deep-learning AI at NP complete problems is the best strategy (especially given the strength of modern 3SAT solvers)
- gopalv 5y ago
  > You don't really need deep-learning or an AI to do a lot of these graph operations. That is right, but we're probably not hunting for absolutely optimal solutions every time. It usually boils down to heuristics - everytime there's a graph reorganization problem where a sub-optimal, but better solution is viable, the solutions always involve short-cuts derived from the domain knowledge in there. This is usually very similar to the AI training operations where there's a guess from an engineer, experiments to validate and modify the heuristic guess to improve the results - finally to give up when the results look acceptable. AIs would do well at parameter tuning, at the very least. My register allocation work would have near infinite loops reordering priorities, until I started forcing invariants into the system which didn't exist in the original design. And the usual arguments about "code is compiled once, executed millions of times" doesn't quite apply to a JIT.
- brandmeyer 5y ago
  > 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

If you consider "compiler theory" an AI problem, then sure. But most of us just call that compiler theory. 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). Today's compilers have an idea of how modern CPUs execute instructions, and optimize accordingly. (Intel's ICC compiler is pretty famous for doing this specifically for Intel chips). Any FPGA synthesis will similarly be written to optimize for resources on the FPGA. ------------ EDIT: Just so that you know... compiler theory and optimization is largely the study of graphs turning into other, provably equivalent but more efficient, graphs. All computer programs can be described as a graph traversal. Reconfiguring the graph to be shorter / smaller / more parallel (more instruction-level parallelism for the CPU to discover), etc. etc. leads to faster execution. You don't really need deep-learning or an AI to do a lot of these graph operations. There's a few NP-complete problems (knapsack problem: minimizing memory moves by optimizing register allocation) along the way that maybe an AI could try to solve. But I have my doubts that throwing a deep-learning AI at NP complete problems is the best strategy (especially given the strength of modern 3SAT solvers)

gopalv 5y ago
> You don't really need deep-learning or an AI to do a lot of these graph operations. That is right, but we're probably not hunting for absolutely optimal solutions every time. It usually boils down to heuristics - everytime there's a graph reorganization problem where a sub-optimal, but better solution is viable, the solutions always involve short-cuts derived from the domain knowledge in there. This is usually very similar to the AI training operations where there's a guess from an engineer, experiments to validate and modify the heuristic guess to improve the results - finally to give up when the results look acceptable. AIs would do well at parameter tuning, at the very least. My register allocation work would have near infinite loops reordering priorities, until I started forcing invariants into the system which didn't exist in the original design. And the usual arguments about "code is compiled once, executed millions of times" doesn't quite apply to a JIT.
brandmeyer 5y ago
> 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.