Abstract

With a few exceptions, academic packing algorithms for FPGAs are typically applied solely to theoretical architectures. This has allowed the algorithms to focus on the basic components of packing while abstracting away many of the details dictated by real hardware. As commercially available FPGAs have advanced, however, the academic algorithms and architectures have diverged significantly from their commercial counterparts. In this dissertation, the RapidSmith 2 framework is presented. This framework accurately reflects the architecture of Xilinx FPGAs and provides support for integrating custom tools into the commercial CAD tools. Using this framework, the RSVPack packing algorithm is implemented. The RSVPack algorithm can accept a design synthesized using the commercial Xilinx CAD tools, pack designs which make use of the many features of commercial FPGA architectures and return the packed designs to the Xilinx CAD tools to be placed and routed in their software. This enables researchers to isolate the packing portion of the algorithm from the commercial flow and evaluate different packing techniques while allowing the high-quality commercial tools to perform the remainder of the flow. Integrating the RSVPack algorithm the commercial flow shows RSVPack produces packing which lead to circuits with minimum clock periods within 10%, on average, of circuits generated using the pure Xilinx flow. Included in this work is a novel table lookup-based algorithm which RSVPack utilizes to quickly determine the routability of a cluster. This algorithm performs 5 times faster on average than the current academic alternatives. Finally, using RSVPack, this dissertation explores various techniques for improving the quality of packing for Xilinx circuits. Together, this demonstrates the potential for academic research into FPGA CAD tools for commercial architectures.

Degree

PhD

College and Department

Ira A. Fulton College of Engineering and Technology; Electrical and Computer Engineering

Rights

http://lib.byu.edu/about/copyright/