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

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

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

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

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

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

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

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

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

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

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

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

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