尚利宏,譚 特,周 密

(1.北京航空航天大學(xué) 計(jì)算機(jī)學(xué)院,北京 100191; 2.北京中航瑞博航空電子技術(shù)有限公司,北京 100191)

0 概述

IEEE1641[1]和IEEE1671[2]標(biāo)準(zhǔn)提出了一種面向信號的自動測試系統(tǒng)設(shè)計(jì)理念。面向信號的自動測試平臺具有很高的自動化程度,在這種平臺下,用戶只需要描述被測對象(Unit Under Test,UUT)的特定端口的激勵信號或測量信號的特性,運(yùn)行時系統(tǒng)(Run-time System,RTS)將自動匹配具有該特定激勵或測試能力的儀器,并通過配置平臺中的開關(guān)矩陣,將儀器引腳和UUT引腳連接起來。測試系統(tǒng)的這些功能將測試邏輯、測試環(huán)境底層實(shí)現(xiàn)完全隔離開,提高了測試程序的可移植性和測試儀器的互換性,并極大降低了測試的工作量[3-6]。

自動測試系統(tǒng)中的一個關(guān)鍵步驟是信號路由。該步驟將建立一條從UUT引腳到測試儀器引腳的信號傳播通道。用于支持信號路由的硬件設(shè)備是矩陣開關(guān),此類設(shè)備是可編程器件,軟件可對其編程以實(shí)現(xiàn)信號路徑的重構(gòu)。另外,多個矩陣開關(guān)可以相互連接,以形成開關(guān)矩陣網(wǎng)絡(luò)。

文獻(xiàn)[7]對開關(guān)矩陣進(jìn)行了建模,并給出了一種信號路徑的建立方法。文獻(xiàn)[8]在此基礎(chǔ)上,為每個開關(guān)關(guān)聯(lián)一個“可靠性參數(shù)”,并提出了一種基于矩陣連乘的最高可靠性路徑生成方法。文獻(xiàn)[9]提出了一種基于Dijkstra算法的可靠性最高路徑搜索算法。上述方法只適用于一路信號的情況,即只能生成單一引腳對(只有一個儀器引腳和一個UUT引腳)之間的路徑。

測試程序有時需要同時在UUT上連接多個激勵或測試信號。文獻(xiàn)[10]提出一種多路信號路徑搜索算法,然而這種算法是一種近似算法,在有些情況下無法找到信號路徑。并且這種算法只適合單個開關(guān)矩陣的情況,對開關(guān)矩陣網(wǎng)絡(luò)并不適用。

多路信號路由問題在很大程度上和FPGA布線問題類似?？梢钥紤]通過主流的FPGA布線算法——PathFinder算法[11]來解決多路信號的路由問題。然而,對于沒有解情況,PathFinder算法可能無法終止,另外,這種算法還有迭代次數(shù)過多、正確性不定等問題。為此,本文研究在滿足一定限制的開關(guān)矩陣互連網(wǎng)絡(luò)中,多個節(jié)點(diǎn)對之間路徑搜索的高效算法。

1 開關(guān)矩陣互連網(wǎng)絡(luò)及路由策略定義

開關(guān)矩陣是一個有M個輸入引腳和N個輸出引腳的電子器件;在功能上,開關(guān)矩陣用于將某個輸入引腳和輸出引腳連接起來。圖1為一個5×4開關(guān)矩陣。此設(shè)備有5個輸入和4個輸出,可以控制開關(guān)的閉/開狀態(tài)來實(shí)現(xiàn)特定的輸入、輸出轉(zhuǎn)接。例如,閉合第3行第4列的開關(guān)即可將4號輸入引腳和3號輸出引腳連接起來。

圖1 開關(guān)矩陣

根據(jù)以上分析可給出開關(guān)矩陣的定義。

定義1開關(guān)矩陣K表示為一個二元組,即K=(I,O)。其中,I={in1,in2,…,in|I|}是輸入引腳的集合,O={out1,out2,…,out|O|}是輸出引腳的集合。

