顧賢貴, 夏銀水

基于單元分類的CMOL常開缺陷單元容錯(cuò)映射

顧賢貴, 夏銀水*

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

CMOS納米分子混合電路(CMOS/nanowire/MOLeclular hybrid circuits, CMOL)在制造過程中會(huì)引入較高缺陷率, 從而導(dǎo)致可用映射資源的減少. 針對(duì)由此產(chǎn)生的映射困難問題, 本文采用單元分類思想, 對(duì)部分缺陷單元加以利用, 以增加可映射單元數(shù), 進(jìn)而提高映射成功率. 首先根據(jù)單元缺陷類型的差異, 將缺陷單元分為可用和不可用兩類進(jìn)行標(biāo)記, 然后對(duì)可用缺陷單元加以利用, 并采用改進(jìn)的進(jìn)化算法完成單元容錯(cuò)映射. 實(shí)驗(yàn)結(jié)果表明, 與已有方法相比, 新方法在運(yùn)行效率和成功率上分別得到了19.17%和30.14%的提升.

CMOL; 進(jìn)化算法; 單元容錯(cuò)映射

隨著CMOS器件特征尺寸的不斷縮小, 量子效應(yīng)加劇, 制造成本飛漲等問題日益凸顯, 使CMOS工藝的發(fā)展面臨著前所未有的挑戰(zhàn)[1]. CMOL電路因兼具CMOS電路豐富的邏輯功能和納米器件的高集成度, 受到了國內(nèi)外專家學(xué)者的廣泛關(guān)注. 研究表明, 在功耗可控情況下, CMOL電路每秒每平方厘米的運(yùn)算次數(shù)可達(dá)1020次, 被認(rèn)為是后摩爾時(shí)代最具前景的CMOS替代工藝之一[2]. 然而, 自底向上自組裝而成的CMOL電路在制造過程中因界面引腳與納米線難以精確校準(zhǔn), 及納米器件尺寸極度縮小等原因, 常會(huì)引入10-3~10-1大小的缺陷率, 這遠(yuǎn)高于傳統(tǒng)CMOS電路10-9~10-7大小的缺陷率, 因此, CMOL單元容錯(cuò)映射方法研究是CMOL工藝邁向?qū)嵱没M(jìn)程的必要條件之一[3].

CMOL電路的單元容錯(cuò)映射通常分為兩步進(jìn)行. 首先考慮連通域約束, 完成無缺陷單元映射, 然后再考慮缺陷情況以及連通域約束, 完成單元容錯(cuò)映射. 其中, CMOL電路缺陷類型通常可分為兩類: 常開缺陷(stuck-at-open defects)和常連缺陷(stuck-at-close defects). 迄今為止, 針對(duì)常開缺陷的單元容錯(cuò)映射工作已取得較大進(jìn)展[4-7], 但針對(duì)常連缺陷的單元容錯(cuò)映射研究則相對(duì)較少[8-9]. Hung等[8]將單元容錯(cuò)映射問題轉(zhuǎn)變可滿足性問題, 并將提出的容錯(cuò)策略轉(zhuǎn)化為布爾約束, 采用一種稱為MINISAT的CHAFF型SAT求解器進(jìn)行CMOL單元容錯(cuò)映射的求解工作, 但該方法存在求解效率低, 電路求解規(guī)模小等問題. 后續(xù)研究表明, 常連缺陷存在缺陷傳播現(xiàn)象, 對(duì)此, Chen等[9]提出一種有效的常連缺陷傳播阻斷方法, 利用反相器對(duì)的互補(bǔ)信號(hào)阻斷常連缺陷傳播路徑, 但引入的反相器對(duì)易造成電路時(shí)延退化.

上述工作共同之處在于均采用舍棄策略處理缺陷單元, 但隨缺陷率的提高, 可映射資源減少造成電路映射成功率急劇降低. 針對(duì)此問題, 本文提出單元分類思想, 根據(jù)單元缺陷類型的差異, 將缺陷單元分為可用和不可用兩類, 并進(jìn)行標(biāo)記. 對(duì)不可用缺陷單元進(jìn)行舍棄, 而對(duì)可用缺陷單元加以利用, 同時(shí)采用改進(jìn)的進(jìn)化算法完成CMOL常開缺陷的單元容錯(cuò)映射. 結(jié)果表明, 新方法能夠快速有效的完成CMOL電路的單元容錯(cuò)映射.

1 CMOL結(jié)構(gòu)與單元容錯(cuò)映射

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

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

1.2 CMOL單元容錯(cuò)映射

