基于多策略離散粒子群算法的MPRM電路延時(shí)與面積優(yōu)化

符　強(qiáng)，汪鵬君，童　楠，王銘波，張會(huì)紅

(1.寧波大學(xué)電路與系統(tǒng)研究所，浙江寧波 315211； 2.寧波大學(xué)科學(xué)技術(shù)學(xué)院，浙江寧波 315212)

?

基于多策略離散粒子群算法的MPRM電路延時(shí)與面積優(yōu)化

符強(qiáng)1,2，汪鵬君1，童楠2，王銘波2，張會(huì)紅1

(1.寧波大學(xué)電路與系統(tǒng)研究所，浙江寧波 315211； 2.寧波大學(xué)科學(xué)技術(shù)學(xué)院，浙江寧波 315212)

針對(duì)大規(guī)?；旌蠘O性Reed-Muller(Mixed Polarity Reed-Muller,MPRM)邏輯電路的延時(shí)與面積優(yōu)化，提出一種基于多策略離散粒子群優(yōu)化(Multi-Strategy Discrete Particle Swarm Optimization,MSDPSO)的極性搜索方法.在MSDPSO算法中，對(duì)粒子進(jìn)行團(tuán)隊(duì)劃分，每個(gè)團(tuán)隊(duì)既執(zhí)行不同策略，又相互聯(lián)系，并行完成探索與開發(fā)的雙重任務(wù).同時(shí)在進(jìn)化過程中采用高斯調(diào)整來激活尋優(yōu)能力較差的粒子.結(jié)合MSDPSO算法和列表極性轉(zhuǎn)換技術(shù)，對(duì)大規(guī)模MPRM電路進(jìn)行延時(shí)與面積極性搜索.最后對(duì)PLA格式的MCNC Benchmark電路進(jìn)行算法性能測(cè)試，結(jié)果驗(yàn)證了MSDPSO算法的有效性.與離散粒子群優(yōu)化(Discrete Particle Swarm Optimization,DPSO)算法的優(yōu)化結(jié)果相比較，MSDPSO算法獲取的電路延時(shí)平均縮短8.43%，面積平均節(jié)省38.36%.

多策略離散粒子群算法；MPRM邏輯電路；延時(shí)與面積優(yōu)化；極性搜索

1　引言

任意邏輯函數(shù)的表達(dá)和實(shí)現(xiàn)都具有布爾邏輯形式和Reed-Muller(RM)邏輯形式.基于XOR/AND 或XNOR/OR運(yùn)算的RM邏輯在算術(shù)電路、奇偶校驗(yàn)電路及通信電路等應(yīng)用中，具有比布爾邏輯更緊湊的結(jié)構(gòu)和更好的可測(cè)性.隨著電子行業(yè)對(duì)環(huán)保節(jié)能要求的不斷提高，RM邏輯設(shè)計(jì)因其特有優(yōu)勢(shì)越來越受到學(xué)術(shù)界關(guān)注.其中，RM邏輯電路的延時(shí)與面積優(yōu)化是電路綜合和優(yōu)化技術(shù)的重要組成部分，受到了普遍重視.

常用的RM邏輯主要有固定極性RM(Fixed Polarity Reed-Muller,FPRM)和混合極性RM(Mixed Polarity Reed-Muller,MPRM)兩種展開式.對(duì)于n個(gè)輸入變量的邏輯函數(shù)，有2n個(gè)固定極性及3n個(gè)混合極性，分別對(duì)應(yīng)著2n種FPRM展開式及3n種MPRM展開式.MPRM表達(dá)式包含所有FPRM表達(dá)式，因此能夠獲取更優(yōu)的電路結(jié)構(gòu).

不同的電路極性對(duì)應(yīng)于不同的電路邏輯展開式，相應(yīng)的電路延遲和面積大小也不一樣.因此，只有確定較佳的電路極性，才能優(yōu)化MPRM電路的延時(shí)和面積[1].MPRM電路極性搜索實(shí)質(zhì)是一個(gè)組合優(yōu)化問題，對(duì)于變量數(shù)較少的電路，可以通過枚舉法來實(shí)現(xiàn)最優(yōu)極性的搜索，但是隨著電路規(guī)模的增大，枚舉法在有限時(shí)間內(nèi)完成最優(yōu)極性搜尋任務(wù)將變得愈發(fā)困難，需要快速有效的優(yōu)化算法來搜索電路最佳極性.

