Analytic methods for the FPGA placement problem

Within the last 20 years, the use of Field Programmable Gate Arrays (FPGAs) to implement digital systems has grown significantly because of their flexibility, dramatic reduction in turn-around time, and start-up costs compared with traditional Application Specific Integrated Circuits (ASICs). Moreover, FPGAs themselves have experienced an exponential growth in size, complexity, and performance. Computer-Aided Design (CAD) plays a critical role in optimizing high-performance design solutions using these high-end FPGAs. However, compilation times for designs, which are dominated by placement and routing times, are growing much more rapidly than the available computation power. While current CAD algorithms provide quality solutions, they often require significant amounts of CPU time. For many circuits, the compile time can be on the order of tens of CPU hours, which adversely impacts the use of FPGAs by hardware designs. This provides compelling motivation to explore new methods for fast compilation of designs.;We present a new "near-linear" model for estimating wirelength, called Star+. The model is similar to the traditional star model [21], but is strictly differentiable, making it suitable for use with analytic placement methods. Most importantly, the time to compute the change in cost resulting from the swap of two blocks always runs in O(1) time. We also present two analytic placement methods based on Conjugate Gradient (CG) [18] and Success Over-Relaxation ( SOR) [33], respectively. Both analytic methods seek to minimize total wirelength using the Star+ model as an estimate of wirelength. The novelty of the CG method lies in the fact that this method avoids computing the Hessian matrix on each iteration, thus reducing the (traditional) cost of computing the inner loop from O(n2) to O(n). The SOR method, on the other hand, has the same runtime complexity as CG, but by properly arranging the sequence in which equations in the nonlinear equation system are processed, SOR placement runs faster by a constant amount (approximately 7x). We also present a novel pre-placement method for pre-assigning certain blocks on the FPGA which runs in O(n log n) time. Finally, we develop and present a timing-driven placement algorithm by adding timing-driven parameters into the original (Star+) objective function used by both CG and SOR.;Compared with Versatile Place and Route (VPR ) -- the state-of-the-art academic placement tool, with our methods we are able to achieve solutions 4 to 40 times faster and with 1 to 8.8% less critical-path delay.;In this thesis, we focus on the placement phase of the FPGA design process. Given a circuit represented as a connection of logic blocks, the placement problem can be stated as that of assigning each logic block to a unique physical resource on the FPGA while achieving a given overall performance. Placement is an NP-complete problem [10] and one of the most time-consuming tasks in the automation of FPGA design.