摘要: 　　随着集成电路工艺的不断进步，现代FPGA 向着高速度、高密度方向发展，FPGA 结构复杂化和规模膨胀化给FPGA 物理设计带来新的挑战。布局问题是FPGA 物理设计的关键环节，布局质量的好坏，严重影响FPGA 电路的最终性能。
　　FPGA 物理设计和FPGA 结构相互关联，对于传统孤岛式FPGA，模拟退火算法证明了其高效性和易用性。然而对于层次式FPGA，由于其布线资源的特点，连线单元和互连线都遵循一定的逻辑层次性，模拟退火算法的单元交换对于层次式FPGA 总线长变化的有效性减低。由于启发式算法在FPGA 结构和规模发展中体现出越来越多的局限性，本文将多层次优化方法引入到处理大规模层次式FPGA 布局问题，采用了一个基于多层次结群的布局算法来解决层次式FPGA 布局问题。
　　首先，我们应用了一个与层次式 FPGA 结构逻辑层次性相对应的多层次结群过程，根据每一层次区域包括的逻辑单元数目来选择不同粒度的结群结果；然后，根据多层次结群过程形成的、与FPGA 逻辑结构对应的不同粒度电路网表，应用构造式的布局过程来快速处理层次式FPGA 布局问题。最后，我们对结群过程和布局过程的时间复杂度进行了分析，再应用MCNC 和ISPD 不同规模的20 个测试电路进行了对比试验。实验结果表明，一个包括5000 个标准逻辑单元（LUT4）的FPGA 电路实际布局时间仅为不到70 秒，而同样的电路采用传统模拟退火布局需要500 秒以上。同时，将所有20 个测试电路采用本文算法的布局结果作为低温模拟退火优化过程的输入，总线长指标在时间延长25 倍的情况下仅能平均优化1.11%。应用本文算法进行大规模层次式FPGA 布局，可以达到很好的线长和运行时间平衡。
　　本文虽然对多层次优化策略在大规模层次式 FPGA 布局问题中的应用进行了研究并取得了一定的结果，当前所做的工作还有一些可以进一步完善的地方，现将其总结如下：
　　1) 启发式优化效果不明显
　　多层次优化方法的一个重要特点是每一层次都有一个启发式再优化过程，本文研究工作主要面向层次式FPGA 结构，由于层次式FPGA 结构非连续性线长空间的特点，尚未找到效果良好的启发式优化方案。下一步应该在各层次局部调整上有所突破，而不是简单地模拟退火优化，力求达到更好的运行时间和布局质量的平衡。
　　2) 尚未考虑时延、功耗等性能指标
　　FPGA 布局结果的质量由多个性能指标衡量，包括线长、时延和功耗等。本文仅仅对FPGA 布局结果的线长优化进行了研究，下一步工作重心就是静态时延分析（Static Timing Analysis，STA）以及时延优化。