基于PDTDPSO算法的MPRM電路面積與功耗優(yōu)化

閆盼盼 俞海珍 史旭華 萬(wàn) 凱

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

0 引 言

隨著集成電路(IC)技術(shù)的發(fā)展，電路集成度正在迅速增加[1-2]。功耗和面積已經(jīng)成為IC設(shè)計(jì)中不容忽視的問(wèn)題，在電路設(shè)計(jì)流程的各個(gè)階段都需要考慮電路面積和功耗。

任何邏輯電路都可以由基于AND/OR/NOT形式的布爾邏輯，或基于AND/XOR或OR/XNOR形式的Reed-Muller(RM)邏輯來(lái)表示。隨著集成電路優(yōu)化設(shè)計(jì)的發(fā)展，以Reed-Muller(RM)邏輯表示的邏輯電路在功耗、面積、速度和可測(cè)試性方面比傳統(tǒng)布爾邏輯的形式更具優(yōu)勢(shì)[3]。

RM邏輯主要分為固定極性RM(fixed-polarityReed-Muller，F(xiàn)PRM)和混合極性RM(mixed-polarityReed-Muller，MPRM)[4]。MPRM展開(kāi)式的極性搜索空間龐大，包含了FPRM展開(kāi)式的所有極性。因此，MPRM具有比FPRM更大的優(yōu)化空間和更好的優(yōu)化效果。極性直接決定MPRM邏輯電路的表達(dá)形式，影響電路的面積和功耗。其優(yōu)化是在特定空間中搜索一個(gè)或多個(gè)極性，使其目標(biāo)函數(shù)獲得最優(yōu)值。但是，MPRM電路也有其劣勢(shì)，它的極性搜索空間龐大，使其電路性能優(yōu)化的時(shí)間和空間復(fù)雜度很高。因此，MPRM邏輯電路需要尋找一種有效的算法來(lái)解決這個(gè)問(wèn)題。目前，MPRM邏輯電路優(yōu)化普遍使用的方法是枚舉法[5-7]和遺傳算法[8-10]。但是，大規(guī)模的MPRM邏輯電路優(yōu)化使用枚舉法需要耗費(fèi)大量時(shí)間，使用遺傳算法求解又會(huì)有種群多樣性保持機(jī)制差、收斂速度慢、局部尋優(yōu)能力弱等缺點(diǎn)。

由以上分析可知，MPRM邏輯電路急需尋找一種并行搜索能力以及搜索效率更好的智能優(yōu)化算法，才能使MPRM邏輯電路優(yōu)化算法能夠有效地解決問(wèn)題。粒子群優(yōu)化(ParticleSwarmOptimization，PSO)算法是一種基于群體智能的新穎的全局優(yōu)化算法，更為重要的是，它具有其他算法不具備的內(nèi)在的并行搜索機(jī)制。PSO算法可以解決枚舉法、遺傳算法等傳統(tǒng)方法很難解決的優(yōu)化問(wèn)題[4]。

綜上所述，在離散三值粒子群優(yōu)化算法研究的基礎(chǔ)上，結(jié)合混合極性的特征，對(duì)文獻(xiàn)[4]中采用TDPSO求解MPRM電路綜合優(yōu)化問(wèn)題作出如下改進(jìn):① 采用Pareto支配關(guān)系構(gòu)造外部集；② 在種群中搜索非支配解集時(shí)，采用快速排序的方法；③ 引入變異算子對(duì)粒子施加擾動(dòng)；④ 對(duì)粒子進(jìn)行邊界約束處理。通過(guò)加入上述四種改進(jìn)策略，提出一種基于Pareto支配的三值多樣性粒子群算法(PDTDPSO)。利用基于PDTDPSO算法對(duì)MPRM邏輯電路進(jìn)行功耗和面積綜合優(yōu)化，得到Pareto前沿，實(shí)現(xiàn)面積和功耗的綜合優(yōu)化，并通過(guò)實(shí)驗(yàn)進(jìn)行了驗(yàn)證。粒子的位置、速度更新公式參考文獻(xiàn)[4]。

1 MPRM電路面積和功耗估計(jì)模型

在混合極性XNOR/OR電路中，對(duì)于任意一個(gè)n變量的邏輯函數(shù)極性P對(duì)應(yīng)的XNOR/OR展開(kāi)式如下所示：

