存儲(chǔ)器測(cè)試算法及診斷覆蓋率研究

摘 要：隨著微電子技術(shù)的快速進(jìn)步，半導(dǎo)體集成電路高速發(fā)展，新的存儲(chǔ)器測(cè)試技術(shù)也不斷更新。文章描述了存儲(chǔ)器的經(jīng)典測(cè)試算法運(yùn)算過程，并分析了其原理。在研究經(jīng)典測(cè)試算法的基礎(chǔ)上，吸收經(jīng)典算法的思想，比較各種不同算法的優(yōu)缺點(diǎn)，改進(jìn)測(cè)試算法，以便在實(shí)際檢測(cè)中能夠減少測(cè)試所需要的時(shí)間，提高故障診斷覆蓋率，達(dá)到比較滿意的測(cè)試效果。

關(guān)鍵詞：存儲(chǔ)器；測(cè)試算法；診斷覆蓋率

中圖分類號(hào)：TP333.8 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1006-8937（2014）12-0009-02

存儲(chǔ)器測(cè)試技術(shù)是一直不斷更新的技術(shù)，隨著存儲(chǔ)器在市場(chǎng)上的需求日益增加，每一種新存儲(chǔ)器技術(shù)的出現(xiàn)都會(huì)引起廣泛的關(guān)注，往往新技術(shù)的出現(xiàn)都對(duì)實(shí)際測(cè)試工作造成巨大的改變。而面對(duì)越來越大的存儲(chǔ)器市場(chǎng)，生產(chǎn)商對(duì)于存儲(chǔ)器功能安全越來越重視，尋找高效的測(cè)試算法一直是存儲(chǔ)器測(cè)試過程中需要解決的問題。

1 存儲(chǔ)器測(cè)試算法

對(duì)于存儲(chǔ)器的測(cè)試，目前有許多種測(cè)試算法，有使用時(shí)間長(zhǎng)久的經(jīng)典算法，也有近些年運(yùn)用廣泛的新型算法，它們都各有特點(diǎn)。

現(xiàn)主要的算法有MSCAN算法（全“0”全“1”算法）、Checkerboard算法（棋盤法）、Gallop算法（奔跳法）、March算法等。一種實(shí)用有效的測(cè)試算法，能夠花費(fèi)較少的時(shí)間和操作程序，更全面的檢測(cè)出存儲(chǔ)器故障。

1.1 MSCAN算法（全“0”全“1”算法）

對(duì)所有單元寫“1”，再讀取所有單元，進(jìn)行對(duì)比。對(duì)所有單元寫“0”，再讀取所有單元，進(jìn)行對(duì)比。算法表達(dá)式：{■（w0）；■（r0）；■（w1）；■（r1）}。算法的執(zhí)行方式可以如下：

①?gòu)臋z測(cè)起始點(diǎn)，沿著地址遞增的方向?qū)⑺写鎯?chǔ)單元寫“0”；②從檢測(cè)起始點(diǎn)，沿著地址遞增的方向讀出所有存儲(chǔ)單元的值“0”；③從檢測(cè)起始點(diǎn)，沿著地址遞增的方向?qū)⑺写鎯?chǔ)單元寫“1”；④從檢測(cè)起始點(diǎn)，按照地址遞增的方向讀出所有儲(chǔ)存單元的值“1”。

可編程為：

For I=1 to n；Do

Write O to cell I

Read cell I for 0

Write 1 to cell I

Read cell I for 1

Continue

End

在運(yùn)用該算法過程中，若存儲(chǔ)單元無(wú)法寫入或讀出的（能夠讀出但是讀出錯(cuò)誤值），則表示此單元出現(xiàn)了故障。這個(gè)算法測(cè)試時(shí)間是T=4n，時(shí)間復(fù)雜度O（n）?？蓹z測(cè)固定故障SAF。

1.2 Checkerboard算法（棋盤法）

