面向信号测试系统的多路信号路由算法研究

尚利宏,谭 特,周 密

(1.北京航空航天大学 计算机学院,北京 100191; 2.北京中航瑞博航空电子技术有限公司,北京 100191)

0 概述

IEEE1641[1]和IEEE1671[2]标准提出了一种面向信号的自动测试系统设计理念。面向信号的自动测试平台具有很高的自动化程度,在这种平台下,用户只需要描述被测对象(Unit Under Test,UUT)的特定端口的激励信号或测量信号的特性,运行时系统(Run-time System,RTS)将自动匹配具有该特定激励或测试能力的仪器,并通过配置平台中的开关矩阵,将仪器引脚和UUT引脚连接起来。测试系统的这些功能将测试逻辑、测试环境底层实现完全隔离开,提高了测试程序的可移植性和测试仪器的互换性,并极大降低了测试的工作量[3-6]。

自动测试系统中的一个关键步骤是信号路由。该步骤将建立一条从UUT引脚到测试仪器引脚的信号传播通道。用于支持信号路由的硬件设备是矩阵开关,此类设备是可编程器件,软件可对其编程以实现信号路径的重构。另外,多个矩阵开关可以相互连接,以形成开关矩阵网络。

文献[7]对开关矩阵进行了建模,并给出了一种信号路径的建立方法。文献[8]在此基础上,为每个开关关联一个“可靠性参数”,并提出了一种基于矩阵连乘的最高可靠性路径生成方法。文献[9]提出了一种基于Dijkstra算法的可靠性最高路径搜索算法。上述方法只适用于一路信号的情况,即只能生成单一引脚对(只有一个仪器引脚和一个UUT引脚)之间的路径。

测试程序有时需要同时在UUT上连接多个激励或测试信号。文献[10]提出一种多路信号路径搜索算法,然而这种算法是一种近似算法,在有些情况下无法找到信号路径。并且这种算法只适合单个开关矩阵的情况,对开关矩阵网络并不适用。

多路信号路由问题在很大程度上和FPGA布线问题类似。可以考虑通过主流的FPGA布线算法——PathFinder算法[11]来解决多路信号的路由问题。然而,对于没有解情况,PathFinder算法可能无法终止,另外,这种算法还有迭代次数过多、正确性不定等问题。为此,本文研究在满足一定限制的开关矩阵互连网络中,多个节点对之间路径搜索的高效算法。

1 开关矩阵互连网络及路由策略定义

开关矩阵是一个有M个输入引脚和N个输出引脚的电子器件;在功能上,开关矩阵用于将某个输入引脚和输出引脚连接起来。图1为一个5×4开关矩阵。此设备有5个输入和4个输出,可以控制开关的闭/开状态来实现特定的输入、输出转接。例如,闭合第3行第4列的开关即可将4号输入引脚和3号输出引脚连接起来。

图1 开关矩阵

根据以上分析可给出开关矩阵的定义。

定义1开关矩阵K表示为一个二元组,即K=(I,O)。其中,I={in1,in2,…,in|I|}是输入引脚的集合,O={out1,out2,…,out|O|}是输出引脚的集合。

此定义并未刻画开关矩阵转接信号的能力,此能力由定义4的“引脚转接函数”来刻画。

多个开关矩阵可以用于构建互连网络。互连网络同时还连接测试仪器和UUT的引脚。下面给出开关矩阵互连网络的定义。

定义2开关矩阵互连网络N表示为四元组,即N=(KS,V1,V2,f),其中,KS表示所有开关矩阵的集合,V1表示所有仪器引脚的集合,V2表示所有UUT引脚的集合,函数f:KSI∪V2→KSO∪V1表示互连关系,其中,KSI表示KS中所有开关矩阵的所有输入引脚的集合,KSO表示KS中所有开关矩阵的所有输出引脚的集合。需要注意的是,函数f隐含着开关矩阵的任何输入引脚和任何UUT引脚,只能和一个开关矩阵输出引脚或测试仪器引脚相连接。

限制1在本文所讨论的开关矩阵互连网络中,所有UUT引脚都连接在同一开关矩阵上。

