一种基于图论的FPGA互连资源可测性设计

文 艺，郑咸剑

（1.电子科技大学自动化工程学院，成都611731；2.北京微电子技术研究所，北京100076）

一种基于图论的FPGA互连资源可测性设计

文 艺1，郑咸剑2

（1.电子科技大学自动化工程学院，成都611731；2.北京微电子技术研究所，北京100076）

针对SRAM型FPGA可编程互连资源可测性设计，采用图论中的Ford－Fulkerson算法开展双长线可测性建模与实现技术研究，研究如何实现可测性结构。在此研究基础上对双长线模型进行扩展，可解决四长线、六长线、八长线等其它复杂结构线段及开关的可测性问题。在Xilinx公司Virtex－II系列XC2V1000百万门FPGA上进行了验证。结果显示该方法可通过软件工具自动化开发测试图形，针对固定1和固定0两种故障模型，在较少的测试配置数量下即能获得较高的故障覆盖率。

SRAM型FPGA；可测性设计；互连资源；图论；Ford－Fulkerson算法；数学模型

1 引 言

随着数字集成电路集成度不断提高、可集成的功能日趋复杂，其可测试性也变得愈加困难，测试开销不断提升。因此，在复杂的数字集成电路设计中往往需采用可测性设计（以下简称DFT）技术来实现所集成功能尽可能地被测试。通常而言，在保证故障覆盖率的前提下，DFT技术主要有两个目标：①尽可能减少额外附加的硬件开销；②尽可能减少测试向量集合，缩短测试时间［1］。

目前，国内外针对ASIC的DFT技术已建立了相应流程和专用的DFT EDA工具，在ASIC设计阶段，采用专用DFT EDA工具在芯片内相关功能单元或周边接口插入专用测试电路结构，在测试过程中，由自动测试设备（ATE）对这些已插入的测试结构进行特定的功能测试［2－3］。采用DFT技术后，芯片的故障覆盖率一般都达到95%以上。

SRAM型FPGA 由于其内部资源的可编程性和边界扫描链的设计，本身即可为DFT构建必要的硬件基础，满足可测性设计的可控制性和可观察性要求。但与ASIC测试不同，FPGA测试结构无法简单应用现有的商用DFT EDA工具插入DFT结构，FPGA内部的每类资源在编程前是无特定功能的，需要可测试设计人员利用其可编程特性设计针对内部每类资源的测试配置图形，通常需要通过多次配置迭代以实现较高的故障覆盖率。目前针对SRAM型FPGA内部的可编程逻辑单元、输入输出单元以及内嵌IP核等资源的可测试设计技术研究已经取得可喜的进展，但对于可编程互连资源，当其数量较少时，很容易构建具有可控制性和可观察性的DFT结构（如使用FPGA中所有的输入输出单元为某一个可编程开关盒构建DFT结构），但当其数量较多时，可作为观测点的外部输入输出单元不足以构建覆盖所有可编程互连资源的DFT结构。并且随着器件规模越来越庞大，互连规律越来越复杂，互连资源测试面临着两方面的挑战：一是难以得到有效率的测试图形；二是穷举等方式需要耗费大量的人力成本且几乎不可实现。目前国内外针对上述问题开展了一定的研究：如伊利诺伊州大学Vishal Suthar使用的蛇形串联法［4］，奥本大学B.E.Dixon使用的回环法［5］等。这两种方法均属于基于规则图形的布线方法，这类方法依靠人工方法寻找由互连线段构成的局部可测性结构，再通过人工或软件方法将局部的可测性结构扩展到全局，得到全局的可测性结构。这类方法虽然实现比较简单，能够覆盖大部分的可编程互连线，但是对于大量的可编程互连点（下称PIP）难以遍历，不能保证互连资源整体的故障覆盖度。北京大学的赵建斌提出采用深度优先遍历算法遍历开关盒内所有PIP的方法［6］。这种方法适用于开关盒简单的Xilinx公司XC4000型FPGA产品，由于深度优先遍历算法固有的复杂度缺陷，随着开关盒复杂度的提高，采用该算法遍历开关盒的复杂度将呈几何倍数增长，导致难以获得最优化的可测性结构。

根据近年的研究，一些图论的相关知识可用于解决FPGA互连可测性的问题，其中用于解决最大流问题的Ford－Fulkerson算法可避免上述规则图形法、深度优先算法的固有缺点，并已在Xilinx公司Virtex型FPGA产品的单长线测试上获得应用［7］。本研究采用了Ford－Fulkerson算法构建可测性结构的方法，在Xilinx公司Virtex－II系列XC2V1000型FPGA产品的双长线、六长线等复杂结构线段及开关的可测试性设计上进行应用，实现了使用软件工具自动化开发测试图形，从而节省了人力成本，并提高了故障覆盖率。