checkerboard算法的測(cè)試過程：對(duì)存儲(chǔ)器所以存儲(chǔ)單元賦值，賦值完后存儲(chǔ)器就像國(guó)際象棋棋盤的形式。即把整個(gè)存儲(chǔ)單元分成a、b兩塊（a為黑色，b為白色），然后用如下方式對(duì)a、b讀寫，如圖1所示。

①對(duì)分塊a（b）中的單元寫0（1）；②讀所有單元；③對(duì)分塊a （b）中的單元寫1 （0）；④讀所有單元。

一種改進(jìn)型checkerboard算法：

①對(duì)分塊a（b）中的單元寫0（1）；②對(duì)分塊a（b）中的單元寫1（0）；③讀所有單元；④對(duì)分塊a（b）中的單元寫1 （0）；⑤讀所有單元。

運(yùn)用第二種checkerboard算法，存儲(chǔ)器在檢測(cè)過程中比未改進(jìn)型的checkerboard算法多經(jīng)歷一次狀態(tài)變化。此算法則可以測(cè)試出TF故障。

checkerboard算法測(cè)試時(shí)間T=4n（5n），時(shí)間復(fù)雜度為0（n）?？蓹z測(cè)出固定故障SAF等故障，診斷覆蓋率不高。

1.3 Gallop（算法）

Gallop測(cè)試算法過程如下：

①所有單元寫0（1）；②A0寫1（0），然后A1讀0（1）；A0讀1（0），A1讀0（1），然后A2讀0（1）；A0讀1（0），接著A2讀0（1），A3讀0（1）；A0讀1（0），…直到全部單元。③將A0改寫為0（1），讀A1位1（0），重復(fù)上述步驟。

可編程為：

For I=1 to n；Do

write 0 to cell I

Continue

White I=1 to n；Do

Write 1 to cell I

Read all cell verify I

Write 0 to Cell I

Continue

End

整個(gè)算法過程類似于1（0）一直在漫游，漫游情況如圖2所示。

Gallop算法測(cè)試時(shí)間，時(shí)間復(fù)雜度為O（n2）。此算法具有較高的診斷覆蓋率，但由于其復(fù)雜度比較高，檢測(cè)過程中花費(fèi)的時(shí)間較為漫長(zhǎng)，故在實(shí)際中使用頻率比較低。

1.4 March算法

March算法是近多年在存儲(chǔ)器測(cè)試算法中使用較廣的算法之一。March算法根據(jù)算法的自由度分為很多種不同算法，March 5n是其中最基本的一種，描述如下：

①全部單元中寫0；②讀A0單元的0，然后再改寫為1，然后讀A1的0，再改寫A1為1，直到An-1。這樣所有單元均為1；③然后從An-1到AO作讀1寫0的操作。

可編程為：

For I=1 to n；Do

Write 0 to cell I

Continue

While I=1 to n；Do

Read cell I verify 0

Write 1 to cell I

Continue

For I=n to 1；Do

Read cell I verify 1

Write 0 to cell I

Read cell I verify 0

Continue

End

這種最一般的March 5n算法的表達(dá)式{■（w0）；？堊（r0，w1）；？墼（r1，w0）}。

March 5n算法的測(cè)試時(shí)間相對(duì)較短，操作程度也簡(jiǎn)單，它的測(cè)試時(shí)間長(zhǎng)為T=5n，時(shí)間復(fù)雜度0（n）。

March算法根據(jù)算法的自由度可以分為很多不同算法，下面就是一些March算法以及表達(dá)式：

March 6n

{■（w0）；？堊（r0，w1）；？墼（r1，w0，r0）}。

March 9n

{■（w0）；？堊（r0，w1）；？堊（r1，w0）；？墼（r0，w1）；？墼（r1，w0）}

march 13n

{■（w0）；？堊（r0，w1，r1）；？堊（r1，w0，r0）；？墼（r0，w1，w1）；？墼（r1，w0，w0）}