图2为一个开关矩阵互连网络。网络共包括3个开关矩阵、2个测试仪器和1个UUT。开关矩阵K1有1个输入引脚和1个输出引脚,开关矩阵K2和K3分别包括2个输入引脚和输出引脚。仪器A的引脚1同时和K1、K2的输入引脚相连,仪器B的引脚1只和K2相连。UUT的2个引脚都和K3的输出引脚相连(这样满足限制1)。

图2 开关矩阵互连网络

下文用“设备名.引脚号”的方式表示设备引脚,例如,仪器A的引脚1表示为A.1,开关矩阵K1的一号输入引脚表示为K1.in1。

根据定义2,如图2所示的互连网络表示为N=(KS,V1,V2,f)。其中,KS=(K1,K2,K3),K1=({in1},{out1}),K2=K3=({in1,in2},{out1,out2}),V1={A.1,B.1},V2={UUT.1,UUT.2},f函数如表1表示。

表1 互连网络中的f函数

在自动测试系统中,运行时系统(RTS)完成测试需求解析和硬件能力匹配之后,将生成一个路由需求,此需求描述测试仪器引脚和UUT引脚的逻辑连接关系。下面给出路由需求的精确定义:

定义3互连网络N=(KS,V1,V2,f)的一个路由需求(route demand)表示为一个函数rdf:V1→V2。它指定了仪器引脚和UUT引脚的对应关系,即描述了将仪器引脚路由到哪一个UUT引脚。

限制2如果函数rdf:V1→V2是一个路由需求,则rdf一定是双射函数。

为了实现某个路由需求rdf,运行时系统需要对开关矩阵进行编程。从本质上讲,对开关矩阵编程等价于为开关矩阵关联一个引脚转接函数。引脚转接函数的定义如下:

定义4开关矩阵K=(I,O)的引脚连接函数(pin transfer function)定义为ptf:I→O,表示K中输入和输出引脚的连接关系。

限制3如果函数ptf是某个开关矩阵K的引脚连接函数,则ptf一定是单射函数。

每个开关矩阵所关联的引脚连接函数由信号路由策略指定,下面给出信号路由策略的定义:

定义5矩阵开关互连网络N=(KS,V1,V2,f)和路由需求rdf的路由策略(route strategy)表示为函数rsf:KS→OI,满足:

1)对于任何开关K∈KS,rsf(K)都可以作为开关矩阵K的引脚转接函数,即rsf(K)满足限制2。

2)在路由策略rsf作用下,所有的仪器引脚v∈V1均被路由到需求rdf要求的UUT引脚rdf(v)。

2 路由策略生成算法

本文提出一种基于网络流的算法,该算法可以判断出路由需求是否得到满足,可为所有的满足限制1～限制3的互连网络的路由需求生成路由策略。对于不满足限制1～限制3的互连网络,此算法不适用。首先引入“生成流网络”的定义,此定义是路由策略生成算法的核心。

定义6给定互连网络N=(KS,V1,V2,f)和路由需求rdf,其生成流网络表示为G=(E,V,c)。其中,V是顶点的集合,E是有向边的集合,c:E→I(I是整数集合)表示各个有向边的容量。流网络G的生成规则如下:

1)顶点集合V=P1∪P2∪P3∪P4∪P5∪{s,t},其中:(1)节点s是源点,节点t是汇点;(2)对于任何仪器引脚v∈V1,则集合P1中有一个对应的顶点;(3)对于任何UUT引脚v∈V2,则集合P2中有一个对应的顶点;(4)对任何开关矩阵K=(I,O)∈KS,集合I中的每个元素在集合P3中有一个对应的顶点,集合O中的每个元素在P4和P5中各有一个顶点。

由于除源点和汇点外,任何顶点和一个设备引脚对应,因此在下文叙述中,有时会直接用顶点指代其对应的引脚。

