基于关键路径的FPGA时序电路最大工作频率测试方法

袁靖茹，杨 震，刘 威，王 健，来金梅

（复旦大学 专用集成电路与系统国家重点实验室，上海 201203）

为了满足应用电路日益复杂的资源和性能需求，现场可编程门阵列（Field Programmable Gate Array，FPGA）在不断扩大可编程逻辑阵列的同时，也在阵列中插入了各种可编程知识产权（Intellectual Property，IP）核，使得FPGA 能实现更多高性能的复杂电路.与此同时，面对专用集成电路（Application Specific Integrated Circuit，ASIC）巨大的设计风险和昂贵的流片成本，芯片设计者开始在FPGA 上直接进行电路设计.在时序电路设计的众多指标中，最大工作频率是最重要的指标之一，它直接反应了所设计时序电路的运行速度.这就要求电路原型设计者针对在FPGA 上实现的时序电路进行最大工作频率的测试.

业界常规的测试时序电路最大工作频率的方法一般是基于各类测试设备［1－2］实现的，比如输出结果采样设备等.然而，当测试设备的能力不能满足待测电路的需求时，测试将无法正确进行.举例来说，当测试结果输出的频率超过了设备的最高采样频率时，设备将无法采样该结果，这就使得测试结果出现误差.此外，常规的方法需要针对待测电路开发一套测试激励（A Suit of Test Patterns，ASTP）.每个测试激励会在逐渐升高或降低的时钟频率下对待测电路进行测试.能使得ASTP测试通过的最大时钟频率就是待测电路在该ASTP下的最大工作频率.然而，这个最大时钟频率会随着ASTP的变化而出现测试误差.文献［3］中的实验结果显示，在不同的ASTP下，同一待测电路的最大工作频率的测试结果会出现7MHz的偏差.并且，随着所设计的电路规模不断变大，开发ASTP将会变得越来越困难，因此，测试前相关准备工作的自动化实现显得尤为重要.

为了解决上述问题，本文提出了一种通过构建内建自测试（Build－In，Self－Test，BIST）电路测试FPGA 时序电路最大工作频率的方法.本文不再对整个时序电路添加ASTP进行测试，而是先从时序电路中抽取关键路径，然后在关键路径两端构建BIST 电路并为其添加测试激励.针对单一路径的测试激励只有一种情况，利用由0到1的激励测试上升延迟，由1到0的激励测试下降延迟.这不仅省去了针对不同电路开发测试激励的过程，还避免了由不同的测试激励而导致的测试误差的问题.同时，本文采用了两项技术来保证关键路径抽取过程的正确性：（1）修改查找表逻辑函数，屏蔽查找表上非关键路径的输入端，保证查找表功能的正确性；（2）处理逻辑单元的多扇出负载，使得关键路径附近的逻辑资源不会被占用，以便BIST 电路能构建在关键路径两端，保证BIST 电路测试的路径与时序电路关键路径完全相同.此外，本文利用C＋＋语言开发了一个软件平台（Software Platform，SP），对时序电路实现自动化抽取关键路径和构建BIST 电路的功能，大大降低了测试前构建BIST 电路的时间和劳动力成本.最后，与消除了由测试激励带来的误差的常规方法相比，本文提出的测试方法的平均误差为2.7%.

1 测试方法介绍

本文提出的测试方法通过3个步骤对时序电路进行最大工作频率测试.第一，确定时序电路的关键路径.根据时序电路的静态时序分析报告，将延迟最大的路径定义为关键路径.第二，从时序电路中自动抽取关键路径.第三，在关键路径两端自动构建BIST 电路并为其添加测试激励，进行关键路径延迟测试.

1.1 关键路径抽取策略

常规的测试方法针对不同的待测电路需要开发特定的测试激励，对于同一待测电路而言，这类测试激励可以有多种.不同开发者针对同一待测电路开发的测试激励一般不相同，这就导致了测试结果出现误差.由于时序电路的最大工作频率是由关键路径延迟确定，本文提出先将关键路径从时序电路抽取出来，再对其添加激励进行测试的方法.对于抽取出来的关键路径来说，测试激励只有一种，这样就避免了由不同的测试激励引起误差的问题.在关键路径的抽取过程中，本文提出了两项技术来保证关键路径抽取的准确性，这两项技术分别为修改查找表逻辑函数和处理中间逻辑单元的多扇出负载，下文将对其详细说明.