(1)

由式(1)可知，XNOR/OR電路實(shí)際是由多輸入XNOR和OR操作組成的，而多輸入的XNOR和OR操作可以分解為二輸入的XNOR和OR操作，二輸入的XNOR和OR操作項(xiàng)數(shù)之和則表示電路面積。

多輸入OR操作分解如下式所示，根據(jù)公式將多輸入OR操作Si可分解為mi個(gè)二輸入OR操作。

(2)

多輸入XNOR和OR操作具體分解如式(3)和式(4)所示。根據(jù)公式將多輸入XNOR和OR操作分解成二輸入OR操作和二輸入XNOR操作。

(3)

(4)

混合極性XNOR/OR電路面積Earea可表示為:

(5)

目前集成電路的主要形式是CMOS電路，對(duì)于一個(gè)由n個(gè)門(mén)組成的電路，其總動(dòng)態(tài)功耗的表達(dá)式為:

(6)

(7)

由式(7)可知，開(kāi)關(guān)活動(dòng)性的大小僅與P(g)有關(guān)，P(g)是輸出信號(hào)概率。根據(jù)文獻(xiàn)[12-13]可將多輸入XNOR和OR分解為一系列二輸入XNOR和OR。分解完成后，把XNOR門(mén)和OR門(mén)的開(kāi)關(guān)活動(dòng)性相加，從而得到整個(gè)MPRM邏輯電路的開(kāi)關(guān)活動(dòng)性，通過(guò)開(kāi)關(guān)活動(dòng)性的總和來(lái)權(quán)衡電路的功耗。

2 MPRM電路面積與功耗優(yōu)化

2.1 基于Pareto支配的三值多樣性粒子群算法

在用Pareto支配概念進(jìn)行算法改進(jìn)的過(guò)程中，涉及三個(gè)集合。

1) 種群：由算法中的所有粒子組合而成。

2) 非支配集：保存了每一代中的非支配解。

3) 外部集：保存了種群從初始到目前搜索到的所有非支配解[14]。

上述三個(gè)集合中，非支配集是保存種群的每一代的非支配解集。外部集的更新是通過(guò)非支配集按照支配關(guān)系插入外部集，進(jìn)而構(gòu)成新的外部集。種群更新是由于個(gè)體和全局最優(yōu)位置的更新。

2.1.1 邊界約束處理

部分粒子會(huì)超出定義的邊界范圍，這種情況會(huì)發(fā)生在粒子進(jìn)行速度、位置更新以及變異的過(guò)程中，可能導(dǎo)致最終搜索到的最優(yōu)值不在定義域范圍內(nèi)[14]，采用以下公式進(jìn)行處理：

(8)

式中：[xmin,j,xmax,j]表示第j維的取值范圍。

經(jīng)過(guò)運(yùn)動(dòng)之后粒子到了一個(gè)新的位置，若此時(shí)超出了邊界，可將粒子設(shè)定在邊界上，使得粒子的速度大小減為原來(lái)的1/10，方向與原來(lái)相反。

2.1.2 變異算子

引入變異算子的目的是對(duì)粒子施加擾動(dòng)，預(yù)防算法陷入局部最優(yōu)。本文引入的變異算子采用了與遺傳算法中的變異算子相似的操作。

變異概率的具體設(shè)計(jì)如下：

(9)

式中：t和nt分別為算法當(dāng)前的代數(shù)和最大迭代次數(shù)。

randx是隨機(jī)數(shù)，在區(qū)間[0,1]中隨機(jī)產(chǎn)生，種群S中的每個(gè)粒子都會(huì)有一個(gè)隨機(jī)數(shù)。當(dāng)randx≥pt時(shí)，不對(duì)粒子進(jìn)行變異；否則就要執(zhí)行變異操作。

本文變異使用的方法為非均勻變異，粒子i的位置按下式進(jìn)行變異。

xi=xi+θμ(1-randx)vi

(10)

式中：θ是在±1兩值中隨機(jī)選取，用以表示粒子經(jīng)過(guò)變異后的運(yùn)動(dòng)方向，+1表示粒子經(jīng)過(guò)變異后與原始的運(yùn)動(dòng)方向相同，-1則表示相反；μ=3，這樣取值的好處是可使粒子跳出局部最優(yōu)。

