FPGA(Field Programmable Gate Array),即现场可编程门阵列,具有集成度高、逻辑资源丰富、设计灵活以及使用范围广等特点,因此在数字系统设计中得到了广泛的应用。FPGA设计流程主要包括设计输入、逻辑综合、逻辑优化、技术映射、打包、布局和布线。在FPGA设计中,布局是极为重要的一个环节,它直接影响到后续布线的质量和整个电路的性能。在FPGA芯片逻辑资源中,布线资源占到整个芯片资源的60%以上,因此如何在布局阶段对布线资源进行合理的估算并有效降低布线的拥挤度成为布局算法重要研究方向。基于布线拥挤度的FPGA布局算法的研究主要分为两个方面：首先是如何使现有的优化算法适应于FPGA结构,即完成现有算法针对特定FPGA结构的建模,同时将布线拥挤度代价函数融于算法结构中,从而达到在布局阶段减少降低布线拥挤度的目的。其次是在布局阶段对布线拥挤度估算模型进行研究。基于FPGA结构对布线资源的使用进行合理的建模,以准确估算布线资源的使用,且在算法中将拥挤度代价作为代价函数的一部分引导算法过程,从而达到减少布线资源使用降低布线拥挤度的目的。本文针对基于布线拥挤度的FPGA布局算法的两个方面进行了较为深入的研究,所做的主要工作如下：基于布线拥挤度问题对FPGA设计领域的主要布局优化算法进行了详细的分析,包括基于划分的布局算法,模拟退火算法,遗传算法,蚁群算法等。基于对常见布局优化算法的比较,本文将蚁群算法应用于FPGA布局中,以FPGA著名开源软件VPR为研究平台,将布线拥挤度作为启发因子引导算法,实验表明基于布线拥挤度的蚁群布局算法能够获得较好的结果。布线拥挤度估算模型是基于布线拥挤度的布局算法的一个重要研究方向。本文对主流拥挤度估算算法的特点进行了分析,提出一种等概率的拥挤度估算模型。该模型基于Bounding Box结构构建,不依靠具体的布线路径来进行布线资源估算,而是将布线资源的估算等概率分配给每个待布局区域,因此不会造成布局时间的显著增加。实验结果表明该模型的估算精确度与Xilinx ISE基本一致,将该模型融于布局算法中在不显著增加FPGA布局时间的情况下降低了布线拥挤度,从而改善了电路的性能。