一种快速预判FPGA布线失败的方法

向明艳 白利琼 刘乙力 鞠瑜华

（成都华微电子科技有限公司 四川省成都市 610000）

随着半导体工艺尺寸进入纳米范畴，FPGA 器件的逻辑容量和复杂程度大幅度上升，对FPGA 电子设计自动化（Electronics Design Automation,简称EDA）软件的要求也越来越高。在FPGAEDA 软件中，将高层次的算法级行为描述编译为用于配置FPGA 可编程开关状态的编程下载文件需要经过综合、映射、打包、布局、布线、位流生成和编程下载等过程。其中布线阶段通常要占据整个流程的近30%的时间[3]，且布线资源占用了整个芯片50%～60%的信号延时[1]。因此布线速度的改进对于提高FPGA EDA 软件的性能至关重要。

FPGA 布线是在布局的基础上，按电路需求打通合适的可编程开关以连通逻辑单元块的输入和输出引脚，使得最后的总线长尽可能地短，同时兼顾面积和时序。布线策略的选取很大程度上决定了布线结果。目前主流的布线算法主要是基于拥挤度协商的路径搜索算法，该方法在解决拥塞问题的同时也能优化时序[2]，但该算法应用于千万门级FPGA 电路时，随着搜索空间的增大，布线所需时间也随之增大。[3]中提出了一种伪布尔满足性布线算法，该方法同时对所有的线网进行布线，可准确判断线网可布通性，改进了传统布尔可满足性算法需要大量的变量和约束条件的问题，但伪布尔可满足性在布线阶段转换成本过大，不适用于大规模布线基准。

本文提出了一种新颖的在布线之前预判布线失败的方法，主要根据FPGA 中预先定制的布线资源，将互连端口间的连接关系用布线查找表表示，根据布线查找表中“1”的分布情况判定线网是否布线失败，一旦预判该网表布线会失败，就不再进行布线操作，从而节约布线时间。该方法操作简单、计算量小、准确性高。目前未见类似方法的公开报道，该方法属于首次提出。

1 FPGA互连模块介绍

目前主流的SRAM 型FPGA 主要由可配置逻辑模块（CLB,Configurable Logic Block）、可编程输入/输出单元（IOB,Input Output Block）、可编程互连资源等部分组成，也可通过嵌入DSP（Digital Signal Processor）、RAM(Random Access Memory)等异构单元来提高FPGA 的处理能力。

FPGA 中有着丰富的可编程互连资源，主要包括互连线和互连开关矩阵。CLB 与互连开关矩阵组成Tile 块以阵列的形式有序地排列在FPGA 中，开关矩阵主要由传输管、多路选择器和三态缓冲器等器件组成，用于实现相应的水平和垂直布线通道中互连线间的连接以及互连线与逻辑资源管脚间的连接。布线通道中存在多种互连线资源，其中全局时钟连线资源为FPGA 中的逻辑单元块传送时钟信号，普通可编程连线资源用于实现重复单元的连接，主要有单倍线、多倍线和长连线，多样的连线资源可以实现不同跨度的连接，从而降低路径的延时，提高电路的性能。

互连开关矩阵由不同长度的导线和多个布线开关组成。图1 为简化的互连开关矩阵内部结构，由2 个二输入多路选择器组成。其中I0 ～I3 为输入端口，O0 ～O2 为输出端口。

互连开关矩阵管脚间的简化连接模型如图2所示，其中CLB为逻辑模块，INT 表示互连矩阵模块，以最左边的INT 所在位置为坐标原点可实现对各INT 的坐标编号。INT 中的I4、O3 端口为互连模块与逻辑模块相连的输入输出端口。通过对互连开关矩阵中多路选择器的通断可实现对不同逻辑资源间的连接，进而实现电路功能。

表1：开关矩阵内部连线关系

表2：开关矩阵间连线关系

图1：互连开关矩阵内部结构

图2：互连模块之间管脚连接关系模型

2 布线查找表的构造

已知FPGA 中所有的布线资源都是预先定制的，也就是说FPGA 中互连开关矩阵间的连接情况和互连开关矩阵内部的走线是可以确定的。又因为FPGA 中的互连矩阵结构相同，故可以根据互连矩阵间的连接方式，内部结构的走线规律得到任意INT 的任意输入端口可到达的所有INT 的输出端口。由此可快速判断给定线网从源端到漏端是否存在可连通的路径。

