基于Pareto支配的MPRM電路面積與功耗優(yōu)化*

閆盼盼，俞海珍，史旭華，萬 凱

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

1 引言

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

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

RM邏輯主要分為固定極性RM FPRM(Fixed-Polarity Reed-Muller)和混合極性RM MPRM(Mixed-Polarity Reed-Muller)。MPRM展開式的極性搜索空間龐大，包含了FPRM展開式的所有極性。因此，MPRM具有比FPRM更大的優(yōu)化空間和更好的優(yōu)化效果。極性直接決定MPRM邏輯電路的表達(dá)形式，然后影響電路的面積和功耗，并且其優(yōu)化是在特定空間中搜索1個(gè)或多個(gè)極性，使其目標(biāo)函數(shù)獲得最優(yōu)值。但是，MPRM電路也有其劣勢，它的極性搜索空間龐大，使其電路性能優(yōu)化的時(shí)間和空間復(fù)雜度很高。因此，需要尋找一種有效的算法來解決MPRM邏輯電路的這個(gè)問題。粒子群算法、遺傳算法、免疫算法都是目前比較常用的智能算法[4 - 6]。由于粒子群算法相比其它算法具有收斂速度快、魯棒性好等優(yōu)點(diǎn)，獲得了越來越多的關(guān)注。此外，它具有內(nèi)在的并行搜索機(jī)制，特別適用于傳統(tǒng)方法難以解決的復(fù)雜優(yōu)化問題。國內(nèi)外很多學(xué)者對粒子群算法進(jìn)行研究，取得了一些成果。文獻(xiàn)[7]提出一種多目標(biāo)量子粒子群算法，采用共享學(xué)習(xí)機(jī)制和雙勢阱模型避免算法發(fā)生過早收斂；文獻(xiàn)[8]提出了一種分群多目標(biāo)粒子群算法，采用向量法劃分子區(qū)域，不同子區(qū)域采用不同的搜索策略進(jìn)行尋優(yōu)操作，保持算法的多樣性；文獻(xiàn)[9]提出了一種三值多樣性粒子群算法，采用廣泛學(xué)習(xí)策略和三值變異操作進(jìn)行算法改進(jìn)，以保持種群多樣性策略，從而有效地克服算法的早熟收斂問題。

綜上所述，本文在離散三值粒子群優(yōu)化算法研究的基礎(chǔ)上，結(jié)合混合極性的特征，對文獻(xiàn)[9]中采用三值多樣性粒子群算法求解MPRM電路綜合優(yōu)化問題主要作了如下改進(jìn):(1)采用Pareto支配關(guān)系構(gòu)造外部集；(2)采用快速排序的方法在種群中搜索非支配解集；(3)對粒子進(jìn)行邊界約束處理。通過加入上述3種改進(jìn)策略，提出一種多目標(biāo)三值多樣性粒子群MOTDPSO(Multi-Objective Ternary Diversity Particle Swarm Optimization)算法。利用MOTDPSO算法對MPRM電路進(jìn)行最佳功耗和面積的綜合優(yōu)化，得到Pareto前沿，實(shí)現(xiàn)面積和功耗的折衷優(yōu)化，并通過實(shí)驗(yàn)進(jìn)行了驗(yàn)證。粒子的位置、速度更新公式參考文獻(xiàn)[9]。

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

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

(1)

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

多輸入OR操作分解如式(2)所示，根據(jù)式(2)，Si可由mi個(gè)二輸入OR操作得到。

(2)

多輸入XNOR 和OR操作具體分解如式(3)和式(4)所示，根據(jù)式(3)和式(4)將多輸入XNOR 和OR操作分解成二輸入OR操作和二輸入XNOR操作，它們的最終項(xiàng)數(shù)可表示為:

(3)

(4)

混合極性O(shè)R/XNOR電路面積Earea可表示為:

Earea=No_of_OR+No_of_XNOR=

(5)

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

(6)

(7)

在式(7)中可看到，開關(guān)活動性的大小僅與P(g)有關(guān)，P(g)是輸出信號g的概率。根據(jù)文獻(xiàn)[10，11]可將多輸入XNOR和OR分解為一系列二輸入XNOR和OR。分解完成后，把XNOR門和OR門的開關(guān)活動性進(jìn)行相加，從而得到整個(gè)MPRM邏輯電路的開關(guān)活動性，通過開關(guān)活動性的總和來權(quán)衡電路的功耗。

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

3.1 基于Pareto支配的三值粒子群算法

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

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

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

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

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

3.1.1 邊界約束處理

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

(8)

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

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

3.1.2 非支配集

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

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

Step 1 選擇1個(gè)個(gè)體i∈S，并且i為種群S的第1個(gè)個(gè)體；

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

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

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

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

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

Step 3S=patrt1，重復(fù)上述過程，直到S=?。

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

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

(9)

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

3.1.4 外部集

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

算法2 外部集的選取

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

Step 1 當(dāng)外部集不為?時(shí)，選取1個(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)直至比較完畢。

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

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

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

