納米電子系統(tǒng)的容缺陷設(shè)計(jì)方法研究.pdf

1、從物理限制和技術(shù)實(shí)現(xiàn)兩方面來(lái)看，傳統(tǒng)的互補(bǔ)金屬氧化物半導(dǎo)體(Complementary Metal-Oxide-Semiconductor-CMOS)集成電路正在迅速接近其尺度極限。新興的納米電子器件技術(shù)和其所對(duì)應(yīng)的納米電子結(jié)構(gòu)技術(shù)被認(rèn)為可以（短期）補(bǔ)充甚至（長(zhǎng)期）替代CMOS技術(shù)。納米電子技術(shù)有望實(shí)現(xiàn)極高的器件密度(1012/cm2)和操作頻率(超過(guò)100GHz)，不僅使得進(jìn)一步延伸摩爾定律成為可能，同時(shí)也展現(xiàn)出未來(lái)計(jì)算系統(tǒng)中存在的巨

2、大機(jī)遇。
　　然而挑戰(zhàn)總是和機(jī)遇并存。納米電子系統(tǒng)的設(shè)計(jì)和制造面臨一系列新的問(wèn)題，如極高的器件缺陷密度、局部互連限制、新的邏輯表達(dá)形式、以及運(yùn)行時(shí)的高瞬態(tài)錯(cuò)誤率等。對(duì)納米電子系統(tǒng)所面臨的一系列新挑戰(zhàn)的認(rèn)識(shí)，是人們向構(gòu)建功能型納米電子系統(tǒng)邁出的第一步。而納米電子器件極小的尺寸和嚴(yán)重的不可靠性，對(duì)設(shè)計(jì)自動(dòng)化技術(shù)提出了新的、嚴(yán)苛的要求，成為當(dāng)前電子科學(xué)和工程所面臨的新挑戰(zhàn)。
　　近年來(lái)，納米電子系統(tǒng)的可靠性設(shè)計(jì)開(kāi)始成為電子設(shè)計(jì)自動(dòng)

3、化和可靠性測(cè)試領(lǐng)域一個(gè)新的研究熱點(diǎn)，工作主要集中在容缺陷設(shè)計(jì)和容錯(cuò)設(shè)計(jì)兩個(gè)方面。本文研究納米電子系統(tǒng)的容缺陷設(shè)計(jì)方法。面對(duì)納米電子系統(tǒng)極高的缺陷密度，為了保證納米芯片的可用性，未來(lái)的納米芯片設(shè)計(jì)和制造工業(yè)迫切需要有效的容缺陷設(shè)計(jì)技術(shù)。有兩種可能的設(shè)計(jì)模式:應(yīng)用相關(guān)的設(shè)計(jì)模式(Application-dependent design)和應(yīng)用獨(dú)立的設(shè)計(jì)模式(Application-independentdesign)。前一種模式直接將邏輯函

4、數(shù)映射到存在缺陷的Crossbar結(jié)構(gòu)中，實(shí)現(xiàn)邏輯計(jì)算功能;后一種模式則先從有缺陷的Crossbar中提取無(wú)缺陷子結(jié)構(gòu)，再在無(wú)缺陷子結(jié)構(gòu)上實(shí)現(xiàn)邏輯映射。本文對(duì)這兩種設(shè)計(jì)模式所涉及的問(wèn)題和算法進(jìn)行了系統(tǒng)深入的研究，主要工作和成果歸納如下:
　　1.系統(tǒng)地研究了基于納米Crossbar結(jié)構(gòu)的容缺陷邏輯映射問(wèn)題及其算法。應(yīng)用相關(guān)設(shè)計(jì)模式的核心步驟是容缺陷邏輯映射(Defect-tolerant logic mapping-DTLM)。本

5、文對(duì)DTLM問(wèn)題模型及其求解算法進(jìn)行了探索性研究，包括:1）在算法設(shè)計(jì)方面，針對(duì)此前的貪婪容缺陷邏輯映射算法映射成功率低的不足，引入多樣性映射的概念，并提出了三種基于多樣性映射機(jī)制的容缺陷邏輯映射算法。實(shí)驗(yàn)結(jié)果顯示，所提算法的映射成功率是傳統(tǒng)的貪婪映射算法的幾倍到十幾倍，并且在大規(guī)模問(wèn)題上性能改進(jìn)尤其明顯。2）在問(wèn)題建模方面，對(duì)一種面向模塊化功能映射的DTLM問(wèn)題進(jìn)行了研究，設(shè)計(jì)了一種新的，更為合理的權(quán)值覆蓋率優(yōu)化模型，與之前的工作相比

6、，新模型考慮了邏輯函數(shù)的具體細(xì)節(jié)，實(shí)驗(yàn)結(jié)果表明，新模型可以更準(zhǔn)確地估計(jì)實(shí)現(xiàn)給定邏輯功能所需的納米Crossbar模塊數(shù)。
　　2.提出了一種基于Memetic算法(Memetic Algorithm-MA)和適應(yīng)度近似策略(Fitness Approximation-FA)的容缺陷邏輯映射算法。容缺陷邏輯映射(DTLM)問(wèn)題可以抽象為兩個(gè)二部圖之間的子圖同構(gòu)問(wèn)題(Subgraphisomorphism problem-SIP)，是

