基于Pareto支配的MPRM電路面積與可靠性優(yōu)化

卜登立,江建慧

(1.井岡山大學(xué)電子與信息工程學(xué)院，江西吉安 343009; 2.同濟(jì)大學(xué)軟件學(xué)院,上海 201804; 3.流域生態(tài)與地理環(huán)境監(jiān)測(cè)國家測(cè)繪地理信息局重點(diǎn)實(shí)驗(yàn)室，江西吉安 343009)

?

基于Pareto支配的MPRM電路面積與可靠性優(yōu)化

卜登立1,2,3,江建慧2

(1.井岡山大學(xué)電子與信息工程學(xué)院，江西吉安 343009; 2.同濟(jì)大學(xué)軟件學(xué)院,上海 201804; 3.流域生態(tài)與地理環(huán)境監(jiān)測(cè)國家測(cè)繪地理信息局重點(diǎn)實(shí)驗(yàn)室，江西吉安 343009)

針對(duì)MPRM(Mixed-Polarity Reed-Muller)電路的面積與可靠性折中優(yōu)化問題，在邏輯級(jí)建立面積估算模型以及電路SER(Soft Error Rate)解析評(píng)價(jià)模型，并采用Pareto支配概念對(duì)MPRM電路進(jìn)行面積與可靠性多目標(biāo)優(yōu)化.通過對(duì)MPRM電路的XOR部分進(jìn)行樹形異或門分解，并考慮多個(gè)輸出之間異或門的共享，建立面積估算模型.采用信號(hào)概率和故障傳播方法，并考慮電路中的邏輯屏蔽因素以及信號(hào)相關(guān)性，建立電路SER解析評(píng)價(jià)模型.根據(jù)所提出的面積和SER評(píng)價(jià)模型，采用極性向量的格雷碼序窮舉搜索MPRM的極性空間得到MPRM電路面積與可靠性的Pareto最優(yōu)解集，并使用效率因子技術(shù)指標(biāo)選取最終解.MCNC基準(zhǔn)電路的實(shí)驗(yàn)結(jié)果表明，與面積最小MPRM電路相比，所選取的MPRM電路可以在較小面積開銷的前提下獲得較高電路可靠性.

MPRM電路;可靠性優(yōu)化;面積優(yōu)化;SER解析評(píng)價(jià)模型;Pareto支配;多目標(biāo)優(yōu)化

1 引言

隨著集成電路技術(shù)和工藝的發(fā)展，無論是傳統(tǒng)的CMOS器件，還是納米器件，其缺陷率均不可避免的增加，同時(shí)對(duì)瞬時(shí)故障(Transient Fault,TF)的敏感度也不斷增加[1,2].因此，電路可靠性問題成為一個(gè)不容忽視的問題，需要在電路設(shè)計(jì)流程的各個(gè)階段考慮可靠性約束.

RM(Reed-Muller)邏輯是布爾函數(shù)基于AND/XOR的邏輯表示[3]，與基于AND/OR的邏輯表示相比，其電路實(shí)現(xiàn)具有面積和速度優(yōu)勢(shì)，因此在算術(shù)電路、校驗(yàn)電路和通信電路等領(lǐng)域得到了較為廣泛的應(yīng)用[4,5].近些年來，RM電路的邏輯綜合以及優(yōu)化得到了較多關(guān)注.如文獻(xiàn)[3]進(jìn)行MPRM (Mixed-Polarity RM)電路的邏輯優(yōu)化，文獻(xiàn)[4]進(jìn)行FPRM(Fixed-Polarity RM)電路的面積優(yōu)化，文獻(xiàn)[5]進(jìn)行混合極性RM電路的面積優(yōu)化，文獻(xiàn)[6]對(duì)包含無關(guān)項(xiàng)的FPRM電路進(jìn)行面積與功耗優(yōu)化，文獻(xiàn)[7]對(duì)MPRM 電路進(jìn)行面積與延時(shí)優(yōu)化.盡管針對(duì)單固定故障和橋接故障模型，RM電路可以實(shí)現(xiàn)具有通用測(cè)試集的確定可測(cè)性設(shè)計(jì)[8]，從而簡化測(cè)試生成并提高測(cè)試速度，但可測(cè)性設(shè)計(jì)進(jìn)行的是基于故障覆蓋率的分析，考慮的是最壞情況，得到的是一個(gè)可靠性下限值.要準(zhǔn)確分析電路的可靠性，需要采用概率分析方法.另外，RM電路之所以具有良好的可測(cè)性，正是由于異或門沒有輸入控制值，即不能通過某個(gè)輸入的信號(hào)值支配其輸出的邏輯信號(hào)值，因此發(fā)生在異或門輸入端的故障以及傳播至其輸入端的故障總是能夠傳播至其輸出，這也導(dǎo)致基于XOR電路的信號(hào)可靠度相對(duì)較低[9].因此更有必要在進(jìn)行RM電路綜合與優(yōu)化時(shí)結(jié)合可靠性約束，從而在保持RM電路其他優(yōu)勢(shì)的同時(shí)，相對(duì)提高其信號(hào)可靠度.然而當(dāng)前還缺乏這方面的研究工作.