此定義并未刻畫開關(guān)矩陣轉(zhuǎn)接信號的能力,此能力由定義4的“引腳轉(zhuǎn)接函數(shù)”來刻畫。

多個開關(guān)矩陣可以用于構(gòu)建互連網(wǎng)絡(luò)。互連網(wǎng)絡(luò)同時還連接測試儀器和UUT的引腳。下面給出開關(guān)矩陣互連網(wǎng)絡(luò)的定義。

定義2開關(guān)矩陣互連網(wǎng)絡(luò)N表示為四元組,即N=(KS,V1,V2,f),其中,KS表示所有開關(guān)矩陣的集合,V1表示所有儀器引腳的集合,V2表示所有UUT引腳的集合,函數(shù)f:KSI∪V2→KSO∪V1表示互連關(guān)系,其中,KSI表示KS中所有開關(guān)矩陣的所有輸入引腳的集合,KSO表示KS中所有開關(guān)矩陣的所有輸出引腳的集合。需要注意的是,函數(shù)f隱含著開關(guān)矩陣的任何輸入引腳和任何UUT引腳,只能和一個開關(guān)矩陣輸出引腳或測試儀器引腳相連接。

限制1在本文所討論的開關(guān)矩陣互連網(wǎng)絡(luò)中,所有UUT引腳都連接在同一開關(guān)矩陣上。

圖2為一個開關(guān)矩陣互連網(wǎng)絡(luò)。網(wǎng)絡(luò)共包括3個開關(guān)矩陣、2個測試儀器和1個UUT。開關(guān)矩陣K1有1個輸入引腳和1個輸出引腳,開關(guān)矩陣K2和K3分別包括2個輸入引腳和輸出引腳。儀器A的引腳1同時和K1、K2的輸入引腳相連,儀器B的引腳1只和K2相連。UUT的2個引腳都和K3的輸出引腳相連(這樣滿足限制1)。

圖2 開關(guān)矩陣互連網(wǎng)絡(luò)

下文用“設(shè)備名.引腳號”的方式表示設(shè)備引腳,例如,儀器A的引腳1表示為A.1,開關(guān)矩陣K1的一號輸入引腳表示為K1.in1。

根據(jù)定義2,如圖2所示的互連網(wǎng)絡(luò)表示為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函數(shù)如表1表示。

表1 互連網(wǎng)絡(luò)中的f函數(shù)

在自動測試系統(tǒng)中,運(yùn)行時系統(tǒng)(RTS)完成測試需求解析和硬件能力匹配之后,將生成一個路由需求,此需求描述測試儀器引腳和UUT引腳的邏輯連接關(guān)系。下面給出路由需求的精確定義:

定義3互連網(wǎng)絡(luò)N=(KS,V1,V2,f)的一個路由需求(route demand)表示為一個函數(shù)rdf:V1→V2。它指定了儀器引腳和UUT引腳的對應(yīng)關(guān)系,即描述了將儀器引腳路由到哪一個UUT引腳。

限制2如果函數(shù)rdf:V1→V2是一個路由需求,則rdf一定是雙射函數(shù)。

為了實(shí)現(xiàn)某個路由需求rdf,運(yùn)行時系統(tǒng)需要對開關(guān)矩陣進(jìn)行編程。從本質(zhì)上講,對開關(guān)矩陣編程等價于為開關(guān)矩陣關(guān)聯(lián)一個引腳轉(zhuǎn)接函數(shù)。引腳轉(zhuǎn)接函數(shù)的定義如下:

定義4開關(guān)矩陣K=(I,O)的引腳連接函數(shù)(pin transfer function)定義為ptf:I→O,表示K中輸入和輸出引腳的連接關(guān)系。

限制3如果函數(shù)ptf是某個開關(guān)矩陣K的引腳連接函數(shù),則ptf一定是單射函數(shù)。

每個開關(guān)矩陣所關(guān)聯(lián)的引腳連接函數(shù)由信號路由策略指定,下面給出信號路由策略的定義:

定義5矩陣開關(guān)互連網(wǎng)絡(luò)N=(KS,V1,V2,f)和路由需求rdf的路由策略(route strategy)表示為函數(shù)rsf:KS→OI,滿足:

1)對于任何開關(guān)K∈KS,rsf(K)都可以作為開關(guān)矩陣K的引腳轉(zhuǎn)接函數(shù),即rsf(K)滿足限制2。

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

2 路由策略生成算法

本文提出一種基于網(wǎng)絡(luò)流的算法,該算法可以判斷出路由需求是否得到滿足,可為所有的滿足限制1～限制3的互連網(wǎng)絡(luò)的路由需求生成路由策略。對于不滿足限制1～限制3的互連網(wǎng)絡(luò),此算法不適用。首先引入“生成流網(wǎng)絡(luò)”的定義,此定義是路由策略生成算法的核心。

定義6給定互連網(wǎng)絡(luò)N=(KS,V1,V2,f)和路由需求rdf,其生成流網(wǎng)絡(luò)表示為G=(E,V,c)。其中,V是頂點(diǎn)的集合,E是有向邊的集合,c:E→I(I是整數(shù)集合)表示各個有向邊的容量。流網(wǎng)絡(luò)G的生成規(guī)則如下:

1)頂點(diǎn)集合V=P1∪P2∪P3∪P4∪P5∪{s,t},其中:(1)節(jié)點(diǎn)s是源點(diǎn),節(jié)點(diǎn)t是匯點(diǎn);(2)對于任何儀器引腳v∈V1,則集合P1中有一個對應(yīng)的頂點(diǎn);(3)對于任何UUT引腳v∈V2,則集合P2中有一個對應(yīng)的頂點(diǎn);(4)對任何開關(guān)矩陣K=(I,O)∈KS,集合I中的每個元素在集合P3中有一個對應(yīng)的頂點(diǎn),集合O中的每個元素在P4和P5中各有一個頂點(diǎn)。

由于除源點(diǎn)和匯點(diǎn)外,任何頂點(diǎn)和一個設(shè)備引腳對應(yīng),因此在下文敘述中,有時會直接用頂點(diǎn)指代其對應(yīng)的引腳。

2)邊的生成規(guī)則。對于頂點(diǎn)集合V中的任意2個頂點(diǎn)u、v∈V:(1)如果u是源點(diǎn)且v∈P1,則u、v之間有一條有向邊;(2)如果v是匯點(diǎn)且u∈P2,則u、v之間有一條有向邊;(3)如果u∈P2∪P3且u∈P1∪P5、N.f(u)=v,則在u和v之間有一條有向邊;(4)如果u∈P3且v∈P4且u、v對應(yīng)同一開關(guān)矩陣的引腳,則u、v之間存在一條有向邊;(5)如果u∈P4、v∈P5且u、v和同一開關(guān)矩陣的同一輸出引腳對應(yīng),則在u、v之間存在一條有向邊。

3)所有邊的容量都為1,即?e∈E,c(e)=1。

圖3顯示了圖2中互連網(wǎng)絡(luò)的生成流網(wǎng)絡(luò),其中每條邊的容量都為1。從圖3中可以直觀地看出,每個開關(guān)矩陣包括3層節(jié)點(diǎn),第1層的每一個節(jié)點(diǎn)對應(yīng)一個輸入引腳,第2層和第3層的每一個節(jié)點(diǎn)和輸出引腳對應(yīng)。這樣的結(jié)構(gòu)可以保證所有第3層的節(jié)點(diǎn)只接收一個第1層節(jié)點(diǎn)的流量。

圖3 生成流網(wǎng)絡(luò)

應(yīng)當(dāng)注意的是,給定互連網(wǎng)絡(luò)下的某些路由需求是不可能滿足的。例如,如果圖1的互連網(wǎng)絡(luò)中沒有矩陣開關(guān)K1,那么A.1和B.12個引腳中只有一個引腳能被連接到正確的UUT引腳。因此,在生成路由策略之前,應(yīng)當(dāng)首先判斷路由需求是否能夠得到滿足。下面的定理可以作為路由是否可需求滿足的判據(jù)。

