Fast CAD for FPGAs

As field-programmable gate array (FPGA) capacities continue to increase in lockstep with semiconductor process shrinking, they are being used for increasingly complex applications. However, because FPGAs are bit-level programmable, the task of generating an FPGA implementation from a user's application description is quite complicated. The CAD tools responsible for this are long-running, taking up to a day to generate an FPGA implementation for the largest applications. This thesis presents several approaches to speed-up FPGA CAD tools.The first proposed approach is to parallelize routing, one of the longest running FPGA CAD steps. The second approach is to modify the FPGA architecture such that a coarsened graph representation can be used during the routing stage, which reduces run-time. This approach involves both architectural and algorithmic changes.Next, a fast analytical technique is proposed for the placement stage, another of the longest-running CAD phases. Following that, this thesis proposes that a library of pre-compiled solutions to commonly occurring application fragments be maintained and re-used when possible. Re-using these application fragments leads to a reduction in CAD run-time, since the entire FPGA implementation need not be generated from scratch. Lastly, this thesis presents an approach that can be used to reduce bitwidths, leading to smaller circuits, which reduces CAD complexity and run-time.Ph.D.2016-06-17 00:00:0