2)边的生成规则。对于顶点集合V中的任意2个顶点u、v∈V:(1)如果u是源点且v∈P1,则u、v之间有一条有向边;(2)如果v是汇点且u∈P2,则u、v之间有一条有向边;(3)如果u∈P2∪P3且u∈P1∪P5、N.f(u)=v,则在u和v之间有一条有向边;(4)如果u∈P3且v∈P4且u、v对应同一开关矩阵的引脚,则u、v之间存在一条有向边;(5)如果u∈P4、v∈P5且u、v和同一开关矩阵的同一输出引脚对应,则在u、v之间存在一条有向边。

3)所有边的容量都为1,即∀e∈E,c(e)=1。

图3显示了图2中互连网络的生成流网络,其中每条边的容量都为1。从图3中可以直观地看出,每个开关矩阵包括3层节点,第1层的每一个节点对应一个输入引脚,第2层和第3层的每一个节点和输出引脚对应。这样的结构可以保证所有第3层的节点只接收一个第1层节点的流量。

图3 生成流网络

应当注意的是,给定互连网络下的某些路由需求是不可能满足的。例如,如果图1的互连网络中没有矩阵开关K1,那么A.1和B.12个引脚中只有一个引脚能被连接到正确的UUT引脚。因此,在生成路由策略之前,应当首先判断路由需求是否能够得到满足。下面的定理可以作为路由是否可需求满足的判据。

定理1给定互连网络N=(KS,V1,V2,f)和路由需求rdf,则rdf可满足的充分必要条件是其生成流网络的最大流和集合V1的基数|V1|相等。

证明:首先非形式化地证明其必要性。如果路由需求rdf可以得到满足,即存在一个路由策略rsf。根据每一对引脚的路由线路,一定可以构造G的一个流f,使得|f|=|V1|。

在证明定理1的充分性前,先给出流网络的“生成子图”的定义以及它的2个性质。

定义7对于生成流网络G=(E,V,c)以及它的一个流量为|V1|的流f:E→I(函数f指定了每条边的流量),可以生成G的一个子图Gf=(V,Ef),其中边(u,v)∈Ef,当且仅当f(u,v)=1。

性质1在网络流G=(E,V,c)和流f的生成子图Gf=(V,Ef)中,如果节点v∈V-{s,t}有输入流量,则在节点v和汇点t之间一定存在一条简单路径。

证明:用反证法证明。假设节点v和汇点t之间没有简单路径。令集合B={v}∪{u∈V且Gf中存在v到u的简单路径}。易知,v∈B且t∈V-B。由于Gf是无向图,B中的节点一定构成以v为根的树,因此一定存在u∈B,在Gf中u没有任何到B中其他节点的出向边。另一方面,在Gf中u也一定没有一条到V-B中节点的出向边(假设存在边(u,w)且w∈V-B,由于v到u有简单路径,因此v到w也一定有简单路径,故w∈B,这与w∈V-B矛盾)。因此,在Gf中u一定不存在任何到其他节点的出向边,这表明u没有输出流量。而由于v可以到达u,在Gf中u一定有一条入向边,这表明u有输入流量。由于u不可能是汇点,因此有输入流量却没有输出流量违背了流的“流量守恒”性质。因此,假设不成立,原命题得证。

性质2在网络流G=(E,V,c)和流f的生成子图Gf=(V,Ef)中,除源点s和汇点t外,任何节点要么是孤立节点,要么有且只有一个出向边和一个入向边。

证明:根据网络流G的生成规则容易验证,G中除源点s和汇点t外的任何节点,要么只有一条容量为1的出向边,要么只有一条容量为1的入向边。因此,为满足“流量守恒”,每个节点最多有1个单位的流量。当某个节点没有流量时,在Gf中它是孤立节点;当某个节点有1个单位流量时,在Gf中一定有一条出向边和一条入向边。因此,性质得证。

