作为集成电路领域内一种半定制电路,现场可编程门阵列(Field Programmable Gate Arrays,简称FPGA)具有设计灵活、成本低、逻辑资源丰富等优点,目前已经广泛应用于现代数字系统设计。以硬件描述语言(Hardware Description Language,简称HDL)设计的电路,经过FPGA EDA(Electronic Design Automation)软件编译后生成二进制位流,使用该位流可以对FPGA芯片中的可编程开关等物理器件进行配置从而最终在FPGA上实现电路功能。随着FPGA集成度和电路规模的增长,FPGA EDA软件耗时越来越长,从而降低FPGA在半导体市场上的竞争力并制约FPGA的健康发展。因此,提升FPGA EDA支撑软件的效率,已经成为当前FPGA领域内主要研究方向之一。FPGA EDA软件的流程包括电路设计、行为综合、工艺映射/逻辑综合、打包/装箱、布局和布线,而其中布线是该流程中耗时最长的步骤之一,且布线的好坏直接影响到电路最终在FPGA硬件上实现后的性能。然而,目前的FPGA布线算法存在以下两方面的不足:(1)算法运行速度慢,导致电路的“编译――调试”周期变长、FPGA电路开发的效率不高;(2)电路布线后的性能较差。为了解决以上问题,本文围绕FPGA电路的高效布线展开,具体工作概括为以下方面:第一,提出了一种利用高效重布线策略的时间优化FPGA布线算法。该算法迭代地对电路线网进行布线,直到得到合法的布线结果。在布线过程中,根据所设置的条件选择低质量路径,而拥挤路径和低质量路径统称为非法路径。在每次布线迭代中,根据新的重布线策略,只对非法的路径进行“拆线――重布”,从而减少了需要重布线的连接的数量。在对单条连接布线时,调用新的迷宫布线算法在布线资源图上不断扩展波前直到找到目标漏端点。在对波前初始化时,只将布线树上距离该连接相对较近的布线资源节点添加到波前,从而避免了由于布线树较大而导致的波前初始化时间过长的问题。实验结果表明,和VPR时序驱动布线算法相比,所提出的时间优化FPGA布线算法运行时间减少了68.5%,同时电路的关键路径延时和总线长分别减少了2.5%和1.4%。第二,提出了一种利用线网混合划分和并行策略的并行FPGA布线算法。所提并行算法主要包括两个阶段:线网划分和并行布线。在线网划分阶段,根据线网特征将所有线网划分为两组集合:互斥线网集合和重叠线网集合,其中不同重叠线网集合中的线网互不重叠,而同一个互斥线网集合中的线网互不重叠。在每次并行布线迭代中,对不同特征的线网集合中的线网采取不同的并行化策略,从而减少线程之间的相互干扰并增大布线的并行度。在对互斥线网集合布线时,每次布线迭代对互斥线网集合逐一进行布线。对于每个互斥线网集合,将该集合内所有线网的非法路径平均分配给多个线程进行“拆线――重布”,从而使所有线程所布线的连接数量基本相同,从而减少线程等待时间。在对重叠线网集合布线时,每个线程分配一个重叠线网集合,并且只对该集合内的非法路径进行“拆线――重布”。实验结果表明,和串行VPR时序驱动布线算法相比,所提出的并行FPGA布线算法使用16线程取得24.3倍加速比,同时电路的质量基本相同。第三,实现了所提出的串行时间优化FPGA布线算法、以及并行FPGA布线算法的支持工具。首先,在VPR框架下实现了利用高效重布线策略的时间优化FPGA布线算法的支持工具。每次布线迭代将使用布线树保存线网的布线结果,从而在接下来的布线迭代中可以根据新的重布线策略对该布线树上的非法路径进行“拆线――重布”。在对每条非法路径重新布线时,改进的迷宫布线算法使用当前布线树上部分节点作为搜索源点,在布线资源图上不断扩展搜索的波前,直到找到目标漏端。实验结果表明,所实现的FPGA布线工具可以在保证电路布线质量的情况下显著减少布线所需时间。接下来,采用OpenMP并行编程技术,实现了利用线网混合划分和并行策略的FPGA布线算法对应的支持工具,该并行布线工具包括线网混合划分和线网并行布线两部分。在线网混合划分阶段,主线程通过调用递归划分函数将FPGA划分为多个区域;相应地,根据线网边界盒判断线网是否在覆盖多个区域,在同一个区域中的线网构成一个重叠线网集合。然后,将跨区域线网进一步划分为多个互斥线网集合。在线网并行布线阶段,多线程采取不同的并行布线策略分别对互斥线网集合和重叠线网集合中的线网布线。当多线程对所有线网布线完成后,由主线程对电路进行时序分析以及检查布线结果是否合法。实验结果表明,所实现的并行FPGA布线工具可以对电路进行快速布线,总体性能优于现有的FPGA布线工具。