為較好地實(shí)現(xiàn)RM電路面積與可靠性之間的折中，快速且相對(duì)準(zhǔn)確的電路可靠性評(píng)價(jià)方法以及較為詳盡的面積估算模型是非常必要的.另一方面，當(dāng)前關(guān)于RM電路的面積與功耗、面積與延時(shí)等多目標(biāo)優(yōu)化問題往往采用聚合函數(shù)方法[6,7].聚合函數(shù)方法具有一定的局限性，只有在多個(gè)目標(biāo)的Pareto前沿(front)是凸函數(shù)時(shí)，其得到的解才是Pareto最優(yōu)解[10].因此，有必要研究適用于RM電路面積與可靠性多目標(biāo)優(yōu)化的方法，避免優(yōu)化結(jié)果過于偏向某個(gè)目標(biāo).

本文根據(jù)建立的納電子MPRM電路結(jié)構(gòu)，先對(duì)電路中的XOR部分進(jìn)行樹形異或門分解，然后估算電路的面積；采用信號(hào)概率[11]和故障傳播方法，并考慮電路中的邏輯屏蔽因素以及信號(hào)相關(guān)性，針對(duì)單瞬時(shí)故障在邏輯級(jí)建立工藝無關(guān)的MPRM電路軟錯(cuò)誤率(Soft Error Rate,SER)解析評(píng)價(jià)模型.根據(jù)所提出的面積估算模型以及SER解析評(píng)價(jià)模型，采用Pareto支配概念，使用基于格雷碼序的窮舉搜索方法進(jìn)行面積與可靠性多目標(biāo)優(yōu)化，得到Pareto前沿，實(shí)現(xiàn)面積和可靠性的折中優(yōu)化，并通過實(shí)驗(yàn)進(jìn)行了驗(yàn)證.

2 MPRM邏輯表示和極性轉(zhuǎn)換

對(duì)于一個(gè)n輸入、m輸出的多輸出布爾函數(shù)，其極性值為g的MPRM可以表示為如式(1)所示的多項(xiàng)式形式[5].

(1)

在MPRM電路優(yōu)化過程中需要進(jìn)行極性轉(zhuǎn)換，OKFDD(Ordered Kronecker Functional Decision Diagram)[12]作為電路的判決圖表示，也可用來實(shí)現(xiàn)極性轉(zhuǎn)換.OKFDD使用非終端結(jié)點(diǎn)表示變量，1結(jié)點(diǎn)作為終端結(jié)點(diǎn)表示常量1，邊表示函數(shù).OKFDD通過依次對(duì)變量xl施香農(nóng)分解和正、負(fù)Davio分解得到，三種分解類型分別對(duì)應(yīng)gl=2、0和1.OKFDD中每個(gè)非終端結(jié)點(diǎn)有兩個(gè)后繼邊，對(duì)這兩個(gè)后繼邊進(jìn)行XOR操作可以改變?cè)摻Y(jié)點(diǎn)所表示變量的分解類型[12]，即改變?cè)撟兞康臉O性.如果將OKFDD中由根結(jié)點(diǎn)到1結(jié)點(diǎn)的路徑稱為1路徑，那么遍歷OKFDD中的1路徑即可得到其所包含的乘積項(xiàng)[12].

