一種基于圖論的FPGA互連資源可測性設計

文 藝，鄭咸劍

（1.電子科技大學自動化工程學院，成都611731；2.北京微電子技術研究所，北京100076）

一種基于圖論的FPGA互連資源可測性設計

文 藝1，鄭咸劍2

（1.電子科技大學自動化工程學院，成都611731；2.北京微電子技術研究所，北京100076）

針對SRAM型FPGA可編程互連資源可測性設計，采用圖論中的Ford－Fulkerson算法開展雙長線可測性建模與實現技術研究，研究如何實現可測性結構。在此研究基礎上對雙長線模型進行擴展，可解決四長線、六長線、八長線等其它復雜結構線段及開關的可測性問題。在Xilinx公司Virtex－II系列XC2V1000百萬門FPGA上進行了驗證。結果顯示該方法可通過軟件工具自動化開發測試圖形，針對固定1和固定0兩種故障模型，在較少的測試配置數量下即能獲得較高的故障覆蓋率。

SRAM型FPGA；可測性設計；互連資源；圖論；Ford－Fulkerson算法；數學模型

1 引 言

隨著數字集成電路集成度不斷提高、可集成的功能日趨復雜，其可測試性也變得愈加困難，測試開銷不斷提升。因此，在復雜的數字集成電路設計中往往需采用可測性設計（以下簡稱DFT）技術來實現所集成功能盡可能地被測試。通常而言，在保證故障覆蓋率的前提下，DFT技術主要有兩個目標：①盡可能減少額外附加的硬件開銷；②盡可能減少測試向量集合，縮短測試時間［1］。

目前，國內外針對ASIC的DFT技術已建立了相應流程和專用的DFT EDA工具，在ASIC設計階段，采用專用DFT EDA工具在芯片內相關功能單元或周邊接口插入專用測試電路結構，在測試過程中，由自動測試設備（ATE）對這些已插入的測試結構進行特定的功能測試［2－3］。采用DFT技術后，芯片的故障覆蓋率一般都達到95%以上。

SRAM型FPGA 由于其內部資源的可編程性和邊界掃描鏈的設計，本身即可為DFT構建必要的硬件基礎，滿足可測性設計的可控制性和可觀察性要求。但與ASIC測試不同，FPGA測試結構無法簡單應用現有的商用DFT EDA工具插入DFT結構，FPGA內部的每類資源在編程前是無特定功能的，需要可測試設計人員利用其可編程特性設計針對內部每類資源的測試配置圖形，通常需要通過多次配置迭代以實現較高的故障覆蓋率。目前針對SRAM型FPGA內部的可編程邏輯單元、輸入輸出單元以及內嵌IP核等資源的可測試設計技術研究已經取得可喜的進展，但對于可編程互連資源，當其數量較少時，很容易構建具有可控制性和可觀察性的DFT結構（如使用FPGA中所有的輸入輸出單元為某一個可編程開關盒構建DFT結構），但當其數量較多時，可作為觀測點的外部輸入輸出單元不足以構建覆蓋所有可編程互連資源的DFT結構。并且隨著器件規模越來越龐大，互連規律越來越復雜，互連資源測試面臨著兩方面的挑戰：一是難以得到有效率的測試圖形；二是窮舉等方式需要耗費大量的人力成本且幾乎不可實現。目前國內外針對上述問題開展了一定的研究：如伊利諾伊州大學Vishal Suthar使用的蛇形串聯法［4］，奧本大學B.E.Dixon使用的回環法［5］等。這兩種方法均屬于基于規則圖形的布線方法，這類方法依靠人工方法尋找由互連線段構成的局部可測性結構，再通過人工或軟件方法將局部的可測性結構擴展到全局，得到全局的可測性結構。這類方法雖然實現比較簡單，能夠覆蓋大部分的可編程互連線，但是對于大量的可編程互連點（下稱PIP）難以遍歷，不能保證互連資源整體的故障覆蓋度。北京大學的趙建斌提出采用深度優先遍歷算法遍歷開關盒內所有PIP的方法［6］。這種方法適用于開關盒簡單的Xilinx公司XC4000型FPGA產品，由于深度優先遍歷算法固有的復雜度缺陷，隨著開關盒復雜度的提高，采用該算法遍歷開關盒的復雜度將呈幾何倍數增長，導致難以獲得最優化的可測性結構。

根據近年的研究，一些圖論的相關知識可用于解決FPGA互連可測性的問題，其中用于解決最大流問題的Ford－Fulkerson算法可避免上述規則圖形法、深度優先算法的固有缺點，并已在Xilinx公司Virtex型FPGA產品的單長線測試上獲得應用［7］。本研究采用了Ford－Fulkerson算法構建可測性結構的方法，在Xilinx公司Virtex－II系列XC2V1000型FPGA產品的雙長線、六長線等復雜結構線段及開關的可測試性設計上進行應用，實現了使用軟件工具自動化開發測試圖形，從而節省了人力成本，并提高了故障覆蓋率。