其中,表示電路節(jié)點(diǎn)(邏輯門)集合;表示電路節(jié)點(diǎn)連接邊集合;(g)表示電路節(jié)點(diǎn)g所映射的CMOL單元;dist表示2個(gè)CMOL單元之間的曼哈頓距離;表示連通域半徑. 式(1)說明每個(gè)CMOL單元能且只能被1個(gè)電路節(jié)點(diǎn)所映射; 式(2)表示有連接關(guān)系的2個(gè)電路節(jié)點(diǎn)所映射單元之間的距離必須滿足連通域約束.

在無缺陷映射階段, 得到滿足式(1)、(2)的初始映射解, 然后在該解中加入缺陷信息, 通過單元重構(gòu)完成CMOL單元容錯(cuò)映射[4,9].

本文涉及的缺陷類型表述如下:

(1)納米二極管常開. 納米二極管無法正常開啟, 致使其連接的2條納米線所處單元之間的信號(hào)通路被阻斷.

(2)納米線非周期性斷裂. 納米線發(fā)生不規(guī)則斷裂, 致使其所處單元的可連接單元數(shù)減少.

(3)CMOS反相器常開. 連接CMOS反相器的界面引腳未與納米線精確對(duì)準(zhǔn), 致使其所在單元無法實(shí)現(xiàn)邏輯非功能.

在CMOL電路中正是由于上述常開缺陷的存在, 使得原本可連接的2個(gè)CMOL單元之間的信號(hào)通路被阻斷, 或無法完成相應(yīng)的邏輯運(yùn)算. CMOL單元容錯(cuò)映射就是一個(gè)在連通域約束下, 通過一定方法消除缺陷影響, 從而保證映射電路邏輯功能正確的過程.

2 基于單元分類的CMOL單元容錯(cuò)映射

2.1 CMOL單元分類與標(biāo)記

在CMOL電路中, 每個(gè)CMOL單元可看作由CMOS反相器、輸入/輸出納米線以及納米二極管三部分組成, 如果其中任一部分發(fā)生缺陷, 那么該CMOL單元?jiǎng)t被視為一個(gè)缺陷單元. 但不同的常開缺陷所產(chǎn)生的影響也有所不同, 其中, CMOS反相器常開意味著該反相器所組成的CMOL單元無法實(shí)現(xiàn)邏輯非功能, 所以此類缺陷單元無法被利用. 結(jié)合CMOL電路結(jié)構(gòu), 每個(gè)納米二極管唯一確定2條正交納米線, 每條納米線唯一確定1個(gè)CMOL單元, 納米二極管常開造成其所連接的2條納米線所確定的2個(gè)CMOL單元之間的信號(hào)通路被阻斷, 但這2個(gè)單元仍可與其他單元進(jìn)行連接, 并構(gòu)成信號(hào)通路, 因此此類缺陷單元可被利用. 同時(shí), 納米線非周期性斷裂表示納米線在非周期性斷點(diǎn)處發(fā)生不規(guī)則斷裂, 此類缺陷僅造成納米線唯一確定CMOL單元的可連接單元數(shù)減少, 所以此類缺陷單元也可被利用. 綜上所述, 根據(jù)CMOL單元是否發(fā)生缺陷以及發(fā)生缺陷時(shí)的影響差異, 可將單元分為以下三類: 無缺陷單元、可用缺陷單元和不可用缺陷單元. 其中,

(1)無缺陷單元: 表示該CMOL單元未發(fā)生任意一種常開缺陷;

(2)不可用缺陷單元: 表示該CMOL單元發(fā)生CMOS反相器常開缺陷;

(3)可用缺陷單元: 表示該CMOL單元的納米二極管常開, 或納米線非周期性斷裂, 但不存在CMOS反相器常開缺陷.

算法1(CMOL單元分類與標(biāo)記)

2.2 可用缺陷單元的映射約束與重構(gòu)

針對(duì)不可用缺陷單元, 因其無法進(jìn)行邏輯運(yùn)算, 所以在單元容錯(cuò)映射階段需要將其舍棄, 即不可被任何電路節(jié)點(diǎn)所映射. 針對(duì)可用缺陷單元, 由于其CMOS反相器功能是正常的, 仍可完成相應(yīng)的邏輯運(yùn)算, 所以其依然可被電路節(jié)點(diǎn)所映射. 但任意2個(gè)可用缺陷單元和, 如果在彼此的輸入/輸出連通域內(nèi), 那么在單元映射過程中將可能出現(xiàn)以下4種情況:

(1)、均未被電路節(jié)點(diǎn)所映射;

(2)、其中一個(gè)被電路節(jié)點(diǎn)映射, 而另一個(gè)未被映射;

(3)、兩者都被電路節(jié)點(diǎn)映射, 但映射的電路節(jié)點(diǎn)不存在連接關(guān)系;

