基于SRAM 的FPGA 导航布局布线方法实现与应用

陈 亮，李 艳，李 明，于 芳，刘忠立

中国科学院微电子研究所，北京100029

现场可编程门阵列(field programmable gate array，FPGA)是目前广泛使用的可编程器件，具有开发周期短和成本低等优点. 在FPGA 设计的CAD软件流程中，布局布线是关键. 布局算法确定了实现电路功能所需的各逻辑单元块在FPGA 中的位置，其优化目标是把相连的逻辑单元块靠近放置以最大限度地减少所需布线资源，但有时也要平衡FPGA 中所需布线密度或最大限度提高电路速度.一旦确定了电路中所有逻辑单元块的位置，布线器即可打通合适的可编程开关以连接电路所需要的所有逻辑单元块的输入和输出引脚. 绝大多数FPGA的布线器有一套避免拥挤的策略，以解决布线资源竞争问题［1］.

为测试FPGA 芯片，用于验证与测试的码流文件需由CAD 软件生成. 然而现有的FPGA CAD 工具，如Xilinx ISE 和Altera Quartus II，不能满足芯片测试的需求. 这些FPGA CAD 工具不能生成用于验证与测试的码流文件. 用户难以轻易控制传统布局布线算法的具体执行过程，导致布局布线结果具有一定的不可控性和不可预知性. 执行布局布线前，用户不知道FPGA 芯片架构中的哪些逻辑单元块和布线资源将会被使用. 为测试FPGA 芯片，用户必须在布局布线执行之前指定将要使用的逻辑单元块和布线资源，以达到测试FPGA 芯片结构中这些逻辑单元块和布线资源的目的.

为此，本研究提出一种导航布局布线方法，以期控制布局布线结果，即在布局布线过程中，用户可根据需求指定逻辑单元块的位置和信号的路径，达到预期的布局布线结果. 该方法基于VPR［2］算法，即布局采用模拟退火［3-6］算法，布线采用路径搜索算法［7］. 将该方法应用于FPGA 芯片测试可得到较高的测试覆盖率. 在导航布线的过程中，会产生一种部分漏端指定路径的线网. 针对这种线网的布线，本研究提出考虑固定路径影响的布线方法，相对直接忽略指定路径的漏端的布线方法，该方法在迭代次数和关键路径延时方面得到了优化.

1 VS1000 FPGA 结构

VS1000 是一款自主研发并已完成流片验证的辐射加固SOI (silicon-on-insulator)工艺的FPGA芯片，其架构如图1. FPGA 芯片架构包括逻辑片(logic tile)阵列，可编程输入输出单元块 (IO block)阵列、2 个全局信号单元块(global signal block). 逻辑片是FPGA 的基本组成单元块，1 个逻辑片由1 个逻辑单元块(LB)、1 个X 方向的连接盒(CBX)、1 个Y 方向的连接盒(CBY)和1 个开关盒(SB)组成. 可编程输入输出单元块提供了芯片管脚和内部信号的通道. 全局信号模块通过专用布线资源将全局信号输送给每个逻辑单元块.全局信号可由芯片外部管脚或内部逻辑信号提供［8］.

图1 VS1000 FPGA 结构Fig.1 VS1000 FPGA architecture

2 导航布局布线的实现

为测试VS1000 FPGA 芯片，本研究提出导航布局布线方法，用以方便FPGA 的阵列化测试，提高测试效率. 在布局布线前，用户可指定将要使用的逻辑单元块和布线资源，以期得到用户预计的布局布线结果.

2.1 用户约束文件

导航布局布线可根据用户约束进行布局布线.其约束由用户写在用户约束文件(user constraint file)中. 导航布局布线工具读取用户约束文件获得约束信息，再根据约束执行布局布线. 用户约束文件包含布局约束和布线约束两部分.

布局约束描述逻辑单元块的位置，即映射过程输出的网表文件中指定的逻辑单元块应该放置在FPGA 结构中的位置坐标(列号、行号). 这些指定的位置坐标必须合法，位置坐标不能超过FPGA结构的范围. 同时，网表文件中被指定的逻辑单元块的类型必须与FPGA 结构中指定位置处的逻辑单元块类型匹配. 若用户指定的位置坐标不合法，则导航布局布线工具会报错，提示用户重新指定位置坐标.

