徐鵬飛, 夏銀水, 查曉婧,顧賢貴

基于矩陣表示的CMOL電路容錯映射

徐鵬飛, 夏銀水*, 查曉婧,顧賢貴

（寧波大學(xué) 信息科學(xué)與工程學(xué)院, 浙江 寧波 315211）

針對存在缺陷的CMOS/納米分子混合(CMOS/nanowire/MOLeclular hybrid, CMOL)電路的單元容錯映射問題, 提出一種基于矩陣表示的CMOL電路容錯映射方法. 首先, 將邏輯電路和CMOL電路建模為矩陣表示; 然后采用文化基因(memetic)算法進行矩陣間可匹配字符的搜索, 采用小矩陣元值優(yōu)先匹配的策略完成單元缺陷容忍映射. ISCAS測試電路的實驗結(jié)果表明, 與已有方法相比, 本文方法在求解速度上有36.98%的提升.

CMOL; 單元容錯映射; 矩陣表示; memetic算法

隨著晶體管特征尺寸不斷縮小至納米級別, 由于微觀世界的寄生效應(yīng)和量子效應(yīng)[1]的影響, 傳統(tǒng)集成電路的設(shè)計方法不適合當(dāng)前發(fā)展的需求. 人們寄希望于新型的納米器件和納米混合電路[2]能夠延續(xù)集成電路的發(fā)展. CMOS/納米分子混合(CMOS/nanowire/MOLeclular hybrid, CMOL)電路[3]結(jié)合納米技術(shù)和傳統(tǒng)的CMOS工藝, 既具有納米技術(shù)的高集成密度, 又具有CMOS豐富的邏輯功能, 被認為是后CMOS時代最具有前途的替代技術(shù)之一.

綜上所述, 已有的研究總是將邏輯電路和CMOL電路建模為有向圖, 將CMOL電路的缺陷容忍映射問題轉(zhuǎn)化為有向圖的匹配問題. 由于在有向圖表示法中的每一節(jié)點、每一有向連接邊一一校對匹配效率較低, 所以這些方法的缺陷容忍映射速率較低[15]. 鑒于此, 本文提出一種基于矩陣表示的CMOL電路容錯映射方法. 首先將邏輯電路和CMOL電路建模為矩陣表示; 然后采用以遺傳算法為主, 模擬退火算法為輔的文化基因算法[16]進行矩陣間可匹配字符的搜索, 采用小矩陣元值優(yōu)先匹配的策略完成單元缺陷容忍映射. 與現(xiàn)有方法相比, 本文方法在求解速度上有較為明顯的優(yōu)勢.

1 研究背景

1.1 CMOL電路結(jié)構(gòu)

圖1 CMOL電路結(jié)構(gòu)[1]

1.2 CMOL單元映射及約束

并滿足以下約束:

圖2 CMOL電路單元映射

1.3 CMOL單元常開缺陷類型

CMOL電路在制造過程中, 由于納米器件尺寸極小且當(dāng)前采用自底向上的自組裝技術(shù)難以精確控制引腳位置, 使得CMOL電路不可避免地存在高缺陷率問題. 缺陷類型大體上可分為兩類, 即常連缺陷和常開缺陷. 對最常出現(xiàn)的常開缺陷類型分析如下:

(1)納米二極管常開. 由于納米二極管一直處于斷開狀態(tài), 連接在納米二極管上的兩層納米線不能實現(xiàn)信號傳輸, 使得通過該納米二極管連接的兩個CMOL單元無法正常通信.

(2)納米線非周期性斷裂. 由于納米線在非周期性斷點處發(fā)生不規(guī)則斷裂, 造成其所連接單元連通域減少.

(3)接口引腳常開. 由于在自底向上的自組裝過程中未能實現(xiàn)接口引腳與納米線精準(zhǔn)對齊, 造成接口引腳兩端連接的納米線層與底層CMOS單元始終處于斷路狀態(tài).

圖3 缺陷類型示意

2 CMOL缺陷容忍映射