群體智能算法，如離散粒子群優(yōu)化算法[2](DPSO)、遺傳算法[3](Genetic Algorithm，GA)及蟻群算法[4](Ant Colony Algorithm，ACA)等是近年發(fā)展起來的新型優(yōu)化方法，在快速解決大型復(fù)雜組合優(yōu)化問題時(shí)具有一定優(yōu)勢(shì)，已得到廣泛應(yīng)用.在MPRM電路優(yōu)化設(shè)計(jì)領(lǐng)域，近年來也出現(xiàn)了關(guān)于群體智能算法的應(yīng)用研究，并取得一定的成果.如文獻(xiàn)[5]在遺傳算法中引入粒子群算法的搜索機(jī)制，提出了一種能有效提高電路面積優(yōu)化效果的方法；文獻(xiàn)[6]基于多種群協(xié)同思想，并結(jié)合三種不同的變異更新方法提出了一種混合多值離散粒子群優(yōu)化算法，加快了電路極性優(yōu)化的速度.

與其他同類算法相比，模擬鳥群覓食的DPSO算法結(jié)構(gòu)簡(jiǎn)單、易于編程，同時(shí)具有搜索速度快、通用性強(qiáng)等優(yōu)點(diǎn).在線性減小的慣性權(quán)重作用下，DPSO算法中的粒子記錄自身最優(yōu)值，并追隨種群最優(yōu)個(gè)體進(jìn)行先全局探索后局部開發(fā)的尋優(yōu)策略，能夠迅速定位并捕捉目標(biāo).但是在算法運(yùn)行后期，粒子將集聚在局部最優(yōu)區(qū)域，易于發(fā)生早熟狀況.

鑒于此，針對(duì)大規(guī)模MPRM電路的特點(diǎn)，提出一種基于多策略離散粒子群算法(MSDPSO)的MPRM電路延時(shí)與面積優(yōu)化方法，將決定MPRM電路延時(shí)與面積的電路極性表示為算法中的粒子，并利用列表技術(shù)進(jìn)行極性轉(zhuǎn)換.然后通過粒子種群的迭代進(jìn)化搜索到MPRM電路的最佳極性，優(yōu)化電路延時(shí)與面積設(shè)計(jì).最后將對(duì)大規(guī)模的MCNC Benchmark電路進(jìn)行測(cè)試以驗(yàn)證算法的有效性.

2　極性轉(zhuǎn)換與延時(shí)和面積估計(jì)模型

2.1極性轉(zhuǎn)換

在MPRM電路中，邏輯函數(shù)f(xn-1,xn-2,…,x0)有3n個(gè)混合極性，其中極性p的MPRM展開式可表示為：

(1)

(2)

(3)

(4)

在MPRM展開式的極性轉(zhuǎn)換算法中，列表轉(zhuǎn)換技術(shù)[7]能實(shí)現(xiàn)任意輸入變量邏輯函數(shù)的快速轉(zhuǎn)換，是應(yīng)用最廣泛的轉(zhuǎn)換算法之一.基于列表轉(zhuǎn)換技術(shù)的從混合極性p轉(zhuǎn)換到極性q的算法描述如下所示.

2.2延時(shí)和面積模型構(gòu)建

2.2.1邏輯分解

對(duì)MPRM電路進(jìn)行邏輯分解能有效簡(jiǎn)化電路，利于延遲優(yōu)化.常用的邏輯分解方法是對(duì)邏輯電路表達(dá)式進(jìn)行提取公因式操作，從而不斷簡(jiǎn)化電路結(jié)構(gòu).根據(jù)Ashenhurst算法[8]，MPRM展開式的具體邏輯分解形式如式(5)所示：

f(xn-1,xn-2,…,x0)=f(A)·f(B)

(5)

其中，A={xn-1,xn-2,…,xi}和B={xi-1,xi-2,…,x0}.符號(hào)“·”為與運(yùn)算.

因此，MPRM電路展開式的邏輯分解算法描述如下：

2.2.2延時(shí)和面積估計(jì)模型