图2 指定位置的线网描述Fig.2 Description of location-fixed net

布线约束描述线网布线要使用的布线资源，即线网的位置. 如图2，每个指定位置的线网都是按照信号的走向，依次描述每一个经过的布线资源图中的结点. 每个线网都是从源端出发，依次经过逻辑单元块输出引脚结点、互连线段结点、逻辑单元块输入引脚结点，最终到达漏端. 每个结点的信息包括该结点的列号、行号、类型、序号4 个部分.然而，用户列出所有指定路径线网上的所有结点是非常困难的. 开关盒布线规则可解决该问题，用户只需写出开关盒布线规则，导航布局布线工具就可根据开关盒布线规则自动选择互连线段结点. 图3列举了部分开关盒布线规则的例子. 如图3 所示，根据信号方向，若信号从左边进入开关盒，则信号从开关盒上边穿出(图3a);若信号从右边进入开关盒，则信号从开关盒左边穿出(图3b);若信号从上边进入开关盒，则信号从开关盒右边穿出(图3c);若信号从下边进入开关盒，则信号从开关盒右边穿出(图3d). 用户可根据自己需要指定开关盒布线规则. 根据开关盒布线规则，大量的互连线段结点不用罗列在用户约束文件中. 结点与结点间的选择要符合FPGA 结构的约束，如源端与逻辑单元块输出引脚结点的选择要符合局部布线结构，互连线段结点之间的选择要符合开关盒结构等.

图3 开关盒布线规则举例Fig.3 Examples of SB route rule

2.2 三种指定路径的线网

映射后输出网表文件中的所有线网都需布线.一个线网只有一个源端，但漏端数量可能是一个，也可能是多个. 在用户约束文件中，用户可指定一个线网中一个源端到该线网的所有或部分漏端的路径. 因此，网表中的线网可分为3 类:无指定路径线网、全部指定路径线网和部分指定路径线网. 无指定路径线网的源端到其所有漏端的路径都是没有被用户约束文件指定的. 如图4(a)，该线网有3个漏端，源端到这3 个漏端的路径都是没有被指定的. 这种线网由布线器来布线. 全部指定路径线网的源端到其所有漏端的路径都是被用户约束文件指定的. 如图4(b)，该线网有3 个漏端，源端到达这3 个漏端的路径都是被指定的. 这种线网不需要由布线器来布线. 但是如果用户需要，这种线网的时序分析还是需要执行. 部分指定路径线网的源端到其一部分漏端的路径是被用户约束文件指定的，到另一部分漏端的路径是未被指定的. 如图4(c)，该线网有3 个漏端，源端到其中一个漏端的路径是被指定的，到另外两个漏端的路径没有被指定. 被指定的路径不需要由布线器来布线，没有被指定的路径由布线器来布线.

图4 三种指定路径线网举例Fig.4 Examples of three kinds of location-fixed nets

3 部分指定路径线网的布线

在使用时序驱动算法对部分指定路径的线网布线时，是否应忽略被指定的源端到漏端的路径.

对一个无指定路径线网布线的流程，如图5，可根据漏端关键度的大小顺序，从源端开始，依次对每个漏端进行布线. 对于部分指定路径线网，只需对用户约束文中未指定路径的漏端进行布线，流程如图6. 在遍历该线网的所有漏端时，若该漏端路径是被指定的，则直接跳过，遍历下一个漏端，这是忽略线网中固定路径漏端的方法. 但考虑总成本TotalCost 的计算方法，固定路径上的结点布线成本势必会影响到线网中其余漏端布线时结点的搜索，从而影响线网的布通率和关键路径延时. 在从源端i 到漏端j 进行布线时，结点n 的总成本为

图5 无指定路径线网布线流程图Fig.5 Flow of no location fixed net routing

其中，PathCost(n)是从当前部分布线树(routing tree)到结点n 的总路径成本，即