(4)、兩者都被電路節(jié)點(diǎn)映射, 但映射的電路節(jié)點(diǎn)存在連接關(guān)系.

由于可用缺陷單元和之間無法構(gòu)成信號(hào)通路, 這就要求兩者不能被具有連接關(guān)系的電路節(jié)點(diǎn)和同時(shí)映射. 因此, 上述第4種情況會(huì)因信號(hào)通路阻斷而出現(xiàn)邏輯錯(cuò)誤, 其他3種情況因單元和之間不存在信號(hào)傳輸, 故不會(huì)導(dǎo)致邏輯錯(cuò)誤. 因此, 在單元映射過程中, 為防止第4種情況出現(xiàn), 需要對(duì)在彼此輸入/輸出連通域內(nèi)的2個(gè)可用缺陷單元的映射進(jìn)行約束施加, 表述如下:

算法2(可用缺陷單元的重構(gòu)判定)

圖2 單元重構(gòu)

2.3 算法實(shí)現(xiàn)

進(jìn)化算法具體實(shí)現(xiàn)以適值函數(shù)、選擇策略和遺傳算子三部分做詳細(xì)說明.

2.3.1 適值函數(shù)

適值是度量個(gè)體性能狀態(tài)優(yōu)良情況的重要參數(shù). 在CMOL單元容錯(cuò)映射中, 每一個(gè)電路映射結(jié)果可視為一個(gè)體, 使用本課題組的LRMA算法[10]生成個(gè)體構(gòu)成初始種群. 個(gè)體違反約束(3)(4)的個(gè)數(shù)越少, 性狀越優(yōu); 否則, 性狀越差. 適值函數(shù)定義如下:

其中,表示邏輯電路的節(jié)點(diǎn)總數(shù);表示電路節(jié)點(diǎn)所映射單元連通域內(nèi)的單元總數(shù);penalty(c,c)表示電路節(jié)點(diǎn)所映射單元與其連通域內(nèi)單元之間違反約束(3)(4)的懲罰因子, 其中,

2.3.2 選擇策略

選擇策略決定著種群演化方向. 為確保性能狀態(tài)優(yōu)的個(gè)體有較大概率, 同時(shí)性能狀態(tài)差的個(gè)體也有不為零的概率被選擇進(jìn)行遺傳操作, 需采用線性排名結(jié)合輪盤賭策略進(jìn)行個(gè)體選擇. 首先計(jì)算種群所有個(gè)體適值, 并進(jìn)行升序排列. 記種群規(guī)模為, 則性狀最優(yōu)個(gè)體編號(hào)為, 且設(shè)定計(jì)算值為max, 性狀最差個(gè)體編號(hào)為1, 且設(shè)定計(jì)算值為min(minp:

隨后對(duì)所有個(gè)體的計(jì)算值p進(jìn)行歸一化處理, 得到個(gè)體選擇概率q,

根據(jù)q進(jìn)行輪盤選擇, 令

2.3.3 遺傳算子

圖3 二維染色體交叉

在進(jìn)化算法中, 變異算子的主要功能是拓寬算法的選擇空間, 以防止陷入局部最優(yōu), 因此變異階段的單元互換不存在連通域約束檢查機(jī)制. 此外, 單元變異率過高則可能導(dǎo)致算法無法收斂, 過低則可能限制了算法的求解能力, 所以本文設(shè)定變異算子僅在種群中性狀最優(yōu)個(gè)體的適值未得到改進(jìn)的情況下被激活實(shí)施. 在CMOL單元容錯(cuò)映射過程中, 變異只會(huì)造成映射電路結(jié)構(gòu)微小的變化, 即在染色體中隨機(jī)選取2個(gè)基因進(jìn)行位置互換. 圖4所示為二維染色體變異示意圖, 其中存在2種變異類型: (1)若2個(gè)單元都已被電路節(jié)點(diǎn)所映射, 則互換位置, 如圖4(a)所示, 將電路節(jié)點(diǎn)4和8位置互換; (2)若2個(gè)單元其中一個(gè)為空白單元, 則將電路節(jié)點(diǎn)重新映射于空白單元上即可, 如圖4(b)所示, 將電路節(jié)點(diǎn)7重新映射于箭頭所指單元上.

圖4 二維染色體變異

綜上所述, 給出基于單元分類的CMOL單元容錯(cuò)映射偽代碼的算法3.

算法3(基于單元分類的CMOL單元容錯(cuò)映射)

3 實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)結(jié)果見表1. 其中,“單元”表示標(biāo)準(zhǔn)測試電路節(jié)點(diǎn)總數(shù); “時(shí)間”表示得到可行解時(shí)程序的運(yùn)行時(shí)間; “線長”表示映射電路互連線長度總和; “成功率”表示100次試驗(yàn)中成功得到映射解的概率;“平均值”表示不同參數(shù)的平均值;“提高量”表示提出方法與比較文獻(xiàn)的改進(jìn)百分比. 同時(shí)選取了2篇在CMOL常開缺陷單元容錯(cuò)映射領(lǐng)域具有代表性的文獻(xiàn)(SimE[4]和DUM[7])進(jìn)行實(shí)驗(yàn)對(duì)比. 由表中數(shù)據(jù)可見, 與SimE相比, 本文方法得到了26.42%的時(shí)間和2.77%的線長優(yōu)化. 但線長優(yōu)化效果不明顯, 主要原因是新方法在進(jìn)化算法變異階段不存在連通域約束檢查機(jī)制, 導(dǎo)致映射解中存在部分違反連通域約束情況, 對(duì)此需要引入反相器對(duì)進(jìn)行路由拓展而產(chǎn)生額外的線長消耗[12]. 與DUM相比, 得到了19.17%的時(shí)間和30.14%的成功率提升, 線長卻存在27.31%的退化. 這主要是因?yàn)镈UM采用缺陷無意識(shí)的映射方法, 即在×大小的缺陷CMOL陣列中提取出一塊×(<)大小的無缺陷子陣列, 然后在該無缺陷子陣列中進(jìn)行單元映射, 與此不同的是, 新方法在整個(gè)×大小的缺陷陣列中尋找映射解. 因此得到最終映射解的緊湊程度要低于DUM, 而線長是反應(yīng)電路映射緊湊程度的重要指標(biāo), 映射結(jié)果越緊湊, 線長越小, 反之, 線長越大. 本文將缺陷單元細(xì)分為可用和不可用兩類, 對(duì)可用缺陷單元加以利用, 映射資源的增加使算法更易找到有效解, 這是求解效率得到提升的主要原因.