定理1給定互連網(wǎng)絡(luò)N=(KS,V1,V2,f)和路由需求rdf,則rdf可滿足的充分必要條件是其生成流網(wǎng)絡(luò)的最大流和集合V1的基數(shù)|V1|相等。

證明:首先非形式化地證明其必要性。如果路由需求rdf可以得到滿足,即存在一個路由策略rsf。根據(jù)每一對引腳的路由線路,一定可以構(gòu)造G的一個流f,使得|f|=|V1|。

在證明定理1的充分性前,先給出流網(wǎng)絡(luò)的“生成子圖”的定義以及它的2個性質(zhì)。

定義7對于生成流網(wǎng)絡(luò)G=(E,V,c)以及它的一個流量為|V1|的流f:E→I(函數(shù)f指定了每條邊的流量),可以生成G的一個子圖Gf=(V,Ef),其中邊(u,v)∈Ef,當(dāng)且僅當(dāng)f(u,v)=1。

性質(zhì)1在網(wǎng)絡(luò)流G=(E,V,c)和流f的生成子圖Gf=(V,Ef)中,如果節(jié)點(diǎn)v∈V-{s,t}有輸入流量,則在節(jié)點(diǎn)v和匯點(diǎn)t之間一定存在一條簡單路徑。

證明:用反證法證明。假設(shè)節(jié)點(diǎn)v和匯點(diǎn)t之間沒有簡單路徑。令集合B={v}∪{u∈V且Gf中存在v到u的簡單路徑}。易知,v∈B且t∈V-B。由于Gf是無向圖,B中的節(jié)點(diǎn)一定構(gòu)成以v為根的樹,因此一定存在u∈B,在Gf中u沒有任何到B中其他節(jié)點(diǎn)的出向邊。另一方面,在Gf中u也一定沒有一條到V-B中節(jié)點(diǎn)的出向邊(假設(shè)存在邊(u,w)且w∈V-B,由于v到u有簡單路徑,因此v到w也一定有簡單路徑,故w∈B,這與w∈V-B矛盾)。因此,在Gf中u一定不存在任何到其他節(jié)點(diǎn)的出向邊,這表明u沒有輸出流量。而由于v可以到達(dá)u,在Gf中u一定有一條入向邊,這表明u有輸入流量。由于u不可能是匯點(diǎn),因此有輸入流量卻沒有輸出流量違背了流的“流量守恒”性質(zhì)。因此,假設(shè)不成立,原命題得證。

性質(zhì)2在網(wǎng)絡(luò)流G=(E,V,c)和流f的生成子圖Gf=(V,Ef)中,除源點(diǎn)s和匯點(diǎn)t外,任何節(jié)點(diǎn)要么是孤立節(jié)點(diǎn),要么有且只有一個出向邊和一個入向邊。

證明:根據(jù)網(wǎng)絡(luò)流G的生成規(guī)則容易驗(yàn)證,G中除源點(diǎn)s和匯點(diǎn)t外的任何節(jié)點(diǎn),要么只有一條容量為1的出向邊,要么只有一條容量為1的入向邊。因此,為滿足“流量守恒”,每個節(jié)點(diǎn)最多有1個單位的流量。當(dāng)某個節(jié)點(diǎn)沒有流量時,在Gf中它是孤立節(jié)點(diǎn);當(dāng)某個節(jié)點(diǎn)有1個單位流量時,在Gf中一定有一條出向邊和一條入向邊。因此,性質(zhì)得證。