现在借助定义7来证明定理1的充分性。对于生成流网络G=(E,V,c),其中顶点集V按照生成规则划分为V=P1∪P2∪P3∪P4∪P5∪(s,t)。由于流f的流量|f|=|V1|,并且根据G的边集E的生成规则,源点s只有指向点集P1中节点的|V1|条容量为1的出向边,因此任何初始节点为源节点的边的流量均为1,并且每个节点v∈P1获得一个单位的流量。由于任何节点v∈P1有一个单位的输入流量,因此子图Gf中一定存在一条始点是v、终点是汇点t的简单路径s(性质1)。由于只有点集P2中的节点有指向汇点t的出向边,因此简单路径s中一定包括一个节点u∈P2。所以,在生成子图Gf中,对于所有的v∈P1,一定存在一个节点u∈P1,在节点v和u之间有一条简单路径。因为所有u∈P2只有一条容量为1的出向边,所以不同的v∈P1,其对应的u∈P2不同。事实上,所有v∈P1、u∈P2之间的简单路径,即可作为节点v对应的仪器引脚和节点u对应的UUT引脚之间的路由路径,它将引脚v路由到引脚u。这是因为从性质2可得,任何不同v、u之间的简单路径不会交叉或重合,并且任何开关矩阵的输出引脚,最多被连接了一个输入引脚,这就满足了引脚连接函数“单射”的要求。由于所有的UUT引脚都连接在同一开关矩阵上,因此通过修改UUT引脚所连的开关矩阵的引脚连接函数,即可为任意的路由需求rdf生成路由策略(从这里可以看出与UUT引脚连接的开关矩阵的作用:所有仪器引脚被路由到此开关矩阵的输入引脚,经过此开关矩阵后转接到相应的UUT引脚)。充分性证明完毕。

定理1的充分性证明是构造性的。它给出了路由策略生成算法的原型。下面的伪代码将给出路由策略生成算法的详细过程。

算法路由策略生成算法(RSG)

输入互连网络N=(KS,V1,V2,f)、测试需求rdf

输出路由策略rsf

1. Route_Strategy_Generate(N,rdf)

2. begin

3. 生成N的生成流网路G

4. 运行最大流算法,得到G的最大流f

5. if(|f|<|V1|)

6. 返回失败

7. else

8. 根据f生成子图Gf

9. for Gf中的每一条边(u,v)

10. if 节点u是不与UUT引脚连接的矩阵开关K的输入引脚

11. 令rsf(K)引脚转接函数的rsf(K)(u)=v

12. else if u是与UUT引脚连接的矩阵开关K的输入引脚

13. 找到与v之间存在简单路径的节点w∈P1

14. 令rsf(K)引脚转接函数的rsf(K)(u)=N.f(rdf(w))

15. end if

16. end for

17. 返回路由需求rsf

18. end if

19.end

上述算法的第12行～第14行给出了与UUT引脚连接的开关矩阵的引脚连接函数生成方法。对于与UUT引脚连接的开关矩阵的某个输入引脚对应的节点u,如果某个节点w∈P1和u之间有一条简单路径,表明w对应的引脚被路由到了u对应的引脚。为了将w引脚路由到路由需求rdf要求的UUT引脚rdf(w),就需要将u连接到与rdf(w)连接的输出引脚N.f(rdf(w))。

3 信号传播路径性能优化

由于不同的开关矩阵存在质量、已使用时长等方面的差异,因此不同的开关矩阵有不同的信号传播阻力。所以,应当将信号传播阻力也作为开关矩阵的参数。

定义8开关矩阵K的信号传播阻力记为K.r。

传播阻力的值和开关矩阵的转接延迟、可靠性等性能有关。例如,文献[6]给出了一种基于开关的可靠性的度量方法。本文不讨论如何度量开关矩阵的传播阻力,只将其视作抽象值。

由于路由策略在仪器引脚和UUT引脚之间建立的信号传播路径会经过若干个开关矩阵,因此信号传播路径也会因为所经过的开关矩阵的不同而表现出不同的信号传播阻力。

定义9如果信号传播路径P所经过的开关矩阵构成集合KP={k1,k2,…,kn},则信号传播路径的传播阻力P.r定义为:

(1)

定义10如果一个路由策略rsf建立的所有信号传播路径构成集合Prsf={P1,P2,…,Pn},则策略rsf的平均阻力rsf.r定义为:

(2)

为了提高整体的信号传播质量,一个最理想的路由策略应当是所有满足路由需求的路由策略中平均阻力最小的策略。

