FPGA互連測試中的反饋橋接故障覆蓋問題

毛志明，張 穎，姚嘉祺，華屹峰，楊濟中，陳 鑫

(南京航空航天大學 電子信息工程學院，南京 211100)

0 引言

由于FPGA的可多次編程、結構靈活和開發周期短等優點，其應用越來越廣[1]，對器件本身的可靠性要求也不斷提高，所以FPGA測試的研究也越來越受重視。FPGA互連資源占用芯片的大部分面積，且隨著FPGA規模和集成度的不斷提高，元器件以及布線的密度越來越大，使得互連資源在制造和使用過程中出現故障的概率增大。為確?；ミB資源的可靠性，國內外已有大量文獻對FPGA互連資源的測試展開了研究。

文獻[2]對現有測試方法進行了完整的綜述，該文獻中將測試方法大致分為應用無關測試和應用相關測試。國外對FPGA的測試研究較早，技術也很成熟，主要在研究如何實現最少的測試配置數和測試時間[3-7]，而國內由于專利壁壘造成的技術壟斷[8]，研究起步較晚，且研究主要是基于應用無關測試[9-13]，應用無關互連測試考慮的是整片FPGA的互連資源，其測試目的是保證整片FPGA互連資源的正確性，而通常在設計中使用不到所有的互連資源，因此應用無關測試的效率相對較低；應用相關互連測試只需考慮設計中所使用的互連資源，無需測試整片FPGA的互連資源，效率更高，且能在測試出互連故障后，在設計中對故障進行容錯，從而使用戶定義的設計不受影響。

在現有的應用相關互連測試方法中，文獻[14]提出通過修改邏輯塊配置并保留互連配置來測試互連資源，并實現互連資源的固定0/1故障的覆蓋測試。隨后文獻[15]中考慮到互連中的無反饋橋接故障，使用單項函數，并結合“沃爾什碼”實現固定故障和無反饋橋接故障的測試。測試FPGA所花費的時間大多由測試配置的數量決定，因此應用相關互連測試的主要目標是通過最小化測試配置的總數來減少測試時間。文獻[16]中提出只使用一種測試配置，在該配置下施加多次測試向量。文獻[17]中提出使用一個激活輸入連接多個網絡，實現測試配置以及激活輸入的減少，但該方案需要設計電路具有較好的連通性，即存在較大扇出數。隨后文獻[18]中指出現有的應用相關測試技術的限制性問題，并對互連故障類型進行了進一步的補充，提出“主導與”無反饋橋接故障及“主導或”無反饋橋接故障，文中還首次對反饋橋接故障進行了定義。文獻[19]中使用SAT對故障進行測試配置生成，其中針對反饋橋接故障，借鑒了文獻[18]中的定義，但文中未給出使用該定義約束生成的測試向量實例。

針對上述互連測試文章中存在的反饋橋接故障的覆蓋難題，本文只考慮單個LUT內的橋接故障，并結合單項函數的使用，對反饋橋接故障模型進行優化，再對相應故障設計約束條件，最后使用SAT求解器生成符合約束條件的測試配置。在ISCAS’89基準電路上進行的測試配置生成實驗表明生成的測試向量不僅成功覆蓋反饋橋接故障，而且所生成的測試配置使用了最少的配置次數實現了故障列表的100%覆蓋。

1 應用相關互連測試準備工作

FPGA互連資源主要分為CLB內的互連資源和CLB間的互連資源。CLB內的互連資源位于每個CLB內部，其測試可以同CLB內的邏輯資源測試同時進行，不在這里討論。CLB間的互連資源實現了CLB與CLB之間的路由，多為LUT與LUT的連接，本文討論的CLB間的互連資源測試，主要考慮LUT與LUT的連接測試，若原始設計中使用了進位鏈、多路復用器等資源，將繞過這些部分。對于CLB間的互連資源測試，可通過修改邏輯資源配置，保持路由資源的配置不變進行測試，具體測試過程將在下文給出。

1.1 單項函數

