Multi-phase placement approach for field programmable gate arrays

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.