郭東升,唐 敏,吳鐵彬,劉衡竹
(國(guó)防科學(xué)技術(shù)大學(xué)計(jì)算機(jī)學(xué)院,湖南 長(zhǎng)沙 410073)
隨著集成電路制造工藝的進(jìn)步和芯片集成規(guī)模的急劇增加,芯片測(cè)試數(shù)據(jù)猛增,導(dǎo)致測(cè)試成本急劇上升,如何降低測(cè)試數(shù)據(jù)的存儲(chǔ)開銷并縮短測(cè)試時(shí)間是當(dāng)前學(xué)術(shù)界研究的熱點(diǎn)。
減少測(cè)試數(shù)據(jù)的存儲(chǔ)開銷可以通過BIST(Build-In Self-Test)結(jié) 構(gòu)[1]和 測(cè) 試 數(shù) 據(jù) 壓 縮 技 術(shù)來實(shí)現(xiàn)[2]。BIST結(jié)構(gòu)需要嵌入到芯片中,常常和片上的測(cè)試數(shù)據(jù)產(chǎn)生模塊聯(lián)合使用。雖然BIST結(jié)構(gòu)可以大幅度地減少需要存儲(chǔ)的測(cè)試數(shù)據(jù)數(shù)量,不過利用BIST結(jié)構(gòu)的測(cè)試時(shí)間會(huì)增加,而且BIST結(jié)構(gòu)會(huì)改變測(cè)試電路的物理結(jié)構(gòu),增加約束條件,這些都限制了BIST結(jié)構(gòu)的使用。而測(cè)試數(shù)據(jù)壓縮技術(shù)則不需要對(duì)電路結(jié)構(gòu)進(jìn)行改變,可以獨(dú)立于測(cè)試電路對(duì)測(cè)試數(shù)據(jù)進(jìn)行壓縮,從而減少測(cè)試數(shù)據(jù)的存儲(chǔ)開銷。
EFDR算法[3]是一種典型的基于編碼壓縮的測(cè)試數(shù)據(jù)壓縮算法。EFDR算法考慮對(duì)連續(xù)0游程和連續(xù)1游程分別編碼,具有算法簡(jiǎn)單、壓縮解壓縮結(jié)構(gòu)小、壓縮效率高等特點(diǎn)。
除了編碼壓縮算法的研究,針對(duì)非確定位填充的研究也很重要。由于測(cè)試數(shù)據(jù)中的非確定位數(shù)量極大[4],合理地對(duì)非確定位填充會(huì)提高壓縮算法的壓縮效率。
本文以EFDR算法為基礎(chǔ),研究EFDR算法的非確定位填充要求,提出了針對(duì)EFDR編碼壓縮算法優(yōu)化的非確定位填充算法ESA(EFDR-Suited X-filling Algorithm)。基于ISCAS’89標(biāo)準(zhǔn)電路[5]的實(shí)驗(yàn)結(jié)果表明,該算法在不提高測(cè)試功耗的前提下,提高了EFDR算法的壓縮效率,縮短了測(cè)試時(shí)間。
測(cè)試數(shù)據(jù)中的非確定位是非常多的,常常占測(cè)試數(shù)據(jù)總數(shù)的70%以上,更有些測(cè)試數(shù)據(jù)中的非確定位數(shù)占到測(cè)試數(shù)據(jù)的90%以上(見表1),所以合理填充非確定位可能會(huì)對(duì)測(cè)試數(shù)據(jù)壓縮效果有所提高。

Table 1 Ratio of X in test data表1 非確定位在測(cè)試數(shù)據(jù)中所占的比例
傳統(tǒng)的非確定位填充技術(shù)主要包括全0填充和全1填充,即分別對(duì)非確定位全部填充0或者全部填充1,除此之外還有一些改進(jìn)的非確定位填充算法,如:最少傳輸跳變填充算法MT-filling(Minimum-Transition-fill)[6]、鄰 近 位 相 同 填 充 算 法Adjacent-filling[7]。MT-filling填 充 算 法 在 填 充時(shí),如果非確定位序列兩邊的確定位相同,非確定位填充值為相同確定位的值,否則隨機(jī)填充0或者1;在Adjacent-filling算法中,非確定位的填充與傳輸方向上的臨近確定位相同。
對(duì)于測(cè)試數(shù)據(jù)0XXX1X0X1XXX1X0
全0填充為:000010001000100
全1填充為:011111011111110
MT-filling為:000011001111100
Adjacent-filling為:000011001111110
EFDR編碼壓縮算法的非確定位填充算法和這些算法不同,EFDR在填充非確定位時(shí),考慮了EFDR算法的特點(diǎn),其編碼字見表2。EFDR編碼壓縮算法對(duì)以1結(jié)尾的0游程或以0結(jié)尾的1游程進(jìn)行編碼,按照游程的長(zhǎng)度范圍將游程劃分到不同的組中,編碼字隨分組編號(hào)的增加而遞增,組編號(hào)小的編碼字短,組編號(hào)大的編碼字長(zhǎng),增幅為兩位。