CMOL缺陷容忍映射問題可描述為: 給定一個邏輯電路和存在缺陷的CMOL電路, 通過缺陷容忍實現(xiàn)映射后電路的邏輯功能正確. 傳統(tǒng)的缺陷容忍方法總是將邏輯電路和CMOL電路建模為有向圖, 將缺陷容忍映射問題轉(zhuǎn)換為子圖同構(gòu)問題[17], 但是其匹配效率低下. 為此, 提出將單元配置的搜索問題轉(zhuǎn)換為矩陣元素匹配問題, 從而實現(xiàn)高效快速的CMOL電路缺陷容忍映射.

2.1 邏輯矩陣(LM)的建立

圖4 LM轉(zhuǎn)化示意

2.2 CMOL矩陣(CM)的建立

根據(jù)CMOL電路連通域約束和電路缺陷分布情況, 將CMOL電路構(gòu)造成矩陣表示. 圖5(a)所示為含有25個單元的存在常開缺陷的CMOL電路. 其中, 左上角數(shù)字表示該單元的編號; 黑色框線內(nèi)的區(qū)域為單元13原始輸出連通域, 單元13的輸出納米線非周期性斷裂成L1、L2兩部分, 故單元11、17、23不在其連通域范圍; 單元13與單元9間的納米二極管①以及單元13與單元7間的納米二極管②存在常開缺陷; 界面接口引腳常開缺陷致使單元15、24與其連通域范圍內(nèi)的其他單元均無法通信, 因此, 需舍棄該單元. 圖5(b)是根據(jù)圖5(a)構(gòu)造的CM, 其中矩陣的行列號均表示CMOL單元編號, 矩陣中的每個矩陣元值表示兩個單元之間的曼哈頓距離.

圖5 CMOL缺陷電路及其矩陣表示

當(dāng)單元發(fā)生界面接口引腳常開缺陷時, 該單元無法與其他所有的正常單元實現(xiàn)通信, 不可將電路節(jié)點映射于該缺陷單元上, 故在構(gòu)造CM時, 應(yīng)該剔除該缺陷單元相關(guān)矩陣信息.

2.3 矩陣匹配策略

由于CMOL單元數(shù)往往多于映射電路的節(jié)點數(shù), 即CM的行列數(shù)大于LM. 矩陣的匹配過程中, 在CM中截取一個與LM相同規(guī)模的子矩陣, 通過交換子矩陣的行列順序與LM匹配即可, 并且規(guī)定截取的子矩陣總是位于CM的左上方.

2.4 算法實現(xiàn)

算法1 MA算法

Step1: 生成初始種群initialize_population();

Step2: 計算個體適應(yīng)值calculate_fitness_ score();

Step3: 選擇親代generate_parents();

Step4: 交叉操作crossover();

Step5: 變異操作mutation();

Step6: 依據(jù)適應(yīng)值選擇存活個體;

Step7: 局部搜索local_search();

Step8: 若矩陣匹配成功或者迭代次數(shù)達到上限, 算法終止; 否則, 重復(fù)Step3~Step7.

2.4.1適應(yīng)值函數(shù)

2.4.2交叉、變異

交叉、變異是遺傳算法的關(guān)鍵步驟, 由于矩陣的行排列與列排列總是相同的, 只針對行排列來進行遺傳操作. 當(dāng)一輪操作結(jié)束后將相應(yīng)的列進行相同的交換操作, 由于每個CMOL單元能且只能被一個電路節(jié)點所映射, 故CMOL單元編號不可重復(fù), 因此采用部分交叉的策略生成子代, 避免因雙切點交叉導(dǎo)致單元重復(fù)問題. 具體的交叉過程如圖6所示, 每一個數(shù)字表示CM行編號, 親代各自將內(nèi)部基因按照箭頭所指方向, 即16-12, 2-11, 10-8, 15-15, 7-1的交換關(guān)系, 進行位置互換得到子代. 變異發(fā)生在交叉之后, 變異操作能夠重現(xiàn)在選擇步驟中丟失的性狀, 從而維持種群的多樣性并且避免算法陷入局部最優(yōu). 變異時, 會隨機選擇種群中需要變異的個體基因進行位置交換.

圖6 交叉操作

2.4.3基于模擬退火算法的局部搜索策略

算法2 基于模擬退火算法的局部搜索

Step1: 讀入個體并計算其初始適應(yīng)值init_ score.

Step2: 對個體隨機交換基因位置, 計算交換后的適應(yīng)值new_score.

Step5: 更新內(nèi)循環(huán)次數(shù).

