[發明專利]一種三值FPRM電路面積與功耗最佳極性搜索方法

有效

• 申請號: 201510552955.2
• 申請日: 2015-09-01
• 公開（公告）號: CN105205534B
• 公開（公告）日: 2017-09-29
• 發明（設計）人: 汪鵬君;厲康平;張會紅
• 申請（專利權）人: 寧波大學
• 主分類號: G06N3/12
• 分類號: G06N3/12;G06F17/30
• 代理公司: 寧波奧圣專利代理事務所(普通合伙)33226
• 代理人: 方小惠

1.一種三值FPRM電路面積與功耗最佳極性搜索方法，其特征在于包括以下步驟：

①構建人口遷移遺傳算法，人口遷移遺傳算法通過將遺傳算法融合到人口遷移算法中得到：在人口遷移算法中發生人口流動時加入遺傳算法的交叉操作和變異操作，在人口遷移算法中發生人口遷移時加入遺傳算法的交叉操作和變異操作；由此實現遺傳算法和人口遷移算法的融合；

②建立三值FPRM電路的面積估計模型和功耗估計模型：

②-1將三值FPRM電路用三值FPRM邏輯函數的表達式表示為：

其中，n為函數f^p(x_n-1,x_n-2,…,x₀)的變量數，x_n-1,x_n-2,…,x₀表示函數f^p(x_n-1,x_n-2,…,x₀)的n個輸入變量，p表示函數f^p(x_n-1,x_n-2,…,x₀)的極性，極性p用三進制形式表示為p_n-1p_n-2…p₀，p_j∈{0,1,2}，j＝0,1,2,…,n-1，表示模3加運算，∑為累加符號，符號“*”表示乘號，下標i＝0,1,2,…,3ⁿ-1，i用三進制形式表示為i_n-1i_n-2…i₀，a_i為FPRM展開式系數，a_i∈{0,1,2}；∏表示模3乘運算，的展開式為：其中i_j∈{0,1,2},極性p和下標i決定變量的表示形式；

②-2 p極性下的三值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加門的數量記為N_u,u＝1,2,…,N；將第o個多輸入模3乘門分解后的二輸入模3乘門的數量記為W_o，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,…,N_u；

P₁(k)_u＝Pk_y11*Pk_y20+Pk_y10*Pk_y21+Pk_y12*Pk_y22(2)

P₂(k)_u＝Pk_y12*Pk_y20+Pk_y11*Pk_y21+Pk_y10*Pk_y22(3)

P₀(k)_u＝1-P₁(k)_u-P₂(k)_u(4)

根據公式(5)、(6)和(7)計算第o個多輸入模3乘門分解后的第g個二輸入模3乘門的輸出變量概率，g＝1,2,…,W_o：

Q₁(g)_o＝Qg_r11*Qg_r21+Qg_r12*Qg_r22(5)

Q₂(g)_o＝Qg_r11*Qg_r22+Qg_r12*Qg_r21(6)

Q₀(g)_o＝1-Q₁(g)_o-Q₂(g)_o(7)

其中，P₁(k)_u表示第u個多輸入模3加門分解后的第k個二輸入模3加門輸出變量為1的概率，P₂(k)_u表示第u個多輸入模3加門分解后的第k個二輸入模3加門輸出變量為2的概率，P₀(k)_u表示第u個多輸入模3加門分解后的第k個二輸入模3加門輸出變量為0的概率，y1和y2表示二輸入模3加門的兩個輸入變量，m∈{0,1,2}，當k＝1時，Pk_y1m為多輸入模3加運算的第1個輸入變量為m的概率，Pk_y2m為多輸入模3加運算的第2個輸入變量為m的概率，當k>1時，Pk_y1m為第k-1個二輸入模3加門輸出變量為m的概率，Pk_y2m為多輸入模3加門的第k+1個輸入變量為m的概率；

Q₁(g)_o表示第o個多輸入模3乘門分解后的第g個二輸入模3乘門輸出變量為1的概率，Q₂(g)_o表示第o個多輸入模3乘門分解后的第g個二輸入模3乘門輸出變量為2的概率，Q₀(g)_o表示第o個多輸入模3乘門分解后的第g個二輸入模3乘門輸出變量為0的概率，r1和r2表示二輸入模3乘門的兩個輸入變量；當g＝1時，Qg_r1m為多輸入模3乘運算的第1個輸入變量為m的概率，Qg_r2m為多輸入模3乘運算的第2個輸入變量為m的概率，當g>1時，Qg_r1m為第g-1個二輸入模3乘門輸出變量為m的概率，Qg_r2m為多輸入模3乘門的第g+1個輸入變量為m的概率；

輸入變量x_j為1和2的概率是由隨即函數產生的概率對(P₁,P₂)，P₀＝1-P₁-P₂；P₀，P₁和P₂分別為0到1之間某個值，P₀表示輸入變量為0的概率，P₁表示輸入變量為1的概率，P₂表示輸入變量為2的概率；

②-6根據二輸入模3加門的輸出變量概率和二輸入模3乘門的輸出變量概率計算三值FPRM電路的功耗，將三值FPRM電路的功耗估計模型表示為：

其中，E_swd表示p極性下三值FPRM電路的功耗，N為p極性下三值FPRM邏輯函數分解后的多輸入模3加門的數量,W為p極性下三值FPRM邏輯函數分解后的多輸入模3乘門的數量；

③設定人口遷移算法中用于計算人口所在地點的吸引力的吸引力函數，吸引力函數用下式表示為：

attraction(t)＝α/(β/A_t+(1-β)/B_t)(9)

其中，符號“/”表示除運算符號，attraction(t)表示第t個人口所在地點的吸引力大小；A_t表示第t個人口所在地點的環境因素，B_t表示第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＝3^s/s²；人口壓力參數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位三進制碼分別記為f₁和f₂，隨機產生一個n位的二進制碼，將該n位的二進制碼記為A，根據二進制碼A更新f₁和f₂，當二進制碼A的第h位為1時，f₁的第h位保持不變，f₂的第h位保持不變；當二進制碼A的第h位為0時，f₁的第h位繼承f₂的第h位，f₂的第h位繼承f₁的第h位，h＝1，2，3，…，n，得到更新后的f₁和f₂，將更新后的f₁和f₂轉換為十進制數據得到f₁'和f₂'，采用f₁'和f₂'更新進行交叉操作的兩個人口所在地點；

⑥-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電路的最小面積和功耗之和。