the proliferation of JIT compilation technique in many fields of application, makes me wondering if there is some way to accelerate compilation tasks by dedicated hardware. This is only a first thinking about the topic, I can’t find too much literature on it.
Hardware acceleration fundamentally means:
a. Parallelize tasks as much as possible (more than multi-core)
b. Synthesize specific operators to speed-up computations (like matrix multiplication, for instance)
c. Minimize data transit between processing units and storage units
In this post, I will talk about point a. only.
Let’s see how basic compilation phases can be improved by HW parallelism.
Lexical analysis is based on the finite state machine model, that works on a strictly serial execution.
But many languages allow multiple rules being partially matched by one string; so, if rule-set can be modeled by an NDA (non-deterministic automata) we can think to associate one HW state machine for each rule.
Again, many languages allow partitioning of source code in a set of class/functions so that we can think to analyze multiple pieces of code on multiple pieces of HW.
The same is possible when code is partitioned in multiple files.
Parsing of CFGs is based on the model of a state machine plus a stack. Also in this case, many languages allows multiple rule to be partially matched, so we can associate one
piece of hardware to one parsing rule and running them in parallel. Stack’s depth is a critical point in designing such a hardware.
Introducing parallelism in this task is really complex, in my first level of analysis.
Searching a key in a lookup table is highly parallelizable.
In type check of binary expressions, left and right sub-trees can be analyzed in parallel.
One can think to partial parallel emission of single function/class, and merging everything at the end
If the final code is expressed in terms of data-flow, there are many algorithms to synthesize code on a parallel hardware
The first comment is that compiling into the hardware is really challenging !!
Any further comment/feedback is welcome.