1.一种多级MPRM逻辑电路功耗优化方法,其特征在于,包括以下步骤:
步骤1、以待优化的多级MPRM逻辑电路作为输入电路,基于动态逻辑功耗关系式评估出输入电路的总功耗E,其中,pr(va)为输入电路中的节点va的跳变概率,N为输入电路中的节点总数,N≥1,k为固定系数,令k=1;
对于输入电路中的AND逻辑节点va1,其跳变概率计算公式为pr(va1)=pr(xa1)pr(ya1),其中pr(xa1)、pr(ya1)分别为逻辑节点va1的输入;
对于输入电路中的XOR逻辑节点va2,其跳变概率计算公式为pr(va2)=pr(xa2)+pr(ya2)-2pr(xa2)pr(ya2),其中pr(xa2)、pr(ya2)分别为逻辑节点va2的输入;
步骤2、定义一种子电路作为割集,割集同时满足以下两个条件:(1)任何从电路的输入节点到割集的输出节点的路径需要经过割集的至少一个节点;(2)除割集的输入节点外,其他节点的输出均在割集中;搜寻输入电路中符合上述两个条件的割集,记为割集C;基于步骤1中的动态逻辑功耗关系式评估出割集C的功耗,并记为E1;
步骤3、对割集C进行功耗优化,具体步骤如下:
步骤3-1、对于割集C中的连续AND逻辑门:
步骤3-1-1、将连续AND逻辑门中输入节点按跳变概率从小到大排列,得到节点序列A1;
步骤3-1-2、对于节点序列A1中跳变概率最小的两个节点,按步骤1中AND逻辑节点跳变概率计算公式计算其跳变概率并得到新节点,将这两个节点从节点序列A1中删除,并将新节点按计算得到的跳变概率的大小排入节点序列A1;
步骤3-1-3、重复步骤3-1-2,直到节点序列A1中只剩下一个节点;
步骤3-2、对于割集C中的连续XOR逻辑门:
步骤3-2-1、将连续XOR逻辑门中输入节点按跳变概率从小到大排列,得到节点序列A2;
步骤3-2-2、对于节点序列A2中跳变概率大于0.5的节点中跳变概率最大和最小的两个节点,按步骤1中XOR逻辑节点跳变概率计算公式计算其跳变概率并得到新节点,将这两个节点从节点序列A2中删除,将新节点按计算得到的跳变概率的大小排入节点序列A2;
步骤3-2-3、重复步骤3-2-2,直到节点序列A2中跳变概率大于0.5的节点的数量小于或等于1;
步骤3-2-4、对于节点序列A2中跳变概率最小的两个节点,按步骤1中XOR逻辑节点跳变概率计算公式计算其跳变概率并得到新节点,将这两个节点从节点序列A2中删除,并将新节点按计算得到的跳变概率的大小排入节点序列A2;
步骤3-2-5、重复步骤3-2-4,直到节点序列A2中只剩下一个节点;
步骤4、具有n个输入变量的MPRM存在n位三进制数极性P,将该n位三进制数极性P中第k位的极性记为Pk,其中0≤k<n,n≥1,Pk决定了MPRM中各输入变量xk的表现形式:当Pk=0时,允许输入变量xk以正变量形式出现或不出现;当Pk=1时,允许输入变量xk以反变量形式出现或不出现;当Pk=2时,允许输入变量xk以正变量或反变量形式出现;
由于不同极性的MPRM逻辑电路的繁简不同,基于列表法,遍历割集C对应的子电路的所有极性,寻找功耗最优的二级MPRM,具体步骤如下:步骤4-1、读取具有n个输入变量的割集C的真值表,将其展开成极性P=3n-1的二级MPRM函数,并将其转化为初始列表L0,其中初始列表L0的表栏为极性P,列表内容i由{0,1}表示;当初始列表L0中第k列的极性Pk=0时,列表内容i为0表示输入变量xk不出现,列表内容i为1表示输入变量xk以正变量形式出现;当初始列表L0中第k列的极性Pk=1时,列表内容i为0表示输入变量xk不出现,列表内容i为1表示输入变量xk以反变量形式出现;当初始列表L0中第k列的极性Pk=2时,列表内容i为0表示输入变量xk以反变量形式出现,列表内容i为1表示输入变量xk以正变量形式出现;
初始化目标极性P=0;
步骤4-2、初始化k=n-1,此时初始列表L0即为当前列表L;
步骤4-3、若Pk=2,则转至步骤4-5;若Pk=0则将当前列表L中第k列i=0的行提取出来生成临时列表L′,并使临时列表L′中第k列的i=1,转至步骤4-4;若Pk=1则将当前列表L中第k列i=1的行提取出来生成临时列表L′,并使临时列表L′中第k列的i=0,转至步骤4-4;
步骤4-4、将当前列表L中的与临时列表L′中内容相同的行删去,并将临时列表L′中的与当前列表L中内容不同的行加入当前列表L,若当前列表L中第k列的极性Pk=1,则将第k列的内容i取反,转至步骤4-5;
步骤4-5、令k=k-1,若k≥0,则转至步骤4-3,否则转至步骤4-6;
步骤4-6、对当前列表L对应的二级MPRM通过步骤3进行功耗优化,记录功耗;令P=P+1,若P<n3,则转至步骤4-2,否则转至步骤4-7;
步骤4-7、比较所有极性的割集C对应的子电路的功耗,将最小功耗记为E2,与E2对应的二级MPRM表达式即为功耗最优的二级MPRM;
步骤5、通过onset法,将极性为0的二级MPRM转化为多级MPRM,并优化其功耗,具体步骤如下:步骤5-1、将极性为0的二级MPRM转化为onset列表T,onset列表T的表栏为变量序号,列表每行的内容为极性为0的二级MPRM表达式的各个AND项,由j=0,1表示,列表每行的内容为0表示输入变量xk出现,列表每行的内容为1表示输入变量xk不出现,行与行之间为XOR关系,列与列之间为AND关系;由于AND逻辑和XOR逻辑满足交换律,故onset法的行列交换不影响其本质;由于AND逻辑和XOR逻辑满足结合律,故onset法的行列提取不影响其本质;
步骤5-2、若onset列表T中某列内容均相同,则提取该列,其在本质上看成:
记录提取后剩余的列表为当前onset列表T′;
步骤5-3、不断调整当前onset列表T′的行列,寻找面积最大的内容全为1的矩形子表ST1,将当前onset列表T′分解为:矩形子表ST1、矩形子表ST1对应的行的剩余子表ST12、剩余行所形成的子表ST2,将ST12代替当前onset列表T′,将ST2存入寄存器;
步骤5-4、若当前onset列表T′中各行内只有一个j=1,或当前onset列表T′只剩一行,则将寄存器中剩余的子表代替当前onset列表T′,并转至步骤5-2;若寄存器中无子表则onset列表优化完成,转至步骤5-5;
步骤5-5、将优化后的onset列表转化为多级MPRM表达式,并利用步骤3对多级MPRM进行功耗优化,记录功耗为E3以及与E3对应的多级MPRM表达式;
步骤6、比较功耗E1、E2、E3,将三者中最小值对应的MPRM表达式代替割集C并入输入电路;若三者中有二者的功耗值相对较小且相同,则选择这二者对应的门电路数量最少的MPRM表达式代替割集C并入输入电路;若三者的功耗值相同,则选择这三者对应的门电路数量最少的MPRM表达式代替割集C并入输入电路;若三者的功耗值和对应的门电路数量均相同,则任选一者对应的门电路数量最少的MPRM表达式代替割集C并入输入电路;
步骤7、重复步骤2~步骤6,直至输入电路中找不到任何割集,即完成对多级MPRM逻辑电路的功耗优化。