{'fraction_non_alphanumeric': 0.024464831804281346, 'fraction_numerical': 0.014678899082568808, 'mean_word_length': 4.621993127147766, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A High-Speed Timing-Aware Router for FPGAs

A High-Speed Timing-Aware Router for FPGAs Master of Applied Science, 1998 Jordan S. Swartz Department of Electrical and Computer Engineering University of Toronto Digital circuits can be realized almost instantly using Field-Programmable Gate Arrays (FPGAs), but unfortunately the CAD tools used to generate FPGA programming bit-streams often require several hours to compile large circuits. We contend that there exists a subset of designers who are willing to pay for much faster compile times by having to use more resources on a given FPGA, a larger FPGA, or some decrease in the circuit speed. A significant portion of the compile time tends to be spent in the placement and routing phases of the compile. This thesis focuses on the routing phase 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, when 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. Since some routing problems are inherently difficult and will unavoidably take a long time to route, the practical use of high-speed routing requires that the tool must be able to predict if the routing task is: (i) difficult and will take a long time to complete, or (ii) impossible to complete. In this research, we present a method for making these predictions and show that it is accurate.