随着现场可编程门阵列FPGA容量的迅速增大,一方面用户的设计编译时间越来越长,另一方面用户设计过程中所施加的约束越来越复杂。在整个FPGA设计流程中,布局是最为耗时的环节之一,并且与FPGA位置约束、时序约束的实现直接相关。为了提高FPGA布局算法的速度,本文在对国内外FPGA布局方面的已有成果充分调研的基础上,提出了一种基于并行模拟退火的FPGA布局算法DPSA (Dynamic Parallel Simulated Annealing).该算法采用了同步多马尔可夫链和网表划分的混合式框架,将整个并行布局划分为两个阶段。在全局优化阶段发挥多马尔可夫链多路同时搜索解空间的优势,并采用了自主设计的交换次数补偿策略,而在局部优化阶段则采用网表划分策略充分挖掘空间局部性。实验结果表明,在4核的实验条件下,DPSA算法比以VPR为代表的串行算法在布局速度上平均提高了2.9倍,布局质量提高了4%,并且加速性能随着CPU核心的增加具有良好的扩展性。另外,由于各线程间采用同步通信的方式,使得DPSA算法具有确定性的布局结果。为了使得本文的DPSA算法发挥更大的实际价值,本文还专门设计了布局模块中绝对位置约束、相对位置约束和频率约束、路径约束等时序约束的处理方案,并把它和DPSA并行框架融合在一起,使得布局模块在获得并行加速的同时依然可以支持用户实际设计中复杂的约束。