在數(shù)字邏輯設(shè)計(jì)中，產(chǎn)生延時(shí)的主要因素是邏輯門的傳輸延遲，電容及其他因素可以忽略.將二輸入門的傳輸延時(shí)大小定義為一個(gè)單位時(shí)間，則可先分解電路為二輸入AND門和二輸入XOR門組合，然后進(jìn)行延時(shí)與面積計(jì)算.設(shè)N(U)為二輸入門電路網(wǎng)絡(luò)，將N中的節(jié)點(diǎn)總數(shù)目表示電路面積，而電路延遲可記為二輸入門在關(guān)鍵路徑的傳輸延時(shí)之和.j為節(jié)點(diǎn)集合U中的某一節(jié)點(diǎn)，代表一個(gè)二輸入門，其延遲可表示為[9]：

tj=1+max(tj-a,tj-b)

(6)

其中，tj-a和tj-b為節(jié)點(diǎn)j的輸入延遲，tj為節(jié)點(diǎn)j的輸出延遲，j∈U.

類Huffman算法常用于獲取邏輯電路的最小延遲.設(shè)T=T1·T2·…·Ti·…Tc為一個(gè)MPRM展開式，其中Ti為第i個(gè)向量的子展開式，c為邏輯分解后的終端節(jié)點(diǎn)向量個(gè)數(shù).令原始輸入信號(hào)的延時(shí)為0，則MPRM電路的延遲分解算法可以描述為：

3　多策略離散粒子群算法(MSDPSO)

3.1離散粒子群算法(DPSO)

在DPSO算法中，每個(gè)個(gè)體的位置和速度都以隨機(jī)方式在解空間內(nèi)進(jìn)行初始化.假設(shè)粒子種群中的粒子總數(shù)為m，搜索空間為n維，其中第i個(gè)粒子在n維空間的位置可表示為Xi=(xi0,xi1,…,xij,…,xin-1)，其飛行速度可表示為Vi=(vi0,vi1,…,vij,…,vin-1).記個(gè)體最優(yōu)位置pbesti=(pbesti0,pbesti1,…,pbestij,…,pbestin-1)，粒子群最優(yōu)位置gbest=(gbest0,gbest1,…,gbestj,…,gbestn-1).則個(gè)體速度更新分別如式(7)和式(8)所示：vij(t+1)=w(t)·vij(t)+c1·random1()·(pbestij-xij(t))+c2·random2()·(gbestj-xij(t))

(7)

xij(t+1)=round(M/(1+exp(-vij(t+1)))+(M-1)

·k·random3())

(8)

其中：t為當(dāng)前進(jìn)化代數(shù)；random1()，random2()和random3()是(0,1)范圍內(nèi)的隨機(jī)數(shù)；round為取整操作；1+exp(-vij(t+1))為sigmoid函數(shù)；M是xij的取值狀態(tài)數(shù)量，k是一常數(shù)；c1和c2為加速因子，用于調(diào)整粒子向pbest和gbest轉(zhuǎn)移的速度；w是慣性權(quán)重，用于協(xié)調(diào)粒子群體的開發(fā)與探索能力.

3.2多策略離散粒子群算法(MSDPSO)

在DPSO算法中，由于gbest粒子對(duì)其他粒子的牽引作用過強(qiáng)，容易引導(dǎo)所有粒子迅速收攏，形成了種群的快速趨同效應(yīng)，導(dǎo)致算法陷入局部最優(yōu)解.針對(duì)以上缺點(diǎn)，文獻(xiàn)[10]借鑒遺傳算法機(jī)制，提出了一種改進(jìn)型DPSO算法(HDPSO)，該算法在粒子群體陷入早熟狀態(tài)時(shí)，利用精英策略及變異算子以幫助粒子跳出局部最優(yōu)區(qū)域，在一定程度上優(yōu)化了粒子種群的搜索性能.

近年來，群體智能優(yōu)化方案中的多策略集成設(shè)計(jì)研究越來越得到關(guān)注[11,12].多策略集成思想指出，由于所求問題的特征不同，單一的搜索策略不易滿足各類要求，因此智能群體在尋優(yōu)過程中應(yīng)提供多種搜索策略，并通過策略整合來平衡探索和開發(fā)的雙重要求.鑒于此，提出了一種基于多策略的離散粒子群算法，通過組建具有不同尋優(yōu)策略的粒子團(tuán)隊(duì)，設(shè)置相應(yīng)的策略集成方案，來實(shí)現(xiàn)探索和開發(fā)的并行操作.

