4 ms·

Extracting enough fine grain parallelism is hard. Manually creating it is tedious and difficult. Memory is slow. Latency hiding is hard. Ahead-of-time speculati

Extracting enough fine grain parallelism is hard. Manually creating it is tedious and difficult. Memory is slow. Latency hiding is hard. Ahead-of-time speculation is hard. Runtime speculation is hard. Good luck.

georgeecollins 5y ago
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
Your comment is very high quality, despite being short. > Extracting enough fine grain parallelism is hard. Manually creating it is tedious and difficult. A big win for NVidia was tricking enough programmers into manually describing large swaths of parallelism available for a GPU to take advantage of. Manually creating fine grained parallelism through classical structures (mutex, semaphores, async, etc. etc.) is tedious and probably counterproductive. But it seems like describing __some__ extremely common forms of parallelism is in fact very useful in certain applications (matrix multiplications). OpenMP, CUDA, OpenCL, (and even Fortran/Matlab to some extent)... even Tensorflow... are showing easy ways to describe a parallel problem. CPUs seem to be the best architecture at discovering latent parallelism in general purpose code that the original programmer wasn't aware of. (Typical programmers are not aware of the multiple-pipelines that a modern CPU tries to fill up... and yet that code continues to accelerate from generation-to-generation... now with Apple's M1 proving that even 8-way decode is reasonable and provides performance gains). CPU designers seem to be experts at finding fine-grain parallelism as it is, and I don't think anyone can beat them at it. (Only another CPU designer will probably make something better). --------- But for these alternative compute paradigms: such as GPU-compute, there are far fewer programmers and compiler experts working on that architecture. Its far easier to find little gold-nuggets here and there that lead to improved execution. SIMD-languages such as C-Star, Lisp-Star, CUDA, OpenCL, OpenMP... have been describing parallel patterns for decades now. And yet, it only feels like we've begun to scratch that surface.

georgeecollins 5y ago

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

Your comment is very high quality, despite being short. > Extracting enough fine grain parallelism is hard. Manually creating it is tedious and difficult. A big win for NVidia was tricking enough programmers into manually describing large swaths of parallelism available for a GPU to take advantage of. Manually creating fine grained parallelism through classical structures (mutex, semaphores, async, etc. etc.) is tedious and probably counterproductive. But it seems like describing __some__ extremely common forms of parallelism is in fact very useful in certain applications (matrix multiplications). OpenMP, CUDA, OpenCL, (and even Fortran/Matlab to some extent)... even Tensorflow... are showing easy ways to describe a parallel problem. CPUs seem to be the best architecture at discovering latent parallelism in general purpose code that the original programmer wasn't aware of. (Typical programmers are not aware of the multiple-pipelines that a modern CPU tries to fill up... and yet that code continues to accelerate from generation-to-generation... now with Apple's M1 proving that even 8-way decode is reasonable and provides performance gains). CPU designers seem to be experts at finding fine-grain parallelism as it is, and I don't think anyone can beat them at it. (Only another CPU designer will probably make something better). --------- But for these alternative compute paradigms: such as GPU-compute, there are far fewer programmers and compiler experts working on that architecture. Its far easier to find little gold-nuggets here and there that lead to improved execution. SIMD-languages such as C-Star, Lisp-Star, CUDA, OpenCL, OpenMP... have been describing parallel patterns for decades now. And yet, it only feels like we've begun to scratch that surface.