1.1.1 修改查找表逻辑函数

在抽取关键路径上的逻辑单元时，需要屏蔽逻辑单元中不在关键路径上的输入端.FPGA 中的逻辑函数由查找表（Look Up Table，LUT）实现，然而，查找表中只有部分输入端位于关键路径上，而不在关键路径上的输入端，会对关键路径延迟测试产生影响.以5个四输入LUT 和其互联线为例，如图1所示.每个LUT 有4个输入端，其中只有1个输入端位于关键路径上，另外的3个输入端不在，它们是由时序电路中非关键路径上的逻辑单元驱动.在抽取关键路径时，所有的输入端口都会被抽取，但是驱动那些不在关键路径上的输入端口的逻辑单元不会被抽取.这就导致了这些输入端悬空，如图1（a）所示，从而出现不确定的电平影响测试准确进行的问题.为了避免这类问题，在抽取关键路径时，本文将修改LUT 的逻辑函数，使其与这三个输入端无关.修改时保留该逻辑函数与关键路径信号的逻辑相关性［4］，从而保证了路径的输出与输入间的逻辑相关性.由于这种修改方式可能带来的延迟变化很小，相关文献［4］中也是采用类似的方法对查找表的逻辑函数进行处理.

图1 LUT 逻辑函数的修改Fig.1 Modification of the LUT logic function

假设LUT 的4个输入端口分别为A1，A2，A3，A4，其中A1是位于关键路径的输入端口，LUT 的原始逻辑函数为f（A1，A2，A3，A4）.本文根据当A2，A3，A43个端口输入任意逻辑信号时，原始逻辑函数的结果对逻辑函数进行修改.当f（x）的取值只有0／1／A1这三种时，这说明LUT 的逻辑函数与A1的相关性为正相相关，此时将该LUT 的逻辑函数修改为f（A1）＝A1，其功能相当于一个缓冲器，如图1（b）中的查找表A 所示；当f（x）的取值只有这三种时，这说明LUT 的逻辑函数与A1的相关性为反相相关，那么将该LUT 的逻辑函数修改为f（A1）＝，其功能相当于一个反相器，如图1（b）中的查找表B所示.当f（x）的取值有4种时，说明LUT 的逻辑函数与A1的相关性为两相相关，那么将该LUT的逻辑函数修改为f（A1，A2）＝A1⊗A2，其功能相当于一个异或门，如图1（b）中的查找表C 所示.此时A2信号连接到一个IO 口，通过外部添加0／1信号控制逻辑单元C的相关性.

图2 处理中间逻辑单元的多扇出负载Fig.2 Multi－fanout load for middle logic elements

1.1.2 处理中间逻辑单元的多扇出负载

负载是在实际电路中影响逻辑单元延迟的因素之一，负载的大小或者数量变化会引起逻辑单元延迟的变化.时序电路关键路径上逻辑单元的负载可能有多个，如图2所示.由A、B、C、D 及之间的互连线构成的关键路径上，A 有4个负载B、E、F、G，其中只有B 位于关键路径上；B有2个负载C、H，其中只有C 位于关键路径上.为了保证关键路径抽取前后，其延迟保持不变，抽取出的关键路径需要保留该路径上的所有负载.但是，这些负载会占用关键路径附近大量的逻辑资源，从而限制了之后BIST 电路的构建.

在FPGA 的硬件结构上，每个可编程逻辑单元（Configurable Logic Block，CLB）都有与之对应的一块局部互联，用以实现CLB之间可编程的连接［5－6］.CLB中每个输入信号均来自该局部互联，并由其中对应的缓冲器驱动.所以，关键路径上每个逻辑单元的负载实际上是输出线网及线网末端局部互联上的缓冲器，而逻辑单元E、F、G、H 并没有充当负载.因此，这部分不在关键路径上的负载逻辑单元是可以去除的，从而大大的简化了关键路径.这时，除了关键路径所占用的CLB以外，整个FPGA 中的CLB都可以用于之后BIST 电路的构建.这就保证了BIST 电路可以构建在关键路径两端，从而保证关键路径延迟测试的准确性.

