动态可重构FPGA的布局布线算法研究

可编程逻辑芯片特别是现场可编程门阵列(Field-Programmable Gate Array，FPGA)芯片的快速发展，使得新的芯片能够根据具体应用动态地调整结构以获得更好的性能，这类芯片称为动态可重构FPGA芯片(Dynamically ReconfigurableFPGA，DRFPGA)。然而，使用这类芯片构建的可重构系统在实际应用前还有许多问题需要解决。一个基本的问题就是动态可重构FPGA芯片中的可重构功能单元(Reconfigurable Functional Unit，RFU)的模块布局问题和模块间的布线问题。 本文从基本的FPGA芯片结构和CAD算法谈起，介绍了可重构计算的概念，建立了可重构计算系统模型和动态可重构FPGA芯片模型，在此模型上提出一个基于划分和时延驱动的在线布局算法，和一个基于Pathfinder协商拥塞算法的布线算法，来解决动态可重构FPGA芯片的布局和布线问题。由硬件描述语言(Hardware Description Language，HDL)描述的电路首先被划分成有限数目的层，然后将这些电路层布局到芯片的每一层，同时确保关键路径的时延最小。实验结果表明，布局算法与传统的布局算法(或者文献[37]中的算法)相比，在时延上平均减少27％，在线长上平均减少34％(或者11％)，在运行时间上平均减少42％(或者97％)。布线算法与传统的布线算法相比，能够将线长降低26％，将水平通道宽度降低27％，显示出较高的性能。