共享OKFDDs是在電路各個(gè)原始輸出(Primary Output,PO)對(duì)應(yīng)的OKFDD之間共享子圖以降低空間復(fù)雜度.本文采用基于共享OKFDDs的極性轉(zhuǎn)換方法[12]進(jìn)行極性轉(zhuǎn)換，先得到某個(gè)極性值的OKFDDs，然后由每個(gè)OKFDD得到其對(duì)應(yīng)PO所包含的乘積項(xiàng)，再由m個(gè)PO所包含乘積項(xiàng)的并集得到如式(1)所示的MPRM表達(dá)式[12].由于MPRM表達(dá)式是由m個(gè)PO所包含乘積項(xiàng)的并集得到，因此可實(shí)現(xiàn)乘積項(xiàng)在多個(gè)PO之間的共享.

3 MPRM電路面積估算

根據(jù)式(1)可將MPRM電路分為由多輸入與門構(gòu)成的AND部分以及XOR部分.在RM電路可測(cè)性設(shè)計(jì)中，為縮短電路延遲，常將其中的XOR部分設(shè)計(jì)成樹形2輸入異或門結(jié)構(gòu)[8]，本文也采用這種結(jié)構(gòu)，以便下一步的可測(cè)性設(shè)計(jì)實(shí)現(xiàn).由于采用納電子技術(shù)的雙極器件[13]能夠?yàn)檫壿嬮T提供負(fù)極性的變量輸入，因此本文結(jié)合納電子技術(shù)建立如圖1所示的納電子MPRM電路結(jié)構(gòu)，在此結(jié)構(gòu)中多個(gè)PO之間可以共享異或門.

為進(jìn)行面積優(yōu)化，需要建立面積估算模型對(duì)電路面積進(jìn)行評(píng)價(jià).由圖1可知AND部分的面積比較容易估算，而XOR部分面積估算的關(guān)鍵是確定其所包含2輸入異或門的數(shù)量.

單輸出電路的XOR部分共有t-1個(gè)異或門；但對(duì)于多輸出電路，XOR部分異或門的數(shù)量取決于乘積項(xiàng)在多個(gè)PO之間的共享.因此，對(duì)于多輸出電路，先對(duì)其XOR部分進(jìn)行樹形異或門分解，在不同PO的XOR部分分解過程中考慮異或門的共享，統(tǒng)計(jì)分解后電路中異或門的數(shù)量，然后再計(jì)算電路面積.

如果為單輸出電路，如算法1中的Step2，可直接獲得異或門數(shù).如果為多輸出電路，如算法1中的Step4，則需要調(diào)用如下所示的算法2依次對(duì)各個(gè)PO的XOR部分進(jìn)行異或門分解.算法2中的|I|表示待分解宏門所包含的輸入數(shù)量.

對(duì)于多輸出電路，算法1依次對(duì)每個(gè)PO調(diào)用算法2進(jìn)行XOR部分的分解，算法2在分解過程中通過XOR樹查找實(shí)現(xiàn)異或門在各個(gè)PO之間的共享，因此算法1統(tǒng)計(jì)的是考慮異或門在多個(gè)PO之間共享后異或門的數(shù)量.

由算法1獲得異或門的數(shù)量s后，根據(jù)式(2)計(jì)算MPRM電路的面積.

(2)

其中2×s為s個(gè)異或門的面積；wi為第i個(gè)乘積項(xiàng)所包含的文字?jǐn)?shù)，也即該乘積項(xiàng)對(duì)應(yīng)與門的面積，條件wi>1表明只有在乘積項(xiàng)中的文字?jǐn)?shù)大于1時(shí)才存在對(duì)應(yīng)與門.因?yàn)楫?dāng)wi=0時(shí)，表示常量1，此時(shí)可將驅(qū)動(dòng)PO的異或門修改為同或門而不會(huì)改變電路的功能，當(dāng)wi=1時(shí)，該文字直接作為異或門的輸入，因此均不存在該乘積項(xiàng)對(duì)應(yīng)的與門.

4 MPRM電路邏輯級(jí)可靠性分析

為分析瞬時(shí)故障對(duì)MPRM電路可靠性的影響，本文采用工藝無關(guān)的單瞬時(shí)故障模型[14,15]，假設(shè)瞬時(shí)故障發(fā)生在邏輯門的輸入端[15]，并且區(qū)分0-TF和1-TF，0-TF指的是邏輯值由1變?yōu)?的故障，1-TF指的是由0變?yōu)?的故障.使用SER來評(píng)價(jià)電路的可靠性，SER指的是電路中節(jié)點(diǎn)發(fā)生的故障被傳播至PO導(dǎo)致該電路出現(xiàn)軟錯(cuò)誤的比率.電路的SER值越小，其可靠性越高.