图6 部分指定路径线网布线方法流程图Fig.6 Flow of partial location fixed net routing

对于无指定路径线网，当完成一个漏端布线后，会将该路径上的所有结点加入到布线树中. 对下一个漏端进行布线时，计算布线树中可作为信号分支结点的总成本，即布线树中可作为信号分支的结点在下一个漏端布线时是可被搜索到的. 对于部分指定路径线网，如果按照图6 的流程进行布线，那么固定路径上的结点没有加入到布线树中，在对其他漏端进行布线时，固定路径上的可作为分支的结点将无法被搜索到，这将大大降低布通率和影响线网的延时. 如图7 中线网中有3 个漏端sink0、sink1和sink2. 源端到漏端0 和源端到漏端1 的路径是被用户约束文件指定的，源端到漏端2 的路径是需由布线器进行布线的. 如果按照图6 的流程，在对漏端2 进行布线时，N1、N2、N3和N4这些本可以使用的结点将永远不会被搜索到，从而影响布通率和线网的延时.

图7 部分指定路径线网布线资源图Fig.7 Routing resource graph of partial location fixed net routing

基于以上原因，对图6 流程进行修改，如图8.在对部分指定路径线网进行布线时，第一步就是将固定路径上的结点加入到布线树中，在对其他漏端进行布线时，固定路径上的可作为分支的结点也可被搜索到. 由于在布线资源图中，N1、N2、N3和N4拥有众多子结点，增加一个可选结点后，源端到漏端的可选路径数量将呈指数增加，因此大大提高了这种线网的布通率，且优化了该线网的延时. 如图7，对漏端2 进行布线时，可作为分支结点的N1、N2、N3和N4的总路径成本分别是

图8 优化后的部分指定路径线网布线方法流程图Fig.8 Flow of optimized partial location fixed net routing

同样可计算出这些结点的总成本，用于时序驱动布线时结点的搜索.

4 实验结果与分析

4.1 导航布局布线的实验结果与分析

导航布局布线方法可以生成应用于FPGA 芯片测试的码流文件. 为测试FPGA 架构中的每个部分，本研究共写了128 个测试实例，如表1. 这些测试实例经过综合和映射之后，使用导航布局布线工具生成应用于验证和测试的布局布线结果. 通过图形用户界面(GUI)可以看到布局布线结果. 图9 给出了应用导航布局布线工具生成的测试长度为1 的互连线段的布局布线结果. 为了测试FPGA 架构中所有长度为1 的互连线段，所有长度为1 的互连线段必须被信号占用. 在用户约束文件中写入布线约束和开关盒布线规则，开关盒布线规则为:从开关盒左入，下出;上入，右出;右入，上出;下入，左出. 应用上述开关盒布线规则，FPGA 芯片中每条长度为1 的互连线段就可全部连接起来. 除此以外，导航布局布线还应用于测试FPGA 架构中其他部分，如所有输入输出单元块、全局信号单元块、逻辑单元块和其他类型的互连线段等，都成功生成了用于测试的布局布线结果.

图9 测试长度为1 的互连线段的布局布线结果Fig.9 Result of placement and routing for testing single-length tracks

表1 VS1000 FPGA 芯片的测试实例和测试覆盖率Table1 Functionality test coverage of total testing cases for VS1000 FPGA chip

由表1 可知，通过使用导航布局布线工具可得到较高的测试覆盖率. 本研究共128 个测试实例，总测试覆盖率达85%.

4.2 优化的部分指定路径线网布线实验结果与分析

本研究从IWLS、itc 等基准电路中选取10 个逻辑复杂的电路，并指定这些电路网表中部分漏端的路径，使其成为部分指定路径线网，来测试优化后的部分指定路径线网的布线方法. 这10 个电路的逻辑单元块数量和部分指定路径线网的数量如表2.

表3 比较了优化前后部分指定路径线网布线的方法. 实验中FPGA EDA 流程中的映射，布局布线都是在自主研发并已完成流片验证的辐射加固SOI工艺的FPGA 芯片VS1000 的架构上进行的. 从表3可见，优化的部分指定路径线网布线方法的迭代次数平均减少22.6%，关键路径延时平均减少20.9%. 电路的逻辑越复杂，优化后的部分指定路径线网布线方法的优化率越高. 如表4，在优化迭代次数和关键路径的同时，并没有影响布线资源利用率.

