一种三值FPRM电路面积与功耗最佳极性搜索方法转让专利
申请号 : CN201510552955.2
文献号 : CN105205534B
文献日 : 2017-09-29
发明人 : 汪鹏君 , 厉康平 , 张会红
申请人 : 宁波大学
摘要 :
权利要求 :
1.一种三值FPRM电路面积与功耗最佳极性搜索方法,其特征在于包括以下步骤:
①构建人口迁移遗传算法,人口迁移遗传算法通过将遗传算法融合到人口迁移算法中得到:在人口迁移算法中发生人口流动时加入遗传算法的交叉操作和变异操作,在人口迁移算法中发生人口迁移时加入遗传算法的交叉操作和变异操作;由此实现遗传算法和人口迁移算法的融合;
②建立三值FPRM电路的面积估计模型和功耗估计模型:
②-1将三值FPRM电路用三值FPRM逻辑函数的表达式表示为:
其中,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决定变量 的表示形式;
②-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加门的数量记为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加门的两个输入变量,m∈{0,1,2},当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乘门的两个输入变量;当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表示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;人s 2口流动次数l为人口所在区域的半径,人口所在区域的半径记为Δt,l=Δt,Δt=3 /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位三进制码分别记为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
⑥-14当收缩优惠区域到一定程度Δt
⑥-15将最后一次得到的吸引力最大地点和最大吸引力输出,吸引力最大地点即为三值FPRM电路的面积和功耗最佳极性;最大吸引力即为三值FPRM电路的最小面积和功耗之和。
说明书 :
一种三值FPRM电路面积与功耗最佳极性搜索方法
技术领域
背景技术
发明内容
[0058] ⑥-14当收缩优惠区域到一定程度Δt[0059] ⑥-15将最后一次得到的吸引力最大地点和最大吸引力输出,吸引力最大地点即为三值FPRM电路的面积和功耗最佳极性;最大吸引力即为三值FPRM电路的最小面积和功耗之和。[0060] 与现有技术相比,本发明的优点在于首先通过将遗传算法融合到人口迁移算法中得到人口迁移遗传算法,然后建立三值FPRM电路的面积估计模型和功耗估计模型,设定人口迁移算法中用于计算人口所在地点的吸引力的吸引力函数,建立三值FPRM电路和人口迁移遗传算法的对应关系,接着设定设置人口迁移遗传算法相关参数,最后采用人口迁移遗传算法得到吸引力最大地点和最大吸引力,吸引力最大地点即为三值FPRM电路的最佳极性;最大吸引力即为三值FPRM电路的最小面积和功耗之和;本发明的方法可以快速搜索到面积和功耗最佳极性,同时优化三值FPRM电路的面积与功耗性能,提高三值FPRM电路的综合性能;采用10个测试电路对本发明的方法和整体退火遗传算法分别进行仿真验证,本发明的优化方法相对于整体退火遗传算法,面积平均节省13.33%,功耗平均节省20.00%,时间平均节省64.96%。具体实施方式
[0061] 以下结合实施例对本发明作进一步详细描述。[0062] 实施例一:一种三值FPRM电路面积与功耗最佳极性搜索方法,包括以下步骤:[0063] ①构建人口迁移遗传算法,人口迁移遗传算法通过将遗传算法融合到人口迁移算法中得到:在人口迁移算法中发生人口流动时加入遗传算法的交叉操作和变异操作,在人口迁移算法中发生人口迁移时加入遗传算法的交叉操作和变异操作;由此实现遗传算法和人口迁移算法的融合;[0064] ②建立三值FPRM电路的面积估计模型和功耗估计模型:[0065] ②-1将三值FPRM电路用三值FPRM逻辑函数的表达式表示为:[0066][0067] 其中,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决定变量 的表示形式;[0068] ②-2p极性下的三值FPRM逻辑函数包含两类多输入运算,两类多输入运算分别为多输入模3加运算和多输入模3乘运算,根据三值FPRM逻辑函数展开式将三值FPRM逻辑函数分解为多个多输入模3加运算和多个多输入模3乘运算,然后将每个多输入运算分别分解为二输入运算,得到二输入模3加运算和二输入模3乘运算,具体分解过程为:[0069] 将多输入运算的第1个输入变量和第2个输入变量作为第一个二输入运算的两个输入变量,得到第一个二输入运算的输出变量;将第一个二输入运算的输出变量和多输入运算的第3个输入变量作为第二个二输入运算的两个输入变量,得到第二个二输入运算的输出变量;将第二个二输入运算的输出变量和多输入运算的第4个输入变量作为第三个二输入运算的两个输入变量,得到第三个二输入运算的输出变量;依此类推,直到所有的多输入运算的输入变量作为二输入运算的输入变量,完成多输入运算的分解;[0070] 将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;[0071] ②-3将 作为三值FPRM电路的面积估计模型,S表示面积; 表示p极性下三值FPRM逻辑函数中所有的多输入模3加门分解后得到的二输入模3加门的总数量; 表示为p极性下三值FPRM逻辑函数中所有的多输入模3乘门分解后得到的二输入模3乘门的总数量;[0072] ②-4将p极性下的三值FPRM逻辑函数分解后得到的所有二输入模3加门和二输入模3乘门引起的功耗作为p极性下的三值FPRM电路的功耗,二输入模3加门引起的功耗采用其开关活动性表示,二输入模3乘门引起的功耗采用其开关活动性表示,门电路的开关活动性用其输出端的输出变量概率表示,二输入模3加门引起的功耗采用其输出端的输出变量概率表示,二输入模3乘门引起的功耗采用其输出端的输出变量概率表示;[0073] ②-5根据公式(2)、(3)和(4)计算第u个多输入模3加门分解后的第k个二输入模3加门的输出变量概率;k=1,2,…,Nu;[0074] P1(k)u=Pky11*Pky20+Pky10*Pky21+Pky12*Pky22 (2)[0075] P2(k)u=Pky12*Pky20+Pky11*Pky21+Pky10*Pky22 (3)[0076] P0(k)u=1-P1(k)u-P2(k)u (4)[0077] 根据公式(5)、(6)和(7)计算第o个多输入模3乘门分解后的第g个二输入模3乘门的输出变量概率,g=1,2,…,Wo:[0078] Q1(g)o=Qgr11*Qgr21+Qgr12*Qgr22 (5)[0079] Q2(g)o=Qgr11*Qgr22+Qgr12*Qgr21 (6)[0080] Q0(g)o=1-Q1(g)o-Q2(g)o (7)[0081] 其中,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加门的两个输入变量,m∈{0,1,2},当k=1时,Pky1m为多输入模3加运算的第1个输入变量为m的概率,Pky2m为多输入模3加运算的第2个输入变量为m的概率,当k>1时,Pky1m为第k-1个二输入模3加门输出变量为m的概率,Pky2m为多输入模3加门的第k+1个输入变量为m的概率;[0082] 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乘门的两个输入变量;当g=1时,Qgr1m为多输入模3乘运算的第1个输入变量为m的概率,Qgr2m为多输入模3乘运算的第2个输入变量为m的概率,当g>1时,Qgr1m为第g-1个二输入模3乘门输出变量为m的概率,Qgr2m为多输入模3乘门的第g+1个输入变量为m的概率;[0083] 输入变量xj为1和2的概率是由随即函数产生的概率对(P1,P2),P0=1-P1-P2;P0,P1和P2分别为0到1之间某个值,P0表示输入变量为0的概率,P1表示输入变量为1的概率,P2表示输入变量为2的概率;[0084] ②-6根据二输入模3加门的输出变量概率和二输入模3乘门的输出变量概率计算三值FPRM电路的功耗,将三值FPRM电路的功耗估计模型表示为:[0085][0086] 其中,Eswd表示p极性下三值FPRM电路的功耗,N为p极性下三值FPRM逻辑函数分解后的多输入模3加门的数量,W为p极性下三值FPRM逻辑函数分解后的多输入模3乘门的数量;[0087] ③设定人口迁移算法中用于计算人口所在地点的吸引力的吸引力函数,吸引力函数用下式表示为:[0088] attraction(t)=α/(β/At+(1-β)/Bt) (9)[0089] 其中,符号“/”表示除运算符号,attraction(t)表示第t个人口所在地点的吸引力大小;At表示第t个人口所在地点的环境因素,Bt表示第t个人口所在地点的经济因素,β为人口所在地点的环境因素和经济因素的权重,0<β<1;[0090] ④建立三值FPRM电路和人口迁移遗传算法的对应关系:[0091] 人口迁移算法包含以下几个关键要素:人口所在地点、人口所在地点的吸引力、吸引力最大地点、最大吸引力、人口可移动地表空间、优惠区域、人口流动、人口迁移、人口扩散、环境因素和经济因素;[0092] 遗传算法包括两个关键因素:交叉操作和变异操作;[0093] 三值FPRM电路面积和功耗综合优化包含以下几个关键要素:极性、相应极性的面积和功耗之和、最佳极性、最小面积和功耗之和、可选择的极性空间、最佳极性所在区间、极性变换、极性向最佳极性所在区间跳变、跳出局部最佳极性、极性交流、极性突变、面积和功耗;[0094] 将人口所在地点映射到三值FPRM电路面积和功耗综合优化,表示为极性;将人口所在地点的吸引力映射到三值FPRM电路面积和功耗综合优化,表示为相应极性的面积和功耗之和;将吸引力最大地点映射到三值FPRM电路面积和功耗综合优化,表示为最佳极性;将最大吸引力映射到三值FPRM电路面积和功耗综合优化,表示为最小面积和功耗之和;将人口可移动地表空间映射到三值FPRM电路面积和功耗综合优化,表示为可选择的极性空间;将优惠区域映射到三值FPRM电路面积和功耗综合优化,表示为最佳极性所在区间;将人口流动域映射到三值FPRM电路面积和功耗综合优化,表示为极性变换;将人口迁移映射到三值FPRM电路面积和功耗综合优化,表示为极性向最佳极性所在区间跳变;将人口扩散映射到三值FPRM电路面积和功耗综合优化,表示为跳出局部最佳极性;将交叉操作映射到三值FPRM电路面积和功耗综合优化,表示为极性交流;将变异操作映射到三值FPRM电路面积和功耗综合优化,表示为极性突变;将环境因素映射到三值FPRM电路面积和功耗综合优化,表示为三值FPRM电路的面积S;将经济因素映射到三值FPRM电路面积和功耗综合优化,表示为三值FPRM电路的功耗;[0095] ⑤设置人口迁移遗传算法相关参数:[0096] 人口迁移遗传算法需设置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的电路;[0097] ⑥采用人口迁移遗传算法得到吸引力最大地点和最大吸引力,吸引力最大地点即为三值FPRM电路的面积和功耗最佳极性;最大吸引力即为三值FPRM电路的最小面积和功耗之和。[0098] 实施例二:一种三值FPRM电路面积与功耗最佳极性搜索方法,包括以下步骤:[0099] ①构建人口迁移遗传算法,人口迁移遗传算法通过将遗传算法融合到人口迁移算法中得到:在人口迁移算法中发生人口流动时加入遗传算法的交叉操作和变异操作,在人口迁移算法中发生人口迁移时加入遗传算法的交叉操作和变异操作;由此实现遗传算法和人口迁移算法的融合;[0100] ②建立三值FPRM电路的面积估计模型和功耗估计模型:[0101] ②-1将三值FPRM电路用三值FPRM逻辑函数的表达式表示为:[0102][0103] 其中,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决定变量 的表示形式;[0104] ②-2p极性下的三值FPRM逻辑函数包含两类多输入运算,两类多输入运算分别为多输入模3加运算和多输入模3乘运算,根据三值FPRM逻辑函数展开式将三值FPRM逻辑函数分解为多个多输入模3加运算和多个多输入模3乘运算,然后将每个多输入运算分别分解为二输入运算,得到二输入模3加运算和二输入模3乘运算,具体分解过程为:[0105] 将多输入运算的第1个输入变量和第2个输入变量作为第一个二输入运算的两个输入变量,得到第一个二输入运算的输出变量;将第一个二输入运算的输出变量和多输入运算的第3个输入变量作为第二个二输入运算的两个输入变量,得到第二个二输入运算的输出变量;将第二个二输入运算的输出变量和多输入运算的第4个输入变量作为第三个二输入运算的两个输入变量,得到第三个二输入运算的输出变量;依此类推,直到所有的多输入运算的输入变量作为二输入运算的输入变量,完成多输入运算的分解;[0106] 将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;[0107] ②-3将 作为三值FPRM电路的面积估计模型,S表示面积; 表示p极性下三值FPRM逻辑函数中所有的多输入模3加门分解后得到的二输入模3加门的总数量; 表示为p极性下三值FPRM逻辑函数中所有的多输入模3乘门分解后得到的二输入模3乘门的总数量;[0108] ②-4将p极性下的三值FPRM逻辑函数分解后得到的所有二输入模3加门和二输入模3乘门引起的功耗作为p极性下的三值FPRM电路的功耗,二输入模3加门引起的功耗采用其开关活动性表示,二输入模3乘门引起的功耗采用其开关活动性表示,门电路的开关活动性用其输出端的输出变量概率表示,二输入模3加门引起的功耗采用其输出端的输出变量概率表示,二输入模3乘门引起的功耗采用其输出端的输出变量概率表示;[0109] ②-5根据公式(2)、(3)和(4)计算第u个多输入模3加门分解后的第k个二输入模3加门的输出变量概率;k=1,2,…,Nu;[0110] P1(k)u=Pky11*Pky20+Pky10*Pky21+Pky12*Pky22 (2)[0111] P2(k)u=Pky12*Pky20+Pky11*Pky21+Pky10*Pky22 (3)[0112] P0(k)u=1-P1(k)u-P2(k)u (4)[0113] 根据公式(5)、(6)和(7)计算第o个多输入模3乘门分解后的第g个二输入模3乘门的输出变量概率,g=1,2,…,Wo:[0114] Q1(g)o=Qgr11*Qgr21+Qgr12*Qgr22 (5)[0115] Q2(g)o=Qgr11*Qgr22+Qgr12*Qgr21 (6)[0116] Q0(g)o=1-Q1(g)o-Q2(g)o (7)[0117] 其中,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},当k=1时,Pky2m为多输入模3加运算的第2个输入变量为m的概率,当k>1时,Pky1m为第k-1个二输入模3加门输出变量为m的概率,Pky2m为多输入模3加门的第k+1个输入变量为m的概率;[0118] 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乘门的两个输入变量;当g=1时,Qgr1m为多输入模3乘运算的第1个输入变量为m的概率,Qgr2m为多输入模3乘运算的第2个输入变量为m的概率,当g>1时,Qgr1m为第g-1个二输入模3乘门输出变量为m的概率,Qgr2m为多输入模3乘门的第g+1个输入变量为m的概率;[0119] 输入变量xj为1和2的概率是由随即函数产生的概率对(P1,P2),P0=1-P1-P2;P0,P1和P2分别为0到1之间某个值,P0表示输入变量为0的概率,P1表示输入变量为1的概率,P2表示输入变量为2的概率;[0120] ②-6根据二输入模3加门的输出变量概率和二输入模3乘门的输出变量概率计算三值FPRM电路的功耗,将三值FPRM电路的功耗估计模型表示为:[0121][0122] 其中,Eswd表示p极性下三值FPRM电路的功耗,N为p极性下三值FPRM逻辑函数分解后的多输入模3加门的数量,W为p极性下三值FPRM逻辑函数分解后的多输入模3乘门的数量;[0123] ③设定人口迁移算法中用于计算人口所在地点的吸引力的吸引力函数,吸引力函数用下式表示为:[0124] attraction(t)=α/(β/At+(1-β)/Bt) (9)[0125] 其中,符号“/”表示除运算符号,attraction(t)表示第t个人口所在地点的吸引力大小;At表示第t个人口所在地点的环境因素,Bt表示第t个人口所在地点的经济因素,β为人口所在地点的环境因素和经济因素的权重,0<β<1;[0126] ④建立三值FPRM电路和人口迁移遗传算法的对应关系:[0127] 人口迁移算法包含以下几个关键要素:人口所在地点、人口所在地点的吸引力、吸引力最大地点、最大吸引力、人口可移动地表空间、优惠区域、人口流动、人口迁移、人口扩散、环境因素和经济因素;[0128] 遗传算法包括两个关键因素:交叉操作和变异操作;[0129] 三值FPRM电路面积和功耗综合优化包含以下几个关键要素:极性、相应极性的面积和功耗之和、最佳极性、最小面积和功耗之和、可选择的极性空间、最佳极性所在区间、极性变换、极性向最佳极性所在区间跳变、跳出局部最佳极性、极性交流、极性突变、面积和功耗;[0130] 将人口所在地点映射到三值FPRM电路面积和功耗综合优化,表示为极性;将人口所在地点的吸引力映射到三值FPRM电路面积和功耗综合优化,表示为相应极性的面积和功耗之和;将吸引力最大地点映射到三值FPRM电路面积和功耗综合优化,表示为最佳极性;将最大吸引力映射到三值FPRM电路面积和功耗综合优化,表示为最小面积和功耗之和;将人口可移动地表空间映射到三值FPRM电路面积和功耗综合优化,表示为可选择的极性空间;将优惠区域映射到三值FPRM电路面积和功耗综合优化,表示为最佳极性所在区间;将人口流动域映射到三值FPRM电路面积和功耗综合优化,表示为极性变换;将人口迁移映射到三值FPRM电路面积和功耗综合优化,表示为极性向最佳极性所在区间跳变;将人口扩散映射到三值FPRM电路面积和功耗综合优化,表示为跳出局部最佳极性;将交叉操作映射到三值FPRM电路面积和功耗综合优化,表示为极性交流;将变异操作映射到三值FPRM电路面积和功耗综合优化,表示为极性突变;将环境因素映射到三值FPRM电路面积和功耗综合优化,表示为三值FPRM电路的面积S;将经济因素映射到三值FPRM电路面积和功耗综合优化,表示为三值FPRM电路的功耗;[0131] ⑤设置人口迁移遗传算法相关参数:[0132] 人口迁移遗传算法需设置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的电路;[0133] ⑥采用人口迁移遗传算法得到吸引力最大地点和最大吸引力,吸引力最大地点即为三值FPRM电路的面积和功耗最佳极性;最大吸引力即为三值FPRM电路的最小面积和功耗之和。[0134] 本实施例中,步骤⑥中采用人口迁移遗传算法得到吸引力最大地点和最大吸引力的具体过程为:[0135] ⑥-1在人口可移动地表空间内用随机函数rand()产生s个人口所在地点,将s个人口所在地点分别记为P1,P2,…,Ps,分别以P1,P2,…,Ps为中点,按人口所在区域的半径确定s个人口所在区域;[0136] ⑥-2通过吸引力函数计算第v个人口所在地点Pv的吸引力,v=1,2,3,…,s,得到人口所在地点P1,P2,…,Ps的吸引力;[0137] ⑥-3比较人口所在地点P1,P2,…,Ps的吸引力,筛选出吸引力最大的人口所在地点作为吸引力最大地点,记录吸引力最大地点和最大吸引力;[0138] ⑥-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()为随机函数;[0139] ⑥-5按照步骤⑥-2~⑥-3对人口所在地点P1,P2,…,Ps进行处理,得到吸引力最大地点和最大吸引力;[0140] ⑥-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'更新进行交叉操作的两个人口所在地点;[0141] ⑥-7按照步骤⑥-2~⑥-3对人口所在地点P1,P2,…,Ps进行处理,得到吸引力最大地点和最大吸引力;[0142] ⑥-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;[0143] ⑥-9按照步骤⑥-2~⑥-3对人口所在地点P1,P2,…,Ps进行处理,得到更新后的吸引力最大地点和最大吸引力;[0144] ⑥-10进行人口迁移:以步骤⑥-9中的吸引力最大地点为中点,按人口所在区域半径Δt的大小确定优惠区域,在优惠区域内用随机函数rand()产生s个人口所在地点,将此时得到的s个人口所在地点对人口所在地点P1,P2,…,Ps再次进行更新;[0145] ⑥-11按照步骤⑥-2~⑥-3对人口所在地点P1,P2,…,Ps进行处理,得到吸引力最大地点和最大吸引力;[0146] ⑥-12重复步骤⑥-6~⑥-9;[0147] ⑥-13收缩优惠区域:令Δt'=(1-c)*Δt,采用Δt'更新Δt;重复步骤⑥-10~⑥-12,直到Δt[0148] ⑥-14当收缩优惠区域到一定程度Δt[0149] ⑥-15将最后一次得到的吸引力最大地点和最大吸引力输出,吸引力最大地点即为三值FPRM电路的最佳极性;最大吸引力即为三值FPRM电路的最小面积和功耗之和(面积和功耗之和的最小值)。[0150] 本发明的三值FPRM电路面积与功耗最佳极性搜索方法在Windows 7 64位操作系统,Intel(R)Core(TM)i3-2130 CPU 3.40GHZ,4G RAM运行环境下,用C语言通过VC6.0编译实现,采用10个MCNC Benchmark电路进行仿真验证,优化结果与整体退火遗传算法比较。[0151] 为计算三值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)}。通过对MCNC Benchmark电路测试表明,对三值FPRM电路具有较好的优化效果。三值FPRM电路面积和功耗最佳极性搜索结果如表1所示。表1中,列1表示电路名称;列2分别指出电路输入变量个数;列3、列4、列5、列6和列7依次分别表示整体退火遗传算法搜索到的最佳极性、模3加运算数量和模3乘运算数量、功耗以及算法的运行时间;列8、列9、列10、列11和列12依次分别表示本发明的方法搜索到的最佳极性、模3加运算和模3乘运算数量、功耗以及算法的运行时间。[0152] 表1基于PMGA的三值FPRM电路面积与功耗优化仿真结果[0153][0154] 与整体退火遗传算法相比,本发明的方法面积、功耗和时间上节省的百分比如表2所示。面积、功耗和时间节省的百分比定义如下:[0155][0156][0157][0158] 其中,SaveArea、SavePower和SaveTime依次分别表示面积、功耗和算法运行时间的节省;AreaWAGA和PowerWAGA依次分别表示整体退火遗传算法搜索到的最佳极性下电路的面积和功耗;AreaPMGA、和PowerPMGA依次分别表示本发明的方法搜索到的最佳极性下电路的面积和功耗;TimeWAGA和TimePMGA依次分别表示整体退火遗传算法和本发明的方法的运行时间。[0159] 表2三值FPRM电路面积、功耗和时间节省百分比[0160][0161] 分析表2数据可知,与整体退火遗传算法相比,本文所提方法优化效果明显,10个测试电路的面积平均节省13.33%,功耗平均节省20.00%,时间平均节省64.96%。