只需要基于最小费用最大流算法,对第2节描述的路由策略生成算法进行改进,即可得到求解阻力最小的路由策略的算法。称此优化算法为ORSG算法(Optimized Route Strategy Generate Algorithm)。

首先,对于生成流网络G=(E,V,c),其中顶点集V=P1∪P2∪P3∪P4∪P5∪{s,t},定义花费函数cst:E→R+∪{0}(R+是正实数集合)。此函数为流网络中的每一条边关联一个费用值。它的值的定义为:对于边(u,v)∈E,如果u∈P3,v∈P4并且u、v分别对应同一开关矩阵K的输入、输出引脚,则cst(u,v)=K.r;否则,cst(u,v)=0。

然后,将RSG算法在第4行调用的最大流改为最小费用最大流。容易看出,在任何满足|f|=|V1|的流f的生成子图Gf中,所有边的花费的和就是由Gf导出的所有信号传播路径的传播阻力的和。由于由最小费用最大流算法生成的流fmin的生成子图Gfmin的边的花费和最小[13-14],因此由Gfmin导出的路由策略的平均阻力也一定最小。

下面分析ORSG算法的时间复杂度。同RSG算法相同,ORSG算法的时间复杂度取决于最小费用最大流算法的时间复杂度。由于最小费用最大流算法调用SPFA算法[15]寻找残量网络中花费最小的增广路径,并且每个增广路径都导致流量增加单位流量,因此ORSG算法最多共执行SPFA算法|V1|次。文献[15]指出,SPFA算法的平均时间复杂度是O(k|E|),其中k是不大于2的常数。因此,ORSG算法的平均时间复杂度是O(k|E||V1|)。

4 实例分析

对于如图2所示的互连网络N=(KS,V1,V2,f),假设有如表2所示的路由需求。现在应用该算法来寻找满足此需求的路由策略。

表2 路由需求rdf函数

首先要生成此互连网络的流网络G。然后求此流网络的最大流f,结果为|f|=2=|V1|,表明路由需求可以得到满足。在求得最大流的基础上,算法继续生成对应于f的生成子图Gf,结果如图4所示。

图4 互连网络的生成子图

由图4可知,在仪器引脚A.1和UUT引脚UUT.1之间有一条简单路径,在仪器引脚B.1和UUT引脚UUT.2之间也有一条简单路径。这2条路径可以分别将A.1路由到UUT.1、B.1路由到UUT.2。最终的路由策略rsf以及各个开关的引脚转接函数ptf如表3～表6所示。

表3 路由策略rsf函数

表4 ptf1引脚转接函数

表5 ptf2引脚转接函数

表6 ptf3引脚转接函数

通过这样的路由策略,仪器引脚A.1通过路径K1.in1→K1.out1→K3.in1→K3.out1到达UUT.1引脚,仪器引脚B.1通过路径K2.in2→K2.out1→K3.in2→K3.out2到达UUT.2引脚。

如果某个路由需求要将A.1路由到UUT.2,将B.1路由到UUT.1,只需将K3的输入引脚in1转接到输出引脚out2,将输入引脚in2转接到输出引脚out1,即可满足该要求。

5 实验结果与分析

本节给出相关实验的实验结果。实验中用到的测试例程由仿真程序生成。仿真程序接收的参数包括互连网络中的开关矩阵数、引脚连接关系数以及路由策略中指定需要路由的信号对数。

第1组实验比较本文提出的算法和文献[9]中给出的算法的有效性。本组实验用到的测试例程参数如表7所示。

表7 实验1测试例程参数

文献[9]中的算法应用Dijkstra算法为单一UUT、仪器引脚对搜索信号传播路径。对于多个UUT、仪器引脚对,文献[9]中的算法所搜索出的多个信号传播路径之间可能会有冲突。一旦发生冲突,文献[9]中的算法就失效。表8显示在不同测试数据下,文献[9]算法和本文算法是否生成了有效的路由策略。

表8 不同测试数据下有效性比较

可见,对于多数情况,文献[9]中的算法无法生成有效的路由策略,而本文算法能够生成有效的路由策略。