存儲(chǔ)器測(cè)試算法還有很多，不同種算法各有優(yōu)勢(shì)，但也有不同的缺點(diǎn)。如何在實(shí)際測(cè)試中發(fā)揮各種算法的優(yōu)點(diǎn)，避除其缺點(diǎn)，提高檢測(cè)效率是算法研究的重點(diǎn)。測(cè)試時(shí)長(zhǎng)和存儲(chǔ)大小的關(guān)系見表1。各種測(cè)試算法診斷覆蓋率的情況見表2。

2 改進(jìn)型的測(cè)試算法

從以上兩張表中可以看出Checkerboard算法和March算法的時(shí)間復(fù)雜度低，一個(gè)為T=4（n），一個(gè)為T=5（n），從公式中可知，。測(cè)試中操作時(shí)間和存儲(chǔ)器容量n成正比利關(guān)系。Gallop算法雖然比前兩種測(cè)試算法的診斷覆蓋率高很多，但是測(cè)試時(shí)需要進(jìn)行的操作太復(fù)雜，花費(fèi)的時(shí)間太長(zhǎng)，在實(shí)際中不具有大量使用的可能性。所以可以嘗試把March算法和Checkerboard算法結(jié)合使用，在March算法的基礎(chǔ)上應(yīng)用checkerboard算法，時(shí)間復(fù)雜度不變，但是提升了診斷覆蓋率。

改進(jìn)型算法的測(cè)試過程如下：

①所有單元寫0；②讀A0單元的0，再改寫為0；讀A1單元的0，再改寫為1；讀A2單元的0，再改寫為0；讀A3單元的0，再改寫為1...直到An-1。（即存儲(chǔ)器中存儲(chǔ)單元排列次數(shù)為奇數(shù)的單元讀0寫0，存儲(chǔ)單元排列次數(shù)為偶數(shù)的單元讀0寫1）這個(gè)步驟結(jié)果之后，存儲(chǔ)器就像被劃分為棋盤一樣，類似與進(jìn)行checkerboard測(cè)試算法操作得到的結(jié)果一樣；③讀An-1單元的1，再改寫為0；讀An-2單元的0，再改寫為1；…直到A0（即讀取每個(gè)存儲(chǔ)單元中的值再寫入相反值）。這一步完成后，存儲(chǔ)器的形式還是棋盤格式，只是其中數(shù)值都相反。

3 結(jié) 語(yǔ)

通過本文分析可知，每一種測(cè)試算法都有各自的優(yōu)點(diǎn)和缺點(diǎn)，沒有完美的測(cè)試算法。改進(jìn)的算法都是在已有的算法的基礎(chǔ)上進(jìn)行改良或者創(chuàng)新。通過理論分析和數(shù)據(jù)方面對(duì)比，改進(jìn)的算法在測(cè)試速度快速的基礎(chǔ)上，診斷覆蓋率有所提高。在日常存儲(chǔ)器測(cè)試工作中，測(cè)試算法需要不斷的完善和更新，人們同時(shí)必須不斷的嘗試和創(chuàng)新，這樣才能根據(jù)測(cè)試的實(shí)際需要尋找到合適的測(cè)試算法以便解決測(cè)試過程中遇到的問題。

參考文獻(xiàn)：

[1] 張衛(wèi)國(guó).RAM檢測(cè)的算法分析及軟件實(shí)現(xiàn)[J].西安科技學(xué)院學(xué)報(bào)，2003，（3）.

[3] 楊士元.數(shù)字系統(tǒng)的故障診斷與可靠性設(shè)計(jì)[M].北京：清華大學(xué)出版社，2000.

[4] 蔣登峰，周娟.隨機(jī)存取存儲(chǔ)器故障分析及測(cè)試方案實(shí)現(xiàn)[J].中國(guó)計(jì)量學(xué)院學(xué)報(bào)，2010，（3）.

[5] 李璇君，辛季齡，張?zhí)旌辏?RAM的故障模型及自測(cè)試算法[J].南京航空航天大學(xué)學(xué)報(bào)，1999，（1）.