2 SRAM型FPGA互连资源建模

Xilinx公司SRAM型FPGA是一种基于查找表（LUT）和触发器（FF）的岛型结构，这种结构也是目前最主流的SRAM型FPGA结构，主要由可配置逻辑模块（CLB）、输入输出单元（IOB）、存储单元、IP核及可编程互连资源等部分组成。这些可编程单元通过全局互连线（Global Line）、局部互连线（Local Line）和可编程开关盒（SM）等可编程互连资源相互连接［8］。

根据SRAM型FPGA互连线跨越逻辑块的数量分类，全局互连线通常包括双长线、四长线、六长线、八长线等类型。这些互连线除了跨越逻辑块的数量不同，结构及传递规律均类似，选择其中一种线进行研究，其结果可以进行参数化处理，并推广到其他类型的线段。在此以双长线为目标，构建一个具体的互连结构数学模型，以该模型为基础研究Ford－Fulkerson算法在互连资源可测性设计中的应用。

假设每个可编程开关盒中，以该开关盒为起点的双长线有四条（上下左右各一条），则进入该开关盒的双长线也为四条，可得开关盒模型如图1（a）所示。假设所建FPGA模型由m*n个图1（a）所示开关盒构成，取m、n为3，根据双长线特性，构建得到简化FPGA模型如图1（b）所示。将如图1（b）所示的模型放入二维坐标系中，可以得到如图1（c）所示的开关盒矩阵，每一个开关盒根据其所在的位置有对应的二维坐标（i，j）。以该开关盒为起点的双长线的终点开关盒的坐标（x（i），y（j））计算方式如公式（1）－（4）所示。由此构建了一个已知开关盒位置、相应互连关系及PIP分布情况的数学模型。

公式（1）为双长线向左传递时终点开关盒的坐标计算方式：

公式（2）为双长线向右传递时终点开关盒的坐标计算方式：

公式（3）为双长线向上传递时终点开关盒的坐标计算方式：

公式（4）为双长线向下传递时终点开关盒的坐标计算方式：

以上述数学模型为基础，研究如何将图论方法应用到该模型中，可大大简化图形设计和覆盖率统计的难度，协助理解真实结构的特点，实现复杂结构的可测性结构。

图1 简单双长线及其数学模型

3 测试图形的生成

通过图论中解决最大流问题的Ford－Fulkerson算法实现有效的SRAM型FPGA互连资源测试图形，将互连资源的PIP和互连线转换为最大流问题的点和边，从而将测试图形的设计问题转换为通过最大流算法寻找包含最多点和边的图形问题。

3.1 算法原理

人们通常用图对网络进行建模，网络的边输送某一类的流量，而结点起着在不同边之间通过流量的“开关”作用。例如，考虑一个公路系统，其中的边是公路，结点是交叉路口；或者一个计算机网络，其中边是可以发送数据包的连接线而结点是开关。或者一个管网，其中边是输送液体的管道，而节点是管道被连在一起的节点。这类型的网络模型有几个要素：边上的容量，指出它们可以运送多少流量；图中的源点，产生交通；图中的汇点，可以吸收到达的交通量。

将这种网络图抽象为在源点产生，通过边输送，并且在汇点被吸收的流。可以说一个流网络是具有如下特征的有向图G＝（V，E）：

（1）每条边e关联一个非负的值，称之为容量c；

（2）有向图中存在单一、包含于V的源点s；

（3）有向图中存在单一、包含于V的汇点t。

给定一个流网络，一个自然的目标就是安排交通以使得有效容量尽可能得到有效使用，故最大流问题即为：对于一个指定流网络，找出一个具有最大值的流。

给定一个流网络G以及G上的流f，可以定义G关于f的剩余图Gf：

（1）Gf的结点集与G的结点集相同；

（2）对G的每一条边e＝（u，v），其中f（e）＜ce，那么存在ce－f（e）的剩余容量单位，则Gf中也存在该条边，其容量为ce－f（e），并称之为前向边；

（3）对G中的每一条边e＝（u，v），其中f（e）＞0，当有必要时，可以通过向后推这个流来“撤销”它，因此在Gf中也包含边e′＝（u，v），其容量为f（e），并将该边称之为后向边；