互連測試在研究測試方法之前首先要考慮故障在測試過程中的傳播。單項函數是一個只含有最大項或最小項的邏輯函數式，在其真值表中，只有一組向量的輸出值與其他向量值不同，該組向量被稱之為激活輸入。圖1中展示了一個4輸入LUT單項函數和其對應的激活輸入，該單項函數只有一個最大項，在施加了對應的激活輸入(1001)之后，相應信號線間的敏感故障會被覆蓋激活，若此時信號線A存在固定0故障，輸入會由1001變為0001，輸出則會由0變為1，于是在LUT輸出處就會發現輸出響應不匹配，并將錯誤的輸出向后傳播，最終到達觀測點。使用單項函數可以保證電路所有敏感故障的檢測，并解決了故障向后傳播的問題。

1.2 故障列表

最早的互連測試只考慮了固定故障，而后對橋接故障進行了分析建模，由“線與”、“線或”橋接發展到“主導”、“主導與”以及“主導或”橋接，最后又增加了對反饋橋接故障的分析，因此目前給出的互連資源故障列表包括固定故障，“主導”、“主導與”、“主導或”橋接故障以及反饋橋接故障。

“主導”橋接只要兩信號線邏輯值不同就會激活故障；“主導與”橋接在兩信號線邏輯值不同且主導信號線的邏輯值為“0”時激活；“主導或”橋接在兩信號線邏輯值不同且主導信號線的邏輯值為“1”時激活，相關故障的真值表在表1中給出。表中第1行展示的是無故障時的真值情況，而其他行都存在相應的故障，表中加粗帶下劃線的邏輯值為故障所導致的變化。

表1 互連故障真值表

2 故障模型改進優化

文獻[20]中將橋接故障分為無反饋和反饋兩種類型，在圖2(a)中虛線展示了無反饋橋接故障，發生在輸入與輸入之間，不存在通路；圖2(b)中虛線展示了反饋橋接故障，發生在輸入與輸出之間，存在反饋通路。而在文獻[18-19]對反饋橋接故障的研究中，都只考慮到輸入通過意外橋接通路影響輸出的情況，而未考慮到輸出通過意外橋接通路影響輸入。

圖2 橋接故障

現有文獻研究反饋橋接故障時考慮了任意信號線之間的可能性，而在FPGA設計中，考慮所有信號線之間的橋接故障是不合適的，因為這樣不僅使故障的數量變得十分龐大，使整個電路的狀態分析變得十分困難，增加了測試的難度，并且基于FPGA的布局布線信息，一些物理距離相對較遠的信號線之間不可能發生橋接故障。

為了優化對反饋橋接故障的測試，本文將反饋橋接故障劃分為影響輸出型橋接和反饋輸入型橋接，并且只考慮單個LUT內的反饋橋接故障，其中電路中存在的橋接故障數與LUT的規格、數量有關。下面在結合單項函數的使用下對這兩種類型的反饋橋接故障進行故障測試現象分析。

影響輸出型橋接表現為輸入信號線D通過意外通路導致輸出信號線F發生變化；反饋輸入型橋接表現為輸出信號線F通過意外通路導致輸入信號D發生變化。結合單項函數的使用，在圖3中針對反饋橋接的兩類故障的故障現象進行分析。圖3(a)將影響輸出型橋接故障分為“主導”橋接、“主導與”以及“主導或”橋接。當存在“主導”橋接故障時，若D和F邏輯值相同，則無法觀察到故障現象，也就無法檢測出D主導F橋接，若D和F的邏輯值不相同時，如圖3(a)中描述的例①，當D為0(1)，F為1(0)時，若存在“主導”橋接故障，輸入信號線D通過意外橋接環路使得輸出線F的邏輯值發生變化，即由1(0)變為0(1)，而這種變化可以通過單項函數傳播到最終輸出，從而可以檢測到影響輸出型“主導”反饋橋接故障的存在?！爸鲗Щ颉睒蚪拥倪壿嬛底兓芍鲗盘柧€的邏輯值1主導，圖3(a)中的例②描述了在D為1，F為0時，若存在D“主導或”F橋接故障，D會導致F由0變為1，結合單項函數的故障傳播機制，使得在后續的觀測點能觀測到故障現象，同樣能夠檢測到故障的存在?！爸鲗c”橋接的邏輯值變化由主導信號線的邏輯值0主導，圖3(a)中的例③描述了在D為0，F為1時，若存在D“主導與”F橋接故障，D會導致F由1變為0，同理也能檢測到故障的存在。