3.2.1多策略劃分

將種群中的粒子按比例分為執(zhí)行不同策略行為的兩個(gè)團(tuán)隊(duì)：senior team和junior team.其中senior team執(zhí)行開發(fā)活動(dòng)，而junior team承擔(dān)探索任務(wù).具體策略劃分方案如下：

對(duì)于senior team中的個(gè)體，其主要任務(wù)為快速高效地進(jìn)行局部開發(fā).令senior team中的粒子圍繞著種群最優(yōu)個(gè)體，按照式(7)和式(8)搜索當(dāng)前最優(yōu)區(qū)域中的最優(yōu)解.為了進(jìn)一步提高尋優(yōu)效率，該隊(duì)所有粒子在完成跟隨行為后，將再次以高斯搜索模式進(jìn)行一次隨機(jī)游走，尋找自身當(dāng)前位置附近可能存在的更好值.此時(shí)速度更新公式調(diào)整為式(9)：

vij(t+1)=c3*gaussian

(9)

其中，gaussian為服從均值為0，方差為1的隨機(jī)數(shù)；c3為一常數(shù).

對(duì)于juniorteam中的個(gè)體，其主要任務(wù)為擴(kuò)展粒子視野，增加粒子行為多樣性.設(shè)置juniorteam中的粒子在每一次迭代進(jìn)化中以概率ρ靠近在seniorteam中隨機(jī)選擇的某個(gè)粒子，而以1-ρ的概率執(zhí)行相反操作.因此，juniorteam中粒子的速度更新公式可由式(10)表示：

vid(t+1)=sgn(random4()-(1-ρ))·(w(t)·vij(t)

+c1·random1()·(pbestij-xij(t))

+c2·random2()·(Xsij(t)-xij(t)))

(10)

junior team中的個(gè)體不是追蹤gbest，而是以senior team為跟蹤目標(biāo)，擴(kuò)大了吸引子的范圍，因此個(gè)體視野更為廣闊.同時(shí)，junior team中的個(gè)體在一定概率下也存在反向跟蹤的可能，增強(qiáng)了全局探索行為，預(yù)防過多個(gè)體陷入同一局部區(qū)域.

3.2.2多策略集成

senior team負(fù)責(zé)快速鎖定局部搜索目標(biāo)，而junior team強(qiáng)調(diào)保持種群多樣性，擴(kuò)大搜索區(qū)域.兩個(gè)團(tuán)隊(duì)內(nèi)的粒子執(zhí)行不同的學(xué)習(xí)策略，具有不同的搜索進(jìn)化能力，在種群內(nèi)部構(gòu)建探索與開發(fā)的并行優(yōu)化方案，增加全面尋優(yōu)的可能性.當(dāng)所有粒子完成一輪尋優(yōu)后，為進(jìn)一步提高種群整體搜索性能，將粒子按照適應(yīng)度大小進(jìn)行排序，并將最差的10%個(gè)體進(jìn)行速度高斯調(diào)整(速度更新公式如式(9)所示)，以激活種群該部分粒子的尋優(yōu)能力.

4　基于MSDPSO的MPRM電路最佳延時(shí)和面積極性搜索

在求解MPRM電路延時(shí)和面積優(yōu)化問題時(shí)，MSDPSO中的搜索空間維度D對(duì)應(yīng)于MPRM電路的變量數(shù).粒子位置對(duì)應(yīng)于電路的極性，即電路極性可以表示為xi=(xi0,xi1,…,xiD-1)，xij的取值范圍為xij∈{0,1,2}，因此式(8)中的M=3.MSDPSO中的最優(yōu)粒子位置gbest則表示MPRM電路優(yōu)化搜索中的最佳極性.

4.1粒子更新及域約束

對(duì)于seniorteam中的粒子，按照式(7)、式(8)、式(9)進(jìn)行速度及位置更新；對(duì)于juniorteam中的粒子按照式(8)、式(10)進(jìn)行更新操作.

為了防止粒子由于飛行過快而失去控制，應(yīng)對(duì)其速度進(jìn)行約束，如式(11)所示：

(11)

同時(shí)限制粒子在合理區(qū)間內(nèi)飛行，由于xij∈{0,1,2}，

