A Completely Parallelizable Analytic Algorithm for Fast and Scalable FPGA Placement

Thumbnail Image




Pattison, Ryan

Journal Title

Journal ISSN

Volume Title


University of Guelph


Modern Field Programmable Gate Arrays (FPGAs) have millions of reconfigurable components capable of implementing complex system on a chip designs. Leveraging the capabilities of FPGAs requires the computer aided design flow, including placement, to be both fast and scalable. Unfortunately, as FPGAs continue to grow, compiling the circuits can take hours or days to complete using placement algorithms based on Simulated Annealing (SA). Analytic placement algorithms, such as StarPlace, have emerged as efficient candidates to solve the placement problem. More recently, a parallel SA-based algorithm, CAMIP, established a methodology for creating scalable parallel placement algorithms. With an aim towards developing a fast and scalable placement algorithm, we apply the methodology from CAMIP to the analytic placement algorithm, StarPlace. Implemented on a graphics processing unit, this algorithm produces 24% less critical path delay, maintains equivalent wirelength, and is 118 times faster than the state of the art academic tool, VPR.



FPGA, Placement, VLSI, CAD