7、一個(gè)著名的NP完全組合搜索問(wèn)題。本文通過(guò)引入最大二部匹配(Maximum-Bipartite-Matching-MBM)，首次將DTLM問(wèn)題建模成一類組合優(yōu)化問(wèn)題?；谠搩?yōu)化模型，本文提出一種高效率的基于Memetic算法和適應(yīng)度近似策略的容缺陷邏輯映射算法，MA/FA。在MA/FA中，設(shè)計(jì)了一種新的貪婪重分配局部搜索算子(Greedy Re-assignment Local Search-GRALS)，利用問(wèn)題的領(lǐng)域知識(shí)和信息來(lái)幫助算

8、法以相對(duì)較低的計(jì)算代價(jià)找到最優(yōu)的邏輯映射方案。此外，提出采用精確MBM算法和近似MBM算法相結(jié)合的適應(yīng)度評(píng)估機(jī)制來(lái)降低算法適應(yīng)度評(píng)估的計(jì)算代價(jià)，引入一種混合策略來(lái)平衡適應(yīng)度評(píng)估的精確性和時(shí)間效率。通過(guò)在大量不同規(guī)模測(cè)試問(wèn)題上的實(shí)驗(yàn)，驗(yàn)證了MA/FA算法的優(yōu)異性能。
　　3.系統(tǒng)地研究了從有缺陷納米Crossbar結(jié)構(gòu)中提取無(wú)缺陷子結(jié)構(gòu)的問(wèn)題。應(yīng)用獨(dú)立的容缺陷設(shè)計(jì)的關(guān)鍵在于無(wú)缺陷子結(jié)構(gòu)的快速提取。對(duì)于所有在相同制造環(huán)境（相近的缺陷密

9、度p）中制造的納米芯片，無(wú)缺陷子結(jié)構(gòu)的尺寸k是相同的。為了得到在利用率和產(chǎn)率之間的平衡，制造商需要知道k值是如何影響產(chǎn)率的:給定Crossbar結(jié)構(gòu)尺寸n和缺陷密度p，存在尺寸為k的無(wú)缺陷子結(jié)構(gòu)的概率為多少？此前只能通過(guò)實(shí)驗(yàn)仿真來(lái)估計(jì)。本文提出一種無(wú)缺陷子結(jié)構(gòu)存在概率Pexist的分析方法，能估計(jì)出其緊湊的上界和下界。通過(guò)實(shí)驗(yàn)仿真驗(yàn)證了所提分析方法的有效性。
　　4.提出了一種快速無(wú)缺陷子結(jié)構(gòu)提取算法。通過(guò)對(duì)此前兩種有效算法的思想

10、進(jìn)行融合，提出一種較低時(shí)間復(fù)雜度的改進(jìn)算法。在此基礎(chǔ)上，進(jìn)一步通過(guò)減少算法主循環(huán)的次數(shù)，提升算法的時(shí)間效率，進(jìn)而提出一種快速的無(wú)缺陷子結(jié)構(gòu)提取算法。與此前最有效的算法相比，所提快速算法的時(shí)間復(fù)雜度從O（n3）降低到O（n2）。通過(guò)大量不同尺寸和缺陷密度的測(cè)試實(shí)例對(duì)算法性能進(jìn)行了測(cè)試，結(jié)果表明所提快速算法可以提供與此前最有效算法相同質(zhì)量的解，而算法的運(yùn)行時(shí)間只是其1/3-1/5。
　　5.提出了一種基于演化算法(Evolutiona

11、ry Algorithm-EA)和結(jié)構(gòu)變異(Structure Mutation-SM)的無(wú)缺陷子結(jié)構(gòu)提取算法。無(wú)缺陷子結(jié)構(gòu)提取問(wèn)題等同于最大平衡Biclique問(wèn)題(Maximum Balanced Biclique Problem-MBBP)，是一個(gè)著名的NP難組合優(yōu)化問(wèn)題。針對(duì)MBBP問(wèn)題，本文提出了一種新的基于結(jié)構(gòu)變異的演化算法，EA/SM。在EA/SM中，結(jié)構(gòu)變異算子在動(dòng)態(tài)改變解的結(jié)構(gòu)的同時(shí)，保持解的尺寸（適應(yīng)度）和合法性不變

12、。結(jié)構(gòu)變異算子實(shí)現(xiàn)了解在MBBP問(wèn)題結(jié)構(gòu)空間的一種大變異，有益于增強(qiáng)啟發(fā)式搜索過(guò)程中算法的探索能力。此外，針對(duì)MBBP問(wèn)題特點(diǎn)，設(shè)計(jì)了一種高效啟發(fā)式搜索算子。采用一種基于修復(fù)輔助的重啟過(guò)程，利用改進(jìn)的Marchiori啟發(fā)式修復(fù)算子，修復(fù)每個(gè)重新初始化的新解。通過(guò)大量不同尺寸和缺陷密度的測(cè)試實(shí)例對(duì)算法性能進(jìn)行了測(cè)試，實(shí)驗(yàn)結(jié)構(gòu)驗(yàn)證了EA/SM算法的先進(jìn)性能、以及結(jié)構(gòu)變異算子和修復(fù)輔助重啟的有效性。
　　本文工作對(duì)未來(lái)納米電子系統(tǒng)設(shè)計(jì)