4 ms·

In the case of Lisp and Smalltalk and other highly dynamic languages, would these on-die FPGAs open new compiler optimisation opportunities?

yvdriess 9y ago
The common sentiment after the 90's is that it's hard to beat optimized x86 implementation of both. Maybe non-offloading FPGA-CPU hardware has the potential of accelerating certain language features (e.g. burn in the CLOS method lookup cache?)
simias 9y ago
The problem is that tailor-made FPGA designs won't run nearly as fast as a modern ASIC CPU. That's why for instance FPGA emulators are not more common, for older hardware software implementations are accurate enough and manage to run in realtime so the additional cost and complexity of FPGAs is not warranted. For more modern hardware software implementations can't reach absolute accuracy in real time but FPGAs big and fast enough to handle these designs are prohibitively expensive (if they even exist in the first place). That's why FPGA GameBoy emulators are not popular and you probably won't see a FPGA PS3 emulator any time soon (unless the pricing changes dramatically in the near future). FPGAs shine when you need to process very high throughput data with low (or at least constant) latency or for special-purpose algorithm with no hardware acceleration available on CPU or GPU (video codecs, crypto, computer vision etc...). But in general when an algorithm becomes popular enough (AES, SHA-256, H264...) hardware support is backed into the ASIC eventually with much better performance and power consumption than a FPGA. I see a potential for FPGAs in CPUs for professional applications if you want to process big datastream without having to rely on external hardware. For instance I work in broadcast video transmission where we routinely handle uncompressed HD or even 4K streams, being able to prototype directly on my workstation's CPU would be pretty cool. As for general purpose programing language optimization I have a hard time imagining what it would look like. The problem is that you don't code for a FPGA the way you code for a CPU. To put it very simply on the CPU serial is cheap while forking and synchronizing threads is expensive. On an FPGA it's basically the other way around. Automatically transforming one form into the other automatically in a compiler or JIT sounds very much non-trivial. Maybe I just don't have enough imagination.
- Boothroid 9y ago
  I'm kind of fascinated by any type of accelerator chip for some reason - I think it has something to do with the design of the computers I had when I was a kid i.e. Spectrum, Amiga etc which had dedicated chips for particular facets of the functioning that became iconic. I would love to do something with FPGAs and am certain their potential is massive, but struggle to come up with a use case that seems in any way novel, and I don't really want to just build my own VGA controller, get bored, and stop there!
- AriaMinaei 9y ago
  I remember a talk by Alan Kay where he mentioned a number of problems commonly solved serially, such as 2D layout and typesetting, and then he demonstrated a parallel algorithm for each problem. If I remember and understand correctly (I may not), one of his points was that such algorithms can become trivially implementable in a dynamic language and would run fast too, if the hardware supported some of the primitives of that dynamic language natively. He expressed hope that FPGAs may create such an opportunity.
  - selimthegrim 9y ago
    Do you remember the title or have a link?
    - morphle 9y ago
      Alan Kay gave a talk at Qualcomm in San Diego, on October 30, 2013. "Is it really complex or did we just make it complicated?" https://vimeo.com/82301919 https://vimeo.com/82301919
      - AriaMinaei 9y ago
        Was just going to post that link. It's a very nice talk. Highly recommended!
jecel 9y ago
I have worked on this in the case of Smalltalk and the opportunities are there but there are significant problems. The opportunity is in the form of adaptive compilation where you initially use a simple compiler (or even an interpreter for the very first execution) and then collect profiling information and call a much better compiler to generate code for the "hot spots". A key optimization is inlining which greatly increases the size of a basic block. You could add a third step for the really, really hot spots and compile to hardware. With commercial FPGAs you have a problem that you can't generate the bits yourself but have to use the vendor tools. These are pretty simplistic and will take minutes or hours to compile non trivial circuits. What I mean by this is that they flatten the netlist at some point so compilation time grows non linearly with circuit size. So if your design has five identical blocks, adding a sixth might make it take twice as long to compile. A second problem is that it takes a while to load the bits into the FPGA. The old XC6000 could be accessed as RAM and quickly rewritten but all other models serially shift in the configuration bits. Xilinx allows partial reconfiguration where you can load the bits to one part of the FPGA while the rest continues to work but that is pretty hard to use and the competitors don't even offer this option.
- AriaMinaei 9y ago
  This was very interesting, thank you! I'm sure I missed something in your first paragraph though, because the process that you described sounds very much like a normal modern JIT compiler. In V8 and SpiderMonkey for example, the engine starts with the first tier, which is a baseline interpreter that collects type information on each function call, and then if a function is invoked enough times, it compiles the function to machine code using the type information collected in the first tier. There are more tiers up the chain, slower to compile and faster to run, where dataflow analysis is done on the hottest functions, which get optimisations such as inline caching, etc. All that is done on the CPU of course, so I'm curious how an FPGA could help in this process?
  - jecel 9y ago
    JIT is a generic term that applies both to dynamic compilation (one pass) and adaptive compilation (multiple passes with profiling). While it is pretty normal these days, many people involved in FPGA research only know about static languages and manual partitioning (like OpenCL) and that is why I always explain what it is. FPGAs don't help JITs at all. I was saying the opposite: if certain problems (slow compilation and slow reconfiguration) could be solved then JITs could offer the opportunity to generate hardware acceleration on demand that would be tuned for a specific execution of an application.

