鬼佬大哥大
  • / 22
  • 下載費用:30 金幣  

一種三值FPRM電路面積與功耗最佳極性搜索方法.pdf

摘要
申請專利號:

CN201510552955.2

申請日:

2015.09.01

公開號:

CN105205534A

公開日:

2015.12.30

當前法律狀態:

授權

有效性:

有權

法律詳情: 授權|||實質審查的生效IPC(主分類):G06N 3/12申請日:20150901|||公開
IPC分類號: G06N3/12; G06F17/30 主分類號: G06N3/12
申請人: 寧波大學
發明人: 汪鵬君; 厲康平; 張會紅
地址: 315211 浙江省寧波市江北區風華路818號
優先權:
專利代理機構: 寧波奧圣專利代理事務所(普通合伙) 33226 代理人: 方小惠
PDF完整版下載: PDF下載
法律狀態
申請(專利)號:

CN201510552955.2

授權公告號:

||||||

法律狀態公告日:

2017.09.29|||2016.01.27|||2015.12.30

法律狀態類型:

授權|||實質審查的生效|||公開

摘要

本發明公開了一種三值FPRM電路面積與功耗最佳極性搜索方法,構建人口遷移遺傳算法,然后建立三值FPRM電路的面積估計模型和功耗估計模型,設定人口遷移算法中用于計算人口所在地點的吸引力的吸引力函數,建立三值FPRM電路和人口遷移遺傳算法的對應關系,接著設定設置人口遷移遺傳算法相關參數,最后采用人口遷移遺傳算法得到吸引力最大地點和最大吸引力,吸引力最大地點即為三值FPRM電路的最佳極性;最大吸引力即為三值FPRM電路的最小面積和功耗之和;優點是可以同時優化三值FPRM電路的面積與功耗性能,提高三值FPRM電路的綜合性能;采用10個測試電路進行仿真驗證,本發明的優化方法相對于整體退火遺傳算法,面積平均節省13.33%,功耗平均節省20.00%,時間平均節省64.96%。

權利要求書

權利要求書
1.  一種三值FPRM電路面積與功耗最佳極性搜索方法,其特征在于包括以下步驟:
①構建人口遷移遺傳算法,人口遷移遺傳算法通過將遺傳算法融合到人口遷移算法中得到:在人口遷移算法中發生人口流動時加入遺傳算法的交叉操作和變異操作,在人口遷移算法中發生人口遷移時加入遺傳算法的交叉操作和變異操作;由此實現遺傳算法和人口遷移算法的融合;
②建立三值FPRM電路的面積估計模型和功耗估計模型:
②-1將三值FPRM電路用三值FPRM邏輯函數的表達式表示為:
fp(xn-1,xn-2,...,x0)=⊕Σi=03n-1ai*Πj=0n-1x·jij---(1)]]>
其中,n為函數fp(xn-1,xn-2,…,x0)的變量數,xn-1,xn-2,…,x0表示函數fp(xn-1,xn-2,…,x0)的n個輸入變量,p表示函數fp(xn-1,xn-2,…,x0)的極性,極性p用三進制形式表示為pn-1pn-2…p0,pj∈{0,1,2},j=0,1,2,…,n-1,⊕表示模3加運算,∑為累加符號,符號“*”表示乘號,下標i=0,1,2,…,3n-1,i用三進制形式表示為in-1in-2…i0,ai為FPRM展開式系數,ai∈{0,1,2};∏表示模3乘運算,的展開式為:其中ij∈{0,1,2},極性p和下標i決定變量的表示形式;
②-2p極性下的三值FPRM邏輯函數包含兩類多輸入運算,兩類多輸入運算分別為多輸入模3加運算和多輸入模3乘運算,根據三值FPRM邏輯函數展開式將三值FPRM邏輯函數分解為多個多輸入模3加運算和多個多輸入模3乘運算,然后將每個多輸入運算分別分解為二輸入運算,得到二輸入模3加運算和二輸入模3乘運算,具體分解過程為:
將多輸入運算的第1個輸入變量和第2個輸入變量作為第一個二輸入運算的兩個輸入變量,得到第一個二輸入運算的輸出變量;將第一個二輸入運算的輸出變量和多輸入運算的第3個輸入變量作為第二個二輸入運算的兩個輸入變量,得到第二個二輸入運算的輸出變量;將第二個二輸入運算的輸出變量和多輸入運算的第4個輸入變量作為第三 個二輸入運算的兩個輸入變量,得到第三個二輸入運算的輸出變量;依此類推,直到所有的多輸入運算的輸入變量作為二輸入運算的輸入變量,完成多輸入運算的分解;
將p極性下的三值FPRM邏輯函數分解后得到多個多輸入模3加運算和多個多輸入模3乘運算,多輸入模3加運算也稱為多輸入模3加門,多輸入模3乘運算也稱為多輸入模3乘門,將p極性下三值FPRM邏輯函數分解后的多輸入模3加門的數量記為N,將p極性下三值FPRM邏輯函數分解后的多輸入模3乘門的數量記為W;將每個多輸入模3加運算分解后得到多個二輸入模3加運算,將每個多輸入模3乘運算分解后得到多個二輸入模3乘運算,二輸入模3加運算也稱為二輸入模3加門,二輸入模3乘運算也稱為二輸入模3乘門;將第u個多輸入模3加門分解后的二輸入模3加門的數量記為Nu,u=1,2,…,N;將第o個多輸入模3乘門分解后的二輸入模3乘門的數量記為Wo,o=1,2,…,W;
②-3將作為三值FPRM電路的面積估計模型,S表示面積;表示p極性下三值FPRM邏輯函數中所有的多輸入模3加門分解后得到的二輸入模3加門的總數量;表示為p極性下三值FPRM邏輯函數中所有的多輸入模3乘門分解后得到的二輸入模3乘門的總數量;
②-4將p極性下的三值FPRM邏輯函數分解后得到的所有二輸入模3加門和二輸入模3乘門引起的功耗作為p極性下的三值FPRM電路的功耗,二輸入模3加門引起的功耗采用其開關活動性表示,二輸入模3乘門引起的功耗采用其開關活動性表示,門電路的開關活動性用其輸出端的輸出變量概率表示,二輸入模3加門引起的功耗采用其輸出端的輸出變量概率表示,二輸入模3乘門引起的功耗采用其輸出端的輸出變量概率表示;
②-5根據公式(2)、(3)和(4)計算第u個多輸入模3加門分解后的第k個二輸入模3加門的輸出變量概率;k=1,2,…,Nu;
P1(k)u=Pky11*Pky20+Pky10*Pky21+Pky12*Pky22(2)
P2(k)u=Pky12*Pky20+Pky11*Pky21*Pky10*Pky22(3)
P0(k)u=1-P1(k)u-P2(k)u(4)
根據公式(5)、(6)和(7)計算第o個多輸入模3乘門分解后的第g個二輸入模3乘門的輸出變量概率,g=1,2,…,Wo:
Q1(g)o=Qgr11*Qgr21+Qgr12*Qgr22(5)
Q2(g)o=Qgr11*Qgr22+Qgr12*Qgr21(6)
Q0(g)o=1-Q1(g)o-Q2(g)o(7)
其中,P1(k)u表示第u個多輸入模3加門分解后的第k個二輸入模3加門輸出變量為1的概率,P2(k)u表示第u個多輸入模3加門分解后的第k個二輸入模3加門輸出變量為2的概率,P0(k)u表示第u個多輸入模3加門分解后的第k個二輸入模3加門輸出變量為0的概率,y1和y2表示二輸入模3加門的兩個輸入變量,Pky1m表示第k個二輸入模3加門中輸入變量y1為m的概率,m∈{0,1,2},Pky2m表示第k個二輸入模3加門中輸入變量y2為m的概率,當k=1時,Pky1m為多輸入模3加運算的第1個輸入變量為m的概率,Pky2m為多輸入模3加運算的第2個輸入變量為m的概率,當k>1時,Pky1m為第k-1個二輸入模3加門輸出變量為m的概率,Pky2m為多輸入模3加門的第k+1個輸入變量為m的概率;
Q1(g)o表示第o個多輸入模3乘門分解后的第g個二輸入模3乘門輸出變量為1的概率,Q2(g)o表示第o個多輸入模3乘門分解后的第g個二輸入模3乘門輸出變量為2的概率,Q0(g)o表示第o個多輸入模3乘門分解后的第g個二輸入模3乘門輸出變量為0的概率,r1和r2表示二輸入模3乘門的兩個輸入變量,Qgr1m表示第g個二輸入模3乘門中輸入變量r1為m的概率,Qgr2m表示第g個二輸入模3乘門中輸入變量r2為m的概率;當g=1時,Qgr1m為多輸入模3乘運算的第1個輸入變量為m的概率,Qgr2m為多輸入模3乘運算的第2個輸入變量為m的概率,當g>1時,Qgr1m為第g-1個二輸入模3乘門輸出變量為m的概率,Qgr2m為多輸入模3乘門的第g+1個輸入變量為m的概率;
輸入變量xj為1和2的概率是由隨即函數產生的概率對(P1,P2),P0=1-P1-P2;P0,P1和P2分別為0到1之間某個值,P0表示輸入變量為0的概率,P1表示輸入變量為1的概率,P2表示輸入變量為2的概率;
②-6根據二輸入模3加門的輸出變量概率和二輸入模3乘門的輸出變量概率計算三值FPRM電路的功耗,將三值FPRM電路的功耗估計模型表示為:
Eswd=2(Σu=1N(Σk=1Nu(P1(k)u+P2(k)u))+Σo=1W(Σg=1Wo(Q1(g)o+Q2(g)o)))---(8)]]>
其中,Eswd表示p極性下三值FPRM電路的功耗,N為p極性下三值FPRM邏輯函數分解后的多輸入模3加門的數量,W為p極性下三值FPRM邏輯函數分解后的多輸入模3乘門的數量;
③設定人口遷移算法中用于計算人口所在地點的吸引力的吸引力函數,吸引力函數用下式表示為:
attraction(t)=α/(β/At+(1-β)/Bt)(9)
其中,符號“/”表示除運算符號,attraction(t)表示第t個人口所在地點的吸引力大小;At表示第t個人口所在地點的環境因素,Bt表示第t個人口所在地點的經濟因素,β為人口所在地點的環境因素和經濟因素的權重,0<β<1;
④建立三值FPRM電路和人口遷移遺傳算法的對應關系:
人口遷移算法包含以下幾個關鍵要素:人口所在地點、人口所在地點的吸引力、吸引力最大地點、最大吸引力、人口可移動地表空間、優惠區域、人口流動、人口遷移、人口擴散、環境因素和經濟因素;
遺傳算法包括兩個關鍵因素:交叉操作和變異操作;
三值FPRM電路面積和功耗綜合優化包含以下幾個關鍵要素:極性、相應極性的面積和功耗之和、最佳極性、最小面積和功耗之和、可選擇的極性空間、最佳極性所在區間、極性變換、極性向最佳極性所在區間跳變、跳出局部最佳極性、極性交流、極性突變、面積和功耗;
將人口所在地點映射到三值FPRM電路面積和功耗綜合優化,表示為極性;將人口所在地點的吸引力映射到三值FPRM電路面積和功耗綜合優化,表示為相應極性的 面積和功耗之和;將吸引力最大地點映射到三值FPRM電路面積和功耗綜合優化,表示為最佳極性;將最大吸引力映射到三值FPRM電路面積和功耗綜合優化,表示為最小面積和功耗之和;將人口可移動地表空間映射到三值FPRM電路面積和功耗綜合優化,表示為可選擇的極性空間;將優惠區域映射到三值FPRM電路面積和功耗綜合優化,表示為最佳極性所在區間;將人口流動域映射到三值FPRM電路面積和功耗綜合優化,表示為極性變換;將人口遷移映射到三值FPRM電路面積和功耗綜合優化,表示為極性向最佳極性所在區間跳變;將人口擴散映射到三值FPRM電路面積和功耗綜合優化,表示為跳出局部最佳極性;將交叉操作映射到三值FPRM電路面積和功耗綜合優化,表示為極性交流;將變異操作映射到三值FPRM電路面積和功耗綜合優化,表示為極性突變;將環境因素映射到三值FPRM電路面積和功耗綜合優化,表示為三值FPRM電路的面積S;將經濟因素映射到三值FPRM電路面積和功耗綜合優化,表示為三值FPRM電路的功耗;
⑤設置人口遷移遺傳算法相關參數:
人口遷移遺傳算法需設置5個參數:人口規模s、人口流動次數l、人口壓力參數q、收縮系數c和人口擴散次數z;令人口規模s等于三值FPRM邏輯函數的輸入變量個數,即s=n;人口流動次數l為人口所在區域的半徑,人口所在區域的半徑記為Δt,l=Δt,Δt=3s/s2;人口壓力參數q為Δt/10;收縮系數c=0.3;三值FPRM電路為小規模電路時,人口擴散次數z=15,三值FPRM電路為大規模電路時,人口擴散次數z=2;
⑥采用人口遷移遺傳算法得到吸引力最大地點和最大吸引力,吸引力最大地點即為三值FPRM電路的面積和功耗最佳極性;最大吸引力即為三值FPRM電路的最小面積和功耗之和。