第2组实验通过运行实例来对RSG算法和ORSG算法进行比较。本组实验用到的测试用例参数如表9所示。

表9 实验2测试例程参数

图5比较了RSG算法和ORSG算法的运行时间。从图5中可知,RSG算法快于ORSG算法。图6比较了RSG算法和ORSG算法生成的路由策略的平均阻力。可见ORSG算法生成的路由策略的平均阻力小于RSG算法生成的路由策略的平均阻力。

图5 运行时间比较

图6 路由策略平均阻力比较

综合图5、图6可知,RSG算法速度快,但生成的路由策略的平均阻力较大;ORSG算法生成的路由策略的平均阻力较小,但速度慢。因此,在对实时性要求较高的场合应使用RSG算法;在对信号传播质量要求较高的场合,应当使用ORSG算法。

6 结束语

为解决自动测试系统中多个激励信号的同时路由问题,本文对矩阵开关、矩阵开关互连网络进行了形式化建模,并给出了路由需求、路由策略的形式化定义。在此基础上,提出一个时间复杂度为O(|E||V1|)的路由策略生成算法——RSG算法,并证明了其正确性。此外定义了路由性能的评价指标,给出用于优化路由性能的优化算法——ORSG算法。最后通过实验对本文的2个算法与文献[9]算法在有效性、运行时间、路由性能等方面进行了比较。实验结果表明,在对实时性要求较高的场合应使用RSG算法;在对信号传播质量要求较高的场合应使用ORSG算法。另外,对开关矩阵互连网络做了一些限制,如不满足这些限制,本文算法将不再适用。下一步将对如何突破上述限制进行研究,进一步完善本文算法。

[1] IEEE.IEEE Standard for Signal and Test Definition:1641TM-2010[S].New York,USA:Institute of Electrical and Electronics Engineers,Inc.,2010.

[2] IEEE.IEEE Trial Use Standard for Automatic Test MarkUp Language(ATML) for Exchanging Automatic Test Equipment and Test Information via XML:Exchanging Instrument Descriptions:1671.5TM-2008[S].New York,USA:Institute of Electrical and Electronics Engineers,Inc.,2008.

[3] 刘金宁,孟 晨,赵锦成.面向信号的自动测试系统软件模型研究[J].测控技术,2010,29(3):63-66.

[4] 梁 旭,李行善,高占宝.基于测试引擎的自动测试系统软件设计[J].电子测量与仪器学报,2006,20(5):11-16.

[5] 钟天云.面向信号的ATS软件平台研究─系统建模工具与运行时服务设计[D].成都:电子科技大学,2013.

[6] 齐少华.TPS流程式开发环境与仪器管理模块的研究与实现[D].成都:电子科技大学,2013.

[7] 赵瑞贤,孟晓风,王国华.通用ATE开关资源测试路径模型及应用[J].北京航空航天大学学报,2006,32(2):181-185.

[8] 王国华,杨中亮,陈妮亚.ATE开关矩阵动态路径搜索算法[J].北京航空航天大学学报,2010,36(1):39-42.

[9] 王怡苹,李文海,文天柱.面向信号测试的路径搜索算法研究[J].仪器仪表学报,2013,34(7):1650-1658.

[10] 王国华,杨中亮,陈妮亚.ATE开关矩阵动态路径搜索算法[J].北京航空航天大学学报,2010,36(1):39-42.

[11] MCMURCHIE L,EBELING C.PathFinder:A Negotiation-based Performance-driven Router for FPGAs[C]//Proceedings of International ACM Symposium on Field-programmable Gate Arrays.New York,USA:ACM Press,1995:111-117.

[12] CORMEN Y H.算法导论[M].3版.徐建平,译.北京:机械工业出版社,2013.

[13] 宋常城.基于最小费用最大流算法的若干研究与分析[D].南京:南京邮电大学,2012.

[14] 赵礼峰,宋常城,白 睿.基于最小费用最大流问题的“排序”算法[J].计算机技术与发展,2011,21(12):82-85.

[15] 段凡丁.关于最短路径的SPFA快速算法[J].西南交通大学学报,1994,29(2):207-212.