現(xiàn)在借助定義7來證明定理1的充分性。對于生成流網(wǎng)絡(luò)G=(E,V,c),其中頂點(diǎn)集V按照生成規(guī)則劃分為V=P1∪P2∪P3∪P4∪P5∪(s,t)。由于流f的流量|f|=|V1|,并且根據(jù)G的邊集E的生成規(guī)則,源點(diǎn)s只有指向點(diǎn)集P1中節(jié)點(diǎn)的|V1|條容量為1的出向邊,因此任何初始節(jié)點(diǎn)為源節(jié)點(diǎn)的邊的流量均為1,并且每個節(jié)點(diǎn)v∈P1獲得一個單位的流量。由于任何節(jié)點(diǎn)v∈P1有一個單位的輸入流量,因此子圖Gf中一定存在一條始點(diǎn)是v、終點(diǎn)是匯點(diǎn)t的簡單路徑s(性質(zhì)1)。由于只有點(diǎn)集P2中的節(jié)點(diǎn)有指向匯點(diǎn)t的出向邊,因此簡單路徑s中一定包括一個節(jié)點(diǎn)u∈P2。所以,在生成子圖Gf中,對于所有的v∈P1,一定存在一個節(jié)點(diǎn)u∈P1,在節(jié)點(diǎn)v和u之間有一條簡單路徑。因?yàn)樗衭∈P2只有一條容量為1的出向邊,所以不同的v∈P1,其對應(yīng)的u∈P2不同。事實(shí)上,所有v∈P1、u∈P2之間的簡單路徑,即可作為節(jié)點(diǎn)v對應(yīng)的儀器引腳和節(jié)點(diǎn)u對應(yīng)的UUT引腳之間的路由路徑,它將引腳v路由到引腳u。這是因?yàn)閺男再|(zhì)2可得,任何不同v、u之間的簡單路徑不會交叉或重合,并且任何開關(guān)矩陣的輸出引腳,最多被連接了一個輸入引腳,這就滿足了引腳連接函數(shù)“單射”的要求。由于所有的UUT引腳都連接在同一開關(guān)矩陣上,因此通過修改UUT引腳所連的開關(guān)矩陣的引腳連接函數(shù),即可為任意的路由需求rdf生成路由策略(從這里可以看出與UUT引腳連接的開關(guān)矩陣的作用:所有儀器引腳被路由到此開關(guān)矩陣的輸入引腳,經(jīng)過此開關(guān)矩陣后轉(zhuǎn)接到相應(yīng)的UUT引腳)。充分性證明完畢。

定理1的充分性證明是構(gòu)造性的。它給出了路由策略生成算法的原型。下面的偽代碼將給出路由策略生成算法的詳細(xì)過程。

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

輸入互連網(wǎng)絡(luò)N=(KS,V1,V2,f)、測試需求rdf

輸出路由策略rsf

1. Route_Strategy_Generate(N,rdf)

2. begin

3. 生成N的生成流網(wǎng)路G

4. 運(yùn)行最大流算法,得到G的最大流f

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

6. 返回失敗

7. else

8. 根據(jù)f生成子圖Gf

9. for Gf中的每一條邊(u,v)

10. if 節(jié)點(diǎn)u是不與UUT引腳連接的矩陣開關(guān)K的輸入引腳

11. 令rsf(K)引腳轉(zhuǎn)接函數(shù)的rsf(K)(u)=v

12. else if u是與UUT引腳連接的矩陣開關(guān)K的輸入引腳

13. 找到與v之間存在簡單路徑的節(jié)點(diǎn)w∈P1

14. 令rsf(K)引腳轉(zhuǎn)接函數(shù)的rsf(K)(u)=N.f(rdf(w))

15. end if

16. end for

17. 返回路由需求rsf

18. end if

19.end

上述算法的第12行～第14行給出了與UUT引腳連接的開關(guān)矩陣的引腳連接函數(shù)生成方法。對于與UUT引腳連接的開關(guān)矩陣的某個輸入引腳對應(yīng)的節(jié)點(diǎn)u,如果某個節(jié)點(diǎn)w∈P1和u之間有一條簡單路徑,表明w對應(yīng)的引腳被路由到了u對應(yīng)的引腳。為了將w引腳路由到路由需求rdf要求的UUT引腳rdf(w),就需要將u連接到與rdf(w)連接的輸出引腳N.f(rdf(w))。

