基于優(yōu)化ATPG的可測(cè)試性設(shè)計(jì)與實(shí)現(xiàn).pdf

1、自動(dòng)測(cè)試模式產(chǎn)生(Automatic Test Pattern Generation:ATPG)技術(shù)在針對(duì)芯片制造缺陷的生產(chǎn)測(cè)試中得到廣泛應(yīng)用。ATPG作為測(cè)試向量的生成工具，它能根據(jù)輸入的故障模型，生成簡(jiǎn)潔、高覆蓋率的測(cè)試向量(Test Vectors)。
　　但是傳統(tǒng)的基于結(jié)構(gòu)化搜索的ATPG算法，如果要提高測(cè)試故障覆蓋率，需要對(duì)電路進(jìn)行大量的試探性的反復(fù)回溯搜索，這樣就要耗費(fèi)大量冗余時(shí)間，使得測(cè)試成本非常昂貴。而本文提出基于

2、代數(shù)公式的二叉判決圖和布爾可滿(mǎn)足性SAT這兩種算法能有效壓縮測(cè)試時(shí)間，它通過(guò)將門(mén)級(jí)電路模塊轉(zhuǎn)化為數(shù)學(xué)邏輯，用求解命題邏輯的代數(shù)問(wèn)題，來(lái)達(dá)到快速遍歷的目的，這樣既能解決冗余回溯搜索的時(shí)間過(guò)長(zhǎng)問(wèn)題，又能提高覆蓋率。
　　但對(duì)于單純基于布爾可滿(mǎn)足性SAT的算法，由于是以整個(gè)變量空間的回溯搜索為基本框架，所以搜索空間很大，時(shí)間復(fù)雜度較高，會(huì)導(dǎo)致算法超時(shí)。因?yàn)樗阉骺臻g越大，就需要越多的回溯搜索時(shí)間，特別是對(duì)于未知的故障時(shí)間將更長(zhǎng)。而那些只基

3、于二叉判決圖BDD的算法又在構(gòu)造二叉判決圖BDD時(shí)可能導(dǎo)致內(nèi)存溢出等棘手問(wèn)題，為改善上述缺陷，本文又提出一種不同于遍歷式搜索的啟發(fā)式策略，用增量的方法盡早識(shí)別出不可測(cè)故障，節(jié)省不必要的搜索判定時(shí)間。這種二叉判決圖BDD與可滿(mǎn)足性SAT相混合的一種代數(shù)方法，采用布爾差分方程的思想，有效發(fā)揮BDD和SAT的各自在時(shí)間和空間上的優(yōu)勢(shì)，在結(jié)點(diǎn)數(shù)上做閥值判斷，做啟發(fā)式策略進(jìn)行算法的互相切換、替代運(yùn)行。同時(shí)避免了在設(shè)計(jì)BDD時(shí)會(huì)出現(xiàn)的內(nèi)存溢出問(wèn)題和

4、SAT算法超時(shí)問(wèn)題。
　　本研究采用BDD算法的工具開(kāi)發(fā)包CUDD和SAT操作的工具包Zchaff，編寫(xiě)了C++語(yǔ)言代碼在基準(zhǔn)電路上實(shí)現(xiàn)了上述混合算法的仿真驗(yàn)證和應(yīng)用分析，通過(guò)和其他算法的數(shù)據(jù)對(duì)比，發(fā)現(xiàn)這種使用智能啟發(fā)式策略的混合算法比傳統(tǒng)的搜索算法或者單一的SAT算法在測(cè)試運(yùn)行時(shí)間、回溯次數(shù)、故障傳遞路徑、內(nèi)存占有率上性能都有大幅提升，還能提高ATPG工具生成向量的效率。
　　通過(guò)該算法在TetraMAX工具平臺(tái)上的實(shí)踐驗(yàn)