2 SRAM型FPGA互連資源建模

Xilinx公司SRAM型FPGA是一種基于查找表（LUT）和觸發器（FF）的島型結構，這種結構也是目前最主流的SRAM型FPGA結構，主要由可配置邏輯模塊（CLB）、輸入輸出單元（IOB）、存儲單元、IP核及可編程互連資源等部分組成。這些可編程單元通過全局互連線（Global Line）、局部互連線（Local Line）和可編程開關盒（SM）等可編程互連資源相互連接［8］。

根據SRAM型FPGA互連線跨越邏輯塊的數量分類，全局互連線通常包括雙長線、四長線、六長線、八長線等類型。這些互連線除了跨越邏輯塊的數量不同，結構及傳遞規律均類似，選擇其中一種線進行研究，其結果可以進行參數化處理，并推廣到其他類型的線段。在此以雙長線為目標，構建一個具體的互連結構數學模型，以該模型為基礎研究Ford－Fulkerson算法在互連資源可測性設計中的應用。

假設每個可編程開關盒中，以該開關盒為起點的雙長線有四條（上下左右各一條），則進入該開關盒的雙長線也為四條，可得開關盒模型如圖1（a）所示。假設所建FPGA模型由m*n個圖1（a）所示開關盒構成，取m、n為3，根據雙長線特性，構建得到簡化FPGA模型如圖1（b）所示。將如圖1（b）所示的模型放入二維坐標系中，可以得到如圖1（c）所示的開關盒矩陣，每一個開關盒根據其所在的位置有對應的二維坐標（i，j）。以該開關盒為起點的雙長線的終點開關盒的坐標（x（i），y（j））計算方式如公式（1）－（4）所示。由此構建了一個已知開關盒位置、相應互連關系及PIP分布情況的數學模型。

公式（1）為雙長線向左傳遞時終點開關盒的坐標計算方式：

公式（2）為雙長線向右傳遞時終點開關盒的坐標計算方式：

公式（3）為雙長線向上傳遞時終點開關盒的坐標計算方式：

公式（4）為雙長線向下傳遞時終點開關盒的坐標計算方式：

以上述數學模型為基礎，研究如何將圖論方法應用到該模型中，可大大簡化圖形設計和覆蓋率統計的難度，協助理解真實結構的特點，實現復雜結構的可測性結構。

圖1 簡單雙長線及其數學模型

3 測試圖形的生成

通過圖論中解決最大流問題的Ford－Fulkerson算法實現有效的SRAM型FPGA互連資源測試圖形，將互連資源的PIP和互連線轉換為最大流問題的點和邊，從而將測試圖形的設計問題轉換為通過最大流算法尋找包含最多點和邊的圖形問題。

3.1 算法原理

人們通常用圖對網絡進行建模，網絡的邊輸送某一類的流量，而結點起著在不同邊之間通過流量的“開關”作用。例如，考慮一個公路系統，其中的邊是公路，結點是交叉路口；或者一個計算機網絡，其中邊是可以發送數據包的連接線而結點是開關。或者一個管網，其中邊是輸送液體的管道，而節點是管道被連在一起的節點。這類型的網絡模型有幾個要素：邊上的容量，指出它們可以運送多少流量；圖中的源點，產生交通；圖中的匯點，可以吸收到達的交通量。

將這種網絡圖抽象為在源點產生，通過邊輸送，并且在匯點被吸收的流。可以說一個流網絡是具有如下特征的有向圖G＝（V，E）：

（1）每條邊e關聯一個非負的值，稱之為容量c；

（2）有向圖中存在單一、包含于V的源點s；

（3）有向圖中存在單一、包含于V的匯點t。

給定一個流網絡，一個自然的目標就是安排交通以使得有效容量盡可能得到有效使用，故最大流問題即為：對于一個指定流網絡，找出一個具有最大值的流。

給定一個流網絡G以及G上的流f，可以定義G關于f的剩余圖Gf：

（1）Gf的結點集與G的結點集相同；

（2）對G的每一條邊e＝（u，v），其中f（e）＜ce，那么存在ce－f（e）的剩余容量單位，則Gf中也存在該條邊，其容量為ce－f（e），并稱之為前向邊；

（3）對G中的每一條邊e＝（u，v），其中f（e）＞0，當有必要時，可以通過向后推這個流來“撤銷”它，因此在Gf中也包含邊e′＝（u，v），其容量為f（e），并將該邊稱之為后向邊；