于是可得位置約束表達(dá)式如下所示：

(12)

4.2適應(yīng)度函數(shù)

MPRM電路的極性優(yōu)劣決定其延時(shí)和面積的大小，某一極性越好，則說明該極性對(duì)應(yīng)電路的延時(shí)與面積越小.因此MSDPSO算法需要對(duì)每個(gè)極性進(jìn)行評(píng)價(jià)，以確定最優(yōu)極性值.結(jié)合延時(shí)與面積的優(yōu)化要求，適應(yīng)度函數(shù)可表示為：

fitness(xi)=α·area(xi)/total-area

+(1-α)·delay(xi)/total-delay

(13)其中，area(xi)和total-area分別為是第i個(gè)粒子對(duì)應(yīng)的MPRM電路面積及所有粒子對(duì)應(yīng)的面積之和.delay(xi)和total-delay分別為是第i個(gè)粒子對(duì)應(yīng)的電路延時(shí)和所有粒子對(duì)應(yīng)的延時(shí)之和.α是優(yōu)化權(quán)重系數(shù)，其取值范圍為[0,1].

4.3最佳極性搜索

綜合以上對(duì)MPRM電路延時(shí)和面積模型的分析，以及對(duì)MSDPSO算法的設(shè)計(jì)，提出針對(duì)MPRM電路延時(shí)和面積最優(yōu)化要求的MSDPSO極性搜索方案如下：

5　實(shí)驗(yàn)與分析

為驗(yàn)證MSDPSO算法在求解MPRM電路的面積和延時(shí)的有效性，將MSDPSO算法與DPSO算法和文獻(xiàn)[10]中的混合粒子群算法(Hybrid Discrete Particle Swarm Optimization，HDPSO)進(jìn)行了性能對(duì)比.三種算法均用c++語言實(shí)現(xiàn)，并在Windows XP操作系統(tǒng)下，通過VC6.0編譯，程序的硬件環(huán)境為Inter Pentium CPU G645(2.9GHz)1.82GB RAM.測(cè)試電路采用PLA格式的MCNC Benchmark電路.

在測(cè)試實(shí)驗(yàn)中，MSDPSO算法的參數(shù)設(shè)置為：優(yōu)化權(quán)重α=0.5，加速因子c1=c2=1.5，粒子總數(shù)Population=40，迭代進(jìn)化次數(shù)iteration=120，c3=0.3.seniorgroup與juniorgroup的粒子數(shù)比例為8∶2，慣性權(quán)重w的最小值wmin=0.4，wmax=0.9，vmax=4，參數(shù)k=0.2，ρ=0.2.DPSO算法與HDPSO算法的參數(shù)設(shè)置與文獻(xiàn)[10]相同.選用15個(gè)中大規(guī)模的Benchmark電路[10]分別進(jìn)行了算法測(cè)試，為減小隨機(jī)數(shù)影響，將所選的電路通過三種算法分別測(cè)試5次，并將5次優(yōu)化結(jié)果之和作為最終測(cè)試結(jié)果.MSDPSO、DPSO、HDPSO算法各自取得最佳極性對(duì)應(yīng)的延時(shí)與面積結(jié)果如表1所示.

表1　MSDPSO與其他算法最佳極性對(duì)應(yīng)的延時(shí)與面積

表2　MSDPSO算法相對(duì)其他算法的優(yōu)化率

表2為MSDPSO算法相對(duì)DPSO算法及HDPSO算法的優(yōu)化率，其中，優(yōu)化率Optr-area、Optr-delay的計(jì)算公式為：

Optr-area=(OA1(OA2)-OA3)/OA3

(14)

Optr-delay=(OD1(OD2)-OD3)/OD3

(15)

其中，OA1、OA2、OA3分別為DPSO、HDPSO、MSDPSO算法搜索到的面積最優(yōu)解；OD1、OD2、OD3分別為DPSO、HDPSO、MSDPSO算法搜索到的延時(shí)最優(yōu)解.

