TIMING AND CONGESTION DRIVEN ALGORITHMS FOR FPGA PLACEMENT

Placement is one of the most important steps in physical design for VLSI circuits. For field programmable gate arrays (FPGAs), the placement step determines the location of each logic block. I present novel timing and congestion driven placement algorithms for FPGAs with minimal runtime overhead. By predicting the post-routing timing-critical edges and estimating congestion accurately, this algorithm is able to simultaneously reduce the critical path delay and the minimum number of routing tracks. The core of the algorithm consists of a criticality-history record of connection edges and a congestion map. This approach is applied to the 20 largest Microelectronics Center of North Carolina (MCNC) benchmark circuits. Experimental results show that compared with the state-of-the-art FPGA place and route package, the Versatile Place and Route (VPR) suite, this algorithm yields an average of 8.1 % reduction (maximum 30.5%) in the critical path delay and 5 % reduction in channel width. Meanwhile, the average runtime of the algorithm is only 2.3X as of VPR. ACKNOWLEDGMENTS I have been fortunate to have my parents over the past 28 years. They always support me whenever I was ambitious or in depression. Without them, I can never be strong enough to stand success and failure. I dedicate this thesis to them