（4）为了与初始流网络G中对应边的容量加以区分，将剩余图Gf中包含边的容量称为剩余容量。

其中Ford－Fulkerson算法能有效找出一个流网络的最大流，其算法原理如下所示。

此时得到的流f即为该流网络G的一个最大流。

最大流问题是在一个图形网络中，寻找出口和入口之间最大限度利用资源的图形，而SRAM型FPGA的互连测试寻求解决的问题与之类似。

3.2 测试图形生成的算法实现

对于一个SRAM型FPGA互连资源形成的网络，对该网络求得一个最大流，则该最大流所经过的路径即为单次配置所能遍历到的最多PIP和互连线。为了使用Ford－Fulkerson算法，需要将根据互连资源构建的数学模型转化为流网络。根据流网络的构造，在上述数学模型中添加虚拟的源点和汇点，并为每一条互连线和每一个PIP添加容量，具体转化规则如下：

（1）由于每一条互连线以及PIP同时只能传递一个信号，故每条边及PIP的容量均为1；

（2）图1（b）所示模型中的开关盒内部结构、功能均相同，故源点与汇点可设置在任一开关盒中。为了避免遗漏两个不同开关盒之间的线段，并方便后期添加BIST结构，将源点与汇点设置在同一个开关盒中。

根据以上规则，得到由图1（b）转化得到的部分流网络如图2所示。

对该流网络执行Ford－Fulkerson算法，获得一个通过该流网络的最大流量，由于此处有实际意义的通道（互连线与PIP）容量均为1，所以也就是获得一个使用最多数目边的测试路径。降低第一次运行最大流算法获得的测试路径上的由PIP构成的边的优先级，获得一个新的流网络，多次运行最大流算法，直到所有的PIP均已遍历。此时即获得一个资源覆盖率为100%的测试路径集合。

图2 FPGA模型部分流网络示意图

由于源点和汇点是算法虚拟出的点，实际生成的最大流测试图形仅含有互连线段和PIP，如图3（a）所示，故需要在测试图形中加入大量输入输出单元模拟源点和汇点，形成完整的测试配置，如图3（b）所示。根据上文规定流网络的源点和汇点均在一个开关盒内，且对于SRAM型FPGA而言，一个开关盒通常通过局部互连线与多个输入逻辑单元相连，使用这些逻辑单元构建BIST结构的激励生成器（TPG）和输出响应分析器（ORA），可以将源点和汇点压缩到少量的CLB单元中，从而节约了大量输入输出资源，降低了向量复杂度。BIST结构如图3（c）所示。

图3 测试路径及BIST结构

综上，针对上述构建的简单双长线模型，通过最大流算法得到了一个优化的测试向量集。

4 模型扩展

在实际应用中，SRAM型FPGA内部的双长线数量远多于图1（b）所示的简化模型的双长线数量。在此以实际系统中应用最广泛的Xilinx公司Virtex－II系列XC2V1000产品为例，将3*3的简化模型扩展为42*38的真实模型，使用Ford－Fulkerson算法，获得一个优化的测试向量集。

XC2V1000结构如图4（a）所示，为一个42*38的矩阵，即m＝42，n＝38。统计得到以其中一个开关矩阵为起点的双长线数量为40条，将这40条双长线按照不同的传递方向以及相互之间的位置分为10组，每组4条双长线（上下左右各一条），同时将相应的以该矩阵为终点的双长线（同样为40条）加入到这10组中。对这10组双长线中的任意一组建模，均能得到与图1（a）所示开关盒相类似的模型。这样，一个复杂的由80条双长线构成的开关矩阵，可以分解为10层的与图1（a）类似的矩阵模型。即将一个42*38的互连资源模型分解为10层与图1（b）所类似的互连关系模型，如图4（b）所示。对该10层模型中的每一个图层进行最大流求解，可得到相对于每一个图层的优化测试路径集合。

图4 XC2V1000结构图及其模型

在得到一系列的最优化测试路径后，可以通过如下规则叠加图层以减少最终的测试配置数量：

（1）若两个测试路径完全没有重叠，则可叠加；

（2）若两个测试路径重叠的互连线均作为扇出端，则可叠加，否则不可叠加。

根据以上分析，整个测试配置生成的流程如图5所示。其中WUT（Wires Under Test）指的是待测试的互连资源图形。

图5 测试配置生成流程图

5 实现与验证

