基于PDTDPSO算法的MPRM電路面積與功耗優化

閆盼盼 俞海珍 史旭華 萬 凱

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

0 引 言

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

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

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

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

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

1 MPRM電路面積和功耗估計模型

在混合極性XNOR/OR電路中，對于任意一個n變量的邏輯函數極性P對應的XNOR/OR展開式如下所示：

(1)

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

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

(2)

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

(3)

(4)

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

(5)

目前集成電路的主要形式是CMOS電路，對于一個由n個門組成的電路，其總動態功耗的表達式為:

(6)

(7)

由式(7)可知，開關活動性的大小僅與P(g)有關，P(g)是輸出信號概率。根據文獻[12-13]可將多輸入XNOR和OR分解為一系列二輸入XNOR和OR。分解完成后，把XNOR門和OR門的開關活動性相加，從而得到整個MPRM邏輯電路的開關活動性，通過開關活動性的總和來權衡電路的功耗。

2 MPRM電路面積與功耗優化

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

在用Pareto支配概念進行算法改進的過程中，涉及三個集合。

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

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

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

上述三個集合中，非支配集是保存種群的每一代的非支配解集。外部集的更新是通過非支配集按照支配關系插入外部集，進而構成新的外部集。種群更新是由于個體和全局最優位置的更新。

2.1.1 邊界約束處理

部分粒子會超出定義的邊界范圍，這種情況會發生在粒子進行速度、位置更新以及變異的過程中，可能導致最終搜索到的最優值不在定義域范圍內[14]，采用以下公式進行處理：

(8)

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

經過運動之后粒子到了一個新的位置，若此時超出了邊界，可將粒子設定在邊界上，使得粒子的速度大小減為原來的1/10，方向與原來相反。

2.1.2 變異算子

引入變異算子的目的是對粒子施加擾動，預防算法陷入局部最優。本文引入的變異算子采用了與遺傳算法中的變異算子相似的操作。

變異概率的具體設計如下：

(9)

式中：t和nt分別為算法當前的代數和最大迭代次數。

randx是隨機數，在區間[0,1]中隨機產生，種群S中的每個粒子都會有一個隨機數。當randx≥pt時，不對粒子進行變異；否則就要執行變異操作。

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

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

(10)

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

對粒子進行變異的過程中，也可能需要采取邊界約束處理，因為粒子可能會有超出定義域邊界的行為。

2.1.3 非支配集

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

算法1 構造非支配集

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

Step 2 將選擇的個體i與種群中其他個體進行比較,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中其他個體支配，將i放入非支配集NP中；

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

Step 3S=part 1重復上述過程，直到S=?。

2.1.4 個體最優位置

根據PSO算法的原理，個體最優位置可解釋為個體i從初始化到目前為止的最優位置，公式表示如下：

(11)

如果粒子i支配個體最優位置，粒子i的當前位置就被定為個體最優位置；如果粒子i不支配個體最優位置，則個體最優位置保持不變。

2.1.5 外部集

外部集的更新是通過非支配集按照支配關系插入外部集，進而構成新的外部集。如算法2所示。

算法2 外部集的選取

Step 1 當外部集=?時，將初始種群的非支配集NP中的個體放入外部集中；

Step 2 當外部集≠?時，選取一個個體i∈NP，將i與外部集中的個體進行比較支配關系；

Step 2.1 如果i被外部集中的某些個體支配，則i不能進入外部集里；

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

Step 3 重復上述循環直至比較完畢。

2.1.6 全局最優位置

全局最優位置是從外部集中選取的。開始時，全局最優位置為粒子本身。接著，在每一代中，先計算擁擠距離，按照擁擠距離對外部集進行降序，然后從外部集的前5%的粒子中隨機選擇一個粒子為全局最優位置。

2.2 PDTDPSO算法在MPRM電路綜合優化上的應用

結合上述的PDTDPSO算法和混合極性XNOR/OR電路的極性轉換，將PDTDPSO算法應用到MPRM電路功耗和面積綜合優化。具體算法流程如圖1所示。

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

3 實驗結果及分析

在Windows 10操作系統下，使用C語言實現算法，通過VS2010軟件進行編譯，程序的硬件環境為Intel(R) Core(TM) i5-8250U@1.60 GHz 8 GB RAM，測試電路均采用PLA格式MCNC基準電路,對10個MCNC電路進行了面積與功耗優化。

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

表1給出了在10個MCNC電路上運行算法3的結果。表中：name和input分別為測試電路的名稱和輸入變量個數，area和power分別為測試20次電路最優解的平均面積和功耗，“Sarea”和“Spower”表示電路面積和功耗的優化率，計算公式如下：

(12)

(13)

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

表1 DPSO、TDPSO和PDTDPSO算法最優解實驗數據和優化率

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

4 結 語

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