A high-speed timing-aware router for FPGAs

grantor: University of TorontoDigital circuits can be realized instantly using Field-Programmable Gate Arrays (FPGAs), but unfortunately the CAD tools used to generate FPGA programming bit-streams often require several hours for large circuits. We contend that there exists a subset of designers willing to pay for faster compile times by having to use more resources on a given FPGA, a larger FPGA, or some decrease in circuit speed. This thesis focuses on the routing phase of the compile and proposes a new high-speed timing-aware routing algorithm. The execution speed of the new router is very fast when the FPGA contains at least 10% more routing resources than the minimum required by a circuit. For example, targeting a model of the Xilinx 4000XL FPGA, the routing time for a 250,000 gate circuit is 127 seconds on a 300 MHz UltraSPARC. The circuit delay is only 19% higher compared to a high-quality timing-driven router.M.A.Sc