（4）為了與初始流網絡G中對應邊的容量加以區分，將剩余圖Gf中包含邊的容量稱為剩余容量。

其中Ford－Fulkerson算法能有效找出一個流網絡的最大流，其算法原理如下所示。

此時得到的流f即為該流網絡G的一個最大流。

最大流問題是在一個圖形網絡中，尋找出口和入口之間最大限度利用資源的圖形，而SRAM型FPGA的互連測試尋求解決的問題與之類似。

3.2 測試圖形生成的算法實現

對于一個SRAM型FPGA互連資源形成的網絡，對該網絡求得一個最大流，則該最大流所經過的路徑即為單次配置所能遍歷到的最多PIP和互連線。為了使用Ford－Fulkerson算法，需要將根據互連資源構建的數學模型轉化為流網絡。根據流網絡的構造，在上述數學模型中添加虛擬的源點和匯點，并為每一條互連線和每一個PIP添加容量，具體轉化規則如下：

（1）由于每一條互連線以及PIP同時只能傳遞一個信號，故每條邊及PIP的容量均為1；

（2）圖1（b）所示模型中的開關盒內部結構、功能均相同，故源點與匯點可設置在任一開關盒中。為了避免遺漏兩個不同開關盒之間的線段，并方便后期添加BIST結構，將源點與匯點設置在同一個開關盒中。

根據以上規則，得到由圖1（b）轉化得到的部分流網絡如圖2所示。

對該流網絡執行Ford－Fulkerson算法，獲得一個通過該流網絡的最大流量，由于此處有實際意義的通道（互連線與PIP）容量均為1，所以也就是獲得一個使用最多數目邊的測試路徑。降低第一次運行最大流算法獲得的測試路徑上的由PIP構成的邊的優先級，獲得一個新的流網絡，多次運行最大流算法，直到所有的PIP均已遍歷。此時即獲得一個資源覆蓋率為100%的測試路徑集合。

圖2 FPGA模型部分流網絡示意圖

由于源點和匯點是算法虛擬出的點，實際生成的最大流測試圖形僅含有互連線段和PIP，如圖3（a）所示，故需要在測試圖形中加入大量輸入輸出單元模擬源點和匯點，形成完整的測試配置，如圖3（b）所示。根據上文規定流網絡的源點和匯點均在一個開關盒內，且對于SRAM型FPGA而言，一個開關盒通常通過局部互連線與多個輸入邏輯單元相連，使用這些邏輯單元構建BIST結構的激勵生成器（TPG）和輸出響應分析器（ORA），可以將源點和匯點壓縮到少量的CLB單元中，從而節約了大量輸入輸出資源，降低了向量復雜度。BIST結構如圖3（c）所示。

圖3 測試路徑及BIST結構

綜上，針對上述構建的簡單雙長線模型，通過最大流算法得到了一個優化的測試向量集。

4 模型擴展

在實際應用中，SRAM型FPGA內部的雙長線數量遠多于圖1（b）所示的簡化模型的雙長線數量。在此以實際系統中應用最廣泛的Xilinx公司Virtex－II系列XC2V1000產品為例，將3*3的簡化模型擴展為42*38的真實模型，使用Ford－Fulkerson算法，獲得一個優化的測試向量集。

XC2V1000結構如圖4（a）所示，為一個42*38的矩陣，即m＝42，n＝38。統計得到以其中一個開關矩陣為起點的雙長線數量為40條，將這40條雙長線按照不同的傳遞方向以及相互之間的位置分為10組，每組4條雙長線（上下左右各一條），同時將相應的以該矩陣為終點的雙長線（同樣為40條）加入到這10組中。對這10組雙長線中的任意一組建模，均能得到與圖1（a）所示開關盒相類似的模型。這樣，一個復雜的由80條雙長線構成的開關矩陣，可以分解為10層的與圖1（a）類似的矩陣模型。即將一個42*38的互連資源模型分解為10層與圖1（b）所類似的互連關系模型，如圖4（b）所示。對該10層模型中的每一個圖層進行最大流求解，可得到相對于每一個圖層的優化測試路徑集合。

圖4 XC2V1000結構圖及其模型

在得到一系列的最優化測試路徑后，可以通過如下規則疊加圖層以減少最終的測試配置數量：

（1）若兩個測試路徑完全沒有重疊，則可疊加；

（2）若兩個測試路徑重疊的互連線均作為扇出端，則可疊加，否則不可疊加。

根據以上分析，整個測試配置生成的流程如圖5所示。其中WUT（Wires Under Test）指的是待測試的互連資源圖形。

圖5 測試配置生成流程圖

5 實現與驗證