yvdriess 9y ago

The common sentiment after the 90's is that it's hard to beat optimized x86 implementation of both. Maybe non-offloading FPGA-CPU hardware has the potential of accelerating certain language features (e.g. burn in the CLOS method lookup cache?)

simias 9y ago

The problem is that tailor-made FPGA designs won't run nearly as fast as a modern ASIC CPU. That's why for instance FPGA emulators are not more common, for older hardware software implementations are accurate enough and manage to run in realtime so the additional cost and complexity of FPGAs is not warranted. For more modern hardware software implementations can't reach absolute accuracy in real time but FPGAs big and fast enough to handle these designs are prohibitively expensive (if they even exist in the first place). That's why FPGA GameBoy emulators are not popular and you probably won't see a FPGA PS3 emulator any time soon (unless the pricing changes dramatically in the near future). FPGAs shine when you need to process very high throughput data with low (or at least constant) latency or for special-purpose algorithm with no hardware acceleration available on CPU or GPU (video codecs, crypto, computer vision etc...). But in general when an algorithm becomes popular enough (AES, SHA-256, H264...) hardware support is backed into the ASIC eventually with much better performance and power consumption than a FPGA. I see a potential for FPGAs in CPUs for professional applications if you want to process big datastream without having to rely on external hardware. For instance I work in broadcast video transmission where we routinely handle uncompressed HD or even 4K streams, being able to prototype directly on my workstation's CPU would be pretty cool. As for general purpose programing language optimization I have a hard time imagining what it would look like. The problem is that you don't code for a FPGA the way you code for a CPU. To put it very simply on the CPU serial is cheap while forking and synchronizing threads is expensive. On an FPGA it's basically the other way around. Automatically transforming one form into the other automatically in a compiler or JIT sounds very much non-trivial. Maybe I just don't have enough imagination.

Boothroid 9y ago
I'm kind of fascinated by any type of accelerator chip for some reason - I think it has something to do with the design of the computers I had when I was a kid i.e. Spectrum, Amiga etc which had dedicated chips for particular facets of the functioning that became iconic. I would love to do something with FPGAs and am certain their potential is massive, but struggle to come up with a use case that seems in any way novel, and I don't really want to just build my own VGA controller, get bored, and stop there!
AriaMinaei 9y ago
I remember a talk by Alan Kay where he mentioned a number of problems commonly solved serially, such as 2D layout and typesetting, and then he demonstrated a parallel algorithm for each problem. If I remember and understand correctly (I may not), one of his points was that such algorithms can become trivially implementable in a dynamic language and would run fast too, if the hardware supported some of the primitives of that dynamic language natively. He expressed hope that FPGAs may create such an opportunity.
- selimthegrim 9y ago
  Do you remember the title or have a link?
  - morphle 9y ago
    Alan Kay gave a talk at Qualcomm in San Diego, on October 30, 2013. "Is it really complex or did we just make it complicated?" https://vimeo.com/82301919 https://vimeo.com/82301919
    - AriaMinaei 9y ago
      Was just going to post that link. It's a very nice talk. Highly recommended!

jecel 9y ago

I have worked on this in the case of Smalltalk and the opportunities are there but there are significant problems. The opportunity is in the form of adaptive compilation where you initially use a simple compiler (or even an interpreter for the very first execution) and then collect profiling information and call a much better compiler to generate code for the "hot spots". A key optimization is inlining which greatly increases the size of a basic block. You could add a third step for the really, really hot spots and compile to hardware. With commercial FPGAs you have a problem that you can't generate the bits yourself but have to use the vendor tools. These are pretty simplistic and will take minutes or hours to compile non trivial circuits. What I mean by this is that they flatten the netlist at some point so compilation time grows non linearly with circuit size. So if your design has five identical blocks, adding a sixth might make it take twice as long to compile. A second problem is that it takes a while to load the bits into the FPGA. The old XC6000 could be accessed as RAM and quickly rewritten but all other models serially shift in the configuration bits. Xilinx allows partial reconfiguration where you can load the bits to one part of the FPGA while the rest continues to work but that is pretty hard to use and the competitors don't even offer this option.

AriaMinaei 9y ago
This was very interesting, thank you! I'm sure I missed something in your first paragraph though, because the process that you described sounds very much like a normal modern JIT compiler. In V8 and SpiderMonkey for example, the engine starts with the first tier, which is a baseline interpreter that collects type information on each function call, and then if a function is invoked enough times, it compiles the function to machine code using the type information collected in the first tier. There are more tiers up the chain, slower to compile and faster to run, where dataflow analysis is done on the hottest functions, which get optimisations such as inline caching, etc. All that is done on the CPU of course, so I'm curious how an FPGA could help in this process?
- jecel 9y ago
  JIT is a generic term that applies both to dynamic compilation (one pass) and adaptive compilation (multiple passes with profiling). While it is pretty normal these days, many people involved in FPGA research only know about static languages and manual partitioning (like OpenCL) and that is why I always explain what it is. FPGAs don't help JITs at all. I was saying the opposite: if certain problems (slow compilation and slow reconfiguration) could be solved then JITs could offer the opportunity to generate hardware acceleration on demand that would be tuned for a specific execution of an application.