從表1、2的測(cè)試數(shù)據(jù)看出，與DPSO算法及HDPSO算法相比，MSDPSO算法能獲取更小的電路面積和更短的電路延時(shí).如dk48電路，MSDPSO算法相比其他算法的面積優(yōu)化率分別達(dá)到142.86%和117.86%，延時(shí)優(yōu)化率均為42.86%.雖然在table5及sct測(cè)試中，MSDPSO算法比HDPSO算法在延時(shí)方面有所延長(zhǎng)，但同時(shí)在面積方面獲得了更多優(yōu)化.就整體測(cè)試結(jié)果而言，MSDPSO算法相比DPSO算法，平均面積優(yōu)化率為38.36%，平均延時(shí)優(yōu)化率為8.43%；與HDPSO算法相比，MSDPSO算法的平均面積減小了34.70%，平均延時(shí)縮短了5.02%.

為了更好地觀察MSDPSO算法的搜索性能表現(xiàn)，本文將MSDPSO、DPSO和HDPSO三種算法的面積與延時(shí)迭代進(jìn)化過程進(jìn)行比較分析，結(jié)果如圖1、圖2所示.

圖1、圖2顯示，DPSO算法和HDPSO算法在20代左右已經(jīng)陷入局部最優(yōu)解，出現(xiàn)進(jìn)化停滯.而MSDPSO算法由于具有探索與開發(fā)并行能力，因此能夠在整個(gè)迭代過程中都保持不斷進(jìn)化的動(dòng)力，預(yù)防粒子種群發(fā)生早熟情況，具有更好的優(yōu)化性能.

6　結(jié)束語

MPRM電路具有較大的極性搜索空間，有必要尋找一種搜索性能強(qiáng)的智能優(yōu)化算法來實(shí)現(xiàn)電路延時(shí)與面積優(yōu)化設(shè)計(jì).本文通過對(duì)MPRM電路和粒子群算法的研究，提出一種基于多策略離散粒子群算法的MPRM電路延時(shí)與面積優(yōu)化方法.在種群內(nèi)部劃分不同策略的團(tuán)隊(duì)，并行協(xié)作完成全局探索和局部開發(fā)任務(wù)，提高了算法的優(yōu)化能力.對(duì)15個(gè)PLA格式的MCNC Benchmark電路進(jìn)行了測(cè)試，實(shí)驗(yàn)結(jié)果表明與已有文獻(xiàn)相比較，MSDPSO算法具有更好的優(yōu)化效率.

[1]卜登立,江建慧.基于對(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)

[2]周雅蘭,王甲海,黃聰.求解排列問題的分布估計(jì)離散粒子群優(yōu)化算法[J].電子學(xué)報(bào),2014,42(3):561-571.

Zhou Y L,Wang J H,Huang C.Estimation of distribution-discrete particle swarm optimization algorithm for permutation-based problems[J].Acta Electronica Sinica,2014,42(3):561-571.(in Chinese)

[3]Yu S W,Wang K,Wei Y M.A hybrid self-adaptive particle swarm optimization-genetic algorithm-radial basis function model for annual electricity demand prediction[J].Energy Conversion and Management,2015,91:176-185.

[4]鄭巧仙,李明,李元香,等.求解雙邊裝配線平衡問題的改進(jìn)蟻群算法[J].電子學(xué)報(bào),2014,42(5):841-845.

Zheng Q X,Li M,Li Y X,et al.An improved ant colony optimization for two-sided assembly line balancing problem[J].Acta Electronica Sinica,2014,42(5):841-845.(in Chinese)

[5]俞海珍,蔣志迪,汪鵬君,等.GA-DTPSO算法及其在混合極性XNOR/OR電路面積優(yōu)化中應(yīng)用[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào),2015,27(5):946-952.Yu H Z,Jiang Z D,Wang P J,et al.GA-DTPSO algorithm and its application in area optimization of mixed polarity XNOR/OR circuits[J].Journal of Computer-Aided Design and Computer Graphics,2015,27(5):946-952.(in Chinese)

[6]卜登立,江建慧.基于混合多值離散粒子群優(yōu)化的混合極性Reed-Muller最小化算法[J].電子與信息學(xué)報(bào),2013,35(2):361-367.

Bu D L,Jiang J H.Hybrid multi-valued discrete particle swarm optimization algorithm for mixed-polarity reed-muller minimization[J].Journal of Electronics and Information Technology,2013,35(2):361-367.(in Chinese)

[7]李輝，汪鵬君，王振海.混合極性列表技術(shù)及其在MPRM電路面積優(yōu)化中的應(yīng)用[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào),2011,32(3):527-533.

