Fast and Flexible CAD for FPGAs and Timing Analysis

Field Programmable Gate Arrays (FPGAs) are a widely used platform for hardware acceleration and digital systems design, which offer high performance and power efficiency while remaining reprogrammable. However a major challenge to using FPGAs is the complex Computer Aided Design (CAD) flow required to program them, which makes FPGAs difficult and time-consuming to use. This thesis investigates techniques to address these challenges. A key component of the CAD flow is timing analysis, which is used to verify correctness and drive optimizations. Since the dominant form of timing analysis, Static Timing Analysis (STA), is time consuming to perform, we investigate methods to efficiently perform STA in parallel. We then develop Extended Static Timing Analysis (ESTA), which performs a more detailed and less pessimistic form of timing analysis by accounting for the probability of signal transitions. We next study a variety of enhancements to the FPGA physical design flow, including to key optimization stages like packing, placement and routing. These techniques are combined in the open-source VTR 8 design flow, and significantly outperform previous methods. We also develop advanced architecture modelling capabilities which allow VTR 8 to target a wider range of FPGA architectures. These enhancements allow FPGA architects more fine grained control of the targeted FPGA architecture, enabling more in depth study of key architectural features such as the routing network. Additionally, we show how these enhancements enable the VPR placement and routing tool within VTR to target commercial FPGAs as part of a fully open-source design flow. Finally, we study how Reinforcement Learning (RL) can be used to learn new effective heuristics for use in CAD algorithms, and show how this can be used to improve the run-time quality trade-off of an FPGA placement algorithm.Ph.D