結(jié)合以上所述的三值多樣性粒子群算法和混合極性O(shè)R/XNOR電路的極性轉(zhuǎn)換，本文提出了一種改進(jìn)的三值粒子群算法，將該算法應(yīng)用于MPRM電路功耗和面積優(yōu)化。算法流程具體描述如圖1所示。

Figure 1 Flow chart of MPRM circuit power consumption and area optimization based on MOTDPSO algorithm圖1 MOTDPSO算法優(yōu)化MPRM電路功耗和面積流程圖

4 實(shí)驗(yàn)數(shù)據(jù)與分析

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

圖2給出了電路rd530、5xp10以及misex10的Pareto前沿。從圖2中可以看出，這3個(gè)電路的面積與功耗的Pareto前沿不是嚴(yán)格的凸函數(shù)，其余電路的Pareto前沿也是如此。這也證實(shí)了使用Pareto支配進(jìn)行MPRM電路面積與功耗優(yōu)化的重要性。

Figure 2 Pareto frontier of MPRM circuit area and power consumption圖2 MPRM電路面積與功耗Pareto前沿

表1給出了在18個(gè)MCNC電路上運(yùn)行MOTDPSO算法的結(jié)果，其中“benchmark”表示測試電路的名稱，“inputs”表示測試電路的輸入變量個(gè)數(shù)；“N_PF”表示Pareto最優(yōu)解集的大??；“面積增加”和“功耗減少”分別表示所選擇的最優(yōu)解相對于面積最小解所引起的面積增加和功耗降低的比率。“所選擇的最優(yōu)解”是根據(jù)效率因子“E=功耗減少/面積增加”所選取的最終解，其選取的原則：(1)如果存在E>1的最優(yōu)解，則所選擇的最優(yōu)解要使E的值最大化；(2)如果不存在E>1的最優(yōu)解，則所選擇的最優(yōu)解就是面積最小解。此原則是基于以盡可能小的面積開銷獲得更低的功耗。

從表1可以看出，這18個(gè)電路的Pareto最優(yōu)解集都包含多個(gè)非支配最優(yōu)解，特別是table3，其非支配最優(yōu)解的數(shù)量達(dá)到了62個(gè)。這也證實(shí)了使用Pareto支配概念進(jìn)行MPRM電路面積與可靠性優(yōu)化的有效性。

根據(jù)效率因子E所選擇的最終解中，有3個(gè)電路所選擇的最優(yōu)解就是面積最小最優(yōu)解，因?yàn)檎也坏紼小于1的最優(yōu)解，換句話說，雖然可以降低功耗，但是面積開銷較大。對于剩余的15個(gè)電路，所選擇的最優(yōu)解的E均大于1；特別是t481，在不到1%的面積開銷下，功耗減少了4.26%，其最終解的E為4.84。對于表1的電路，從平均值看，相對于面積最小解，所選擇的最終解面積增加了5.30%，并且功耗減少了8.18% 。

Table 1 Area and power consumption optimization results using MOTDPSO algorithm表1 MOTDPSO算法面積與功耗優(yōu)化結(jié)果

為了進(jìn)一步驗(yàn)證MOTDPSO算法求解MPRM電路面積與功耗優(yōu)化的有效性，將其與NSGA-II[12]算法進(jìn)行實(shí)驗(yàn)比對。將上述2種算法分別測試20次,對20次結(jié)果的最優(yōu)解求平均值。表2給出了在18個(gè)MCNC電路上運(yùn)行上述2種算法的結(jié)果。表中“benchmark”和“inputs”分別為測試電路的名稱和輸入變量個(gè)數(shù)，“area”和“power”分別為測試20次電路最優(yōu)解的平均面積和功耗，“S(area)”和“S(power)”表示電路面積和功耗的優(yōu)化率，計(jì)算公式如下所示：

(10)

(11)

其中，SA1(SP1)、SA2(SP2)分別表示對NSGA-II和MOTDPSO算法測試20次搜索到的最優(yōu)解的平均面積和功耗。

由表2可知，MOTDPSO算法相比NSGA-II算法能獲得更小的電路面積和功耗。比如pcle電路，MOTDPSO算法相比于NSGA-II算法面積和功耗分別優(yōu)化了8.50%和13.83%。在misex3電路中，即使MOTDPSO算法搜索到的最佳極性電路面積有所增加，但功耗減少了。根據(jù)18個(gè)Benchmark電路的測試結(jié)果可知，MOTDPSO算法相比NSGA-II算法，電路面積與功耗平均優(yōu)化率分別為4.29%和6.02%。最后，將2種算法運(yùn)行20次的面積與功耗進(jìn)行方差計(jì)算，NSGA-II算法面積與功耗方差為5.64和8.56，MOTDPSO算法面積與功耗方差分別為4.87和6.35，所以MOTDPSO算法具有良好的魯棒性。

5 結(jié)束語

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

Table 2 Optimal solution data and optimization rate of MOTDPSO and NSGA-II algorithms表2 MOTDPSO與NSGA-II算法最優(yōu)解和優(yōu)化率