Li H,Wang P J,Wang Z H.Tabular techniques for mixed-polarity and its application in area optimization of MPRM circuits[J].Journal of Computer-Aided Design and Computer Graphics,2011,32(3):527-533.(in Chinese)

[8]Hrynkiewicz E,Kotodziński S.An Ashenhurst disjoint and non-disjoint decomposition of logic functions in Reed-Muller spectral domain[A].Proceedings of Mixed Design of Integrated Circuits and System[C].Warsaw:IEEE,2010.200-204.

[9]王振海，汪鵬君，俞海珍,等.基于PSO算法的FPRM電路延時(shí)和面積優(yōu)化[J].電路與系統(tǒng)學(xué)報(bào).2012,17(5):75-80.

Wang Z H,Wang P J,Yu H Z,et al.Delay and area optimization for FPRM circuits based on PSO algorithm[J].Journal of Circuits and Systems,2012,17(5):75-80.(in Chinese)

[10]Jiang Z D,Wang Z H,Wang P J.Delay-area trade-off MPRM circuits based on hybrid discrete particle swarm optimization[J].Journal of Semiconuctors,2013,34(6):065007.

[11]Du W,Li B.Multi-strategy ensemble particle swarm optimization for dynamic optimization[J].Information Sciences,2008,178(15):3096-3109.

[12]Wang H,Wu Z,Rahnamayan S,et al.Multi-strategy ensemble artificial bee colony algorithm[J].Information Sciences,2014,279:587-603.

符強(qiáng)男,1975年出生,江西贛州人.博士研究生,講師,主要研究方向?yàn)榈凸募呻娐防碚摷皟?yōu)化設(shè)計(jì).

E-mail：fuqiang@nbu.edu.cn

汪鵬君(通信作者)男,1966年出生,浙江奉化人.博士,教授,博士生導(dǎo)師,中國(guó)電子學(xué)會(huì)高級(jí)會(huì)員,中國(guó)計(jì)算機(jī)學(xué)會(huì)高級(jí)會(huì)員,中國(guó)電子學(xué)會(huì)電子線路與系統(tǒng)專業(yè)委員會(huì)委員,中國(guó)計(jì)算機(jī)學(xué)會(huì)多值邏輯與模糊邏輯專業(yè)委員會(huì)委員.主要研究方向?yàn)槎嘀颠壿嫼偷凸募呻娐防碚摷皟?yōu)化設(shè)計(jì).

E-mail：wangpengjun@nbu.edu.cn

Delay and Area Optimization for MPRM Circuits Based on Multi-strategy Discrete Particle Swarm Optimization

FU Qiang1,2,WANG Peng-jun1,TONG Nan2,WANG Ming-bo2,ZHANG Hui-hong1

(1.InstituteofCircuitsandSystems,NingboUniversity,Ningbo，Zhejiang315211，China;2.CollegeofScienceandTechnology,NingboUniversity,Ningbo,Zhejiang315212,China)

In order to improve the delay and area design of large-scale MPRM circuits,the multi-strategy discrete particle swarm optimization(MSDPSO)is proposed.In MSDPSO,the particles were divided into several teams with different strategy,and each team cooperated with others to promote the exploration and exploitation of the particle population.Meanwhile,the Gaussian adjustment was adopted to activate the worse individuals.Combined with MSDPSO and tabular technique,the best polarity of delay and area was searched for large-scale MPRM circuits.MCNC Benchmarks with PLA format are tested to verify the effectiveness of the MSDPSO,and the results show that MSDPSO has achieved an average saving of 8.46% and 38.73% on delay and area respectively in comparison with the DPSO.

multi-strategy discrete particle swarm optimization(MSDPSO)；MPRM circuits；delay and area optimization；polarity search

2015-12-09；

2016-02-04；責(zé)任編輯：馬蘭英

國(guó)家自然科學(xué)基金(No.61306041，No.61234002)；寧波市自然科學(xué)基金(No.2014A610069);浙江省教育廳科研項(xiàng)目(No.Y201326770)

TP391.72

A

0372-2112 (2016)05-1202-06

電子學(xué)報(bào)URL:http://www.ejournal.org.cn10.3969/j.issn.0372-2112.2016.05.027