以Xilinx公司Virtex－II系列XC2V1000百萬門FPGA產品為目標器件進行了設計實現與驗證，獲得了針對雙長線的有效測試向量。對10個圖層執行Ford－Fulkerson算法之后，獲得40條測試路徑，通過疊加圖層，最終得到有36個測試配置的測試向量集。該模型中的所有待測點均在36次測試中得到覆蓋，因此該測試向量集針對固定0及固定1等故障的故障覆蓋率能達到100%。由于其他類型線與雙長線為平行關系，雙長線的測試圖形可以與其他類型線的測試圖形進行疊加，從而減少整個互連資源測試向量集的數目。如圖6為其中某一個測試配置的布線圖形。

使用軟故障注入的方法（修改碼流，插入人為斷點），對該測試配置進行驗證，可以得到如圖7所示的波形，插入到CLB結構中的響應收集器將錯誤信息以高電平形式反饋到輸出端。通過故障注入軟件對100%的雙長線開關進行了遍歷，結果表明，雙長線的全部故障均可被檢測。

圖6 XC2V1000型FPGA雙長線資源的某個測試配置

圖7 仿真波形

6 結束語

研究了圖論中的Ford－Fulkerson算法在構建FPGA互連資源可測性設計中的應用，并在Xilinx公司XC2V1000百萬門FPGA產品中進行了驗證，形成了有效的可測性結構。所研究的方法具有一定的通用性，可以方便地應用到其他類型的互連線段測試圖形設計中，所生成的測試圖形針對固定1和固定0兩種故障模型可獲得較高的故障覆蓋率。由于各類型線段的數學模型相互獨立，因此，各類型線段的測試圖形可以進一步疊加，壓縮整體的配置數量。可以看到利用最大流相關的Ford－Fulkerson算法來尋找和構建互連資源的可測性結構是一種靈活、方便、高效的方法。

［1］ 王厚軍.可測性設計技術的回顧與發展綜述［J］.中國科技論文在線，2008，3（1）：52－58.

Wang Houjun.Reviews of Testability Design Technology［J］.China Science Paper Online，2008，3（1）：52－58.

［2］ Williams M J Y，Angell J B.Enhancing Testability of Large－scale Integrated Circuits via Test Points and Additional Logic［J］.IEEE Transactions on Computers，1973，c－22（1）：46－60.

［3］ 韓威，江川.ASIC集成電路的可測性設計與技術實現［J］.計算機科學，2009，36（4）：289－292.

Han Wei，Jiang Chuan.Design for Testability and Implement Technology in ASIC Design［J］.Computer Science，2009，36（4）：289－292.

［4］ Suthar V，Dutt S.Efficient On－line Interconnect Testing in FPGAs with Provable Detectability for Multiple Faults［C］.//Design，Automation＆Test in Europe，Date，2006，1：1－6.

［5］ B.E.Dixon Jr，Built－In Self－Test of the Programmable Interconnect in Field Programmable Gate Arrays［D］.Auburn：Auburn University，2008.

［6］ Zhao J，Feng J，Lin T，et al.A Novel FPGA Manufactureoriented Interconnect Fault test［C］.//Solid－State and Integrated－Circuit Technology，ICSICT 2008：2091－2094.

［7］ M.B.Tahoori，Test FPGAs［D］.California：Stanford University，2003.

［8］ Xilinx，Inc.Virtex－II Platform FPGAs：Complete Data Sheet，DS031（v3.5）［Z］，2007.

Design for Testability of FPGA Interconnect Resources Based on Graph Theory

Wen Yi1，Zheng Xianjian2
（1.School of Automation Engineering，University of Electronic Science and Technology of China，Chengdu 611731，China；2.Beijing Microelectronics Technology Institute，Beijing 100076，China）

Aiming at constructing an effective test pattern for SRAM－based FPGA interconnect resources，a graph theorymethod，called Ford－Fulkerson arithmetic，is applied in a simplified doublelinemathematic model to research the effective design for testability.The testability of other complicated segment lines and switches in SRAM－based FPGA，such as quad lines，hex lines and octal lines，can be obtained by expanding the double－line model.The method is verified in one kind of Virtex－II platform FPGA called XC2V1000，and the results indicate that the test patterns can be generated automatically through software tools and a high fault coverage rate are achieved with a small number of test configurations for stuck－at－0 fault and stuck－at－1 fault.

SRAM－Based FPGA；Design for testability；Interconnect resources；Graph theory；Ford－Fulkerson arithmetic；Mathematic model

10.3969/j.issn.1002－2279.2015.06.003

TN79

A

1002－2279（2015）06－0009－06

文藝（1990－），女，北京市人，碩士研究生，主研方向：寬帶時域測試技術與儀器。

2015－04－28