在圖3(b)中分析了反饋輸入型橋接故障的故障現象檢測。同樣將反饋輸入型橋接分為“主導”橋接、“主導或”和“主導與”橋接。F“主導”D橋接故障的現象只有在D和F的邏輯值不等時才能被激活，圖3(b)中例①描述了D和F的邏輯值不相等的兩種情況，當D為0，F為1時，若存在F“主導”D橋接故障，輸出信號線F通過意外橋接環路使得輸入D的邏輯值發生變化，即D會由0變為1，但輸入D發生改變后，在使用單項函數的情況下，此時的輸入向量與單項函數的激活輸入不同，因此輸出F會發生改變，即由1變為0。這時D為1，F為0，D和F的值又不相同，“主導”橋接故障激活，F又會使D發生由1變為0的變化，這時輸入恢復為原來的激活輸入，導致F又會發生改變，重復以上變化，將形成振蕩。當D為1，F為0時，同理可得，故障現象也表現為邏輯值振蕩，雖然反饋輸入型“主導”橋接會導致電路發生振蕩，但是由于單項函數的存在，故障的振蕩現象會向后傳播，在最后的觀測點可以觀測到，所以能檢測反饋輸入型“主導”橋接故障的存在。圖3(b)的例②和例③分別分析了F“主導或”D橋接故障以及F“主導與”D橋接故障，其中例②故障發生的邏輯變化由F的邏輯1主導，例③故障發生的邏輯變化由F的邏輯值0主導，對應故障現象的分析步驟與上述相同，且都能在輸出端檢測到故障的存在，但反饋輸入型“主導與”橋接、“主導或”橋接并不會發生反饋輸入型“主導”橋接的反復振蕩現象。

圖3 反饋橋接故障測試現象分析

從上述對優化的故障模型進行分析中，可以看出使用單項函數并施加特定的測試向量能夠很好地檢測到反饋橋接故障的存在，相比于以往文獻，該優化的故障模型既解決了數量龐大的故障列表問題，又優化了反饋橋接故障存在的測試難題。表2中給出了單個4輸入LUT存在的所有互連故障。

表2 單個4輸入LUT的故障列表

不同規格的LUT由于輸入信號線數量的不同，因此所存在的互連故障數量會不相同，如圖4所示，圖中實線描繪了單個不同規格的LUT所存在的互連故障總數，虛線描繪了單個配置下能覆蓋到的最多的互連故障數占單個LUT總故障數的百分比情況。從圖4中可看出含輸入信號線數量越多的LUT，所存在的互連故障越多，而隨著LUT輸入信號線的增多，單個配置能覆蓋到的最多的故障數占相應故障總數的比重逐漸減小。針對反饋橋接故障所優化的故障模型適用于任意規格的LUT，且對于具體的電路映射在不同型號的FPGA上，測試該電路所需的互連測試配置數與該FPGA的LUT規格呈反比趨勢。

圖4 不同規格LUT的故障情況

3 測試向量生成

在對反饋橋接故障模型進行改進優化之后，再對整個互連故障列表進行測試向量約束，即給出覆蓋到上述所有故障應該滿足的條件，并用布爾等式或不等式對這些條件進行描述的過程。而通過使用SAT，可知曉是否存在這樣的測試配置滿足上述的布爾等式約束，若存在，則使用SAT求解器進行求解，從而生成測試配置，最終目的是使用最少數量的測試配置并覆蓋到所有的故障。所使用的SAT是一類用來發現是否有任何值可以滿足公式表示的約束的問題。來自不同領域的許多問題的表述都可以使用SAT來完成。用布爾公式表示的問題可用布爾可滿足性來解決，而需要非布爾值的問題可以使用可滿足性模理論(SMT)來表述[21]。因此，測試向量生成問題可以被表述為一組約束條件，并使用SAT求解器來求解滿足約束條件的測試向量。為了構建測試電路，將SAT求解器算出的滿足約束條件的測試向量，即分配給每個LUT信號線的值，充當對應LUT的激活輸入，這些值也決定了在每個LUT上實現的單項函數功能。

1)固定故障約束：為了檢測互連網絡中的特定故障，測試向量首先應該激活故障，因此檢測固定故障，就需要施加激活固定故障的測試向量。檢測固定0故障，需要施加邏輯值“1”；檢測固定1故障，需要施加邏輯值“0”。在一個應用設計中存在許多互連信號線，這些信號線無法在一次測試配置中完全覆蓋所有信號線的固定故障，因此需要多次測試配置，所以固定故障的約束條件為至少存在一種配置，使得某一條被測互連線被施加邏輯值“0”，存在另一種配置使得同一條被測互連線被施加邏輯值“1”，即：

