面向信號測試系統的多路信號路由算法研究

尚利宏,譚 特,周 密

(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.