一种fpga中的可配置互连节点的测试方法
技术领域
1.本技术涉及fpga技术领域，尤其是一种fpga中的可配置互连节点的测试方法。
背景技术：
2.可编程逻辑器件(fpga，field programmable gate array)具有开发周期短、成本低、风险小、集成度高、灵活性大且便于电子系统维护和升级等优点，因此成为了数字芯片的主流，被广泛应用在通信、控制、视频、信息处理、消费电子、互连网、汽车、航空航天、大数据以及人工智能等诸多领域。
3.除一些专用的进位逻辑或者功能扩展相关通道外，fpga内部不同的功能模块(诸如clb、io、dsp、bram等)之间主要通过互连资源相连。互连资源包括开关矩阵(swb)以及互连线，互连线用于实现功能模块与相应的开关矩阵的输入输出端之间的连接、以及用于实现不同开关矩阵的输入输出端之间的连接。开关矩阵的底层实际包括大量的pip(programmable interconnect points，可编程互连点)，用于通过配置打通经过该处的互连线间的互连。请参加图1所示的单个开关矩阵的互连示意图，开关矩阵外部的连线1～16分别表示该开关矩阵连接的16条互连线，开关矩阵内部的每一条虚线分别表示一个可选的通路就是一个pip，而其真实电路的通常实现方式是，一个选择端由配置sram控制的多路选择器来实现多个去向相同的pip的功能。图1仅是示例，在实际应用时，fpga内包含大量的开关矩阵，每个开关矩阵可以连接大量的互连线，开关矩阵内部也包括大量的pip，互连资源占据整个fpga的大部分电路面积(大约50％～90％)，是fpga资源中发生故障概率最高的部分，这其中又以pip的故障为概率最高的部分，因此pip的可靠性直接影响了整个fpga的运行可靠性。
4.所以目前在fpga的设计开发过程中，往往需要对可配置互连节点进行测试，传统的测试方法主要是利用fpga中的可编程逻辑块来实现内建自测试通路，或者通过将可配置互连节点进行分类后处理等等，但现有传统的这些测试方法对于fpga的芯片架构的依赖性很强，需要针对特定的芯片架构来设计测试用例，测试效率和通用性较低。
技术实现要素：
5.本技术人针对上述问题及技术需求，提出了一种fpga中的可配置互连节点的测试方法，本技术的技术方案如下：
6.一种fpga中的可配置互连节点的测试方法，该测试方法包括：
7.将fpga内的每条互连线抽象为每个顶点、将fpga内的每两条互连线之间的可配置互连节点抽象为相应的两个顶点之间的有向边，构建得到用于表征fpga内的互连线与可配置互连节点之间的连接关系的有向图；
8.初始化若干个输入顶点和若干个输出顶点，输入顶点是具有激励施加功能的互连线对应的顶点，输出顶点是具有信号采集功能的互连线对应的顶点；
9.基于有向图搜寻测试通路，测试通路以其中一个输入顶点为信号输入端、以其中
一个输出顶点为信号输出端，且包括从信号输入端到信号输出端之间的顶点和有向边；
10.重复执行基于有向图搜寻测试通路的步骤，直至测试覆盖率达到预定阈值时，得到包括若干条测试通路的测试用例，在测试用例中的各条测试通路的信号输入端处施加激励信号、并在对应的信号输出端处采集响应信号，完成对fpga中的可配置互连节点的测试。
11.其进一步的技术方案为，基于有向图搜寻测试通路，包括：
12.随机选取任意一个输入顶点初始化为当前顶点；
13.基于有向图搜寻当前顶点连接的一条有向边作为候选有向边；
14.当候选有向边连接的另一个顶点不是输出顶点时，以候选有向边连接的另一个顶点作为更新后的当前顶点并重新执行在有向图中搜寻当前顶点连接的一条有向边作为候选有向边的步骤；
15.当候选有向边连接的另一个顶点为输出顶点时，完成搜寻并得到一条测试通路，测试通路包括初始化的输入顶点和确定得到的输出顶点以及中间依次经过的若干条候选有向边。
16.其进一步的技术方案为，对于任意一个当前顶点，当前顶点所连接的候选有向边在当前顶点连接的全部有向边中使用次数最少、且候选有向边连接的另一个顶点在测试用例中未被使用过。
17.其进一步的技术方案为，有向图中全部有向边的使用次数初始化为0，基于有向图搜寻当前顶点连接的一条有向边作为候选有向边包括对于任意一个当前顶点：
18.基于有向图按照使用次数从小到大的顺序依次遍历当前顶点连接的各条有向边，对于遍历到的任意一条有向边：
19.当确定遍历到的有向边连接的另一个顶点在测试用例中未被使用过时，以遍历到的有向边作为当前顶点的候选有向边，并将候选有向边的使用次数增加一次；
20.当确定遍历到的有向边连接的另一个顶点在测试用例中已经被使用过时，确定遍历到的有向边不可用，再次执行基于有向图按照使用次数从小到大的顺序依次遍历当前顶点连接的各条有向边的步骤。
21.其进一步的技术方案为，测试覆盖率是有向图中，使用次数非0的有向边的数量与全部有向边的数量之间的比值。
22.其进一步的技术方案为，构建有向图还包括：
23.将fpga内与互连线相连的功能模块内部形成的每条数据通路抽象为相应的两个顶点之间的有向边。
24.其进一步的技术方案为，测试方法还包括：在将fpga内的功能模块内部的数据通路抽象为有向边时，在有向边上插入逻辑器件，逻辑器件为寄存器或锁存器；
25.则在任意一条测试通路的信号输入端处施加激励信号、并在对应的信号输出端处采集响应信号确定测试通路中存在至少一个可配置互连节点出现故障时，根据测试通路中的逻辑器件的密度确定出现故障的可配置互连节点。
26.其进一步的技术方案为，根据测试通路中的逻辑器件的状态确定出现故障的可配置互连节点包括：读取测试通路中各个逻辑器件的值并确定测试通路上的沿着数据传输方向相邻的第一逻辑器件和第二逻辑器件，第二逻辑器件相对于第一逻辑器件位于数据传输方向的上游，第二逻辑器件的读取值正常，第一逻辑器件的读取值异常；检测第二逻辑器件
至第一逻辑器件之间的互连通路上的可配置互连节点以确定出现故障的可配置互连节点。
27.其进一步的技术方案为，初始化的输入顶点是fpga内部分具有激励施加功能的互连线对应的顶点，且初始化的输入顶点的数量在fpga内具有激励施加功能的全部互连线对应的顶点的数量中的占比达到第一阈值；
28.初始化的输出顶点是fpga内部分具有信号采集功能的互连线对应的顶点，且初始化的输出顶点的数量在fpga内具有信号采集功能的全部互连线对应的顶点的数量中的占比达到第二阈值。
29.本技术的有益技术效果是：
30.本技术公开了一种fpga中的可配置互连节点的测试方法，该测试方法将全芯片中的所有待测的可配置互连节点以及相应的辅助通路模型化为一张包含顶点和有向边的完整的有向图，基于图论的以覆盖率为驱动的方法遍历搜寻测试通路以得到覆盖率达标的测试用例，该方法以fpga内互连资源的相互结构构建的有向图为基础来建立测试用例，而并不基于特定的芯片架构，因此该方法是不依赖于芯片架构的通用性方法，且得到的测试通路都是简单的从一个信号输入端经过若干条互连线和pip后到达一个信号输出端，测试向量即是在这些测试通路的起点施加激励并在终点处得到相应响应即可，该测试方法的适用范围广、通用性强、易于操作、测试效率高。
31.传统的测试方法为了达到一个较优的测试覆盖率往往需要使用到数以千计的测试用例，测试覆盖率和速率难以兼得，且测试覆盖率往往只能达到30％多。而本技术的测试方法基于图论的方法遍历搜寻，一直在有意识地寻找未曾覆盖过的有向边，因此通过较少数量的测试用例就能达到较高的测试覆盖率，经过实际验证，通过300多个测试用例就能达到95％以上的测试覆盖率，因此本技术的方法不仅可以在测试覆盖率和测试速率两方面都有较好的表现，而且可以极高的提高测试覆盖率，优化测试效率。
32.本技术的方法还可以推广至用于对fpga内诸如查找表、寄存器之类的类似于pip功能的电路结构进行测试，通过相同的模型化的方法将诸如查找表、寄存器之类的与待测试的电路结构纳入到有向图中，也可以实现相同的高效率测试。
附图说明
33.图1是开关矩阵内部的可配置互连节点以及外部的互连线的连接示意图。
34.图2是本技术一个实施例的可配置互连节点的测试方法的方法流程图。
35.图3是本技术一个实例中对fpga内局部的互连线的可配置互连节点之间的连接关系抽象得到的有向图的局部结构的示意图。
36.图4是本技术另一个实施例的可配置互连节点的测试方法的方法流程图。
具体实施方式
37.下面结合附图对本技术的具体实施方式做进一步说明。
38.本技术公开了一种fpga中的可配置互连节点的测试方法，该测试方法包括如下步骤，请参考图2所示的流程图：
39.步骤1，将fpga内的每条互连线抽象为每个顶点、将fpga内的每两条互连线之间的可配置互连节点抽象为相应的两个顶点之间的有向边，构建得到用于表征fpga内的互连线
与可配置互连节点之间的连接关系的有向图。
40.根据测试基本原理，如果一个电路结构只有输入没有输出，或者只有输出没有输入，那么这个电路结构是没有办法通过故障模型来分析测试的，因此除了对fpga内的互连线和可配置互连节点进行抽象之外，还将fpga内与互连线相连的功能模块内部形成的每条数据通路抽象为相应的两个顶点之间的有向边，并同样模型化到有向图中，从而将fpga内所有相连的互连线与开关矩阵中的可配置互连节点全部模型化为一张有向图。
41.在一个实例中，fpga内的两个开关矩阵中的可配置互连节点以及所连接的互连线以及相应模型化得到的有向图如图3所示，模型化得到的有向图中的顶点分别与互连线一一对应，模型化得到的有向图中的有向边分别与开关矩阵中的可配置互连节点一一对应，且有向图中的顶点与有向边的连接关系和对应的互连线与可配置互连节点的连接关系一致。
42.步骤2，初始化若干个输入顶点和若干个输出顶点。
43.其中，输入顶点是具有激励施加功能的互连线对应的顶点，也即需要保证在输入顶点处便于施加激励信号，常见的可以将fpga内的io口、bscan链上的寄存器数据端口、其它寄存器的数据端口所连接的互连线对应的顶点作为输入顶点。输出顶点是具有信号采集功能的互连线对应的顶点，也即需要保证在输出顶点处便于采集响应信号。
44.为了提高搜寻测试通路的成功率，初始化的输入顶点和输出顶点的数量不能太少，但数量太多又会增加搜寻复杂度，本技术并不要求找到所有具有激励施加功能的互连线对应的顶点都作为输入顶点，同样也不要求找到所有具有信号采集功能的互连线对应的顶点都作为输出顶点，本技术的方法可以保证即便不找到所有具有激励施加功能的互连线对应的顶点和所有具有激励施加功能的互连线对应的顶点，仍然可以保证测试覆盖率。
45.因此在一个实施例中，初始化的输入顶点是fpga内部分具有激励施加功能的互连线对应的顶点，且初始化的输入顶点的数量在fpga内具有激励施加功能的全部互连线对应的顶点的数量中的占比达到第一阈值。初始化的输出顶点是fpga内部分具有信号采集功能的互连线对应的顶点，且初始化的输出顶点的数量在fpga内具有信号采集功能的全部互连线对应的顶点的数量中的占比达到第二阈值。第一阈值和第二阈值是自定义的取值，从而可以在保证搜寻测试通路的成功率的基础上，降低搜寻复杂度。
46.步骤3，基于有向图搜寻测试通路。
47.搜寻到的每条测试通路以其中一个输入顶点为信号输入端、以其中一个输出顶点为信号输出端，且包括从信号输入端到信号输出端之间的顶点和有向边，每条测试通路的信号输入端到信号输出端之间包括一条或多条有向边。
48.基于有向图搜寻测试通路的方法包括，请参考图4所示的流程图：
49.(1)随机选取任意一个输入顶点初始化为当前顶点。
50.(2)基于有向图搜寻当前顶点连接的一条有向边作为候选有向边。
51.在该步骤中，对于任意一个当前顶点，搜寻到的当前顶点所连接的候选有向边在当前顶点连接的全部有向边中使用次数最少、且候选有向边连接的另一个顶点在测试用例中未被使用过。则该方法在加载有向图之后，首先会将有向图中全部有向边的使用次数初始化为0。
52.则对于任意一个当前节点，首先基于有向图按照使用次数从小到大的顺序依次遍
历当前顶点连接的各条有向边，对于遍历到的任意一条有向边：当确定遍历到的有向边连接的另一个顶点在测试用例中未被使用过时，说明该有向边连接的另一个顶点未被使用在当前测试用例中的任意一个测试通路中，则以遍历到的该有向边作为当前顶点的候选有向边，并将候选有向边的使用次数增加一次。当确定遍历到的有向边连接的另一个顶点在测试用例中已经被使用过时，确定遍历到的有向边不可用，再次执行基于有向图按照使用次数从小到大的顺序依次遍历当前顶点连接的各条有向边的步骤。
53.(3)当候选有向边连接的另一个顶点不是输出顶点时，以候选有向边连接的另一个顶点作为更新后的当前顶点并重新执行在有向图中搜寻当前顶点连接的一条有向边作为候选有向边的步骤，重复上述步骤(2)继续搜寻。
54.(4)当候选有向边连接的另一个顶点为输出顶点时，完成搜寻并得到一条测试通路，得到的测试通路即包括初始化的输入顶点和确定得到的输出顶点以及中间依次经过的若干条候选有向边。由于fpga内的连接资源丰富，且本技术初始化输入顶点和输出顶点的数量不会太少，因此理论上不会出现无法寻找到满足要求的测试通路的情况。
55.步骤4，重复执行基于有向图搜寻测试通路的步骤，直至测试覆盖率达到预定阈值时，得到包括若干条测试通路的测试用例。在本技术中，测试覆盖率是有向图中，使用次数非0的有向边的数量与全部有向边的数量之间的比值。该预定阈值是预设值，在本技术中，测试覆盖率可以达到95％以上甚至趋近于100％，预定阈值可以根据实际需要来设定。
56.步骤5，在测试用例中的各条测试通路的信号输入端处施加激励信号、并在对应的信号输出端处采集响应信号，完成对fpga中的可配置互连节点的测试。包括：当在一条测试通路中的信号输入端处施加为1的激励信号、而在对应的信号输出端处采集到常为0的响应信号时，确定该测试通路中存在至少一条有向边对应的可配置互连节点出现stuck-at 0故障(简称sa0故障)。或者，当在一条测试通路中的信号输入端处施加为0的激励信号、而在对应的信号输出端处采集到常为1的响应信号时，确定该测试通路中存在至少一条有向边对应的可配置互连节点出现stuck-at 1故障(简称sa1故障)。可配置互连节点的sa0故障和sa1故障都是因为sram的编程信息不能改变此可配置互连节点的导通状态而导致的。
57.在一个实施例中，在步骤1构建有向图将fpga内的功能模块内部的数据通路抽象为有向边时，还在该抽象得到的有向边上插入逻辑器件，逻辑器件为寄存器或锁存器。则在确定测试通路中存在可配置互连节点出现sa0故障或sa1故障时，可以根据测试通路中的逻辑器件的密度快速确定出现故障的可配置互连节点，快速实现出现故障的可配置互连节点的定位。定位出故障点的原理是：当某一个逻辑器件的值异常时，表示在该测试通路上沿着数据传输方向位于该逻辑器件之前的互连通路中有可配置互连节点出现sa0故障或sa1故障；当某一个逻辑器件的值正常时，表示在该测试通路上沿着数据传输方向位于该逻辑器件之前的互连通路中所有可配置互连节点都未出现sa0故障和sa1故障。因此在确定测试通路上任意的第一逻辑器件之前的互连通路出现sa0故障或sa1故障时，继续确定测试通路上的第二逻辑器件的值，第二逻辑器件是测试通路上沿着数据传输方向位于第一逻辑器件之前的前一个逻辑器件，第二逻辑器件与第一逻辑器件之前不存在其他逻辑器件。当读取第二逻辑器件的值确定测试通路上沿着数据传输方向位于第二逻辑器件之前的互连通路出现sa0故障或sa1故障时，重复上述过程继续读取沿着数据传输方向位于第二逻辑器件之前的前一个逻辑器件的值重复上述过程。当读取第二逻辑器件的值确定测试通路上沿着数据
传输方向位于第二逻辑器件之前的互连通路未出现sa0故障和sa1故障时，确定第二逻辑器件和第一逻辑器件之间的互连通路上存在可配置互连节点出现sa0故障或sa1故障，由此可以快速定位到出现故障的可配置互连节点。因此测试通路中的逻辑器件的密度越高，越利于快速完成故障定位。
58.基于上述定位出故障点的原理，根据测试通路中的逻辑器件的状态确定出现故障的可配置互连节点的方法包括：读取测试通路中各个逻辑器件的值，确定测试通路上的沿着数据传输方向相邻的第一逻辑器件和第二逻辑器件，第二逻辑器件相对于第一逻辑器件位于数据传输方向的上游，第二逻辑器件的读取值正常，第一逻辑器件的读取值异常，检测第二逻辑器件至第一逻辑器件之间的互连通路上的可配置互连节点以实现故障定位。在实际操作时，由于第二逻辑器件至第一逻辑器件之间的互连通路上存在可配置互连节点出现sa0故障或sa1故障，导致第一逻辑器件的读取值异常，则一般也会导致沿着数据传输方向位于第一逻辑器件下游的各个逻辑器件的读取值也异常，则在定位并修复第二逻辑器件至第一逻辑器件之间的互连通路上的可配置互连节点的故障后，可以重新对该测试通路按照上述流程进行测试，以快速定位其他可配置互连节点的故障，或者也可以直接对第一逻辑器件下游的互连通路上的可配置互连节点进行故障定位。
59.以上所述的仅是本技术的优选实施方式，本技术不限于以上实施例。可以理解，本领域技术人员在不脱离本技术的精神和构思的前提下直接导出或联想到的其他改进和变化，均应认为包含在本技术的保护范围之内。