1.2 BIST电路构建

本文在上述抽取出来的关键路径两端，构建BIST 电路用于延迟测试.为了解决常规测试方法依赖于测试设备的问题，本文借鉴了文献［4，7］的BIST 电路结构，提出了如图3所示的BIST 电路结构.该BIST电路包括3 个模块，分别为序列发生器（Sequence Generator）、待测路径模块（PUT）和结果分析模块（Response Analysis Block）.其中，从时序电路中抽取出来的关键路径就连接到PUT 模块中的AB两端.在时钟信号CLOCK 的作用下，序列发生器输出端SGO 产生0／1的序列，为关键路径提供测试激励.

图3 BIST 电路结构Fig.3 Architecture of BIST circuit

PUT 中的触发器FFS传递来自序列发生器的激励信号，在某个时钟沿来临时，关键路径A 端出现0到1或1到0的变化，从而为关键路径添加0到1或1到0激励.在下一个时钟沿来临时，触发器FFD 采样关键路径B端的逻辑值，并将采样结果通过RAI传入结果分析模块中.若关键路径的传播延迟小于CLOCK 的时钟周期，FFD 采样到的是正确值；若关键路径的传播延迟大于CLOCK 的时钟周期，FFD 采样到的是错误值.在不断提高BIST 电路时钟频率的情况下，当FFD 采样到的值从正确变为错误时的时钟周期就是关键路径的延迟.

从BIST 电路结构可以看出，除了需要外部信号发生器产生测试时钟外，整个测试过程不需要其他测试设备，这就避免了由于测试设备能力不足带来的测试限制的问题.

2 软件平台

本节通过C＋＋语言构建了一个软件平台，该平台可以实现对时序电路抽取关键路径并构建BIST电路的过程，有利于降低测试前构建BIST 电路的时间和劳动力成本.该软件平台根据时序电路关键路径信息、时序电路网表、BIST 电路模板网表和FPGA 硬件结构描述文件，通过抽取时序电路关键路径上的逻辑单元和线网、修改查找表逻辑函数、处理多扇出负载、构建BIST 电路、布线连接BIST 电路与关键路径，最终产生能测试该时序电路关键路径延迟的BIST 电路网表，整个软件流程的伪代码如图4所示.

图4 软件平台的伪代码Fig.4 The pseudocode in the software platform

图4（a）描述了提取时序电路关键路径的逻辑单元和互联线网的过程.CPI来自外部输入的关键路径信息文件，包括关键路径上所有（n 个）逻辑单元的名称、位置、输入输出端口、负载线网名等，CPI＿i是CPI 中第i个逻辑单元的信息.NETLIST 是来自外部输入的时序电路网表文件.提取逻辑单元的过程是根据CPI中关键路径上第i个逻辑单元的名称和位置，在NETLIST 中查找得到该逻辑单元的原始配置Config＿i，其中包含各个编程点信息和查找表的初始逻辑函数.继而根据CPI中该单元接入关键路径的端口信息与Config＿i信息，修改查找表逻辑函数并生成新的配置Config＿i＿new，该配置只打开了与关键路径上逻辑单元相关的编程点，而关闭了Config＿i中与关键路径上逻辑单元无关的编程点.当处理第1个和第n个逻辑单元时，Config＿1＿new 和Config＿n＿new 需要打开触发器的编程点，将时序电路关键路径两端现成的触发器分别作为BIST 电路中的FFS和FFD，这是为了保证BIST 的待测路径与时序电路的关键路径完全相同.最后根据Config＿i＿new 重新产生第i 个逻辑单元的网表Inst＿i.提取关键路径中互联线网的过程是根据CPI中关键路径上第i个逻辑单元的负载线网名称，在NETLIST 中查找得到该线网网表NET＿i，它描述了该负载线网上各个逻辑单元的驱动关系和之间的线网.然后，保留NET＿i中全部线网和CPI 中第i和第i＋1个逻辑单元的驱动关系，而将线网其他末端的被驱动逻辑单元去除，最后产生修改后的第i个逻辑单元的负载线网网表NET＿i＿new.将n个逻辑单元的网表Inst＿i（i＝1，2，…，n）和n－1个负载线网网表NET＿i＿new（（i＝1，2，…，n－1）整合形成BIST 的待测路径，也就完成了对时序电路关键路径的抽取过程.

