FPGA布线的保持时间违规的解决方法

孙铁力，郭冠男，廉程

（1.北京大学在职研究生，上海 200433；2.伊利诺伊大学香槟分校本科生，美国伊利诺伊州；3.上海汽车数据业务部，上海 200041）

0 引言

FPGA（Field-Programmable Gate Array），即现场可编程门阵列。FPGA的EDA技术就是以计算机为工具，设计者在EDA软件平台上，用硬件描述语言Verilog/VHDL完成设计文件，然后由计算机自动地完成逻辑综合、打包、布局、布线和仿真，直至对于特定目标芯片的适配编译、逻辑映射和编程下载等工作。

FPGA布线是使用布线矩阵（Routing Matrix）来将单元按照线网的连接关系来实现具体的连接。FPGA布线要求详细布线，无冲突，运行时间满足用户需求，所有线网无时序违规，较优的FMAX。

其中，要保证FPGA的布线无时序违规，就需要布线器和静态时序分析（STA）工具的协同工作，每次布线迭代完成之后，STA工具给出当前所有不满足用户时序约束（SDC）的点，再由布线器对这些点进行修复。

STA工具一般会检查建立时间（clock setup check），保持时间（clock hold check），恢复时间和去除时间（recovery and removal time check）,同一点可能会有多种违规。在现代的FPGA的EDA工具中，我们还要考虑多时钟周期路径（multi-cycle path）,时钟的不确定性（clock uncertainty）和多角（multi-corner）时序分析等。布线器需要去修正时序违规的点，最重要的是修正两种违规，即建立时间违规和保持时间违规，前者表示关键路径的延时大于用户的约束，后者表示关键路径的延时小于用户的约束。前者业界已经有成熟的解决方案，本文主要讨论后者的解决方案。

保持时间就是在时钟沿锁存到数据以后，数据需要保持的时间。如图所示，触发器的数据输入端是D，时钟输入端是CLK。触发器在时钟的上升沿锁存数据，而数据在时钟的上升沿到来之后还需要保持一段时间才能确保触发器能正确的锁存数据，这个数据需要保持的时间就是保持时间。一般情况下，数据路径的延时要大于时钟路径上的延时的，但是现代的FPGA的阵列在不断增大，硬件很难保证时钟树的平衡，当产生数据触发器的时钟和接收数据触发器的时钟偏斜足够大时，保持时间的违规就会产生。

ASIC解决保持时间违规的主要方法是添加缓冲器（buffer insertion），但是由于结构原因，FPGA解决保持时间违规的主要方法是在触发器数据输入端增加旁路延时单元，或者通过特殊的布线器来增加布线延时，Xilinx的Vertex2的硬件解决方案如图1所示：

图1 Xilinx的硬件解决方案

1 修正的A＊算法

现阶段FPGA布线器主要采用对线网的每根线用A*算法单独布线，整体使用pathfinder算法。由于A*算法属于求最短路径的算法，会与pathfinder算法配合求出不冲突的最短路径，但是由于解决保持时间违规需要在存在保持时间违规的路径上增加一定的延时，即要满足路径的延时位于[t1，t2]，其中，t1表示路径要满足保持时间需要的最小延时，t2表示路径要满足建立时间需要的最大延时。当时钟树的布线不再发生变化时，即可消除对应的触发器上的保持时间违规。

本文采用修正的A*算法来完成这一目标。A*算法是一种在图中求解最短路径最有效的直接搜索方法，根据图的结构特征、初始点与目标点的位置信息以及路径构成等先验知识来对搜索过程加以正确引导，使其沿着目标的方向逐步逼近进行的搜索方法。代价函数可表示为：f(n)=g(n)+h(n)，其中g(n)表示初始点到当前点的实际代价，h(n)即当前点到目标点的最佳路径的估计代价(futurecost)。A*算法的伪代码如下所示：

在第26行中，相邻节点已经在openlist中，如图所示，这时可分为两种情况讨论，当前节点和相邻节点确定的边为前向边（Forward edge）或者横向边（Cross edge）。由于FPGA的架构原因，导致少数边为无向边，多数边为有向边，当相邻节点为当前节点的祖先时为前向边，这时添加该边将构成环路，是应该避免的情况；当相邻节点不是当前节点的祖先时为横向边，这时，从初始点到达相邻节点的路径变成了两条，为了寻找最短路径，我们选择代价较小的路径继续进行搜索。