2.  根據權利要求1所述的一種三值FPRM電路面積與功耗最佳極性搜索方法,其特征在于所述的步驟⑥中采用人口遷移遺傳算法得到吸引力最大地點和最大吸引力的具體過程為:
⑥-1在人口可移動地表空間內用隨機函數rand()產生s個人口所在地點,將s個人口所在地點分別記為P1,P2,…,Ps,分別以P1,P2,…,Ps為中點,按人口所在區域的半徑確定s個人口所在區域;
⑥-2通過吸引力函數計算第v個人口所在地點Pv的吸引力,v=1,2,3,…,s,得到人口所在地點P1,P2,…,Ps的吸引力;
⑥-3比較人口所在地點P1,P2,…,Ps的吸引力,篩選出吸引力最大的人口所在地點作為吸引力最大地點,記錄吸引力最大地點和最大吸引力;
⑥-4進行人口流動:在人口所在地點Pv所對應的人口所在區域內采用隨機函數隨機產生一個人口所在地點P′v,得到P′1,P′2,…,P′s,采用P′1,P′2,…,P′s更新人口所在地點P1,P2,…,Ps,即P1=P′1,P2=P′2,…,Ps=P′s,其中,P′v=2*Δt*rand()+(Pv-Δt),符號“*”為乘運算符號,Δt表示人口所在區域的半徑;rand()為隨機函數;
⑥-5按照步驟⑥-2~⑥-3對人口所在地點P1,P2,…,Ps進行處理,得到吸引力最大地點和最大吸引力;
⑥-6進行交叉操作:若s為偶數,將P1和P2、P3和P4、…、Ps-1和Ps兩兩分別進行交叉操作;若s為奇數,將P1和P2、P3和P4、…、Ps-2和Ps-1兩兩分別進行交叉操作,Ps不參與交叉操作;兩個人口所在地點交叉操作的具體過程為:將進行交叉操作的兩個人口所在地點分別轉換為n位三進制碼,轉換后的兩個n位三進制碼分別記為f1和f2,隨機產生一個n位的二進制碼,將該n位的二進制碼記為A,根據二進制碼A更新f1和f2,當二進制碼A的第h位為1時,f1的第h位保持不變,f2的第h位保持不變;當二進制碼A的第h位為0時,f1的第h位繼承f2的第h位,f2的第h位繼承f1的第h位,h=1,2,3,…,n,得到更新后的f1和f2,將更新后的f1和f2轉換為十進制數據得到f′1和f′2,采用f′1和f′2更新進行交叉操作的兩個人口所在地點;
⑥-7按照步驟⑥-2~⑥-3對人口所在地點P1,P2,…,Ps進行處理,得到吸引力最大地點和最大吸引力;
⑥-8進行變異操作:將P1,P2,…,Ps轉化為n位三進制碼,得到F1,F2,…,Fs;對Fv的每一位均用隨機函數rand()產生一個0到1之間的值,若這個值小于0.01,則這個值對應的位就是Fv的變異位,對Fv的變異位進行變異,變異規則為“0→1, 1→2,2→0”;F1,F2,…,Fs變異操作后得到F1′,F2′,…,Fs′,v=1,2,3,…,s;將F1′,F2′,…,Fs′轉換為十進制數據后更新人口所在地點P1,P2,…,Ps;
⑥-9按照步驟⑥-2~⑥-3對人口所在地點P1,P2,…,Ps進行處理,得到更新后的吸引力最大地點和最大吸引力;
⑥-10進行人口遷移:以步驟⑥-9中的吸引力最大地點為中點,按人口所在區域半徑Δt的大小確定優惠區域,在優惠區域內用隨機函數rand()產生s個人口所在地點,將此時得到的s個人口所在地點對人口所在地點P1,P2,…,Ps再次進行更新;
⑥-11按照步驟⑥-2~⑥-3對人口所在地點P1,P2,…,Ps進行處理,得到吸引力最大地點和最大吸引力;
⑥-12重復步驟⑥-6~⑥-9;
⑥-13收縮優惠區域:令Δt′=(1-c)*Δt,采用Δt′更新Δt;重復步驟⑥-10~⑥-12,直到Δt<q;
⑥-14當收縮優惠區域到一定程度Δt<q后,進行人口擴散:重復步驟⑥-1-⑥-13,直到滿足人口擴散次數z,算法結束,得到吸引力最大地點和最大吸引力;
⑥-15將最后一次得到的吸引力最大地點和最大吸引力輸出,吸引力最大地點即為三值FPRM電路的面積和功耗最佳極性;最大吸引力即為三值FPRM電路的最小面積和功耗之和。

