PARALLEL ROUTING FOR FIELD PROGRAMMABLE GATE ARRAYS

Abstract

Moore’s Law has enabled the creation of larger and faster FPGAs. Unfortunately, the increase in speed and capacity of FPGAs is faster than the development of effective design tools to fully utilize it. One of the major inefficiencies with existing FPGA design flow is that they take a long time to implement state-of-the-art designs, and routing of nets remains as one of the most time-consuming stages of the flow. Fast routing is crucial in not just implementing designs on FPGAs, but also evaluating new FPGA architectures. In this thesis, FPGA routing is accelerated by parallelizing the process, and the design space of parallel FPGA routers is explored by evaluating tradeoffs between speedup, quality-of-result, and determinism.