電路對(duì)瞬時(shí)故障存在多種屏蔽因素，由于本文進(jìn)行工藝無關(guān)的電路優(yōu)化，在邏輯級(jí)評(píng)價(jià)組合電路的SER，因此僅考慮邏輯屏蔽因素.

4.1 基于節(jié)點(diǎn)敏感度的電路SER計(jì)算

為簡化分析過程，采用均勻故障模型，并假設(shè)節(jié)點(diǎn)發(fā)生0-TF和1-TF的概率相同，均為pf，則電路C的SER由式(3)計(jì)算.

(3)

與文獻(xiàn)[2,15,16]不同，本文采用信號(hào)概率以及故障傳播方法，分別計(jì)算節(jié)點(diǎn)故障被敏化的概率psens(ck)，以及沒有被后級(jí)電路邏輯屏蔽而傳播至PO的概率pp(ck)，然后根據(jù)式(4)計(jì)算pcrit(ck)，并推導(dǎo)出SER與MPRM電路中異或門數(shù)以及與門扇入數(shù)間的解析關(guān)系.

pcrit(ck)=psens(ck)×pp(ck)

(4)

4.2 MPRM電路SER解析評(píng)價(jià)模型

下面先針對(duì)單輸出電路進(jìn)行分析，得到MPRM電路的SER解析評(píng)價(jià)模型，然后再分析其對(duì)多輸出電路的適用性.

4.2.1 與門敏感度計(jì)算

與門的輸入是原始輸入(Primary Input,PI).假設(shè)所有PI相互獨(dú)立，PI的信號(hào)概率為0.5，第i個(gè)與門的輸入數(shù)為wi(wi>1).當(dāng)與門的某個(gè)輸入發(fā)生0-TF或1-TF時(shí)，其敏化概率為該輸入的信號(hào)概率.對(duì)于單輸出電路，與門的輸出不存在扇出分支，并且異或門沒有輸入控制值，只要該故障能夠傳播至與門的輸出，就可經(jīng)XOR部分傳播至PO，因而該故障的傳播概率為其余wi-1個(gè)輸入同時(shí)為1的概率：2-(wi-1).對(duì)于與門的一個(gè)輸入端，如果既考慮0-TF又考慮1-TF，根據(jù)式(4)可知其敏感度為2-(wi-1).對(duì)于輸入數(shù)為wi的與門，其敏感度由式(5)計(jì)算.

(5)

由于與門的各個(gè)輸入信號(hào)相互獨(dú)立，因此式(5)的計(jì)算結(jié)果是準(zhǔn)確的.

4.2.2 異或門敏感度計(jì)算

盡管異或門的輸入之間可能存在信號(hào)相關(guān)性，但對(duì)于單輸出電路，異或門的輸出也不存在扇出分支，因此如果其輸入發(fā)生單故障，只要該故障被敏化，那么不管另一個(gè)輸入信號(hào)為何值，該故障必然被傳播至其輸出，從而經(jīng)后面的異或門傳播至PO，可見故障的傳播概率為1.由于異或門的輸入由與門的輸出或PI驅(qū)動(dòng)，因此故障的敏化概率由驅(qū)動(dòng)發(fā)生單故障輸入的與門或PI確定，如果發(fā)生0-TF，需要該與門的輸出或PI為1才能被敏化，即敏化0-TF的概率等于該與門的輸出或PI為1的概率，設(shè)為psens0，同理，敏化1-TF的概率等于該與門的輸出或PI為0的概率，設(shè)為psens1.因?yàn)榭傆衟sens0+psens1=1，因此根據(jù)式(4)可知異或門一個(gè)輸入端的敏感度為1.異或門有2個(gè)輸入端，因此異或門的敏感度為2.

由于考慮了信號(hào)相關(guān)性，因此異或門輸入端故障傳播概率和敏化概率的計(jì)算是準(zhǔn)確的，異或門敏感度的計(jì)算也是準(zhǔn)確的.

