文 藝，鄭咸劍

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

一種基于圖論的FPGA互連資源可測(cè)性設(shè)計(jì)

文 藝1，鄭咸劍2

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

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

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

1 引 言

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

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

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

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

2 SRAM型FPGA互連資源建模

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

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

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

公式（1）為雙長(zhǎng)線向左傳遞時(shí)終點(diǎn)開關(guān)盒的坐標(biāo)計(jì)算方式：

公式（2）為雙長(zhǎng)線向右傳遞時(shí)終點(diǎn)開關(guān)盒的坐標(biāo)計(jì)算方式：

公式（3）為雙長(zhǎng)線向上傳遞時(shí)終點(diǎn)開關(guān)盒的坐標(biāo)計(jì)算方式：

公式（4）為雙長(zhǎng)線向下傳遞時(shí)終點(diǎn)開關(guān)盒的坐標(biāo)計(jì)算方式：

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

圖1 簡(jiǎn)單雙長(zhǎng)線及其數(shù)學(xué)模型

3 測(cè)試圖形的生成

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

3.1 算法原理

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

將這種網(wǎng)絡(luò)圖抽象為在源點(diǎn)產(chǎn)生，通過(guò)邊輸送，并且在匯點(diǎn)被吸收的流。可以說(shuō)一個(gè)流網(wǎng)絡(luò)是具有如下特征的有向圖G＝（V，E）：

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

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

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

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

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

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

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

（3）對(duì)G中的每一條邊e＝（u，v），其中f（e）＞0，當(dāng)有必要時(shí)，可以通過(guò)向后推這個(gè)流來(lái)“撤銷”它，因此在Gf中也包含邊e′＝（u，v），其容量為f（e），并將該邊稱之為后向邊；

（4）為了與初始流網(wǎng)絡(luò)G中對(duì)應(yīng)邊的容量加以區(qū)分，將剩余圖Gf中包含邊的容量稱為剩余容量。

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

此時(shí)得到的流f即為該流網(wǎng)絡(luò)G的一個(gè)最大流。

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

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

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

（1）由于每一條互連線以及PIP同時(shí)只能傳遞一個(gè)信號(hào)，故每條邊及PIP的容量均為1；

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

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

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

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

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

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

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

4 模型擴(kuò)展

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

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

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

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

（1）若兩個(gè)測(cè)試路徑完全沒(méi)有重疊，則可疊加；

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

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

圖5 測(cè)試配置生成流程圖

5 實(shí)現(xiàn)與驗(yàn)證

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

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

圖6 XC2V1000型FPGA雙長(zhǎng)線資源的某個(gè)測(cè)試配置

圖7 仿真波形

6 結(jié)束語(yǔ)

研究了圖論中的Ford－Fulkerson算法在構(gòu)建FPGA互連資源可測(cè)性設(shè)計(jì)中的應(yīng)用，并在Xilinx公司XC2V1000百萬(wàn)門FPGA產(chǎn)品中進(jìn)行了驗(yàn)證，形成了有效的可測(cè)性結(jié)構(gòu)。所研究的方法具有一定的通用性，可以方便地應(yīng)用到其他類型的互連線段測(cè)試圖形設(shè)計(jì)中，所生成的測(cè)試圖形針對(duì)固定1和固定0兩種故障模型可獲得較高的故障覆蓋率。由于各類型線段的數(shù)學(xué)模型相互獨(dú)立，因此，各類型線段的測(cè)試圖形可以進(jìn)一步疊加，壓縮整體的配置數(shù)量。可以看到利用最大流相關(guān)的Ford－Fulkerson算法來(lái)尋找和構(gòu)建互連資源的可測(cè)性結(jié)構(gòu)是一種靈活、方便、高效的方法。

［1］ 王厚軍.可測(cè)性設(shè)計(jì)技術(shù)的回顧與發(fā)展綜述［J］.中國(guó)科技論文在線，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集成電路的可測(cè)性設(shè)計(jì)與技術(shù)實(shí)現(xiàn)［J］.計(jì)算機(jī)科學(xué)，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í)域測(cè)試技術(shù)與儀器。

2015－04－28