3 信號傳播路徑性能優(yōu)化

由于不同的開關(guān)矩陣存在質(zhì)量、已使用時長等方面的差異,因此不同的開關(guān)矩陣有不同的信號傳播阻力。所以,應(yīng)當(dāng)將信號傳播阻力也作為開關(guān)矩陣的參數(shù)。

定義8開關(guān)矩陣K的信號傳播阻力記為K.r。

傳播阻力的值和開關(guān)矩陣的轉(zhuǎn)接延遲、可靠性等性能有關(guān)。例如,文獻(xiàn)[6]給出了一種基于開關(guān)的可靠性的度量方法。本文不討論如何度量開關(guān)矩陣的傳播阻力,只將其視作抽象值。

由于路由策略在儀器引腳和UUT引腳之間建立的信號傳播路徑會經(jīng)過若干個開關(guān)矩陣,因此信號傳播路徑也會因?yàn)樗?jīng)過的開關(guān)矩陣的不同而表現(xiàn)出不同的信號傳播阻力。

定義9如果信號傳播路徑P所經(jīng)過的開關(guān)矩陣構(gòu)成集合KP={k1,k2,…,kn},則信號傳播路徑的傳播阻力P.r定義為:

(1)

定義10如果一個路由策略rsf建立的所有信號傳播路徑構(gòu)成集合Prsf={P1,P2,…,Pn},則策略rsf的平均阻力rsf.r定義為:

(2)

為了提高整體的信號傳播質(zhì)量,一個最理想的路由策略應(yīng)當(dāng)是所有滿足路由需求的路由策略中平均阻力最小的策略。

只需要基于最小費(fèi)用最大流算法,對第2節(jié)描述的路由策略生成算法進(jìn)行改進(jìn),即可得到求解阻力最小的路由策略的算法。稱此優(yōu)化算法為ORSG算法(Optimized Route Strategy Generate Algorithm)。

首先,對于生成流網(wǎng)絡(luò)G=(E,V,c),其中頂點(diǎn)集V=P1∪P2∪P3∪P4∪P5∪{s,t},定義花費(fèi)函數(shù)cst:E→R+∪{0}(R+是正實(shí)數(shù)集合)。此函數(shù)為流網(wǎng)絡(luò)中的每一條邊關(guān)聯(lián)一個費(fèi)用值。它的值的定義為:對于邊(u,v)∈E,如果u∈P3,v∈P4并且u、v分別對應(yīng)同一開關(guān)矩陣K的輸入、輸出引腳,則cst(u,v)=K.r;否則,cst(u,v)=0。

然后,將RSG算法在第4行調(diào)用的最大流改為最小費(fèi)用最大流。容易看出,在任何滿足|f|=|V1|的流f的生成子圖Gf中,所有邊的花費(fèi)的和就是由Gf導(dǎo)出的所有信號傳播路徑的傳播阻力的和。由于由最小費(fèi)用最大流算法生成的流fmin的生成子圖Gfmin的邊的花費(fèi)和最小[13-14],因此由Gfmin導(dǎo)出的路由策略的平均阻力也一定最小。

下面分析ORSG算法的時間復(fù)雜度。同RSG算法相同,ORSG算法的時間復(fù)雜度取決于最小費(fèi)用最大流算法的時間復(fù)雜度。由于最小費(fèi)用最大流算法調(diào)用SPFA算法[15]尋找殘量網(wǎng)絡(luò)中花費(fèi)最小的增廣路徑,并且每個增廣路徑都導(dǎo)致流量增加單位流量,因此ORSG算法最多共執(zhí)行SPFA算法|V1|次。文獻(xiàn)[15]指出,SPFA算法的平均時間復(fù)雜度是O(k|E|),其中k是不大于2的常數(shù)。因此,ORSG算法的平均時間復(fù)雜度是O(k|E||V1|)。

4 實(shí)例分析

