一种利用穷举法的三值FPRM电路功耗优化方法

摘要

本发明公开了一种利用穷举法的三值FPRM电路功耗优化方法，首先将三值FPRM电路采用p极性下的三值FPRM逻辑函数进行表示，然后分解三值FPRM逻辑函数中含有的多输入运算，得到p极性下的多个二输入模3加门和多个二输入模3乘门，将二输入模3加门和二输入模3乘门引起的功耗作为p极性下的三值FPRM电路的功耗，构建得到三值FPRM电路的功耗估计模型，最后采用穷举法对三值FPRM电路进行功耗最佳极性搜索，搜索得到三值FPRM电路的最小功耗和功耗最佳极性；优点是可实现三值FPRM电路的功耗优化；随机采用13个MCNC Benchmark电路进行仿真验证，本发明搜索到的最佳极性与0极性比较，模3加门数量平均节省54.94％，模3乘门数量平均节省46.89％，功耗平均节省72.72％，功耗优化效果显著。

主权项

一种利用穷举法的三值FPRM电路功耗优化方法，其特征在于包括如下步骤：①建立三值FPRM电路的功耗估计模型：①‑1将三值FPRM电路采用三值FPRM逻辑函数表示为如下形式：$f^p(x_{n-1},x_{n-2},\mathrm{...},x_0)=\oplus \underset{i=0}{\overset{3^n-1}{\Sigma }}{a}_i*\underset{j=0}{\overset{n-1}{\Pi }}{\stackrel{·}{x}}_j^{i_j}---\left(1\right)$其中,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用n位三进制形式表示为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用n位三进制形式表示为i_n‑1i_n‑2…i₀，i_j∈{0,1,2},a_i为FPRM系数；a_i∈{0,1,2}；∏表示多输入模3乘运算，的展开式为：$\underset{j=0}{\overset{n-1}{\Pi }}{\stackrel{·}{x}}_j^{i_j}={\stackrel{·}{x}}_{n-1}^{i_{n-1}}{\stackrel{·}{x}}_{n-2}^{i_{n-2}}...{\stackrel{·}{x}}_0^{i_0},$其中${\stackrel{·}{x}}_j=(x_j\oplus p_j),$${\stackrel{·}{x}}_j^0=1,{\stackrel{·}{x}}_j^1={\stackrel{·}{x}}_j,{\stackrel{·}{x}}_j^2={\stackrel{·}{x}}_j*{\stackrel{·}{x}}_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加门的数量记为N_u,u＝1,2,…,N；将第o个多输入模3乘门分解后的二输入模3乘门的数量记为W_o，o＝1,2,…,W；①‑3将p极性下的三值FPRM逻辑函数分解后得到的所有二输入模3加门和二输入模3乘门引起的功耗作为p极性下的三值FPRM电路的功耗，二输入模3加门引起的功耗采用其开关活动性表示，二输入模3乘门引起的功耗采用其开关活动性表示，门电路的开关活动性用其输出端的输出变量概率表示，二输入模3加门引起的功耗采用其输出端的输出变量概率表示，二输入模3乘门引起的功耗采用其输出端的输出变量概率表示；①‑4根据公式(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加门的两个输入变量，Pk_y1m表示第k个二输入模3加门中输入变量y1为m的概率，m∈{0,1,2}，Pk_y2m表示第k个二输入模3加门中输入变量y2为m的概率，当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乘门的两个输入变量，Qg_r1m表示第g个二输入模3乘门中输入变量r1为m的概率，Qg_r2m表示第g个二输入模3乘门中输入变量r2为m的概率；当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的概率是由随即函数产生的概率对(P1,P2)，P0＝1‑P1‑P2；P0，P1和P2分别为0到1之间某个值，P0表示输入变量为0的概率，P1表示输入变量为1的概率，P2表示输入变量为2的概率；①‑5根据二输入模3加门的输出变量概率和二输入模3乘门的输出变量概率计算三值FPRM电路的功耗，将三值FPRM电路的功耗估计模型表示为：$E_{swd}=2\left(\underset{u=1}{\overset{N}{\Sigma }}\right(\underset{k=1}{\overset{N_u}{\Sigma }}(P_1{\left(k\right)}_u+P_2{\left(k\right)}_u))+\underset{o=1}{\overset{W}{\Sigma }}\left(\underset{g=1}{\overset{W_o}{\Sigma }}\right(Q_1{\left(g\right)}_o+Q_2{\left(g\right)}_o)))---\left(8\right)$其中，E_swd表示p极性下三值FPRM电路的功耗，N为p极性下三值FPRM逻辑函数分解后的多输入模3加门的数量,W为p极性下三值FPRM逻辑函数分解后的多输入模3乘门的数量；②采用穷举法对三值FPRM电路进行功耗最佳极性搜索，得到三值FPRM电路的功耗最佳极性和该功耗最佳极性下三值FPRM电路的最小功耗。