Table 2 Code word of EFDR code表2 EFDR編碼算法編碼字表
由表2可知,測(cè)試數(shù)據(jù)游程越長(zhǎng),編碼效率越高。故EFDR算法的非確定位填充規(guī)則如下:
(1)當(dāng)非確定位游程兩邊的確定位相同時(shí),非確定位填充值為該確定位值。
(2)當(dāng)非確定位游程兩邊的確定位不相同時(shí),沿測(cè)試數(shù)據(jù)的傳輸方向:
①當(dāng)非確定位游程前的確定位游程長(zhǎng)度大于1時(shí),非確定位的填充值與前邊的確定位值相同;
②當(dāng)非確定位游程前的確定位游程長(zhǎng)度為1時(shí),非確定位填充值與后邊的確定位值相同。
依據(jù)上述填充規(guī)則,對(duì)于測(cè)試數(shù)據(jù):
1XXXX1 11XXXXX0XXXX1 1XXX0 0XXXX1XX0XXXX01
EFDR算法的填充結(jié)果為:111111 11111110 11111 11110 000001 000000001
EFDR算法對(duì)非確定位的填充已經(jīng)考慮到了其算法的編碼特點(diǎn),不過由于每個(gè)分組都包含一定的游程長(zhǎng)度,所以對(duì)于包含非確定位的測(cè)試數(shù)據(jù)段,不同的非確定位填充方法,得到的編碼游程分組可能不同。
例如,對(duì)于測(cè)試數(shù)據(jù)序列:
11111XXX00XXXXXXXXXXX1
使用EFDR算法的填充為:
111111110 0000000000001
所屬編碼分組都為A3,需要的編碼字長(zhǎng)為14位。
考慮第一個(gè)非確定位游程,由表2可知,如果將第一個(gè)非確定位游程的前一個(gè)非確定位填充為1,后兩個(gè)確定位填充為0,這樣填充之后得到的測(cè)試數(shù)據(jù)可以劃分為一個(gè)屬于A2組的連續(xù)1游程和一個(gè)屬于A3組的連續(xù)0游程,即:
1111110 000000000000001
壓縮該測(cè)試數(shù)據(jù)段需要的壓縮編碼總長(zhǎng)為12位,相對(duì)于EFDR算法的填充方法少了2位。
本文提出的非確定位填充算法按照以下的填充規(guī)則填充:
規(guī)則1 當(dāng)非確定位兩邊為1時(shí),即測(cè)試數(shù)據(jù)序列形如:1XXXX1時(shí),非確定位填充為1;
規(guī)則2 當(dāng)非確定位兩邊為0時(shí),即測(cè)試數(shù)據(jù)序列形如:0XXXX0時(shí),非確定位填充為0;
規(guī)則3 當(dāng)非確定位兩邊的確定位不同時(shí),即測(cè)試數(shù)據(jù)形如:1XXXXX0或0XXXXX1時(shí),考慮兩邊確定位的情況進(jìn)行填充。
本文提出的非確定位(ESA)填充算法可以分為三步:首先對(duì)滿足規(guī)則1和規(guī)則2情形的非確定位進(jìn)行填充;之后將待填測(cè)試數(shù)據(jù)進(jìn)行預(yù)處理,得到測(cè)試數(shù)據(jù)游程類型數(shù)組T={ti},確定游程長(zhǎng)度數(shù)組L={li}以及非確定位游程長(zhǎng)度數(shù)組M={mi};最后利用數(shù)組T、L、M對(duì)非確定位游程進(jìn)行劃分和填充,得到待壓縮測(cè)試數(shù)據(jù)游程長(zhǎng)度數(shù)組S={si}。
例如,對(duì)于測(cè)試數(shù)據(jù):11XXX000XXX110,預(yù)處理得到的數(shù)組T={1,0,1,0},L={2,3,2,1},M={3,3,0,0};之后將M中的每一個(gè)元素mi分割成ai與bi之和,mi=ai+bi,其中,非確定位游程中的前ai個(gè)非確定位填充和ti相同,后bi個(gè)非確定位填充和ti+1相同;最終得到的待壓縮測(cè)試數(shù)據(jù)游程長(zhǎng)度數(shù)組S={si},si=bi-1+li+ai。
由以上討論可知,對(duì)非確定位游程長(zhǎng)度mi的劃分是ESA填充算法的核心,考慮EFDR算法的非確定位填充要求,根據(jù)測(cè)試數(shù)據(jù)的特征數(shù)組T、L,非確定位游程長(zhǎng)度mi的劃分方法見表3。