表1 不同方法實(shí)驗(yàn)結(jié)果比較

4 結(jié)語

針對(duì)CMOL常開缺陷的單元容錯(cuò)映射問題, 本文采用缺陷單元分類處理思想, 提高了單元利用率從而提高了映射效率和求解成功率. 但提出方法僅限于常開缺陷的容錯(cuò)映射, 因此涵蓋常開與常連缺陷的方法研究是未來的主要研究方向.

[1] Likharev K K, Strukov D B. CMOL: Devices, Circuits and Architectures[M]. Lecture Notes in Physics. Heidelberg: Springer, 2005.

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

[3] Yan H, Choe H S, Nam S W, et al. Programmable nanowire circuits for nanoprocessors[J]. Nature, 2011, 470(7333):240-244.

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

[5] Zha X, Xia Y. Genetic algorithm based on divide-and- conquer strategy for defect-tolerant CMOL mapping[C]. Proceedings of the 12th IEEE International Conference on ASIC. Los Alamitos: IEEE Computer Society Press, 2017:863-866.

[6] 汪紀(jì)波, 夏銀水, 儲(chǔ)著飛, 等. 基于門節(jié)點(diǎn)分級(jí)選擇的CMOL電路單元快速容錯(cuò)映射[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2017, 29(1):172-179.

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

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

[9] 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.

[10] Xia Y, Chu Z, 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.

[11] Brglez F, Bryan D, Ko?miński K. Combinational profiles of sequential benchmark circuits[C]. Proceedings of IEEE International Symposium on Circuits and Systems. Los Alamitos: IEEE Computer Society Press, 1989:1929- 1934.

[12] Chu Z, Xia Y, Hung W N N, et al. Timing-driven logic restructuring for nano-hybrid circuits[J]. International Journal of Electronics, 2013, 100(5):669-685.

Cell classification based CMOL stuck-at-open defect-tolerant cell mapping

GU Xiangui, XIA Yinshui*

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

To tackle the problem of high defect rate in CMOS/nanowire/MOLeclular hybrid circuits (CMOL), a cell classification based defect-tolerant cell mapping method is proposed. First, recoverable and unrecoverable defective cells are marked, and the recoverable defective ones are put to use again. Then, a modified evolutionary algorithm is used to complete the defect-tolerant cell mapping. Compared with the existing approaches, the CPU time and success rate using the proposed method are optimized to 19.17% and 30.14%, respectively.

CMOL; evolutionary algorithm; defect-tolerant cell mapping

TP391.41

A

1001-5132（2020）01-0051-07

2019?07?22.

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

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

顧賢貴（1995－）, 男, 浙江寧波人, 在讀碩士研究生, 主要研究方向: 邏輯電路綜合與優(yōu)化. E-mail: 1014406105@qq.com

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

（責(zé)任編輯 章踐立）