4.2.3 MPRM電路SER計(jì)算

盡管節(jié)點(diǎn)發(fā)生故障的概率pf與電路實(shí)現(xiàn)所采用的工藝有關(guān)，由于本文在優(yōu)化過程中是進(jìn)行不同極性值MPRM電路SER的比較，可以認(rèn)為pf對(duì)不同極性值的MPRM電路而言均相同，因此在計(jì)算電路SER時(shí)不考慮pf.

(6)

式(6)用于在極性優(yōu)化過程中比較不同極性值MPRM電路的可靠性，SER值越小，可靠性越高.

對(duì)于多輸出電路，盡管由于與門以及異或門在多個(gè)PO之間的共享，使與門和異或門的輸出呈現(xiàn)扇出分支，但是不同的扇出分支屬于不同的PO，并且只要有一個(gè)PO出現(xiàn)錯(cuò)誤就認(rèn)為該電路出現(xiàn)軟錯(cuò)誤，因此在計(jì)算電路SER時(shí)與門和異或門的扇出分支不會(huì)帶來扇出重匯聚問題.另外，式(6)中的t為考慮乘積項(xiàng)在多個(gè)PO之間共享后的乘積項(xiàng)數(shù)量，s為考慮異或門在多個(gè)PO之間共享后的異或門數(shù)量，因此式(6)的SER計(jì)算不存在節(jié)點(diǎn)以及節(jié)點(diǎn)敏感度重復(fù)統(tǒng)計(jì)問題.可見式(6)同樣適用于多輸出電路，并且計(jì)算結(jié)果是準(zhǔn)確的.

5 MPRM電路面積與可靠性優(yōu)化

5.1 面積與可靠性多目標(biāo)優(yōu)化

由式(2)和式(6)可以看出面積與SER之間存在著沖突，因此MPRM電路的面積和可靠性優(yōu)化問題屬于多目標(biāo)優(yōu)化問題，并且由于面積與SER的Pareto前沿并不一定是凸函數(shù)，因此本文采用基于Pareto支配概念的多目標(biāo)優(yōu)化方法[10].

采用Pareto支配概念，MPRM電路面積與可靠性優(yōu)化問題定義如下.

(1)由3n個(gè)決策變量向量G=[gn-1,gn-2,…,g0](gl∈{0,1,2})構(gòu)成的極性空間為可行解空間；

(3)求Pareto最優(yōu)解集：P={Gi|?Gj∈F(Gj)F(Gi)}，P?，對(duì)應(yīng)的Pareto前沿：Q={F(Gi)|Gi∈P}，Q?.

5.2 面積與可靠性優(yōu)化算法

根據(jù)定義1所定義的多目標(biāo)優(yōu)化問題，本文采用窮舉搜索極性向量空間的方法進(jìn)行面積與可靠性優(yōu)化.為加快搜索速度，按照極性向量的格雷碼序(相鄰的兩個(gè)極性向量僅有一個(gè)極性屬性編碼值不同)進(jìn)行搜索.使用外部歸檔來保存非支配最優(yōu)解集，并在搜索過程中不斷更新外部歸檔，最終得到Pareto最優(yōu)解集以及Pareto前沿，并從Pareto最優(yōu)解集中選取最符合實(shí)際需要的解.算法3給出了MPRM電路面積與可靠性優(yōu)化算法的描述.

6 實(shí)驗(yàn)結(jié)果及分析

文中算法使用C++實(shí)現(xiàn)，并在Linux操作系統(tǒng)下使用g++編譯器編譯.使用算法3在配置為Intel Core i3-2350M CPU 6GB RAM的個(gè)人計(jì)算機(jī)上對(duì)24個(gè)MCNC電路進(jìn)行了面積與可靠性優(yōu)化，求得了Pareto最優(yōu)解集以及Pareto前沿.

圖2給出了電路5xp1、alu2以及t3的Pareto前沿，其中歸一化面積是根據(jù)每個(gè)電路的Pareto前沿中的最小面積進(jìn)行歸一化處理的結(jié)果.

由圖2可以看出，MPRM電路面積與可靠性的Pareto前沿并不是嚴(yán)格的凸函數(shù)，未給出電路的Pareto前沿也具有這個(gè)特點(diǎn).這驗(yàn)證了使用Pareto支配進(jìn)行MPRM電路面積與可靠性優(yōu)化的必要性.