Table 3 Segmentation of mi表3 算法中mi的劃分方法
非確定位填充算法的主要步驟如下:

利用ESA填充算法對(duì)非確定位填充,可以得到更短的壓縮字,例如,對(duì)于如下長(zhǎng)度為60位的測(cè)試數(shù)據(jù)段:

利用EFDR算法的填充算法得到的壓縮后的需要存儲(chǔ)的測(cè)試數(shù)據(jù)為(共46位):

利用ESA填充算法得到的壓縮后的需要存儲(chǔ)的測(cè)試數(shù)據(jù)為(共40位):

相對(duì)于利用EFDR算法的填充方案,ESA填充算法可以減少壓縮數(shù)據(jù)的長(zhǎng)度,提高壓縮效率。
為了驗(yàn)證填充算法ESA的有效性,本文使用Matlab實(shí)現(xiàn)該算法,基于ISCAS’89基準(zhǔn)測(cè)試電路,Mintest ATPG[8]產(chǎn) 生 的 測(cè) 試 向 量 集,使 用ESA填充算法填充測(cè)試數(shù)據(jù)中的非確定位;再利用EFDR算法壓縮測(cè)試數(shù)據(jù),得到的測(cè)試數(shù)據(jù)壓縮效率與原EFDR算法的壓縮效率比較見表4。假設(shè)TD是原始的測(cè)試數(shù)據(jù)總位數(shù),TE是壓縮后的編碼字的總位數(shù),壓縮效率CR可以表示如下:


Table 4 Comparison of compression ratio between EFDR and EFDR+ESA表4 改進(jìn)填充算法壓縮效率比較
表4中,TD代表原始測(cè)試數(shù)據(jù)量,EFDR代表使用EFDR的填充算法得到的壓縮后的測(cè)試數(shù)據(jù)數(shù)量TE和壓縮效率CR,EFDR+ESA表示使用ESA填充算法得到的壓縮后的測(cè)試數(shù)據(jù)數(shù)量TE和壓縮效率CR。由Improvement的數(shù)據(jù)可知,利用ESA填充算法時(shí),EFDR編碼壓縮的壓縮效率提高1.14%,證明ESA填充算法是有效的。其中,對(duì)于電路S9234和電路S38417的提高相對(duì)較高,這說明,ESA所針對(duì)的特征非確定位在這兩個(gè)電路中占的比例較大。
由于本文僅對(duì)填充算法進(jìn)行了優(yōu)化,并未對(duì)壓縮和解壓縮結(jié)構(gòu)做任何改變,所以本節(jié)只考慮可能會(huì)受到填充算法改變而影響到的測(cè)試數(shù)據(jù)的翻轉(zhuǎn)功耗。
由前文可知,本文提出的算法只針對(duì)非確定位兩邊確定位不相同的情形,即0XXXX1或1XXXX0這兩種情形,對(duì)于這種情形的填充方法,由表3可知,可以分為以下幾種情況:
非確定位與前邊確定位相同;
非確定位與后邊確定位相同;
非確定位前一部分與前邊確定位相同,后一部分與后邊確定位相同。
例如,對(duì)于0XXXXX1,本文得到的填充方案只有:00000001、01111111、00011111這三種情況,而這三種情況都不會(huì)增加該序列的01和10的翻轉(zhuǎn)數(shù),故本文提出的填充算法不會(huì)增加測(cè)試數(shù)據(jù)的翻轉(zhuǎn)率。
本節(jié)分析ESA填充算法對(duì)測(cè)試時(shí)間開銷的影響,按照文獻(xiàn)[9]的方法,測(cè)試時(shí)間可以通過以下方法計(jì)算:
假設(shè)頻率比率α=fCUT/fATE,fCUT是被測(cè)試電路的工作頻率,fATE是測(cè)試設(shè)備的時(shí)鐘頻率。假設(shè)測(cè)試集有N個(gè)編碼字C1~CN,每個(gè)編碼字的長(zhǎng)度為Wi,則αmax[9]為:

其中,Hi-1為Ci-1解壓縮得到的測(cè)試數(shù)據(jù)的長(zhǎng)度。
如果α<αmax,由于解壓縮一個(gè)編碼字用的時(shí)間比從自動(dòng)測(cè)試設(shè)備ATE(Automatic Test Equipment)傳輸一個(gè)編碼字到被測(cè)電路CUT(Circuit Under Test)所用的時(shí)間長(zhǎng),這時(shí)ATE會(huì)等CUT幾個(gè)時(shí)鐘周期,則測(cè)試時(shí)間TAT[9]為:

如果α>αmax,可以得到為:

表5給出了使用ESA填充算法時(shí)的時(shí)間開銷和使用EFDR算法的填充算法的時(shí)間開銷對(duì)比,頻率比率α從4~10,表格的第三列為使用EFDR算法填充的時(shí)間開銷,第四列是使用ESA填充算法時(shí)的時(shí)間開銷,最后一列Improvement表示使用ESA填充算法相對(duì)于使用EFDR填充算法的時(shí)間開銷的節(jié)省幅度。由表5中數(shù)據(jù)可知,相對(duì)于EFDR的填充算法,ESA填充算法可以適當(dāng)減少時(shí)間開銷,減少幅度大都在1%~2%,當(dāng)頻率比率α增大時(shí),提升幅度相應(yīng)也會(huì)提高。

Table 5 Comparison of test time表5 不同填充算法測(cè)試時(shí)間開銷比較
本文提出了一種新的基于EFDR編碼壓縮算法的非確定位填充算法,該算法針對(duì)測(cè)試向量中可能出現(xiàn)的一些特定情況進(jìn)行優(yōu)化改善。針對(duì)ISCAS’89基準(zhǔn)測(cè)試電路的實(shí)驗(yàn)結(jié)果表明,在使用本文提出的填充算法對(duì)非確定位進(jìn)行填充時(shí),壓縮效率相對(duì)于原始EFDR算法提高了1.14%,時(shí)間開銷相對(duì)減少了2%左右,并且本算法不會(huì)增加測(cè)試向量的翻轉(zhuǎn)率,即不會(huì)引入額外的測(cè)試功耗,同時(shí)硬件開銷與原有EFDR算法一致。
[1] McCluskey E J.Built-in-self-test structures[J].IEEE Design &Test of Computers,1985,2(2):29-33.
[2] Touba N A.Survey of test vector compression techniques[J].IEEE Design &Test of Computers,2006,23(4):294-303.
[3] EL-Maleh A H.Test data compression for system-on-a-chip using extended frequency-directed run-length code[J].IET Computer Digital Technology,2008,2(3):155-163.
[4] Miyase K,Kajihara S.Don’t care identification of test patterns for combinational circuits[J].IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems,2004,23(2):321-326.
[5] Bglez F,Bryan D,Kozminski K.Combinational profiles of sequential benchmark circuits[C]∥Proc of International Symposium on Circuits and Systems,1989:1924-1934.
[6] Sankaralingam R,Touba N.Multi-phase shifting to reducing instantaneous peak power during scan[C]∥Proc of the 4th IEEE Latin American Test Workshop,2003:78-83.
[7] Girard P,Nicolici N,Wen X.Power-aware testing and test strategies for low power devices[M].New York:Springer,2009.
[8] Hamzaoglu I,Patel J H.Test set compaction algorithms for combinational circuits[C]∥Proc of IEEE International Conference on Computer-Aided Design,1998:283-289.
[9] Gonciari P T,Al-Hashimi B M,Nicolici N.Improving compression ratio,area overhead,and test application time for system-on-a-chip test data compression/decompression[C]∥Proc of Design,Automation and Test in Europe Conference and Exhibition,2002:604-611.