图4（b）描述了把上文得到的待测路径两端接入测试电路，最后产生完整的BIST 测试电路的主要流程.在实验室过去研究成果中，已经实现了布线资源图（Routing Resource Graph，RRG）的构建以及FPGA 布线程序.由于本文的着重点在于研究时序电路最大工作频率的测试方法，而不是RRG 和布线程序的实现，所以相关程序的算法和实现方法请部分参考文献［8］.布线资源图是将FPGA 硬件描述文件上的信息在计算机内存中构建成的一种图的数据结构，该图描述了这款FPGA 芯片的物理资源数量、种类、结构及其相互之间的连接关系等信息.BIST＿inst和BIST＿net是从预先设计的BIST 模板电路网表文件中读取的，分别描述的是实现BIST 测试电路用到的逻辑单元和互连线网.从时序电路关键路径的抽取过程可以看出，BIST 测试电路中的触发器FFS和触发器FFD 的物理位置是随着时序电路关键路径的位置变化而变化的，因此，BIST 模板电路网表中不包含触发器FFD 和FFS的物理信息.到目前为止，软件已经产生了含有触发器FFS、FFD 的待测路径和缺少触发器FFS、FFD 的BIST 这两块单独的电路网表.而完整的BIST 测试电路需要将待测路径两端的触发器FFS、FFD 分别连接到BIST 模板电路中的RD 和SQ 节点.因此，通过应用文献［8］中的布线程序将待测路径连接到BIST 模板电路中，如图4（b）所示.与FPGA 中一般布线过程不同的是，本布线过程不能使用待测路径和BIST 模板电路所占用的线网节点.因此，在布线之前，需要通过查找RRG 将待测路径中互连线NET＿i＿new（（i＝1，2，…，n－1）和BIST＿net上的线网节点，并分别将其转换成布线算法使用的数据类型NET＿i＿HopUnit和BIST＿HopUnit，并将该线网节点定为已使用的线网节点Occupied＿HopUnit.在使用广度优先的布线算法搜索线网节点时，若某些节点已经在Occupied＿HopUnit中被占用，则这部分节点就不参与布线，布线结果与待测路径和BIST 模板电路就不会发生资源冲突.最后，经过整合待测路径网表、BIST 模板电路网表和布线结果即可产生用于时序电路关键路径延迟测试的完整的BIST 电路.

3 实验结果

以Xilinx Virtex－4LX15芯片［9］为例，本文用30个MCNC［10］和6个OpenCores［11］的测试用例对软件平台和关键路径抽取策略进行验证.最后，在同一组待测电路上，就本文提出的测试最大工作频率的方法和常规的测试方法进行对比测试.由于常规的测试方法存在由不同的测试激励带来的误差，本文专门将待测电路设计为只有一个输入端口（时钟输入）.常规方法对该电路进行测试时，不需要开发测试激励，这就避免了由不同的测试激励所带来的误差，从而更有利于验证本文的测试方法的准确性.

3.1 软件平台正确性验证

本节将验证上文的软件平台能否实现对时序电路关键路径的抽取并在关键路径两端构建BIST 电路的过程，最后输出完整的BIST 电路网表.根据时序电路网表和静态时序分析得出的关键路径信息，该软件平台抽取时序电路的关键路径，并完成修改逻辑函数与处理多扇出负载两项技术，继而根据FPGA 芯片硬件描述文件和BIST 电路模板文件在关键路径两端构建BIST 电路.为了保证该平台实现上述过程的正确性，本文基于Xilinx Virtex－4LX15芯片的硬件描述文件，用软件平台对36 个不同资源覆盖率的时序测试用例实现上述过程.

表1中列出的验证用例的资源覆盖率不具有特殊性，主要是来自行业常用的MCNC 和OpenCores的测试用例.实验结果表明，该软件平台成功的实现了关键路径的抽取和构建BIST 电路的过程，使得整个测试电路的构建流程得以自动化产生.

表1 软件平台的验证Tab.1 Verification for software platform

3.2 关键路径抽取结果