Step6: 若內(nèi)部循環(huán)次數(shù)上限達到num_inner_ loop, 終止內(nèi)循環(huán). 更新溫度, 否則, 重復(fù)Step2~ Step5.

在SA中溫度和冷卻策略對于算法的成功實施至關(guān)重要. 初始溫度和模擬退火算法所做的基因交換的接受率有關(guān), 初始溫度越高則接受率越高, 反之越低. 由于全局搜索采用GA來實現(xiàn), SA只是用來進行局部搜索, 因此初始溫度的設(shè)定不應(yīng)太高, 根據(jù)實驗將初始溫度設(shè)定在0.2℃比較合適. 隨著算法的執(zhí)行, 溫度會逐漸降低以限制基因交換的接受率. 溫度按照下式進行更新:

式中,為冷卻因子, 與基因交換的接受率有關(guān),

3 實驗結(jié)果與分析

實驗結(jié)果見表1, 其中,“單元”表示標(biāo)準(zhǔn)測試電路節(jié)點數(shù),“時間”表示成功完成電路缺陷容忍映射時CPU運行時間,“線長”表示映射電路互連線長度總和,“成功率”表示在20次試驗中成功完成缺陷容忍映射的概率,“平均值”表示對應(yīng)方法運行的結(jié)果平均值,“改進量”表示本文方法相對于其他方法平均值的改進量.

由表1可知, 本文方法與SimE方法相比, 時間和線長分別有36.98%和26.79%的改進, 這主要是由于本文方法將CMOL電路映射配置單元的搜索問題轉(zhuǎn)化為矩陣間矩陣元的匹配問題, 減少了缺陷容忍映射問題的復(fù)雜性, 并且在矩陣匹配過程中對不同的矩陣元值施加不同的懲罰系數(shù), 矩陣元值越大, 其懲罰系數(shù)越大. 因此, 最終得到映射結(jié)果的緊湊程度會高于SimE, 而線長是反映電路映射結(jié)果緊湊程度的重要指標(biāo), 映射結(jié)果越緊湊, 線長越小, 反之, 線長越大. 此外, 本文提出的方法當(dāng)且僅當(dāng)矩陣中所有矩陣元都匹配成功時才返回解, 并不需要插入反相器對來拓展違反連通域約束的單元路徑, 因此沒有產(chǎn)生額外線長的消耗.

表1 不同方法實驗結(jié)果比較

與DS相比, 時間改進29.16%, 線長卻存在11.43%的代價. 這是因為DS采用動態(tài)分層的缺陷容忍映射方法, 分層之后, 由于每層中的映射資源有限, DS以時間為代價在層內(nèi)進行就近容忍映射來減小線長, 與本文采用的在全局范圍內(nèi)進行矩陣間矩陣元匹配的缺陷容忍映射方法相比, DS映射結(jié)果的緊湊程度更高, 因此線長更小.

4 結(jié)語

針對CMOL常開缺陷的容忍映射問題, 本文將邏輯電路和CMOL陣列分別建模為矩陣表示, 通過交換矩陣間行列的位置實現(xiàn)矩陣間元素匹配來完成映射, 與已有方法相比, 在求解速度上具有優(yōu)勢. 由于本文不涉及常連缺陷容忍映射, 而常連缺陷存在缺陷傳播的問題, 如何針對常連缺陷對CMOL陣列進行矩陣的重新建模是未來研究重點.

[1] Likharev K K, Strukov D B. CMOL: devices, circuits and architectures[M]//Cuniberti G, Richter K, Fagas G. Introducing Molecular Electronics. Heidelberg: Springer, 2005, 680:447-477.

[2] Lu W, Lieber C M. Nanoelectronics from the bottom up [J]. Nature Materials, 2007, 6(11):841-850.

[3] Likharev K. Electronics below 10 nm[M]//Greer J, Korkin A, Labanowski J. Nano and Giga Challenges in Microelectronics. Amsterdam: Elsevier, 2003:27-68.

[4] Xia Y S, Chu Z F, Hung W N N, et al. An integrated optimization approach for nanohybrid circuit cell mapping[J]. IEEE Transactions on Nanotechnology, 2011, 10(6):1275-1284.

[5] Sait S M, Arafeh A M. Efficient CMOL nanoscale hybrid circuit cell assignment using simulated evolution heuristic [C]//Proceedings of the Great Lakes Symposium on VLSI, New York: ACM Press, 2012:21-26.