對(duì)粒子進(jìn)行變異的過(guò)程中，也可能需要采取邊界約束處理，因?yàn)榱Ｗ涌赡軙?huì)有超出定義域邊界的行為。

2.1.3 非支配集

非支配集的構(gòu)造采用快速排序的方法，如算法1所示。

算法1 構(gòu)造非支配集

Step 1 首先選擇一個(gè)個(gè)體i∈S，一般情況下i為種群S的第一個(gè)個(gè)體；

Step 2 將選擇的個(gè)體i與種群中其他個(gè)體進(jìn)行比較,S被分為part 1和part 2。

Step 2.1 如果part 2被i支配,即i支配part 2，清除part 2;

Step 2.2 如果part 1不被i支配，保留part 1；

Step 2.2.1 如果i不被part 1中其他個(gè)體支配，將i放入非支配集NP中；

Step 2.2.2 如果i被part 1中其他個(gè)體支配，清除i；

Step 3S=part 1重復(fù)上述過(guò)程，直到S=?。

2.1.4 個(gè)體最優(yōu)位置

根據(jù)PSO算法的原理，個(gè)體最優(yōu)位置可解釋為個(gè)體i從初始化到目前為止的最優(yōu)位置，公式表示如下：

(11)

如果粒子i支配個(gè)體最優(yōu)位置，粒子i的當(dāng)前位置就被定為個(gè)體最優(yōu)位置；如果粒子i不支配個(gè)體最優(yōu)位置，則個(gè)體最優(yōu)位置保持不變。

2.1.5 外部集

外部集的更新是通過(guò)非支配集按照支配關(guān)系插入外部集，進(jìn)而構(gòu)成新的外部集。如算法2所示。

算法2 外部集的選取

Step 1 當(dāng)外部集=?時(shí)，將初始種群的非支配集NP中的個(gè)體放入外部集中；

Step 2 當(dāng)外部集≠?時(shí)，選取一個(gè)個(gè)體i∈NP，將i與外部集中的個(gè)體進(jìn)行比較支配關(guān)系；

Step 2.1 如果i被外部集中的某些個(gè)體支配，則i不能進(jìn)入外部集里；

Step 2.2 如果i不被外部集中的某些個(gè)體支配，將i放入外部集里，外部集里被個(gè)體i支配的那些個(gè)體要被剔除；

Step 3 重復(fù)上述循環(huán)直至比較完畢。

2.1.6 全局最優(yōu)位置

全局最優(yōu)位置是從外部集中選取的。開(kāi)始時(shí)，全局最優(yōu)位置為粒子本身。接著，在每一代中，先計(jì)算擁擠距離，按照擁擠距離對(duì)外部集進(jìn)行降序，然后從外部集的前5%的粒子中隨機(jī)選擇一個(gè)粒子為全局最優(yōu)位置。

2.2 PDTDPSO算法在MPRM電路綜合優(yōu)化上的應(yīng)用

結(jié)合上述的PDTDPSO算法和混合極性XNOR/OR電路的極性轉(zhuǎn)換，將PDTDPSO算法應(yīng)用到MPRM電路功耗和面積綜合優(yōu)化。具體算法流程如圖1所示。

圖1 基于PDTDPSO算法的MPRM電路面積與功耗優(yōu)化流程

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

在Windows 10操作系統(tǒng)下，使用C語(yǔ)言實(shí)現(xiàn)算法，通過(guò)VS2010軟件進(jìn)行編譯，程序的硬件環(huán)境為Intel(R) Core(TM) i5-8250U@1.60 GHz 8 GB RAM，測(cè)試電路均采用PLA格式MCNC基準(zhǔn)電路,對(duì)10個(gè)MCNC電路進(jìn)行了面積與功耗優(yōu)化。

