Logarithmic-Time FPGA Bitstream Analysis

Just-In-Time (JIT) compilation is frequently used in software engineering to accelerate program execution. Parts of the code are translated to machine code at runtime to speedup their execution by exploiting local and dynamic information of the computation. Modern FPGAs manufactured by Xilinx allow partial and dynamic configuration. Such features make them eligible platforms for JIT hardware compilation. Nevertheless, this has not been achieved until now because the mapping between a bitstream and the programmable points inside these FPGAs is not documented. In this article, we propose a methodology to retrieve the relevant information in logarithmic time per bit by methodically using the tools distributed by Xilinx. We give a practical case study which details the analysis of a Virtex-II Pro FPGA bitstream. The mapping of CLBs, BRAMs, and multipliers has been fully determined. Thanks to this information, we have been able to prototype tools in the fields of reverse mapping FPGA bitstreams, low-level simulation, and custom place-and-route. Finally preliminary results demonstrate that a processor embedded in an FPGA can compile, place, and route arithmetic and logic expressions inside the FPGA within a few milliseconds.