其中：Vni代表一個LUT的第ni條輸入信號線的值，x和y代表配置號。

2)無反饋橋接故障約束：無反饋橋接故障主要發生在LUT輸入端的成對信號線中，只有在同一個測試配置中對相應的成對信號線施加相反的邏輯值時，才能檢測到無反饋橋接故障的存在。如圖2中C與D存在的無反饋橋接故障，而橋接故障又分為“主導”型、“主導與”型 、“主導或”型，要激活對應的故障，只需在同一個測試配置中對C和D施加不同的邏輯值。因此，對于某一個LUT的無反饋橋接約束如下：

其中：ni和nj代表該LUT的兩個不同輸入信號線，ni為主導方，nj為被主導方，Vni和Vnj代表相應的邏輯值，x為配置號。

3)反饋橋接故障約束：文獻[18]中對反饋橋接故障的測試進行了一系列的等式約束，但該約束條件只考慮了輸入影響輸出的情況；在文獻[19]中對反饋橋接故障進行約束時，借鑒了文獻[18]中的約束條件，但在該文中并未舉例說明反饋橋接故障的測試配置結果。而本文只考慮單個LUT內的反饋橋接故障，并將反饋橋接分為影響輸出型和反饋輸入型，對應的約束條件相比于以往研究中所使用的一系列等式約束更加簡捷方便，使用簡單的測試向量就能夠覆蓋反饋橋接故障的各種類型。其原理與無反饋橋接故障約束類似，若要檢測圖2中的D與F之間存在的反饋橋接故障，只需要在同一配置中對D和F施加不同的邏輯值，以激活不同類型的反饋橋接故障。因此，對于某一個LUT的影響輸出型橋接的約束如下：

其中：ni代表該LUT的第ni條輸入信號線，nf代表該LUT的輸出線,Vni和Vnf代表其相應的邏輯值，ni為主導方，nf為被主導方，x為配置號。反饋輸入型橋接與影響輸出型橋接的區別在于主導和被主導的對象相反，其約束與影響輸出型橋接約束同理，不再贅述。

4)賦值沖突約束：對于特定的設計，其中的LUT之間的錯綜復雜連接，會使得同一條信號線分別連接到多個LUT，而在上述對不同故障類型的激活約束過程中，可能會使得同一條信號線被賦值為多個邏輯值，即某條信號線在同一測試配置中被同時賦值“0”和“1”兩種邏輯值，所以對于此類的賦值沖突需要進行避免。賦值沖突約束如下：

為了覆蓋電路中所有故障的測試，生成的測試向量必須滿足上述所有的約束條件，使用SAT求解器算出滿足約束條件的測試配置。針對圖5所示的電路，使用上述的約束條件進行測試向量生成，在表3中展示了所提出的方法生成的測試配置和對應的單項函數，考慮到文章篇幅，未在表3中列出對應測試配置所覆蓋的故障，但結合文章上述對互連故障的介紹，可以分析出表3中所生成的測試配置不僅覆蓋到所有固定故障和無反饋橋接故障，而且還覆蓋到所有的反饋橋接故障，成功解決了以往研究中的反饋橋接覆蓋難題。上述生成的測試配置所覆蓋的故障數占總故障數的百分比折線如圖6所示。其中使用SAT求解器生成的第一次測試配置覆蓋了41%的故障，在第二次覆蓋69%的故障，第三和第四次分別覆蓋了89%和100%的故障。

圖5 示例電路

表3 針對圖6電路生成的測試配置及對應的單項函數

圖6 測試配置所覆蓋的故障數占總故障數的百分比

4 仿真與分析

針對上述優化后的反饋橋接故障模型，在ISCAS’89基準時序電路上進行測試配置生成實驗，本文所有實驗都是在一個8 GB內存的Window系統上進行的。為了與先前研究結果進行比對，選擇了先前文獻[19]中相同的20個基準電路，并將這些電路映射到相同型號的Xilinx Virtex4(XC4VLX100)FPGA上，表4展示了這些基準電路所使用的資源數量，以及相應互連資源所存在的故障數量。

