Field Programmable Gate Arrays (FPGAs) are integrated circuits that contain configurable logic blocks and wiring resources that enable them to implement digital circuits. To create a design, the designer typically describes the design using a Hardware Description Language (HDL). This HDL is synthesized into a configuration bitstream to program the FPGA using Computer-Aided Design (CAD) tools. Due to their rapid growth in size, FPGAs are able to implement increasingly larger circuit designs. However, this has also lead to the run-time of the CAD tools increasing dramatically. To improve the run-time of CAD tools, this thesis focuses on improving the run-time of the placement stage of the CAD algorithms, which accounts for a significant portion of the overall run-time of the CAD flow. This thesis explores techniques for creating design specific groupings of logic blocks (called multi-blocks) that can be used in conjunction with a new placement algorithm, called the singularity placer. This approach allows the flow to collapse related logic blocks in the design into “multi-blocks”, thereby reducing the design complexity for placement. This reduced complexity can be used to reduce placement runtime, despite having to re-expand these multi-blocks into their original logic blocks to complete the placement phase of the design. This approach allows tradeoffs between the run-time of the CAD tools and the design’s key performance metrics (e.g. operating frequency). This thesis first proposes and evaluates a number of algorithms to divide a design comprised of logic blocks into groups of logic blocks (also known as “multi-blocks”). The objective of this approach is to reduce the run-time as grouping logic blocks of a design decreases the number of nodes to be processed for placement. Next, a two-phase placement algorithm, called the singularity placer, is proposed that can place a mix of multi-blocks and singular logic blocks onto FPGA resources. The experimental evaluation shows that the proposed approach to placement enables up to 30X speedup with an average wirelength degradation of 12% with respect to VPR. This speedup is a dramatic increase that has the potential to make FPGA devices and design flows more useful to application spaces that desire acceleration over pure software in a timely fashion, while not requiring the “best” operating frequency possible.
Copyright is held by the author.
This thesis may be printed or downloaded for non-commercial research and scholarly purposes.
Member of collection