表2 测试电路Table 2 Test circuit

表3 优化前后部分指定路径线网布线方法的对比Table 3 Comparison between un-optimized and optimized methods for partial location-fix neted routing

表4 未优化与优化的部分指定路径线网布线方法的布线资源利用率对比Table4 Comparison of routing resource utilization rate between un-optimized and optimized methods for partial location-fixed net routing%

结 语

本研究针对FPGA 芯片开发过程中的验证和测试提出了导航布局布线方法，适用于任何架构的岛式FPGA 芯片的验证和测试. 对自行研发的基于SOI 的辐射加固FPGA 芯片VS1000 的验证和测试结果表明，该导航布局布线方法可获得较高的测试覆盖率. 所提出的针对部分漏端指定路径的线网布线方法，比直接忽略指定路径的布线方法，平均可减少迭代次数22.6%，关键路径延时可减少20.9%，能有效提高FPGA 验证和测试过程中布局布线的性能.

/References:

［1］Betz V. Architecture and CAD for Deep-Submicron FPGAs［M］. Toronto (Canada):Kluwer Academic Publishers，1999:22-26.

［2］Vaughn B. Architecture and CAD for Deep-Submicron FPGAs ［M］. WANG Ling-li，YANG Meng，ZHOU Xuegong，tran. Beijing:Publishing House of Electronics Industry 1999:41.(in Chinese)Betz V. 深亚微米FPGA 结构与CAD 设计［M］. 王伶俐，杨 萌，周学功，译. 北京:电子工业出版社，2008:41.

［3］LIAO Yong-bo，LI Ping，RUAN Ai-wu，et al. A HW/SW co-verification technique for field programmable gate array(FPGA)test ［C］ // IEEE Circuits and Systems International Conference on Testing and Diagnosis (ICTD '09).Chengdu (China):IEEE Press，2009:1-4

［4］LI Ping，LIAO Yong-bo，RUAN Ai-wu，et al. Novel Approach to Test Field Programmable Gate Array Based on SoC HW/SW Co-Verification Technology ［J］. Journal of University of Electronic Science and Technology of China，2009，38(5):716-720.(in Chinese)李 平，廖永波，阮爱武，等. SoC 软硬件协同技术的FPGA 芯片测试新方法［J］. 电子科技大学学报，2009，38(5):716-720.

［5］ZHAO Chang-hong，CHEN Jian，ZHOU Dian，et al. A VLSI floorplanning algorithm based on weight ［J］. Journal of Computer-Aided Design ＆ Computer Graphics，2006，18(7):994-998.(in Chinese)赵长虹，陈 建，周 电，等. 基于权重的超大规模集成电路布图规划算法［J］. 计算机辅助设计与图形学学报，2006，18(7):994-998.

［6］SUI Wen-tao，DONG She-qin，BIAN Ji-nian. Wirelengthdriven fast placement algorithm for island style FPGAs［J］. Journal of Computer-Aided Design ＆ Computer Graphics，2009，21(9):1275-1282.(in Chinese)隋文涛，董社勤，边计年. 岛式FPGA 线长驱动快速布局算法［J］. 计算机辅助设计与图形学学报，2009，21(9):1275-1282.

［7］JI Guo-fan，ZHAO Zhi-hao，YANG Song. ATE-based FPGA test approach ［J］. Electronic Test，2007(12):43-46.(in Chinese)吉国凡，赵智昊，杨 嵩. 基于ATE 的FPGA 测试方法［J］. 电子测试，2007(12):43-46.

［8］HAN Xiao-wei. Design and Verification of Radiation-Hardened SOI-Based FPGA:II ［D］. Beijing:Chinese Academy of Science. Institute of Semiconductors，2011.(in Chinese)韩小炜. 辐射加固SOI 工艺FPGA 的设计与验证:II［D］. 北京:中国科学院半导体研究所，2011.