由于关键路径抽取过程中删除了中间逻辑单元的多扇出负载逻辑单元，为了验证该变化是否会造成BIST 电路中实际待测路径延迟与时序电路关键路径延迟不一致，本节将使用Xilinx的ISE 设计套件中静态时序分析软件（Timing Analyzer［12］）分别对软件平台产生的BIST电路中的待测路径、时序电路的关键路径进行静态时序分析.本文抽取关键路径的方法不依赖于时序电路的功能和结构，因此，验证用例选用行业内常用的7 组MCNC测试用例.相对于Xilinx Virtex－4LX15芯片的最大时钟频率为500MHz，这七组测试用例关键路径延迟的验证范围从3.230ns到12.469ns，能代表该芯片上实现的大多数时序电路的情况，因此，本测试用例的验证结果具有代表性.

表2列出了Timing Analyzer对每个测试用例的关键路径延迟与对应的BIST 电路中待测路径延迟的对比数据.实验数据显示每组验证用例的关键路径与BIST 的待测路径延迟完全相同，这说明了本文提出的抽取关键路径的方法保证了BIST 电路的待测路径延迟与时序电路关键路径延迟的一致性.同时，从实验结果可以看出，由修改查找表逻辑函数而引起的误差很小，在Timing Analyzer分析的精度范围内，该误差不能在路径延迟的大小中反应出来.

表2 关键路径延迟与BIST待测路径延迟对比Tab.2 Comparison between the PUT in BIST and the critical path

3.3 最大工作频率对比测试结果

为了验证本文提出的测试FPGA 时序电路最大工作频率方法的准确性，在同一组待测电路上，就本文提出的测试最大工作频率的方法和常规的测试方法进行对比测试.由于常规的测试方法存在由不同的测试激励带来的误差，本文专门将待测电路设计为只有一个输入端口（时钟输入）的电路——加法器AB电路.常规方法对该电路进行测试时，不需要开发测试激励，这就避免了由不同的测试激励所带来的误差，从而更有利于验证本文的测试方法的准确性.

逻辑上，该电路含有A、B两组加法器.在每个时钟周期内，这两组加法器分别完成一次加法运算并比较两组加法器计算的值是否相等，继而输出比较结果.在时钟频率较低时，两组加法器内部时序正常，输出结果符合预期.当不断提高时钟频率，直到该电路中某条路径出现时序异常，输出结果将不符合预期，这时的输入时钟频率即是该电路的最大工作频率.

该加法AB电路的结构如图5所示，由AB两组加法器组成，A 组加法器由5个A 类型的的加法宏单元构成，每个加法宏单元实现自加功能；B组加法器是由一个B类型的加法器实现，该加法器也是实现自加功能.A／B两组加法器的加数为任意正整数，满足的关系为：DB＝D0＋D1＋D2＋D3＋D4.在每个时钟周期内，A 组的5个加法器A＿n首先分别自加Dn，再将5个加法器A＿n的和加起来得到S＿A；同时，B组加法器实现加数为DB的自加功能得到S＿B，最后将AB两组加法器的和进行对比，在下一个时钟沿来临时对S＿A 和S＿B的对比结果采样输出.当时钟频率较低时，对比结果会显示S＿A 和S＿B是相同的.但是，随着时钟频率的增加，当时钟频率大于最大工作频率时，时序错误将会引起某组加法器的结果计算错误从而导致S＿A 和S＿B的对比结果为不相同.

基于Xilinx Virtex－4LX15芯片，本文设计了5种不同规模的加法器AB电路，N 分别为32，64，128，256，512.首先通过对该组电路不断提高时钟频率测试得到由常规方法测得的最大工作频率F＿common，再通过本文提出的测试方法测得该组电路的最大工作频率F＿BIST.对于此类研究，业界可接受小于5%［4］的误差范围.如表3所示，与F＿common相比，F＿BIST 的平均差异为2.70%，最低低至1.60%.

图5 加法器AB电路结构Fig.5 Architecture of adder AB

表3 F＿common与F＿BIST 对比Tab.3 Comparison between F＿commonand F＿BIST