表1給出了對(duì)24個(gè)MCNC電路運(yùn)行算法3的結(jié)果.其中“I/O”表示電路的輸入數(shù)和輸出數(shù)；“N-PF”表示Pareto最優(yōu)解集的大?。弧懊娣e增加”和“SER減少”分別表示所選取的最優(yōu)解相對(duì)于面積最小解所導(dǎo)致的面積開銷和SER下降的比例.“所選取的最優(yōu)解”是根據(jù)效率因子“E=SER減少/面積增加”所選取的最終解，其選取的原則是在E>1的前提下最大化E的值，如果不存在E>1的最優(yōu)解，則選取面積最小解作為最終解，此原則的依據(jù)是盡可能在較小面積開銷的前提下獲得較大的可靠性提升.

由表1可以看出，這些電路的Pareto最優(yōu)解集均包含多個(gè)非支配最優(yōu)解，特別是cm151a，其非支配最優(yōu)解數(shù)達(dá)到了134個(gè).這驗(yàn)證了使用Pareto支配概念進(jìn)行MPRM電路面積與可靠性優(yōu)化的有效性.

根據(jù)效率因子E所選取的最終解中，有6個(gè)電路，最終解就是面積最小解，因?yàn)樵谶@些電路的Pareto最優(yōu)解集中，除面積最小解外的其他非支配最優(yōu)解的E均小于1，也就是說盡管可以提高可靠性，但面積開銷較大.對(duì)其余的18個(gè)電路，所選取最優(yōu)解的E均大于1；除cm85a外，相對(duì)于面積最小的MPRM電路，最終所選取的MPRM電路均能夠在較小面積開銷的前提下獲得較大可靠性提升；特別是clip和ex5，在不到1%的面積開銷下，可靠性分別提升了6.10%和9.11%，其最終解的E分別為6.63和22.27.對(duì)表1中的這些電路，從平均角度看，所選取的最終解相對(duì)于面積最小解，面積增加了4.42%，SER減少了7.25%.

對(duì)于cm85a，盡管所選取最終解的效率因子達(dá)到了2.20，可靠性提升了33.09%，但面積開銷達(dá)到了15.02%.表2給出了cm85a的MPRM電路面積與可靠性的Pareto前沿.

由表2可以看出，對(duì)于cm85a，除面積最小解外的5個(gè)非支配最優(yōu)解均滿足E>1，有較大的最終解選擇空間.例如，可以選擇面積開銷為3.76%，SER減少5.21%的解.

另外，對(duì)表1中電路的最小面積解和最終解MPRM電路進(jìn)行分析，在那些最終解不是最小面積的MPRM電路中，對(duì)于絕大多數(shù)電路而言，最終解的異或門數(shù)要小于最小面積解的異或門數(shù)，而與門的平均扇入數(shù)要略高于最小面積解的與門平均扇入數(shù)，這個(gè)結(jié)果符合式(6)的SER計(jì)算，因?yàn)楫惢蜷T的敏感度較高，異或門的減少可以降低SER，與門扇入數(shù)的增加可以降低與門的敏感度.盡管可將此結(jié)果作為MPRM電路面積與可靠性優(yōu)化的指導(dǎo)原則，但如果不附加其他原則，將會(huì)導(dǎo)致優(yōu)化結(jié)果過于偏向可靠性目標(biāo).

對(duì)表1中21個(gè)多輸出電路某個(gè)極性值的MPRM電路使用算法1計(jì)算了其所包含的異或門數(shù)，由于空間關(guān)系，這里僅給出統(tǒng)計(jì)結(jié)果.從平均角度看，有7個(gè)異或門被多個(gè)PO共享，占異或門總數(shù)的11.09%；與不考慮多個(gè)PO間的異或門共享相比，異或門數(shù)減少了13.45%；如果使用t來估算異或門數(shù)，異或門數(shù)被低估了23.15%.

表1 面積與可靠性多目標(biāo)優(yōu)化結(jié)果

表2 cm85a的Pareto前沿