[6] Sait S M, Oughali F C, Arafeh A M. Engineering a memetic algorithm from discrete Cuckoo search and Tabu search for cell assignment of hybrid nanoscale CMOL circuits[J]. Journal of Circuits, Systems and Computers, 2016, 25(4):1650023.

[7] Sait S M, Arafeh A M. Cell assignment in hybrid CMOS/nanodevices architecture using Tabu search[J]. Applied Intelligence, 2014, 40(1):1-12.

[8] Farazmand N, Tahoori M B. Multiple fault diagnosis in crossbar nano-architectures[C]//2010 15th IEEE European Test Symposium, IEEE Computer Society, 2010:94-99.

[9] Strukov D B, Likharev K K. CMOL FPGA: a reconfigurable architecture for hybrid digital circuits with two-terminal nanodevices[J]. Nanotechnology, 2005, 16 (6):888-900.

[10] Hung W N N, Gao C J, Song X Y, et al. Defect-tolerant CMOL cell assignment via satisfiability[J]. IEEE Sensors Journal, 2008, 8(6):823-830.

[11] 陳定亨, 夏銀水, 儲著飛. 缺陷無意識的CMOL單元容錯映射[J]. 計算機輔助設(shè)計與圖形學(xué)學(xué)報, 2017, 29(11):2133-2139.

[12] Sait S M, Arafeh A M. Reconfiguration-based defect- tolerant design automation for hybrid CMOS/nanofabrics circuits using evolutionary and non-deterministic heuristics [J]. Arabian Journal for Science and Engineering, 2015, 40(9):2515-2529.

[13] Chen D, Xia Y, Wang Z. Stuck-at-close defect propagation and its blocking technique in CMOL cell mapping[J]. Microelectronics Journal, 2018, 72(2):100- 108.

[15] 陳定亨. CMOL電路的容錯映射研究[D]. 寧波: 寧波大學(xué), 2018.

[16] Chu Z F, Xia Y S, Hung W N N, et al. A memetic approach for nanoscale hybrid circuit cell mapping[C]// 2010 13thEuromicro Conference on Digital System Design, IEEE Computer Society, 2010.

[17] G?ren S, Ugurdag H F, Palaz O. Defect-aware nanocrossbar logic mapping through matrix canonization using two-dimensional radix sort[J]. ACM Journal on Emerging Technologies in Computing Systems, 2011, 7(3):1-16.

[18] Brglez F, Bryan D, Kozminski K. Combinational profiles of sequential benchmark circuits[C]//Proceedings of IEEE International Symposium on Circuits and Systems, IEEE Computer Society, 1989:1929-1934.

Defect-tolerant mapping of CMOL circuit expressed by matrix

Xu Pengfei, Xia Yinshui*, Zha Xiaojing, Gu Xiangui

( Faculty of Electrical Engineering and Computer Science, Ningbo University, Ningbo 315211, China )

To address the problem of cell defect-tolerant mapping in flawed CMOS/nanowire/molecular hybrid (CMOL) circuits, a matrix-based defect-tolerant mapping method for CMOL circuits is proposed. The logic circuit and CMOL circuit are first expressed by a matrix respectively, followed by using the memetic algorithm to search for matching characters between the matrices. The matching strategy with priority assigned to small matrix element value is used to complete the cell defect-tolerance mapping. The experimental results of the ISCAS benchmarks show that, compared with the existing approaches, the CPU runtime of the proposed method is increased by 36.98%.

CMOL; defect-tolerant cell mapping; matrix representation; memetic algorithm

TP391.41

A

1001-5132（2021）02-0001-08

2020?08?10.

寧波大學(xué)學(xué)報（理工版）網(wǎng)址: http://journallg.nbu.edu.cn/

國家自然科學(xué)基金（61571248）.

徐鵬飛（1995－）, 男, 湖北鐘祥人, 在讀碩士研究生, 主要研究方向: 邏輯綜合與優(yōu)化. E-mail: 1079290675@qq.com

夏銀水（1963－）, 男, 浙江余姚人, 研究員, 主要研究方向: 集成電路邏輯綜合與優(yōu)化. E-mail: xiayinshui@nbu.edu.cn

（責(zé)任編輯 韓 超）