對于如圖2所示的互連網(wǎng)絡(luò)N=(KS,V1,V2,f),假設(shè)有如表2所示的路由需求。現(xiàn)在應(yīng)用該算法來尋找滿足此需求的路由策略。

表2 路由需求rdf函數(shù)

首先要生成此互連網(wǎng)絡(luò)的流網(wǎng)絡(luò)G。然后求此流網(wǎng)絡(luò)的最大流f,結(jié)果為|f|=2=|V1|,表明路由需求可以得到滿足。在求得最大流的基礎(chǔ)上,算法繼續(xù)生成對應(yīng)于f的生成子圖Gf,結(jié)果如圖4所示。

圖4 互連網(wǎng)絡(luò)的生成子圖

由圖4可知,在儀器引腳A.1和UUT引腳UUT.1之間有一條簡單路徑,在儀器引腳B.1和UUT引腳UUT.2之間也有一條簡單路徑。這2條路徑可以分別將A.1路由到UUT.1、B.1路由到UUT.2。最終的路由策略rsf以及各個開關(guān)的引腳轉(zhuǎn)接函數(shù)ptf如表3～表6所示。

表3 路由策略rsf函數(shù)

表4 ptf1引腳轉(zhuǎn)接函數(shù)

表5 ptf2引腳轉(zhuǎn)接函數(shù)

表6 ptf3引腳轉(zhuǎn)接函數(shù)

通過這樣的路由策略,儀器引腳A.1通過路徑K1.in1→K1.out1→K3.in1→K3.out1到達(dá)UUT.1引腳,儀器引腳B.1通過路徑K2.in2→K2.out1→K3.in2→K3.out2到達(dá)UUT.2引腳。

如果某個路由需求要將A.1路由到UUT.2,將B.1路由到UUT.1,只需將K3的輸入引腳in1轉(zhuǎn)接到輸出引腳out2,將輸入引腳in2轉(zhuǎn)接到輸出引腳out1,即可滿足該要求。

5 實(shí)驗(yàn)結(jié)果與分析

本節(jié)給出相關(guān)實(shí)驗(yàn)的實(shí)驗(yàn)結(jié)果。實(shí)驗(yàn)中用到的測試?yán)逃煞抡娉绦蛏?。仿真程序接收的參?shù)包括互連網(wǎng)絡(luò)中的開關(guān)矩陣數(shù)、引腳連接關(guān)系數(shù)以及路由策略中指定需要路由的信號對數(shù)。

第1組實(shí)驗(yàn)比較本文提出的算法和文獻(xiàn)[9]中給出的算法的有效性。本組實(shí)驗(yàn)用到的測試?yán)虆?shù)如表7所示。

表7 實(shí)驗(yàn)1測試?yán)虆?shù)

文獻(xiàn)[9]中的算法應(yīng)用Dijkstra算法為單一UUT、儀器引腳對搜索信號傳播路徑。對于多個UUT、儀器引腳對,文獻(xiàn)[9]中的算法所搜索出的多個信號傳播路徑之間可能會有沖突。一旦發(fā)生沖突,文獻(xiàn)[9]中的算法就失效。表8顯示在不同測試數(shù)據(jù)下,文獻(xiàn)[9]算法和本文算法是否生成了有效的路由策略。

表8 不同測試數(shù)據(jù)下有效性比較

可見,對于多數(shù)情況,文獻(xiàn)[9]中的算法無法生成有效的路由策略,而本文算法能夠生成有效的路由策略。

第2組實(shí)驗(yàn)通過運(yùn)行實(shí)例來對RSG算法和ORSG算法進(jìn)行比較。本組實(shí)驗(yàn)用到的測試用例參數(shù)如表9所示。

表9 實(shí)驗(yàn)2測試?yán)虆?shù)

圖5比較了RSG算法和ORSG算法的運(yùn)行時間。從圖5中可知,RSG算法快于ORSG算法。圖6比較了RSG算法和ORSG算法生成的路由策略的平均阻力?？梢奜RSG算法生成的路由策略的平均阻力小于RSG算法生成的路由策略的平均阻力。