綜上所述，MPRM電路存在著較好的面積與可靠性折中空間，可以通過極性優(yōu)化實(shí)現(xiàn)面積與可靠性之間的折中.較為準(zhǔn)確的目標(biāo)函數(shù)值估算以及采用Pareto支配概念進(jìn)行多目標(biāo)優(yōu)化，能夠更好地探索多個(gè)目標(biāo)的折中空間，可以避免由于某個(gè)目標(biāo)占絕對(duì)優(yōu)勢(shì)，使優(yōu)化結(jié)果過于偏向這個(gè)目標(biāo).

7 總結(jié)與展望

對(duì)于一個(gè)布爾函數(shù)而言，存在著指數(shù)量級(jí)不同函數(shù)結(jié)構(gòu)的MPRM，可以利用不同的MPRM函數(shù)結(jié)構(gòu)來進(jìn)行MPRM電路多個(gè)目標(biāo)的折中優(yōu)化.為了避免優(yōu)化結(jié)果過于偏向某個(gè)目標(biāo)，較為準(zhǔn)確的目標(biāo)估算以及恰當(dāng)?shù)膬?yōu)化策略對(duì)多目標(biāo)優(yōu)化而言至關(guān)重要.本文根據(jù)納電子MPRM電路結(jié)構(gòu)，給出了MPRM電路面積估算模型和SER解析評(píng)價(jià)模型，并使用Pareto支配概念進(jìn)行了面積與可靠性優(yōu)化，實(shí)驗(yàn)結(jié)果驗(yàn)證了所提出方法的有效性.通過合理地選擇最終非支配最優(yōu)解，可使MPRM電路在較小面積開銷的前提下獲得較大可靠性提升.

本文使用了窮舉搜索進(jìn)行MPRM電路的多目標(biāo)優(yōu)化，對(duì)于輸入數(shù)較多的電路，窮舉搜索無法在合理時(shí)間內(nèi)獲得Pareto最優(yōu)解集.因此下一步的工作是研究用于MPRM電路多目標(biāo)優(yōu)化的基于Pareto支配的智能算法，提高多目標(biāo)優(yōu)化的時(shí)間效率.

[1]Rao W,Yang C,Karri R,et al.Toward future systems with nanoscale devices:overcoming the reliability challenge[J].Computer,2011,44(2):46-53.

[2]Luckenbill S,Lee J-Y,Hu Y,et al.RALF:reliability analysis for logic faults-an exact algorithm and its applications[A].Proceedings of the 2010 Design,Automation & Test in Europe Conference & Exhibition[C].IEEE,2010.783-788.

[3]Al-Jassani B A,Urquhart N,Almaini A E A.Manipulation and optimisation techniques for Boolean logic[J].IET Computers and Digital Techniques,2010,4(3):227-239.

[4]汪鵬君,李輝,吳文晉,等.量子遺傳算法在多輸出Reed-Muller邏輯電路最佳極性搜索中的應(yīng)用[J].電子學(xué)報(bào),2010,38(5):1058-1063.

Wang P J,Li H,Wu W J,et al.Application of quantum genetic algorithm in searching for best polarity of multi-output Reed-Muller logic circuits[J].Acta Electronica Sinica,2010,38(5):1058-1063.(in Chinese)

[5]卜登立,江建慧.基于對(duì)偶邏輯的混合極性RM電路極性轉(zhuǎn)換和優(yōu)化方法[J].電子學(xué)報(bào),2015,43(1):79-85.

Bu D L,Jiang J H.Dual logic based polarity conversion and optimization of mixed polarity RM circuits[J].Acta Electronica Sinica,2015,43(1):79-85.(in Chinese)

[6]汪鵬君,汪迪生,蔣志迪,等.基于PSGA算法的ISFPRM電路面積與功耗優(yōu)化[J].電子學(xué)報(bào),2013,41(8):1542-1548.

Wang P J,Wang D S,Jiang Z D,et al.Area and power optimization of ISFPRM circuits based on PSGA algorithm[J].Acta Electronica Sinica,2013,41(8):1542-1548.(in Chinese)

[7]Jiang Z,Wang Z,Wang P.Delay-area trade-off for MPRM circuits based on hybrid discrete particle swarm optimization[J].Journal of Semiconductors,2013,34(6):132-137.

[8]Rahaman H,Das D K,Bhattacharya B B.Testable design of AND-EXOR logic networks with universal test sets[J].Computers and Electrical Engineering,2009,35(5):644-658.