以Xilinx公司Virtex－II系列XC2V1000百万门FPGA产品为目标器件进行了设计实现与验证，获得了针对双长线的有效测试向量。对10个图层执行Ford－Fulkerson算法之后，获得40条测试路径，通过叠加图层，最终得到有36个测试配置的测试向量集。该模型中的所有待测点均在36次测试中得到覆盖，因此该测试向量集针对固定0及固定1等故障的故障覆盖率能达到100%。由于其他类型线与双长线为平行关系，双长线的测试图形可以与其他类型线的测试图形进行叠加，从而减少整个互连资源测试向量集的数目。如图6为其中某一个测试配置的布线图形。

使用软故障注入的方法（修改码流，插入人为断点），对该测试配置进行验证，可以得到如图7所示的波形，插入到CLB结构中的响应收集器将错误信息以高电平形式反馈到输出端。通过故障注入软件对100%的双长线开关进行了遍历，结果表明，双长线的全部故障均可被检测。

图6 XC2V1000型FPGA双长线资源的某个测试配置

图7 仿真波形

6 结束语

研究了图论中的Ford－Fulkerson算法在构建FPGA互连资源可测性设计中的应用，并在Xilinx公司XC2V1000百万门FPGA产品中进行了验证，形成了有效的可测性结构。所研究的方法具有一定的通用性，可以方便地应用到其他类型的互连线段测试图形设计中，所生成的测试图形针对固定1和固定0两种故障模型可获得较高的故障覆盖率。由于各类型线段的数学模型相互独立，因此，各类型线段的测试图形可以进一步叠加，压缩整体的配置数量。可以看到利用最大流相关的Ford－Fulkerson算法来寻找和构建互连资源的可测性结构是一种灵活、方便、高效的方法。

［1］ 王厚军.可测性设计技术的回顾与发展综述［J］.中国科技论文在线，2008，3（1）：52－58.

Wang Houjun.Reviews of Testability Design Technology［J］.China Science Paper Online，2008，3（1）：52－58.

［2］ Williams M J Y，Angell J B.Enhancing Testability of Large－scale Integrated Circuits via Test Points and Additional Logic［J］.IEEE Transactions on Computers，1973，c－22（1）：46－60.

［3］ 韩威，江川.ASIC集成电路的可测性设计与技术实现［J］.计算机科学，2009，36（4）：289－292.

Han Wei，Jiang Chuan.Design for Testability and Implement Technology in ASIC Design［J］.Computer Science，2009，36（4）：289－292.

［4］ Suthar V，Dutt S.Efficient On－line Interconnect Testing in FPGAs with Provable Detectability for Multiple Faults［C］.//Design，Automation＆Test in Europe，Date，2006，1：1－6.

［5］ B.E.Dixon Jr，Built－In Self－Test of the Programmable Interconnect in Field Programmable Gate Arrays［D］.Auburn：Auburn University，2008.

［6］ Zhao J，Feng J，Lin T，et al.A Novel FPGA Manufactureoriented Interconnect Fault test［C］.//Solid－State and Integrated－Circuit Technology，ICSICT 2008：2091－2094.

［7］ M.B.Tahoori，Test FPGAs［D］.California：Stanford University，2003.

［8］ Xilinx，Inc.Virtex－II Platform FPGAs：Complete Data Sheet，DS031（v3.5）［Z］，2007.

Design for Testability of FPGA Interconnect Resources Based on Graph Theory

Wen Yi1，Zheng Xianjian2
（1.School of Automation Engineering，University of Electronic Science and Technology of China，Chengdu 611731，China；2.Beijing Microelectronics Technology Institute，Beijing 100076，China）

Aiming at constructing an effective test pattern for SRAM－based FPGA interconnect resources，a graph theorymethod，called Ford－Fulkerson arithmetic，is applied in a simplified doublelinemathematic model to research the effective design for testability.The testability of other complicated segment lines and switches in SRAM－based FPGA，such as quad lines，hex lines and octal lines，can be obtained by expanding the double－line model.The method is verified in one kind of Virtex－II platform FPGA called XC2V1000，and the results indicate that the test patterns can be generated automatically through software tools and a high fault coverage rate are achieved with a small number of test configurations for stuck－at－0 fault and stuck－at－1 fault.

SRAM－Based FPGA；Design for testability；Interconnect resources；Graph theory；Ford－Fulkerson arithmetic；Mathematic model

10.3969/j.issn.1002－2279.2015.06.003

TN79

A

1002－2279（2015）06－0009－06

文艺（1990－），女，北京市人，硕士研究生，主研方向：宽带时域测试技术与仪器。

2015－04－28