圖5 運(yùn)行時間比較

圖6 路由策略平均阻力比較

綜合圖5、圖6可知,RSG算法速度快,但生成的路由策略的平均阻力較大;ORSG算法生成的路由策略的平均阻力較小,但速度慢。因此,在對實(shí)時性要求較高的場合應(yīng)使用RSG算法;在對信號傳播質(zhì)量要求較高的場合,應(yīng)當(dāng)使用ORSG算法。

6 結(jié)束語

為解決自動測試系統(tǒng)中多個激勵信號的同時路由問題,本文對矩陣開關(guān)、矩陣開關(guān)互連網(wǎng)絡(luò)進(jìn)行了形式化建模,并給出了路由需求、路由策略的形式化定義。在此基礎(chǔ)上,提出一個時間復(fù)雜度為O(|E||V1|)的路由策略生成算法——RSG算法,并證明了其正確性。此外定義了路由性能的評價指標(biāo),給出用于優(yōu)化路由性能的優(yōu)化算法——ORSG算法。最后通過實(shí)驗(yàn)對本文的2個算法與文獻(xiàn)[9]算法在有效性、運(yùn)行時間、路由性能等方面進(jìn)行了比較。實(shí)驗(yàn)結(jié)果表明,在對實(shí)時性要求較高的場合應(yīng)使用RSG算法;在對信號傳播質(zhì)量要求較高的場合應(yīng)使用ORSG算法。另外,對開關(guān)矩陣互連網(wǎng)絡(luò)做了一些限制,如不滿足這些限制,本文算法將不再適用。下一步將對如何突破上述限制進(jìn)行研究,進(jìn)一步完善本文算法。

[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] 劉金寧,孟 晨,趙錦成.面向信號的自動測試系統(tǒng)軟件模型研究[J].測控技術(shù),2010,29(3):63-66.

[4] 梁 旭,李行善,高占寶.基于測試引擎的自動測試系統(tǒng)軟件設(shè)計(jì)[J].電子測量與儀器學(xué)報(bào),2006,20(5):11-16.

[5] 鐘天云.面向信號的ATS軟件平臺研究─系統(tǒng)建模工具與運(yùn)行時服務(wù)設(shè)計(jì)[D].成都:電子科技大學(xué),2013.

[6] 齊少華.TPS流程式開發(fā)環(huán)境與儀器管理模塊的研究與實(shí)現(xiàn)[D].成都:電子科技大學(xué),2013.

[7] 趙瑞賢,孟曉風(fēng),王國華.通用ATE開關(guān)資源測試路徑模型及應(yīng)用[J].北京航空航天大學(xué)學(xué)報(bào),2006,32(2):181-185.

[8] 王國華,楊中亮,陳妮亞.ATE開關(guān)矩陣動態(tài)路徑搜索算法[J].北京航空航天大學(xué)學(xué)報(bào),2010,36(1):39-42.

[9] 王怡蘋,李文海,文天柱.面向信號測試的路徑搜索算法研究[J].儀器儀表學(xué)報(bào),2013,34(7):1650-1658.

[10] 王國華,楊中亮,陳妮亞.ATE開關(guān)矩陣動態(tài)路徑搜索算法[J].北京航空航天大學(xué)學(xué)報(bào),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.算法導(dǎo)論[M].3版.徐建平,譯.北京:機(jī)械工業(yè)出版社,2013.

[13] 宋常城.基于最小費(fèi)用最大流算法的若干研究與分析[D].南京:南京郵電大學(xué),2012.

[14] 趙禮峰,宋常城,白 睿.基于最小費(fèi)用最大流問題的“排序”算法[J].計(jì)算機(jī)技術(shù)與發(fā)展,2011,21(12):82-85.

[15] 段凡丁.關(guān)于最短路徑的SPFA快速算法[J].西南交通大學(xué)學(xué)報(bào),1994,29(2):207-212.