[9]Limbrick D B,Yue S.Impact of synthesis constraints on error propagation probability of digital circuits[A].Proceedings of the 2011 IEEE International Symposium on Defect and Fault Tolerance in VLSI and Nanotechnology Systems[C].IEEE,2011.103-111.

[10]Chinchuluun A,Pardalos P M.A survey of recent developments in multiobjective optimization[J].Annual Operational Research,2007,154:29-50.

[11]Parker K P,Mccluskey E J.Probabilistic treatment of general combinational networks[J].IEEE Transactions on Computers,1975,C-24(6):668-670.

[12]Drechsler R,Becker B.Ordered Kronecker functional decision diagrams-a data structure for representation and manipulation of Boolean functions[J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,1998,17(10):965-973.

[13]Ben-Jamaa M H,Mohanram K,De-Micheli G.An efficient gate library for ambipolar CNTFET logic[J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,2011,30(2):242-255.

[14]Krishnaswamy S,Plaza S M,Markov I L,et al.Signature-based SER analysis and design of logic circuits[J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,2009,28(1):74-86.

[15]Polian I,Hayes J P,Reddy S M,et al.Modeling and mitigating transient errors in logic circuits[J].IEEE Transactions on Dependable and Secure Computing,2011,8(4):537-547.

[16]Takata T,Matsunaga Y.A robust algorithm for pessimistic analysis of logic masking effects in combinational circuits[A].Proceedings of the 17th International on-Line Testing Symposium[C].IEEE,2011.246-251.

卜登立 男，1975年出生，河北定州人.博士，副教授.主要研究領(lǐng)域?yàn)閂LSI設(shè)計(jì)和可靠性評(píng)估、計(jì)算機(jī)輔助設(shè)計(jì).

E-mail:bodengli@163.com

江建慧 男，1964年出生，浙江淳安人.博士，教授，博士生導(dǎo)師，CCF高級(jí)會(huì)員.主要研究領(lǐng)域?yàn)榭尚畔到y(tǒng)與網(wǎng)絡(luò)、軟件可靠性工程、VLSI/SoC測(cè)試與容錯(cuò).

E-mail:jhjiang@#edu.cn

Pareto Dominance Based Area and Reliability Optimization of MPRM Circuits

BU Deng-li1,2,3,JIANG Jian-hui2

(1.SchoolofElectronicsandInformationEngineering,JinggangshanUniversity,Ji’an,Jiangxi343009,China;2.SchoolofSoftwareEngineering,TongjiUniversity,Shanghai201804,China;3.KeyLaboratoryofWatershedEcologyandGeographicalEnvironmentMonitoringNASG,Ji’an,Jiangxi343009,China)

Area and SER (Soft Error Rate) evaluation models at logic level are proposed for area and reliability optimization of MPRM (Mixed-Polarity Reed-Muller) circuits,the trade-off between area and reliability is achieved by using Pareto dominance based multiobjective optimization.The area is computed by decomposing the XOR part of MPRM circuit as trees of XOR gates and counting in XOR gate sharing among multiple outputs.The SER is computed by using signal probability and fault propagation techniques,and taking into account the logic masking effects and correlations among signals in the circuit network.Based on the proposed area and SER evaluation models,the Pareto optimal set for area and SER of MPRM circuit is obtained by using polarity optimization method with Gray code based exhaustive search strategy,the final solution is selected by using a metric called efficiency factor.Experimental results by using a set of benchmark circuits from MCNC show that,in comparison with the MPRM circuits with minimized area,the selected MPRM circuits have improved reliability with less area overhead.

MPRM circuits;reliability optimization;area optimization;analytical SER evaluation model;Pareto dominance;multiobjective optimization

2015-05-05;

2015-10-28;責(zé)任編輯：藍(lán)紅杰

國家自然科學(xué)基金(No.61432017);流域生態(tài)與地理環(huán)境監(jiān)測(cè)國家測(cè)繪地理信息局重點(diǎn)實(shí)驗(yàn)室資助課題(No.WE2016012);吉安市科技局指導(dǎo)性科技計(jì)劃(吉市科計(jì)字[2016]4-4)

TP331.2,TP391.72,TP202+.1

A

0372-2112 (2016)11-2653-07

??學(xué)報(bào)URL:http://www.ejournal.org.cn

10.3969/j.issn.0372-2112.2016.11.013