该测试误差主要来自于3个方面：（1）是由静态时序分析软件带来的，静态时序分析软件可能将时序电路的次关键路径计算为了关键路径，目前的静态时序分析软件的准确度较高，带来的误差是很小的；（2）是由修改查找表的逻辑函数引起的误差，该误差引起的延迟变化的最差情况为5%左右［4］；（3）在两种方法测试中，都由外部信号发生器向PCB板添加时钟信号，由测试过程带来的偶然误差也可能导致两种测试结果存在少量的差异.从本文使用的ISE 自带的时序分析软件Timing Analyzer来看，本文的方法在只有2.70%的测试误差下，可以获得以下两个方面的优势：（1）整个测试不再需要针对不同的待测时序电路开发测试激励；（2）本测试方法几乎不依赖于测试设备，可适用于在FPGA中实现的所有时序电路.

4 结论

本文设计了一种基于关键路径抽取策略，构建BIST 电路测试时序电路关键路径延迟，计算得到FPGA 时序电路最大工作频率的方法.该方法根据时序电路的静态时序分析结果，从时序电路中抽取关键路径，并采用了两项技术来保证关键路径抽取过程的正确性.随后在关键路径两端构建BIST 电路并为其提供测试激励，测试关键路径延迟.最后计算关键路径延迟的倒数得到该时序电路的最大工作频率.此外，本文设计了一个C＋＋软件平台，该平台能对时序电路自动抽取关键路径并构建BIST 电路，大大的降低了测试前构建BIST 电路的时间和劳动力成本.实验表明，与消除了测试激励带来的误差的常规测试方法相比，本文提出的测试方法的平均误差仅为2.70%.同时，本文的测试方法获得了两个优势：（1）整个测试不再需要针对不同的待测时序电路开发测试激励；（2）本测试方法几乎不依赖于测试设备，可适用于在FPGA 中实现的所有时序电路.

［1］LEE J W，CHUN J J，ABRAHAM J A.Indirect method for random jitter measurement on SOCs using critical path characterization［C］∥Test symposium（ETS），IEEE European.Annecy，France：IEEE Press，2012：1－6.

［2］BALAJEE S，MAJHI A K.Automated AC（Timing）characterization for digital circuit testing［C］∥Proceedings of international conference on VLSI Design.Chennai，India：IEEE Press，1998：374－377.

［3］QIU W Q，WALKER D.M.H，SIMPSON N，et al.Comparison of delay tests on silicon［C］∥Test Conference on IEEE.Santa Clara，CA：IEEE Press，2006：1－10.

［4］MENON P R，XU W F，TESSIER R.Design－specific path delay testing in Look Up－Table－Based FPGAs［J］.IEEE Transaction on Computer－Aided Design of Integrated Circuits and Systems，2006，25：867－877.

［5］FAROOQ U，MARRAKCHI Z，MRABET H，et al.The effect of LUT and cluster size on a tree based FPGA architecture［C］∥Reconfigurable Computing and FPGAs.Cancun，Mexico：IEEE Press，2008：115－120.

［6］AHMED E，ROSE J.The effect of LUT and cluster size on deep－submicron FPGA performance anddensity［J］.IEEE Transaction on Very Large Scale Integration（VLSI）System，2004，12（3）：288－298.

［7］HARRIS I G，MENON P R，TESSIER R.BIST－Based delay path testing in FPGA architectures［C］∥Test Conference on IEEE.Baltimore，MD，USA：IEEE Press，2001：932－938.

［8］朱 春，来金梅.高压缩性FPGA 布线资源图与并行布线算法的设计与实现［D］.上海：复旦大学，2012.

［9］Xilinx Inc.Virtex－4FPGA datasheet［EB／OL］.（2010－08－30）［2015－03－27］.http：∥www.xilinx.com／support／documentation／data＿sheets／ds112.pdf.

［10］BRGLEZ F.The benchmark archives at CBL［EB／OL］.（1996－05－01）［2015－03－27］.http：∥www.cbl.ncsu.edu／benchmarks／Benchmarks－upto－1996.html.

［11］OpenCores.org.OpenCores benchmarks［EB／OL］.［2015－3－27］.http：∥opencores.org／forum／.

［12］Xilinx Inc.Timing analyzer［EB／OL］.［2015－3－27］.http：∥www.xilinx.com／.