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

文 藝，鄭咸劍

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

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

文 藝1，鄭咸劍2

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

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

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

1 引 言

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

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

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

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

2 SRAM型FPGA互連資源建模

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

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

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

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

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

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

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

以上述數(shù)學模型為基礎(chǔ)，研究如何將圖論方法應用到該模型中，可大大簡化圖形設計和覆蓋率統(tǒng)計的難度，協(xié)助理解真實結(jié)構(gòu)的特點，實現(xiàn)復雜結(jié)構(gòu)的可測性結(jié)構(gòu)。

圖1 簡單雙長線及其數(shù)學模型

3 測試圖形的生成

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

3.1 算法原理

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

將這種網(wǎng)絡圖抽象為在源點產(chǎn)生，通過邊輸送，并且在匯點被吸收的流?？梢哉f一個流網(wǎng)絡是具有如下特征的有向圖G＝（V，E）：

（1）每條邊e關(guān)聯(lián)一個非負的值，稱之為容量c；

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

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

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

給定一個流網(wǎng)絡G以及G上的流f，可以定義G關(guān)于f的剩余圖Gf：

（1）Gf的結(jié)點集與G的結(jié)點集相同；

（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）為了與初始流網(wǎng)絡G中對應邊的容量加以區(qū)分，將剩余圖Gf中包含邊的容量稱為剩余容量。

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

此時得到的流f即為該流網(wǎng)絡G的一個最大流。

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

3.2 測試圖形生成的算法實現(xiàn)

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

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

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

根據(jù)以上規(guī)則，得到由圖1（b）轉(zhuǎn)化得到的部分流網(wǎng)絡如圖2所示。

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

圖2 FPGA模型部分流網(wǎng)絡示意圖

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

圖3 測試路徑及BIST結(jié)構(gòu)

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

4 模型擴展

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

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

圖4 XC2V1000結(jié)構(gòu)圖及其模型

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

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

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

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

圖5 測試配置生成流程圖

5 實現(xiàn)與驗證

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

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

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

圖7 仿真波形

6 結(jié)束語

研究了圖論中的Ford－Fulkerson算法在構(gòu)建FPGA互連資源可測性設計中的應用，并在Xilinx公司XC2V1000百萬門FPGA產(chǎn)品中進行了驗證，形成了有效的可測性結(jié)構(gòu)。所研究的方法具有一定的通用性，可以方便地應用到其他類型的互連線段測試圖形設計中，所生成的測試圖形針對固定1和固定0兩種故障模型可獲得較高的故障覆蓋率。由于各類型線段的數(shù)學模型相互獨立，因此，各類型線段的測試圖形可以進一步疊加，壓縮整體的配置數(shù)量?？梢钥吹嚼米畲罅飨嚓P(guān)的Ford－Fulkerson算法來尋找和構(gòu)建互連資源的可測性結(jié)構(gòu)是一種靈活、方便、高效的方法。

［1］ 王厚軍.可測性設計技術(shù)的回顧與發(fā)展綜述［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集成電路的可測性設計與技術(shù)實現(xiàn)［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，F(xiàn)eng 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－），女，北京市人，碩士研究生，主研方向：寬帶時域測試技術(shù)與儀器。

2015－04－28