說明書

說明書一種三值FPRM電路面積與功耗最佳極性搜索方法
技術領域
本發明涉及一種三值FPRM電路最佳極性搜索方法,尤其是涉及一種三值FPRM電路面積與功耗最佳極性搜索方法。
背景技術
多值邏輯電路單線攜帶信息能力強,能有效提高空間或時間的利用率,減少數字系統的連線,節省電路面積與成本。任意三值邏輯函數均可以用布爾邏輯和Reed-Muller(RM)邏輯來表示。與傳統的布爾邏輯電路相比,基于RM邏輯的電路具有以下三個方面的優勢:首先,在某些功能電路(算通信電路、奇偶校驗電路、運算電路等)中,用RM邏輯表示的電路在功耗、面積和速度等方面體現出了巨大的優勢;其次,用RM邏輯表示的電路可測性強;最后,用RM邏輯表示的電路結構更加緊湊。固定極性(Fixed-polarityReed-Muller,FPRM)是RM邏輯常用表達方式。在三值FPRM邏輯函數中,n變量函數有3n個固定極性,對應3n個不同的三值FPRM表達式,其表達式的簡單與復雜程度由極性決定。由此可知,極性對三值FPRM電路的功耗、面積等性能產生很大的影響。
三值FPRM電路的功耗和面積屬于兩個獨立的性能指標,其功耗較小時面積不一定較小,面積較小時功耗也不一定較小。目前,三值FPRM電路的面積優化方法主要是通過找到最佳極性來實現面積優化。對較小規模的三值FPRM電路進行面積優化時,通常使用窮舉法遍歷表示該三值FPRM電路的RM邏輯函數的每個極性來搜索最佳極性;對較大規模三值FPRM電路的面積進行優化時,由于極性與變量存在指數關系使得搜索空間急劇增加,窮舉法很難在有限的時間內得到優化結果,目前最新的研究是采用整體退火遺傳算法在大規模三值FPRM電路面積優化時進行最佳極性搜索,從而得到最小面積,然而其極性搜索結果存在改進空間,難以找到最佳極性。而在FPRM電路的功耗優化方面,國內外專家學者的研究仍停留二值電路領域,對三值FPRM電路耗優化技術未進行研究。
人口遷移算法(PopulationMigrationAlgorithm,PMA)是以人口遷移規律為依據的一種新的全局優化搜索算法,主要模擬人口跟隨經濟中心轉移以及人口由于壓力增大而擴散的機制。人口遷移算法是一種全局優化的仿生算法,將目標函數的選擇空間模擬成人類的生存空間,將目標函數值模擬成某個地域的吸引力,利用人口流動、遷移和擴散行為搜索可行解,通過個體的流動、遷移和擴散行為找到局部最優解,最后比較多個局部最優解得到全局最優解。
遺傳算法通過選擇、交叉和變異三個操作模擬種群進化過程。首先,隨機產生初代種群,根據適應度函數計算每個個體的適應度值,按適應度值的大小評價個體的好壞。其次,通過選擇操作挑選出適應能力較強的個體。最后,通過對挑選出的個體進行交叉和變異操作,產生子代,形成新的種群。選擇操作能淘汰掉種群中適應能力較差的個體,選出優秀的個體。交叉操作隨機選擇兩個個體,將父代個體的部分結構進行替換,產生新的個體。選擇和交叉操作能保留種群中優秀的個體,避免了優秀個體的丟失。變異操作模擬基因突變現象,以極小的概率改變個體的某些基因,增加種群多樣性,能使算法避免陷入局部最優解。
鑒此,結合人口遷移算法和遺傳算法,設計一種三值FPRM電路面積與功耗最佳極性搜索方法具有重要意義。
發明內容
本發明所要解決的技術問題是提供一種三值FPRM電路面積與功耗最佳極性搜索方法。該方法可以找到面積與功耗最佳極性,同時優化三值FPRM電路的面積與功耗性能,提高三值FPRM電路的綜合性能。
本發明解決上述技術問題所采用的技術方案為:一種三值FPRM電路面積與功耗最佳極性搜索方法,包括以下步驟:
①構建人口遷移遺傳算法,人口遷移遺傳算法通過將遺傳算法融合到人口遷移算法中得到:在人口遷移算法中發生人口流動時加入遺傳算法的交叉操作和變異操作,在人口遷移算法中發生人口遷移時加入遺傳算法的交叉操作和變異操作;由此實現遺傳算法和人口遷移算法的融合;
②建立三值FPRM電路的面積估計模型和功耗估計模型:
②-1將三值FPRM電路用三值FPRM邏輯函數的表達式表示為:
fp(xn-1,xn-2,...,x0)=&CirclePlus;Σi=03n-1ai*Πj=0n-1x&CenterDot;jij---(1)]]>
其中,n為函數fp(xn-1,xn-2,…,x0)的變量數,xn-1,xn-2,…,x0表示函數fp(xn-1,xn-2,…,x0)的n個輸入變量,p表示函數fp(xn-1,xn-2,…,x0)的極性,極性p用三進制形式表示為pn-1pn-2…p0,pj∈{0,1,2},j=0,1,2,…,n-1,表示模3加運算,∑為累加符號,符號“*”表示乘號,下標i=0,1,2,…,3n-1,i用三進制形式表示為in-1in-2…i0,ai為FPRM展開式系數,ai∈{0,1,2};∏表示模3乘運算,的展開式為:其中ij&Element;{0,1,2},x&CenterDot;j=(xj&CirclePlus;pj),x&CenterDot;j0=1,x&CenterDot;j1=x&CenterDot;j,x&CenterDot;j2=x&CenterDot;j*x&CenterDot;j,]]>極性p和下標i決定變量的表示形式;
②-2p極性下的三值FPRM邏輯函數包含兩類多輸入運算,兩類多輸入運算分別為多輸入模3加運算和多輸入模3乘運算,根據三值FPRM邏輯函數展開式將三值FPRM邏輯函數分解為多個多輸入模3加運算和多個多輸入模3乘運算,然后將每個多輸入運算分別分解為二輸入運算,得到二輸入模3加運算和二輸入模3乘運算,具體分解過程為:
將多輸入運算的第1個輸入變量和第2個輸入變量作為第一個二輸入運算的兩個輸入變量,得到第一個二輸入運算的輸出變量;將第一個二輸入運算的輸出變量和多輸入運算的第3個輸入變量作為第二個二輸入運算的兩個輸入變量,得到第二個二輸入運算的輸出變量;將第二個二輸入運算的輸出變量和多輸入運算的第4個輸入變量作為第三個二輸入運算的兩個輸入變量,得到第三個二輸入運算的輸出變量;依此類推,直到所有的多輸入運算的輸入變量作為二輸入運算的輸入變量,完成多輸入運算的分解;
將p極性下的三值FPRM邏輯函數分解后得到多個多輸入模3加運算和多個多輸入模3乘運算,多輸入模3加運算也稱為多輸入模3加門,多輸入模3乘運算也稱為多輸入模3乘門,將p極性下三值FPRM邏輯函數分解后的多輸入模3加門的數量記為N,將p極性下三值FPRM邏輯函數分解后的多輸入模3乘門的數量記為W;將每個多輸入模3加運算分解后得到多個二輸入模3加運算,將每個多輸入模3乘運算分解后得到多個二輸入模3乘運算,二輸入模3加運算也稱為二輸入模3加門,二輸入模3乘運算也稱為二輸入模3乘門;將第u個多輸入模3加門分解后的二輸入模3加門的數量記為Nu,u=1,2,…,N;將第o個多輸入模3乘門分解后的二輸入模3乘門的數量記為Wo,o=1,2,…,W;
②-3將作為三值FPRM電路的面積估計模型,S表示面積;表示p極性下三值FPRM邏輯函數中所有的多輸入模3加門分解后得到的二輸入模3加門的總數量;表示為p極性下三值FPRM邏輯函數中所有的多輸入模3乘門分解后得到的二輸入模3乘門的總數量;
②-4將p極性下的三值FPRM邏輯函數分解后得到的所有二輸入模3加門和二輸入模3乘門引起的功耗作為p極性下的三值FPRM電路的功耗,二輸入模3加門引起的功耗采用其開關活動性表示,二輸入模3乘門引起的功耗采用其開關活動性表示,門電路的開關活動性用其輸出端的輸出變量概率表示,二輸入模3加門引起的功耗采用其輸出端的輸出變量概率表示,二輸入模3乘門引起的功耗采用其輸出端的輸出變量概率表示;
②-5根據公式(2)、(3)和(4)計算第u個多輸入模3加門分解后的第k個二輸入模3加門的輸出變量概率;k=1,2,…,Nu;
P1(k)u=Pky11*Pky20+Pky10*Pky21+Pky12*Pky22(2)
P2(k)u=Pky12*Pky20+Pky11*Pky21+Pky10*Pky22(3)
P0(k)u=1-P1(k)u-P2(k)u(4)
根據公式(5)、(6)和(7)計算第o個多輸入模3乘門分解后的第g個二輸入模3乘門的輸出變量概率,g=1,2,…,Wo:
Q1(g)o=Qgr11*Qgr21+Qgr12*Qgr22(5)
Q2(g)o=Qgr11*Qgr22+Qgr12*Qgr21(6)
Q0(g)o=1-Q1(g)o-Q2(g)o(7)
其中,P1(k)u表示第u個多輸入模3加門分解后的第k個二輸入模3加門輸出變量為1的概率,P2(k)u表示第u個多輸入模3加門分解后的第k個二輸入模3加門輸出變量為2的概率,P0(k)u表示第u個多輸入模3加門分解后的第k個二輸入模3加門輸出變量為0的概率,y1和y2表示二輸入模3加門的兩個輸入變量,Pky1m表示第k個二輸入模3加門中輸入變量y1為m的概率,m∈{0,1,2},Pky2m表示第k個二輸入模3加門中輸入變量y2為m的概率,當k=1時,Pky1m為多輸入模3加運算的第1個輸入變量為m的概率,Pky2m為多輸入模3加運算的第2個輸入變量為m的概率,當k>1時,Pky1m為第k-1個二輸入模3加門輸出變量為m的概率,Pky2m為多輸入模3加門的第k+1個輸入變量為m的概率;
Q1(g)o表示第o個多輸入模3乘門分解后的第g個二輸入模3乘門輸出變量為1的概率,Q2(g)o表示第o個多輸入模3乘門分解后的第g個二輸入模3乘門輸出變量為2的概率,Q0(g)o表示第o個多輸入模3乘門分解后的第g個二輸入模3乘門輸出變量為0的概率,r1和r2表示二輸入模3乘門的兩個輸入變量,Qgr1m表示第g個二輸入模3乘門中輸入變量r1為m的概率,Qgr2m表示第g個二輸入模3乘門中輸入變量r2為m的概率;當g=1時,Qgr1m為多輸入模3乘運算的第1個輸入變量為m的概率,Qgr2m為多輸入模3乘運算的第2個輸入變量為m的概率,當g>1時,Qgr1m為第g-1個二輸入模3乘門輸出變量為m的概率,Qgr2m為多輸入模3乘門的第g+1個輸入變量為m的概率;
輸入變量xj為1和2的概率是由隨即函數產生的概率對(P1,P2),P0=1-P1-P2;P0,P1和P2分別為0到1之間某個值,P0表示輸入變量為0的概率,P1表示輸入變量為1的概率,P2表示輸入變量為2的概率;
②-6根據二輸入模3加門的輸出變量概率和二輸入模3乘門的輸出變量概率計算三值FPRM電路的功耗,將三值FPRM電路的功耗估計模型表示為:
Eswd=2(Σu=1N(Σk=1Nu(P1(k)u+P2(k)u))+Σo=1W(Σg=1Wo(Q1(g)o+Q2(g)o)))---(8)]]>
其中,Eswd表示p極性下三值FPRM電路的功耗,N為p極性下三值FPRM邏輯函數分解后的多輸入模3加門的數量,W為p極性下三值FPRM邏輯函數分解后的多輸入模3乘門的數量;
③設定人口遷移算法中用于計算人口所在地點的吸引力的吸引力函數,吸引力函數用下式表示為:
attraction(t)=α/(β/At+(1-β)/Bt)(9)
其中,符號“/”表示除運算符號,attraction(t)表示第t個人口所在地點的吸引力大小;At表示第t個人口所在地點的環境因素,Bt表示第t個人口所在地點的經濟因素,β為人口所在地點的環境因素和經濟因素的權重,0<β<1;
④建立三值FPRM電路和人口遷移遺傳算法的對應關系:
人口遷移算法包含以下幾個關鍵要素:人口所在地點、人口所在地點的吸引力、吸引力最大地點、最大吸引力、人口可移動地表空間、優惠區域、人口流動、人口遷移、人口擴散、環境因素和經濟因素;
遺傳算法包括兩個關鍵因素:交叉操作和變異操作;
三值FPRM電路面積和功耗綜合優化包含以下幾個關鍵要素:極性、相應極性的面積和功耗之和、最佳極性、最小面積和功耗之和、可選擇的極性空間、最佳極性所在區間、極性變換、極性向最佳極性所在區間跳變、跳出局部最佳極性、極性交流、極性突變、面積和功耗;
將人口所在地點映射到三值FPRM電路面積和功耗綜合優化,表示為極性;將人口所在地點的吸引力映射到三值FPRM電路面積和功耗綜合優化,表示為相應極性的面積和功耗之和;將吸引力最大地點映射到三值FPRM電路面積和功耗綜合優化,表示為最佳極性;將最大吸引力映射到三值FPRM電路面積和功耗綜合優化,表示為最小面積和功耗之和;將人口可移動地表空間映射到三值FPRM電路面積和功耗綜合優化,表示為可選擇的極性空間;將優惠區域映射到三值FPRM電路面積和功耗綜合優化,表示為最佳極性所在區間;將人口流動域映射到三值FPRM電路面積和功耗綜合優化,表示為極性變換;將人口遷移映射到三值FPRM電路面積和功耗綜合優化,表示為極性向最佳極性所在區間跳變;將人口擴散映射到三值FPRM電路面積和功耗綜合優化,表示為跳出局部最佳極性;將交叉操作映射到三值FPRM電路面積和功耗綜合優化,表示為極性交流;將變異操作映射到三值FPRM電路面積和功耗綜合優化,表示為極性突變;將環境因素映射到三值FPRM電路面積和功耗綜合優化,表示為三值FPRM電路的面積S;將經濟因素映射到三值FPRM電路面積和功耗綜合優化,表示為三值FPRM電路的功耗;
⑤設置人口遷移遺傳算法相關參數:
人口遷移遺傳算法需設置5個參數:人口規模s、人口流動次數l、人口壓力參數q、收縮系數c和人口擴散次數z;令人口規模s等于三值FPRM邏輯函數的輸入變量個數,即s=n;人口流動次數l為人口所在區域的半徑,人口所在區域的半徑記為Δt,l=Δt,Δt=3s/s2;人口壓力參數q為Δt/10;收縮系數c=0.3;三值FPRM電路為小規模電路時,人口擴散次數z=15,三值FPRM電路為大規模電路時,人口擴散次數z=2;
⑥采用人口遷移遺傳算法得到吸引力最大地點和最大吸引力,吸引力最大地點即為三值FPRM電路的面積和功耗最佳極性;最大吸引力即為三值FPRM電路的最小面積和功耗之和。
所述的步驟⑥中采用人口遷移遺傳算法得到吸引力最大地點和最大吸引力的具體過程為:
⑥-1在人口可移動地表空間內用隨機函數rand()產生s個人口所在地點,將s個人口所在地點分別記為P1,P2,…,Ps,分別以P1,P2,…,Ps為中點,按人口所在區域的半徑確定s個人口所在區域;
⑥-2通過吸引力函數計算第v個人口所在地點Pv的吸引力,v=1,2,3,…,s,得到人口所在地點P1,P2,…,Ps的吸引力;
⑥-3比較人口所在地點P1,P2,…,Ps的吸引力,篩選出吸引力最大的人口所在地點作為吸引力最大地點,記錄吸引力最大地點和最大吸引力;
⑥-4進行人口流動:在人口所在地點Pv所對應的人口所在區域內采用隨機函數隨機產生一個人口所在地點P'v,得到P'1,P'2,…,P's,采用P'1,P'2,…,P's更新人口所在地點P1,P2,…,Ps,即P1=P'1,P2=P'2,…,Ps=P's,其中,P'v=2*Δt*rand()+(Pv-Δt),符號“*”為乘運算符號,Δt表示人口所在區域的半徑;rand()為隨機函數;
⑥-5按照步驟⑥-2~⑥-3對人口所在地點P1,P2,…,Ps進行處理,得到吸引力最大地點和最大吸引力;
⑥-6進行交叉操作:若s為偶數,將P1和P2、P3和P4、…、Ps-1和Ps兩兩分別進行交叉操作;若s為奇數,將P1和P2、P3和P4、…、Ps-2和Ps-1兩兩分別進行交叉操作,Ps不參與交叉操作;兩個人口所在地點交叉操作的具體過程為:將進行交叉操作的兩個人口所在地點分別轉換為n位三進制碼,轉換后的兩個n位三進制碼分別記為f1和f2,隨機產生一個n位的二進制碼,將該n位的二進制碼記為A,根據二進制碼A更新f1和f2,當二進制碼A的第h位為1時,f1的第h位保持不變,f2的第h位保持不變;當二進制碼A的第h位為0時,f1的第h位繼承f2的第h位,f2的第h位繼承f1的第h位,h=1,2,3,…,n,得到更新后的f1和f2,將更新后的f1和f2轉換為十進制數據得到f1'和f2',采用f1'和f2'更新進行交叉操作的兩個人口所在地點;
⑥-7按照步驟⑥-2~⑥-3對人口所在地點P1,P2,…,Ps進行處理,得到吸引力最大地點和最大吸引力;
⑥-8進行變異操作:將P1,P2,…,Ps轉化為n位三進制碼,得到F1,F2,…,Fs;對Fv的每一位均用隨機函數rand()產生一個0到1之間的值,若這個值小于0.01,則這個值對應的位就是Fv的變異位,對Fv的變異位進行變異,變異規則為“0→1,1→2,2→0”;F1,F2,…,Fs變異操作后得到F1',F2',…,Fs',v=1,2,3,…,s;將F1',F2',…,Fs'轉換為十進制數據后更新人口所在地點P1,P2,…,Ps;
⑥-9按照步驟⑥-2~⑥-3對人口所在地點P1,P2,…,Ps進行處理,得到更新后的吸引力最大地點和最大吸引力;
⑥-10進行人口遷移:以步驟⑥-9中的吸引力最大地點為中點,按人口所在區域半徑Δt的大小確定優惠區域,在優惠區域內用隨機函數rand()產生s個人口所在地點,將此時得到的s個人口所在地點對人口所在地點P1,P2,…,Ps再次進行更新;
⑥-11按照步驟⑥-2~⑥-3對人口所在地點P1,P2,…,Ps進行處理,得到吸引力最大地點和最大吸引力;
⑥-12重復步驟⑥-6~⑥-9;
⑥-13收縮優惠區域:令Δt'=(1-c)*Δt,采用Δt'更新Δt;重復步驟⑥-10~⑥-12,直到Δt<q;
⑥-14當收縮優惠區域到一定程度Δt<q后,進行人口擴散:重復步驟⑥-1-⑥-13,直到滿足人口擴散次數z,算法結束,得到吸引力最大地點和最大吸引力;
⑥-15將最后一次得到的吸引力最大地點和最大吸引力輸出,吸引力最大地點即為三值FPRM電路的面積和功耗最佳極性;最大吸引力即為三值FPRM電路的最小面積和功耗之和。
與現有技術相比,本發明的優點在于首先通過將遺傳算法融合到人口遷移算法中得到人口遷移遺傳算法,然后建立三值FPRM電路的面積估計模型和功耗估計模型,設定人口遷移算法中用于計算人口所在地點的吸引力的吸引力函數,建立三值FPRM電路和人口遷移遺傳算法的對應關系,接著設定設置人口遷移遺傳算法相關參數,最后采用人口遷移遺傳算法得到吸引力最大地點和最大吸引力,吸引力最大地點即為三值FPRM電路的最佳極性;最大吸引力即為三值FPRM電路的最小面積和功耗之和;本發明的方法可以快速搜索到面積和功耗最佳極性,同時優化三值FPRM電路的面積與功耗性能,提高三值FPRM電路的綜合性能;采用10個測試電路對本發明的方法和整體退火遺傳算法分別進行仿真驗證,本發明的優化方法相對于整體退火遺傳算法,面積平均節省13.33%,功耗平均節省20.00%,時間平均節省64.96%。
具體實施方式
以下結合實施例對本發明作進一步詳細描述。
實施例一:一種三值FPRM電路面積與功耗最佳極性搜索方法,包括以下步驟:
①構建人口遷移遺傳算法,人口遷移遺傳算法通過將遺傳算法融合到人口遷移算法中得到:在人口遷移算法中發生人口流動時加入遺傳算法的交叉操作和變異操作,在人口遷移算法中發生人口遷移時加入遺傳算法的交叉操作和變異操作;由此實現遺傳算法和人口遷移算法的融合;
②建立三值FPRM電路的面積估計模型和功耗估計模型:
②-1將三值FPRM電路用三值FPRM邏輯函數的表達式表示為:
fp(xn-1,xn-2,...,x0)=&CirclePlus;Σi=03n-1ai*Πj=0n-1x&CenterDot;jij---(1)]]>
其中,n為函數fp(xn-1,xn-2,…,x0)的變量數,xn-1,xn-2,…,x0表示函數fp(xn-1,xn-2,…,x0)的n個輸入變量,p表示函數fp(xn-1,xn-2,…,x0)的極性,極性p用三進制形式表示為pn-1pn-2…p0,pj∈{0,1,2},j=0,1,2,…,n-1,表示模3加運算,∑為累加符號,符號“*”表示乘號,下標i=0,1,2,…,3n-1,i用三進制形式表示為in-1in-2…i0,ai為FPRM展開式系數,ai∈{0,1,2};∏表示模3乘運算,的展開式為:其中ij&Element;{0,1,2},x&CenterDot;j=(xj&CirclePlus;pj),x&CenterDot;j0=1,x&CenterDot;j1=x&CenterDot;j,x&CenterDot;j2=x&CenterDot;j*x&CenterDot;j,]]>極性p和下標i決定變量的表示形式;
②-2p極性下的三值FPRM邏輯函數包含兩類多輸入運算,兩類多輸入運算分別為多輸入模3加運算和多輸入模3乘運算,根據三值FPRM邏輯函數展開式將三值FPRM邏輯函數分解為多個多輸入模3加運算和多個多輸入模3乘運算,然后將每個多輸入運算分別分解為二輸入運算,得到二輸入模3加運算和二輸入模3乘運算,具體分解過程為:
將多輸入運算的第1個輸入變量和第2個輸入變量作為第一個二輸入運算的兩個輸入變量,得到第一個二輸入運算的輸出變量;將第一個二輸入運算的輸出變量和多輸入運算的第3個輸入變量作為第二個二輸入運算的兩個輸入變量,得到第二個二輸入運算的輸出變量;將第二個二輸入運算的輸出變量和多輸入運算的第4個輸入變量作為第三個二輸入運算的兩個輸入變量,得到第三個二輸入運算的輸出變量;依此類推,直到所有的多輸入運算的輸入變量作為二輸入運算的輸入變量,完成多輸入運算的分解;
將p極性下的三值FPRM邏輯函數分解后得到多個多輸入模3加運算和多個多輸入模3乘運算,多輸入模3加運算也稱為多輸入模3加門,多輸入模3乘運算也稱為多輸入模3乘門,將p極性下三值FPRM邏輯函數分解后的多輸入模3加門的數量記為N,將p極性下三值FPRM邏輯函數分解后的多輸入模3乘門的數量記為W;將每個多輸入模3加運算分解后得到多個二輸入模3加運算,將每個多輸入模3乘運算分解后得到多個二輸入模3乘運算,二輸入模3加運算也稱為二輸入模3加門,二輸入模3乘運算也稱為二輸入模3乘門;將第u個多輸入模3加門分解后的二輸入模3加門的數量記為Nu,u=1,2,…,N;將第o個多輸入模3乘門分解后的二輸入模3乘門的數量記為Wo,o=1,2,…,W;
②-3將作為三值FPRM電路的面積估計模型,S表示面積;表示p極性下三值FPRM邏輯函數中所有的多輸入模3加門分解后得到的二輸入模3加門的總數量;表示為p極性下三值FPRM邏輯函數中所有的多輸入模3乘門分解后得到的二輸入模3乘門的總數量;
②-4將p極性下的三值FPRM邏輯函數分解后得到的所有二輸入模3加門和二輸入模3乘門引起的功耗作為p極性下的三值FPRM電路的功耗,二輸入模3加門引起的功耗采用其開關活動性表示,二輸入模3乘門引起的功耗采用其開關活動性表示,門電路的開關活動性用其輸出端的輸出變量概率表示,二輸入模3加門引起的功耗采用其輸出端的輸出變量概率表示,二輸入模3乘門引起的功耗采用其輸出端的輸出變量概率表示;
②-5根據公式(2)、(3)和(4)計算第u個多輸入模3加門分解后的第k個二輸入模3加門的輸出變量概率;k=1,2,…,Nu;
P1(k)u=Pky11*Pky20+Pky10*Pky21+Pky12*Pky22(2)
P2(k)u=Pky12*Pky20+Pky11*Pky21+Pky10*Pky22(3)
P0(k)u=1-P1(k)u-P2(k)u(4)
根據公式(5)、(6)和(7)計算第o個多輸入模3乘門分解后的第g個二輸入模3乘門的輸出變量概率,g=1,2,…,Wo:
Q1(g)o=Qgr11*Qgr21+Qgr12*Qgr22(5)
Q2(g)o=Qgr11*Qgr22+Qgr12*Qgr21(6)
Q0(g)o=1-Q1(g)o-Q2(g)o(7)
其中,P1(k)u表示第u個多輸入模3加門分解后的第k個二輸入模3加門輸出變量為1的概率,P2(k)u表示第u個多輸入模3加門分解后的第k個二輸入模3加門輸出變量為2的概率,P0(k)u表示第u個多輸入模3加門分解后的第k個二輸入模3加門輸出變量為0的概率,y1和y2表示二輸入模3加門的兩個輸入變量,Pky1m表示第k個二輸入模3加門中輸入變量y1為m的概率,m∈{0,1,2},Pky2m表示第k個二輸入模3加門中輸入變量y2為m的概率,當k=1時,Pky1m為多輸入模3加運算的第1個輸入變量為m的概率,Pky2m為多輸入模3加運算的第2個輸入變量為m的概率,當k>1時,Pky1m為第k-1個二輸入模3加門輸出變量為m的概率,Pky2m為多輸入模3加門的第k+1個輸入變量為m的概率;
Q1(g)o表示第o個多輸入模3乘門分解后的第g個二輸入模3乘門輸出變量為1的概率,Q2(g)o表示第o個多輸入模3乘門分解后的第g個二輸入模3乘門輸出變量為2的概率,Q0(g)o表示第o個多輸入模3乘門分解后的第g個二輸入模3乘門輸出變量為0的概率,r1和r2表示二輸入模3乘門的兩個輸入變量,Qgr1m表示第g個二輸入模3乘門中輸入變量r1為m的概率,Qgr2m表示第g個二輸入模3乘門中輸入變量r2為m的概率;當g=1時,Qgr1m為多輸入模3乘運算的第1個輸入變量為m的概率,Qgr2m為多輸入模3乘運算的第2個輸入變量為m的概率,當g>1時,Qgr1m為第g-1個二輸入模3乘門輸出變量為m的概率,Qgr2m為多輸入模3乘門的第g+1個輸入變量為m的概率;
輸入變量xj為1和2的概率是由隨即函數產生的概率對(P1,P2),P0=1-P1-P2;P0,P1和P2分別為0到1之間某個值,P0表示輸入變量為0的概率,P1表示輸入變量為1的概率,P2表示輸入變量為2的概率;
②-6根據二輸入模3加門的輸出變量概率和二輸入模3乘門的輸出變量概率計算三值FPRM電路的功耗,將三值FPRM電路的功耗估計模型表示為:
Eswd=2(Σu=1N(Σk=1Nu(P1(k)u+P2(k)u))+Σo=1W(Σg=1Wo(Q1(g)o+Q2(g)o)))---(8)]]>
其中,Eswd表示p極性下三值FPRM電路的功耗,N為p極性下三值FPRM邏輯函數分解后的多輸入模3加門的數量,W為p極性下三值FPRM邏輯函數分解后的多輸入模3乘門的數量;
③設定人口遷移算法中用于計算人口所在地點的吸引力的吸引力函數,吸引力函數用下式表示為:
attraction(t)=α/(β/At+(1-β)/Bt)(9)
其中,符號“/”表示除運算符號,attraction(t)表示第t個人口所在地點的吸引力大小;At表示第t個人口所在地點的環境因素,Bt表示第t個人口所在地點的經濟因素,β為人口所在地點的環境因素和經濟因素的權重,0<β<1;
④建立三值FPRM電路和人口遷移遺傳算法的對應關系:
人口遷移算法包含以下幾個關鍵要素:人口所在地點、人口所在地點的吸引力、吸引力最大地點、最大吸引力、人口可移動地表空間、優惠區域、人口流動、人口遷移、人口擴散、環境因素和經濟因素;
遺傳算法包括兩個關鍵因素:交叉操作和變異操作;
三值FPRM電路面積和功耗綜合優化包含以下幾個關鍵要素:極性、相應極性的面積和功耗之和、最佳極性、最小面積和功耗之和、可選擇的極性空間、最佳極性所在區間、極性變換、極性向最佳極性所在區間跳變、跳出局部最佳極性、極性交流、極性突變、面積和功耗;
將人口所在地點映射到三值FPRM電路面積和功耗綜合優化,表示為極性;將人口所在地點的吸引力映射到三值FPRM電路面積和功耗綜合優化,表示為相應極性的面積和功耗之和;將吸引力最大地點映射到三值FPRM電路面積和功耗綜合優化,表示為最佳極性;將最大吸引力映射到三值FPRM電路面積和功耗綜合優化,表示為最小面積和功耗之和;將人口可移動地表空間映射到三值FPRM電路面積和功耗綜合優化,表示為可選擇的極性空間;將優惠區域映射到三值FPRM電路面積和功耗綜合優化,表示為最佳極性所在區間;將人口流動域映射到三值FPRM電路面積和功耗綜合優化,表示為極性變換;將人口遷移映射到三值FPRM電路面積和功耗綜合優化,表示為極性向最佳極性所在區間跳變;將人口擴散映射到三值FPRM電路面積和功耗綜合優化,表示為跳出局部最佳極性;將交叉操作映射到三值FPRM電路面積和功耗綜合優化,表示為極性交流;將變異操作映射到三值FPRM電路面積和功耗綜合優化,表示為極性突變;將環境因素映射到三值FPRM電路面積和功耗綜合優化,表示為三值FPRM電路的面積S;將經濟因素映射到三值FPRM電路面積和功耗綜合優化,表示為三值FPRM電路的功耗;
⑤設置人口遷移遺傳算法相關參數:
人口遷移遺傳算法需設置5個參數:人口規模s、人口流動次數l、人口壓力參數q、收縮系數c和人口擴散次數z;令人口規模s等于三值FPRM邏輯函數的輸入變量個數,即s=n;人口流動次數l為人口所在區域的半徑,人口所在區域的半徑記為Δt,l=Δt,Δt=3s/s2;人口壓力參數q為Δt/10;收縮系數c=0.3;三值FPRM電路為小規模電路時,人口擴散次數z=15,三值FPRM電路為大規模電路時,人口擴散次數z=2;大規模電路通常指輸入變量大于等于4的電路,小規模電路通常指輸入變量小于4的電路;
⑥采用人口遷移遺傳算法得到吸引力最大地點和最大吸引力,吸引力最大地點即為三值FPRM電路的面積和功耗最佳極性;最大吸引力即為三值FPRM電路的最小面積和功耗之和。
實施例二:一種三值FPRM電路面積與功耗最佳極性搜索方法,包括以下步驟:
①構建人口遷移遺傳算法,人口遷移遺傳算法通過將遺傳算法融合到人口遷移算法中得到:在人口遷移算法中發生人口流動時加入遺傳算法的交叉操作和變異操作,在人口遷移算法中發生人口遷移時加入遺傳算法的交叉操作和變異操作;由此實現遺傳算法和人口遷移算法的融合;
②建立三值FPRM電路的面積估計模型和功耗估計模型:
②-1將三值FPRM電路用三值FPRM邏輯函數的表達式表示為:
fp(xn-1,xn-2,...,x0)=&CirclePlus;Σi=03n-1ai*Πj=0n-1x&CenterDot;jij---(1)]]>
其中,n為函數fp(xn-1,xn-2,…,x0)的變量數,xn-1,xn-2,…,x0表示函數fp(xn-1,xn-2,…,x0)的n個輸入變量,p表示函數fp(xn-1,xn-2,…,x0)的極性,極性p用三進制形式表示為pn-1pn-2…p0,pj∈{0,1,2},j=0,1,2,…,n-1,表示模3加運算,∑為累加符號,符號“*”表示乘號,下標i=0,1,2,…,3n-1,i用三進制形式表示為in-1in-2…i0,ai為FPRM展開式系數,ai∈{0,1,2};∏表示模3乘運算,的展開式為:其中ij&Element;{0,1,2},x&CenterDot;j=(xj&CirclePlus;pj),x&CenterDot;j0=1,x&CenterDot;j1=x&CenterDot;j,x&CenterDot;j2=x&CenterDot;j*x&CenterDot;j,]]>極性p和下標i決定變量的表示形式;
②-2p極性下的三值FPRM邏輯函數包含兩類多輸入運算,兩類多輸入運算分別為多輸入模3加運算和多輸入模3乘運算,根據三值FPRM邏輯函數展開式將三值FPRM邏輯函數分解為多個多輸入模3加運算和多個多輸入模3乘運算,然后將每個多輸入運算分別分解為二輸入運算,得到二輸入模3加運算和二輸入模3乘運算,具體分解過程為:
將多輸入運算的第1個輸入變量和第2個輸入變量作為第一個二輸入運算的兩個輸入變量,得到第一個二輸入運算的輸出變量;將第一個二輸入運算的輸出變量和多輸入運算的第3個輸入變量作為第二個二輸入運算的兩個輸入變量,得到第二個二輸入運算的輸出變量;將第二個二輸入運算的輸出變量和多輸入運算的第4個輸入變量作為第三個二輸入運算的兩個輸入變量,得到第三個二輸入運算的輸出變量;依此類推,直到所有的多輸入運算的輸入變量作為二輸入運算的輸入變量,完成多輸入運算的分解;
將p極性下的三值FPRM邏輯函數分解后得到多個多輸入模3加運算和多個多輸入模3乘運算,多輸入模3加運算也稱為多輸入模3加門,多輸入模3乘運算也稱為多輸入模3乘門,將p極性下三值FPRM邏輯函數分解后的多輸入模3加門的數量記為N,將p極性下三值FPRM邏輯函數分解后的多輸入模3乘門的數量記為W;將每個多輸入模3加運算分解后得到多個二輸入模3加運算,將每個多輸入模3乘運算分解后得到多個二輸入模3乘運算,二輸入模3加運算也稱為二輸入模3加門,二輸入模3乘運算也稱為二輸入模3乘門;將第u個多輸入模3加門分解后的二輸入模3加門的數量記為Nu,u=1,2,…,N;將第o個多輸入模3乘門分解后的二輸入模3乘門的數量記為Wo,o=1,2,…,W;
②-3將作為三值FPRM電路的面積估計模型,S表示面積;表示p極性下三值FPRM邏輯函數中所有的多輸入模3加門分解后得到的二輸入模3加門的總數量;表示為p極性下三值FPRM邏輯函數中所有的多輸入模3乘門分解后得到的二輸入模3乘門的總數量;
②-4將p極性下的三值FPRM邏輯函數分解后得到的所有二輸入模3加門和二輸入模3乘門引起的功耗作為p極性下的三值FPRM電路的功耗,二輸入模3加門引起的功耗采用其開關活動性表示,二輸入模3乘門引起的功耗采用其開關活動性表示,門電路的開關活動性用其輸出端的輸出變量概率表示,二輸入模3加門引起的功耗采用其輸出端的輸出變量概率表示,二輸入模3乘門引起的功耗采用其輸出端的輸出變量概率表示;
②-5根據公式(2)、(3)和(4)計算第u個多輸入模3加門分解后的第k個二輸入模3加門的輸出變量概率;k=1,2,…,Nu;
P1(k)u=Pky11*Pky20+Pky10*Pky21+Pky12*Pky22(2)
P2(k)u=Pky12*Pky20+Pky11*Pky21+Pky10*Pky22(3)
P0(k)u=1-P1(k)u-P2(k)u(4)
根據公式(5)、(6)和(7)計算第o個多輸入模3乘門分解后的第g個二輸入模3乘門的輸出變量概率,g=1,2,…,Wo:
Q1(g)o=Qgr11*Qgr21+Qgr12*Qgr22(5)
Q2(g)o=Qgr11*Qgr22+Qgr12*Qgr21(6)
Q0(g)o=1-Q1(g)o-Q2(g)o(7)
其中,P1(k)u表示第u個多輸入模3加門分解后的第k個二輸入模3加門輸出變量為1的概率,P2(k)u表示第u個多輸入模3加門分解后的第k個二輸入模3加門輸出變量為2的概率,P0(k)u表示第u個多輸入模3加門分解后的第k個二輸入模3加門輸出變量為0的概率,y1和y2表示二輸入模3加門的兩個輸入變量,Pky1m表示第k個二輸入模3加門中輸入變量y1為m的概率,m∈{0,1,2},Pky2m表示第k個二輸入模3加門中輸入變量y2為m的概率,當k=1時,Pky1m為多輸入模3加運算的第1個輸入變量為m的概率,Pky2m為多輸入模3加運算的第2個輸入變量為m的概率,當k>1時,Pky1m為第k-1個二輸入模3加門輸出變量為m的概率,Pky2m為多輸入模3加門的第k+1個輸入變量為m的概率;
Q1(g)o表示第o個多輸入模3乘門分解后的第g個二輸入模3乘門輸出變量為1的概率,Q2(g)o表示第o個多輸入模3乘門分解后的第g個二輸入模3乘門輸出變量為2的概率,Q0(g)o表示第o個多輸入模3乘門分解后的第g個二輸入模3乘門輸出變量為0的概率,r1和r2表示二輸入模3乘門的兩個輸入變量,Qgr1m表示第g個二輸入模3乘門中輸入變量r1為m的概率,Qgr2m表示第g個二輸入模3乘門中輸入變量r2為m的概率;當g=1時,Qgr1m為多輸入模3乘運算的第1個輸入變量為m的概率,Qgr2m為多輸入模3乘運算的第2個輸入變量為m的概率,當g>1時,Qgr1m為第g-1個二輸入模3乘門輸出變量為m的概率,Qgr2m為多輸入模3乘門的第g+1個輸入變量為m的概率;
輸入變量xj為1和2的概率是由隨即函數產生的概率對(P1,P2),P0=1-P1-P2;P0,P1和P2分別為0到1之間某個值,P0表示輸入變量為0的概率,P1表示輸入變量為1的概率,P2表示輸入變量為2的概率;
②-6根據二輸入模3加門的輸出變量概率和二輸入模3乘門的輸出變量概率計算三值FPRM電路的功耗,將三值FPRM電路的功耗估計模型表示為:
Eswd=2(Σu=1N(Σk=1Nu(P1(k)u+P2(k)u))+Σo=1W(Σg=1Wo(Q1(g)o+Q2(g)o)))---(8)]]>
其中,Eswd表示p極性下三值FPRM電路的功耗,N為p極性下三值FPRM邏輯函數分解后的多輸入模3加門的數量,W為p極性下三值FPRM邏輯函數分解后的多輸入模3乘門的數量;
③設定人口遷移算法中用于計算人口所在地點的吸引力的吸引力函數,吸引力函數用下式表示為:
attraction(t)=α/(β/At+(1-β)/Bt)(9)
其中,符號“/”表示除運算符號,attraction(t)表示第t個人口所在地點的吸引力大小;At表示第t個人口所在地點的環境因素,Bt表示第t個人口所在地點的經濟因素,β為人口所在地點的環境因素和經濟因素的權重,0<β<1;
④建立三值FPRM電路和人口遷移遺傳算法的對應關系:
人口遷移算法包含以下幾個關鍵要素:人口所在地點、人口所在地點的吸引力、吸引力最大地點、最大吸引力、人口可移動地表空間、優惠區域、人口流動、人口遷移、人口擴散、環境因素和經濟因素;
遺傳算法包括兩個關鍵因素:交叉操作和變異操作;
三值FPRM電路面積和功耗綜合優化包含以下幾個關鍵要素:極性、相應極性的面積和功耗之和、最佳極性、最小面積和功耗之和、可選擇的極性空間、最佳極性所在區間、極性變換、極性向最佳極性所在區間跳變、跳出局部最佳極性、極性交流、極性突變、面積和功耗;
將人口所在地點映射到三值FPRM電路面積和功耗綜合優化,表示為極性;將人口所在地點的吸引力映射到三值FPRM電路面積和功耗綜合優化,表示為相應極性的面積和功耗之和;將吸引力最大地點映射到三值FPRM電路面積和功耗綜合優化,表示為最佳極性;將最大吸引力映射到三值FPRM電路面積和功耗綜合優化,表示為最小面積和功耗之和;將人口可移動地表空間映射到三值FPRM電路面積和功耗綜合優化,表示為可選擇的極性空間;將優惠區域映射到三值FPRM電路面積和功耗綜合優化,表示為最佳極性所在區間;將人口流動域映射到三值FPRM電路面積和功耗綜合優化,表示為極性變換;將人口遷移映射到三值FPRM電路面積和功耗綜合優化,表示為極性向最佳極性所在區間跳變;將人口擴散映射到三值FPRM電路面積和功耗綜合優化,表示為跳出局部最佳極性;將交叉操作映射到三值FPRM電路面積和功耗綜合優化,表示為極性交流;將變異操作映射到三值FPRM電路面積和功耗綜合優化,表示為極性突變;將環境因素映射到三值FPRM電路面積和功耗綜合優化,表示為三值FPRM電路的面積S;將經濟因素映射到三值FPRM電路面積和功耗綜合優化,表示為三值FPRM電路的功耗;
⑤設置人口遷移遺傳算法相關參數:
人口遷移遺傳算法需設置5個參數:人口規模s、人口流動次數l、人口壓力參數q、收縮系數c和人口擴散次數z;令人口規模s等于三值FPRM邏輯函數的輸入變量個數,即s=n;人口流動次數l為人口所在區域的半徑,人口所在區域的半徑記為Δt,l=Δt,Δt=3s/s2;人口壓力參數q為Δt/10;收縮系數c=0.3;三值FPRM電路為小規模電路時,人口擴散次數z=15,三值FPRM電路為大規模電路時,人口擴散次數z=2;大規模電路通常指輸入變量大于等于4的電路,小規模電路通常指輸入變量小于4的電路;
⑥采用人口遷移遺傳算法得到吸引力最大地點和最大吸引力,吸引力最大地點即為三值FPRM電路的面積和功耗最佳極性;最大吸引力即為三值FPRM電路的最小面積和功耗之和。
本實施例中,步驟⑥中采用人口遷移遺傳算法得到吸引力最大地點和最大吸引力的具體過程為:
⑥-1在人口可移動地表空間內用隨機函數rand()產生s個人口所在地點,將s個人口所在地點分別記為P1,P2,…,Ps,分別以P1,P2,…,Ps為中點,按人口所在區域的半徑確定s個人口所在區域;
⑥-2通過吸引力函數計算第v個人口所在地點Pv的吸引力,v=1,2,3,…,s,得到人口所在地點P1,P2,…,Ps的吸引力;
⑥-3比較人口所在地點P1,P2,…,Ps的吸引力,篩選出吸引力最大的人口所在地點作為吸引力最大地點,記錄吸引力最大地點和最大吸引力;
⑥-4進行人口流動:在人口所在地點Pv所對應的人口所在區域內采用隨機函數隨機產生一個人口所在地點P'v,得到P'1,P'2,…,P's,采用P'1,P'2,…,P's更新人口所在地點P1,P2,…,Ps,即P1=P'1,P2=P'2,…,Ps=P's,其中,P'v=2*Δt*rand()+(Pv-Δt),符號“*”為乘運算符號,Δt表示人口所在區域的半徑;rand()為隨機函數;
⑥-5按照步驟⑥-2~⑥-3對人口所在地點P1,P2,…,Ps進行處理,得到吸引力最大地點和最大吸引力;
⑥-6進行交叉操作:若s為偶數,將P1和P2、P3和P4、…、Ps-1和Ps兩兩分別進行交叉操作;若s為奇數,將P1和P2、P3和P4、…、Ps-2和Ps-1兩兩分別進行交叉操作,Ps不參與交叉操作;兩個人口所在地點交叉操作的具體過程為:將進行交叉操作的兩個人口所在地點分別轉換為n位三進制碼,轉換后的兩個n位三進制碼分別記為f1和f2,隨機產生一個n位的二進制碼,將該n位的二進制碼記為A,根據二進制碼A更新f1和f2,當二進制碼A的第h位為1時,f1的第h位保持不變,f2的第h位保持不變;當二進制碼A的第h位為0時,f1的第h位繼承f2的第h位,f2的第h位繼承f1的第h位,h=1,2,3,…,n,得到更新后的f1和f2,將更新后的f1和f2轉換為十進制數據得到f1'和f2',采用f1'和f2'更新進行交叉操作的兩個人口所在地點;
⑥-7按照步驟⑥-2~⑥-3對人口所在地點P1,P2,…,Ps進行處理,得到吸引力最大地點和最大吸引力;
⑥-8進行變異操作:將P1,P2,…,Ps轉化為n位三進制碼,得到F1,F2,…,Fs;對Fv的每一位均用隨機函數rand()產生一個0到1之間的值,若這個值小于0.01,則這個值對應的位就是Fv的變異位,對Fv的變異位進行變異,變異規則為“0→1,1→2,2→0”;F1,F2,…,Fs變異操作后得到F1',F2',…,Fs',v=1,2,3,…,s;將F1',F2',…,Fs'轉換為十進制數據后更新人口所在地點P1,P2,…,Ps;
⑥-9按照步驟⑥-2~⑥-3對人口所在地點P1,P2,…,Ps進行處理,得到更新后的吸引力最大地點和最大吸引力;
⑥-10進行人口遷移:以步驟⑥-9中的吸引力最大地點為中點,按人口所在區域半徑Δt的大小確定優惠區域,在優惠區域內用隨機函數rand()產生s個人口所在地點,將此時得到的s個人口所在地點對人口所在地點P1,P2,…,Ps再次進行更新;
⑥-11按照步驟⑥-2~⑥-3對人口所在地點P1,P2,…,Ps進行處理,得到吸引力最大地點和最大吸引力;
⑥-12重復步驟⑥-6~⑥-9;
⑥-13收縮優惠區域:令Δt'=(1-c)*Δt,采用Δt'更新Δt;重復步驟⑥-10~⑥-12,直到Δt<q;
⑥-14當收縮優惠區域到一定程度Δt<q后,進行人口擴散:重復步驟⑥-1-⑥-13,直到滿足人口擴散次數z,算法結束,得到吸引力最大地點和最大吸引力;
⑥-15將最后一次得到的吸引力最大地點和最大吸引力輸出,吸引力最大地點即為三值FPRM電路的最佳極性;最大吸引力即為三值FPRM電路的最小面積和功耗之和(面積和功耗之和的最小值)。
本發明的三值FPRM電路面積與功耗最佳極性搜索方法在Windows764位操作系統,Intel(R)Core(TM)i3-2130CPU3.40GHZ,4GRAM運行環境下,用C語言通過VC6.0編譯實現,采用10個MCNCBenchmark電路進行仿真驗證,優化結果與整體退火遺傳算法比較。
為計算三值FPRM電路的開關活動性,隨機產生15組輸入信號概率:(P1,P2)={(0.21,0.53),(0.49,0.30),(0.33,0.24),(0.68,0.13),(0.15,0.26),(0.57,0.22),(0.18,0.51),(0.71,0.24),(0.08,0.35),(0.57,0.32),(0.46,0.28),(0.17,0.05),(0.32,0.43),(0.14,0.72),(0.25,0.61)}。通過對MCNCBenchmark電路測試表明,對三值FPRM電路具有較好的優化效果。三值FPRM電路面積和功耗最佳極性搜索結果如表1所示。表1中,列1表示電路名稱;列2分別指出電路輸入變量個數;列3、列4、列5、列6和列7依次分別表示整體退火遺傳算法搜索到的最佳極性、模3加運算數量和模3乘運算數量、功耗以及算法的運行時間;列8、列9、列10、列11和列12依次分別表示本發明的方法搜索到的最佳極性、模3加運算和模3乘運算數量、功耗以及算法的運行時間。
表1基于PMGA的三值FPRM電路面積與功耗優化仿真結果

