Fast heuristic techniques for FPGA placement based on multilevel clustering

Thumbnail Image
Du, Peng
Journal Title
Journal ISSN
Volume Title
University of Guelph

Within the last ten to fifteen years, the use of Field-Programmable Gate Arrays (FPGAs) has grown almost exponentially. It is, therefore, crucial to provide additional Computer-Aided Design (CAD) tools to support FPGA-based designs. This thesis presents two novel placement heuristics that significantly reduce the amount of computation time required to achieve high-quality placement, compared with VPR, which is considered to be a state-of-the-art FPGA placement and routing tool. The first algorithm is an enhancement of simulated-annealing and attempts to solve the problem top down by considering all blocks simultaneously. The second algorithm is a hierarchical approach, which is based on a two-step procedure that first proceeds bottom-up then top-down. The bottom-up technique is clustering, and involves the grouping of highly connected blocks into clusters and then combines clusters into larger clusters. The goal of the top-down method is to determine the location for all the clusters, and eventually the location of all blocks within those clusters. The overall effect is to reduce the number of entities that need be considered at each level, making time-consuming, e.g., simulated-annealing, feasible for larger problems.

Field-Programmable Gate Arrays, Computer-Aided Design tools, CAD tools, design, novel placement heuristics, computation time, high-quality placement, VPR, placement, routing tool