我们寻找较长路径时，将记录较长路径的信息。当搜索完成之后，如果最终得到的路径的代价小于t1，我们将根据较长的路径的信息来修正搜索到的路径，逐渐加大该路径的代价，来达到要求的t1。如图2所示：

图2 搜索的结果示例

搜索的顺序为 src->B，B->C，B->D，C->E，src->F，F->G，G->I，E->H，E->F，F->J，I->J，J->dest。其中，src->F->J->dest为搜索到的最短路径，E->F和I->J为搜索到的横向边，通过这两个横向边，我们可以恢复出三条其他的src到的dest的非最短路径，分别为：src->B->C->E->F->J->dest，src->F->G->I->J->dest，src->B->C->E->F->G->I->J->dest，这三条路径的代价均不小于搜索到的最短路径，如果这三条路径的代价位于[t1,t2]之间，那么我们就完成了搜索。

修正的A*算法是在A*算法完成搜索之后，对产生的横向边继续进行分析，找到由横向边构造的代价在[t1,t2]之间的路径。算法流程如图3所示。

2 实验数据

我们使用标准测试集中经过布局和布线之后依然存在HOLD问题的设计进行进一步的分析，实验通过调整A*算法的不同参数来找到合适的横向边来重建路径。

图3 算法流程

实验结果，如图4所示。横坐标为A*算法的代价因子，取值范围0.4～1之间。Size的含义是总共的横向边的数量，branch size的含义是在主要路径上的横向边的数量，delay的含义是重建后的路径将要延长的长度，这个值越大。就表明越容易修复HOLD问题。

图4 代价因子对结果的影响

可以看出，当代价因子的值大于0.7时，横向边的数量很少，路径长度很小当小于0.7时，横向边的数量按照指数增长，但是代价因子在小于0.7且大于0.4时，路径长度无明显增加，代价因子小于0.4时，横向边的数量急剧增大，但是在主要路径上的横向边的数量没有明显变化（可以看出在代价因子为0.4时，横向边数量为主要路径上的横向边数量的1000倍），因此没有列出。

图5是标准测试集中HOLD问题的设计中存在HOLD问题的设计，在代价因子设定为0.5时的横向边的数量，主要路径的横向边的数量和重建后的路径将要延长的长度。

图6 设计的详细结果

4 结语

本文提出了一种采用修正的A*算法来解决HOLD问题的思路，可以解决多数的HOLD违规的问题。我们还可以通过调整代价因子来提高主要路径的横向边的数量或者减少横向边的总数量。

主要路径的横向边的数量和横向边的总数量之间的关系尚不明确，需要进一步的实验和理论分析。从主要路径的横向边到重建后的路径，是另外的一个较简单的搜索问题，但是当主要路径的横向边数量较多时，需要一个复杂度较低的算法来完成。

[1]Betz V,Rose J.VPR:a New Packing,Placement and Routing Tool for FPGA Research[C].International Workshop on Field-Programmable Logic and Applications.Springer-Verlag,1997:213-222.

[2]L.McMurchie，C.Ebeling.PathFinder:A Negotiation-Based Performance-Driven Router for FPGAs.Third International ACM Symposium on Field-Programmable Gate Arrays,1995,pp.111-117.

[3]Virtex-2 FPGA User Guide，UG002：http://download.csdn.net/download/yangguanghaozi/9582746

[4]Guy G Lemieux,Stephen D.Brown.A Detailed Routing Algorithm for Allocating Wire Segments in Field-Programmable Gate Arrays.ACM/SIGDA Physical Design Workshop,1993,pp.215-226

[5]Cong J,Ding Y.Flowmap.An Optimal Technology Mapping Algorithm for Delay Optimization in Lookup-Table based FPGA Designs.IEEE Trans.on Computer-Aided Design of Integrated Circuits and Systems,1994,13:1-12.

[6]C.Y.Lee.An Algorithm for Path Connections and its Applications.IRE Trans.Electron.Comput.,01EC=10,1961,pp.346-365.

[7]G.Lemieux,S Brown.A Detailed Router for Allocating Wire Segments in FPGAs.ACM/SIGDA Ph)7sical Design Workshop，1993，pp.215-226.