令互连矩阵输入端口为I={I0,I1,…,Ii,…,In}，输出端口为O={O0,O1,…,Oj,…,Om}，其中n 为互连矩阵的输入端口数，m 为互连矩阵的输出端口数。根据图1 可知n=3，m=2，可得到互连开关矩阵输入端口Ii 可连接的所有输出端口Oj。例如输入端口I0 可到达的输出端口为：O0，输入端口I3 可到达的输出端口为：O1、O2，具体对应关系如表1所示。

假设互连矩阵INT 的行数为R，列数为C，第p 行q 列的互连矩阵坐标为(p,q)，其中p=0,1,2,…,R，q=0,1,2,…,C。(p,q)_Oj 表示坐标为(p,q)的INT 的输出端口Oj。根据图2 可得到一个互连模块的输出端口到另一互连模块的输入端口的对应关系如表2所示。例如INT(0,0)的输出端口O0 可到达INT(2,0)的I0 端口。

根据表1 和表2 遍历INT，得到INT 的输入端口通过跳转能够到达的所有INT 的输出端口，从而构建布线查找表。假设当前INT的坐标为(p,q)，其当前输入端口名为Ii，详细步骤如下：

（1）根据表1 将与当前INT 的端口(p,q)_Ii 可达的输出端口(p,q)_Oi 加入到临时集合Temp 中；

（2）判断Temp 是否为空，若是则退出循环；否则进入下一步；

（3）选取Temp 中第一个元素加入到集合O 中，并获取相应的INT 坐标(p,q)和输出端口Oi，通过表2 和表1 获取通过端口Oi跳转可达到的其它INT 的输出端口集合，与集合O 去重后加入到Temp 中，删除Temp[0]。跳转到（2）。

由此可得到(p,q)_Ii 所能到达的所有输出端口的集合O。得到所有输入端口的可达输出端口后，将所得的结果转换为C*R*(n+1)行C*R*(m+1)列的布线查找表，初始化查找表为全0，遍历集合O 设置相应位置为1。例如输入端口为(p,q)_Ii，其可达输出端口为(p’,q')_Oj，则设置布线查找表第(p*C+q)*N+i 行(p'*C+q')*M+j 列为1。表3 为最终的布线查找表。

该查找表能够准确的表达INT 的输入端口到达其他输出端口是否存在相应的路径。通过该查找表能够快速准确预判一个线网是否布线失败。根据布局结果获得需要布线的线网Nt，t∈N*，针对任意布线需求Nt，有(x,y)_Ok →(x',y')_Ik'，表示坐标为(x,y)的功能模块的输出端口k 需要连接到坐标为(x',y')的功能模块输入端口k'。遍历线网，参照布线查找表判断是否存在线网布线失败的情况。预判Nt是否存在布线通路的具体步骤如下：

（1）根据器件模型获得(x,y)_Ok 对应的INT 端口(p,q)_Ii，同理获得(x',y')_Ik'对应的INT 端口(p’,q' )_Oj；

（2）将查询位置为(p,q)的INT 端口Ii 和位置为(p’,q')的INT 端口Oj 是否有路径转换为查询布线查找表中第(p*C+q)*N+i行(p'*C+q')*M+j 列是否为1。若为1 则线网Nt中存在布线通路，否则布线失败。

如果有一个线网Nt布线失败，则预判整个布线过程无法完成，就不再进行布线操作，从而节约布线时间。

表3：布线查找表

3 结论

本文提出了在布线之前预判布线失败的方法，主要根据FPGA中预先定制的布线资源，将互连端口间的连接关系用布线查找表表示。对布线需求的线网进行遍历，得到源端和漏端，根据布线查找表中“1”的分布情况判定线网是否布线失败。一旦预判该网表布线会失败，就不再进行布线操作，从而节约布线时间。该方法操作简单、计算量小、准确性高。此外，该方法对于布局和综合阶段也具有重要意义，可通过对拥挤度的情况改善布局结果，将时延的预估加入物理综合。