為證明PDTDPSO算法在求解三值MPRM電路面積與功耗綜合優(yōu)化問(wèn)題的有效性,將PDTDPSO算法與DPSO算法和文獻(xiàn)[4]的TDPSO算法進(jìn)行對(duì)比。為了方便對(duì)比，本文選用了文獻(xiàn)[4]中的10個(gè)測(cè)試電路。TDPSO算法參數(shù)設(shè)置參考文獻(xiàn)[4]，采用加權(quán)求和法搜索最優(yōu)解，w取0.8，電路的功耗和面積綜合優(yōu)化最佳。DPSO算法采用加權(quán)求和法搜索最優(yōu)解，參數(shù)設(shè)置均與TDPSO算法相同。PDTDPSO采用多目標(biāo)優(yōu)化方法搜索最佳極性解集，需對(duì)PDTDPSO算法搜索到的最佳極性解集進(jìn)行處理,選取一個(gè)最優(yōu)解與DPSO算法和TDPSO算法進(jìn)行結(jié)果比較?！八x擇的最優(yōu)解”是根據(jù)效率因子“E=功耗減少/面積增加”所選取的最終解，其選取的原則：① 如果存在E>1的最優(yōu)解，則所選擇的最優(yōu)解要使E的值最大化；② 如果不存在E>1的最優(yōu)解，則所選擇的最優(yōu)解就是面積最小解。此原則是基于以盡可能小的面積開(kāi)銷(xiāo)獲得更低的功耗。將上述3種算法分別測(cè)試20次,對(duì)20次結(jié)果的最優(yōu)解求平均值。

表1給出了在10個(gè)MCNC電路上運(yùn)行算法3的結(jié)果。表中：name和input分別為測(cè)試電路的名稱(chēng)和輸入變量個(gè)數(shù)，area和power分別為測(cè)試20次電路最優(yōu)解的平均面積和功耗，“Sarea”和“Spower”表示電路面積和功耗的優(yōu)化率，計(jì)算公式如下：

(12)

(13)

式中：SA1(SP1)、SA2(SP2)、SA3(SP3)分別表示對(duì)DPSO、TDPSO和PDTDPSO算法測(cè)試20次搜索到的最優(yōu)解的平均面積和功耗。

表1 DPSO、TDPSO和PDTDPSO算法最優(yōu)解實(shí)驗(yàn)數(shù)據(jù)和優(yōu)化率

由表1可知，PDTDPSO算法相比DPSO算法和TDPSO算法能獲得更小的電路面積和功耗。例如在Rd84電路中，PDTDPSO算法比DPSO算法面積和功耗分別優(yōu)化了31.25%和24.25%，PDTDPSO算法比TDPSO算法面積和功耗分別優(yōu)化了16.67%和10.87%。在Ex1010電路中，即使PDTDPSO算法搜索到的最佳極性電路面積有所增加，但功耗減少了。根據(jù)10個(gè)Benchmark電路的測(cè)試結(jié)果可知，PDTDPSO算法相比DPSO算法，電路面積與功耗平均優(yōu)化率分別為11.10%和13.71%，PDTDPSO算法相比TDPSO算法，電路面積與功耗平均優(yōu)化率分別為5.84%和8.08%。最后，將3種算法運(yùn)行20次的面積與功耗進(jìn)行方差計(jì)算，DPSO算法面積與功耗方差為13.15和7.64，TDPSO算法面積與功耗方差為12.98和7.43，PDTDPSO算法方差分別為6.89和3.47?？梢钥闯?，PDTDPSO算法具有良好的魯棒性。

4 結(jié) 語(yǔ)

針對(duì)MPRM電路的面積與功耗綜合優(yōu)化問(wèn)題，提出了一種基于PDTDPSO算法的MPRM電路面積與功耗最佳極性搜索方案。在TDPSO算法求解MPRM電路綜合優(yōu)化問(wèn)題的基礎(chǔ)上，引入變異算子對(duì)粒子施加擾動(dòng)，對(duì)超出定義的邊界范圍的粒子，執(zhí)行邊界約束處理，并結(jié)合Pareto支配概念來(lái)改進(jìn)算法;然后建立了基于Pareto支配的三值粒子群算法的粒子與MPRM電路極性之間的參數(shù)映射關(guān)系，并結(jié)合了面積與功耗估計(jì)模型以及XNOR/OR電路混合極性轉(zhuǎn)換方法，將該算法應(yīng)用于MPRM電路的功耗和面積優(yōu)化。最后對(duì)10個(gè)PLA格式MCNC Benchmark電路進(jìn)行測(cè)試，與DPSO和TDPSO算法搜索到的最優(yōu)解相比，PDTDPSO算法有較好的優(yōu)化效果和魯棒性。