表4 ISCAS’89基準電路實現在Virtex-4上的結果

在整個實驗過程中，首先選擇對應型號的FPGA建立工程，并對基準電路進行綜合，使用Python腳本對綜合后生成的網表文件提取電路的連接關系；再根據電路的連接關系對電路互連線進行故障約束以及賦值沖突約束，并使用Python自帶的庫SAT求解器：Z3[22]，生成滿足上述約束的測試配置，將生成的測試向量作為LUT的激活輸入，計算出對應的單項函數。生成測試配置后，需要將原始電路修改為測試電路，即將原始電路中LUT的邏輯功能修改為測試配置中的單項函數。為了修改LUT的內容，使用 “xdl-ncd2xdl **.ncd” 命令將基準電路經過映射后所生成的本地電路描述(NCD)文件轉成賽靈思設計語言(XDL)文件，其中XDL文件是可讀文本文件。同樣使用腳本語言對XDL文件中LUT的邏輯功能進行批量修改，再使用 “xdl -xdl2ncd **.xdl”命令將修改好的XDL文件轉回NCD文件，得到了對應的測試電路，最后施加測試向量進行測試分析，表5中列出了對應的基準電路所需要的測試配置數。

在文獻[15]中使用“沃爾什碼”生成測試配置的方法測試n條信號線需要log2(n+2)次配置；而在文獻[18]中指出“沃爾什碼”生成的配置存在無法完備覆蓋“主導與”、“主導或”故障的問題，并提出在2≤n<7時，需要額外一個配置實現故障列表的100%覆蓋。而本文因為只考慮了單個LUT內的橋接故障，需要對LUT與LUT之間的連接進行賦值沖突約束，對于較為復雜的電路連接關系就需要額外的1個配置處理賦值沖突，所以針對本文所描述的優化故障模型，需要最多log2(n+2)次配置才能實現故障列表的100%覆蓋，其中n為單個LUT的信號線數。

而本文是在Virtex4上進行測試配置生成實驗，其中Virtex4的LUT規格為4輸入，按上述分析得出實現故障列表的100%覆蓋所需要的最大配置數為5，與表5中所展示的配置生成實驗的結果相吻合，表明了本文分析的最大配置數的正確性。本文的主要貢獻是解決了反饋橋接故障的覆蓋難題，為了更加公平地進行結果比對，在表5中只列出了文獻[19]中的測試配置次數，而未列出現有研究中未覆蓋反饋橋接故障的實驗結果。文獻[19]針對反饋橋接故障進行的測試配置生成實驗，其所使用的測試生成方法與本文相同，但該文針對反饋橋接故障的約束條件借鑒了文獻[18]中的對反饋橋接故障的定義。因此，將本文實驗數據與文獻[19]的數據進行比較最能表明本文優化后的反饋橋接故障模型的可行性。從表5中可看出，本文與文獻[19]所生成的測試配置次數在前幾個基準電路上持平，而在后續的基準電路上，本文實現了測試配置數量的減少，而測試FPGA所花費的時間主要取決于測試配置的數量。上述結果表明本文所做的反饋橋接故障模型優化和改進不僅成功地解決了反饋橋接故障的覆蓋問題，還實現了測試配置數的減少，對提升應用相關的FPGA互連資源測試的效率具有重要的意義。

5 結束語

本文針對以往研究中所生成的測試配置存在的反饋橋接故障覆蓋難題進行了研究，分析了以往研究中的不足，并對反饋橋接故障模型進行優化改進，而后對固定故障、無反饋橋接故障以及優化后的反饋橋接故障進行覆蓋約束，并用SAT求解器生成滿足約束條件的互連測試配置，最后在ISCAS’89基準電路上進行測試配置生成實驗，生成的測試向量成功解決反饋橋接故障的覆蓋難題，實現了故障列表的100%覆蓋，且與先前研究相比，所生成的測試配置次數實現了最小化。為提高在FPGA上實現的任意設計的可靠性，不僅需要生成測試配置進行故障測試，后續還需要相應的診斷配置實現進行故障定位以及故障容錯工作。本文所做的應用相關互連測試配置生成研究旨在解決FPGA互連資源的測試配置的故障列表覆蓋問題，為完成對設計的測試以及后續互連故障定位和互連故障容錯等研究奠定了基礎。