與整體退火遺傳算法相比,本發明的方法面積、功耗和時間上節省的百分比如表2所示。面積、功耗和時間節省的百分比定義如下:
SaveArea%=AreaWAGA-AreaPMGAAreaWAGA×100%---(8)]]>
SavePower%=PowerWAGA-PowerPMGAPowerWAGA×100%---(9)]]>
SaveTime%=TimeWAGA-TimePMGATimeWAGA×100%---(10)]]>
其中,SaveArea、SavePower和SaveTime依次分別表示面積、功耗和算法運行時間的節省;AreaWAGA和PowerWAGA依次分別表示整體退火遺傳算法搜索到的最佳極性下電路的面積和功耗;AreaPMGA、和PowerPMGA依次分別表示本發明的方法搜索到的最佳極性下電路的面積和功耗;TimeWAGA和TimePMGA依次分別表示整體退火遺傳算法和本發明的方法的運行時間。
表2三值FPRM電路面積、功耗和時間節省百分比

分析表2數據可知,與整體退火遺傳算法相比,本文所提方法優化效果明顯,10個測試電路的面積平均節省13.33%,功耗平均節省20.00%,時間平均節省64.96%。

關 鍵 詞:
一種 FPRM 電路 面積 功耗 最佳 極性 搜索 方法
  專利查詢網所有資源均是用戶自行上傳分享,僅供網友學習交流,未經上傳用戶書面授權,請勿作他用。
關于本文
本文標題:一種三值FPRM電路面積與功耗最佳極性搜索方法.pdf
鏈接地址:http://www.wwszu.club/p-6405719.html
關于我們 - 網站聲明 - 網站地圖 - 資源地圖 - 友情鏈接 - 網站客服客服 - 聯系我們

[email protected] 2017-2018 zhuanlichaxun.net網站版權所有
經營許可證編號:粵ICP備17046363號-1 
 


收起
展開
鬼佬大哥大