基于矩形覆盖的FPRM电路多级面积优化
|
摘要
Reed-Muller(RM)逻辑因其优越的性能而广泛应用于数字电路,本文提出一种固定极性RM(FixedPolarityRM,FPRM)逻辑函数的多级优化方法.首先将电路表示成XOR/AND形式的FPRM逻辑函数,再计算函数的kernels和co-kernels,并由其生成矩阵,然后从矩阵中搜索尽可能多的矩形覆盖,利用矩阵分块和贪心策略逐步提取公共变量,最后生成多级逻辑表达式.MCNC Benchmarks测试后的结果表明,本方法得到的表达式比原RM逻辑表达式减少66%的文字(literals)数目,比onset表方法的优化结果减少19%.
Reed-Muller(RM) logic is widely used in digital circuits for its superior performance. A multi-level optimization method for Fixed Polarity RM(FPRM) logic function is proposed in this paper. First, logic circuits are converted into FPRM logic function in XOR/AND form. Next, the kernels and co-kernels of the function are calculated to generate a matrix. Then rectangular overlays are searched for in the matrix, in which process the matrix partition and greedy strategy are used to gradually extract the public variables. Finally, the multi-level logic expressions are generated. The results tested using the MCNC Benchmarks show that the number of literals obtained by the proposed method is 66% less than that of polarity optimization, and 19% less than that of the onset table method.
Reed-Muller(RM) logic is widely used in digital circuits for its superior performance. A multi-level optimization method for Fixed Polarity RM(FPRM) logic function is proposed in this paper. First, logic circuits are converted into FPRM logic function in XOR/AND form. Next, the kernels and co-kernels of the function are calculated to generate a matrix. Then rectangular overlays are searched for in the matrix, in which process the matrix partition and greedy strategy are used to gradually extract the public variables. Finally, the multi-level logic expressions are generated. The results tested using the MCNC Benchmarks show that the number of literals obtained by the proposed method is 66% less than that of polarity optimization, and 19% less than that of the onset table method.
引文
[1]符强,汪鹏君,王铭波,等.求解FPRM电路极性优化问题的改进多目标粒子群算法[J].计算机辅助设计与图形学学报,2018,30(3):540-548.
[2]He Z X,Xiao L M,Gu F,et al.An efficient and fast polarity optimization approach for mixed polarity ReedMuller logic circuits[J].Frontiers of Computer Science,2017,11(4):728-742.
[3]Al Jassani B A,Urquhart N,Almaini A E A.Manipulation and optimisation techniques for Boolean logic[J].IETComputers&Digital Techniques.2010,4(3):227-239.
[4]王玉花,王伦耀,夏银水.基于不相交项并行列表技术的FPRM实现[J].电子与信息学报,2014,36(9):2258-2264.
[5]Apangshu D,Sambhu N P.Thermal aware FPRM based AND-XOR network synthesis of logic circuits[C].IEEE2nd International Conference on Recent Trends in Information Systems,2015:497-502.
[6]李辉,汪鹏君,王振海.混合极性列表技术及其在MPRM电路面积优化中的应用[J].计算机辅助设计与图形学学报,2011,32(3):527-533.
[7]卜登立.基于混合遗传算法的MPRM最小化[J].浙江大学学报(理学版),2016,43(2):184-189.
[8]符强,汪鹏君,童楠,等.基于多策略离散粒子群算法的MPRM电路延时与面积优化[J].电子学报,2016,44(5):1202-1207.
[9]Xia Y S,Wang L Y,Meng Y,et al.Onset based optimization of multi-level mixed polarity Reed-Muller Functions[C].Proceedings of the 5th WSEAS International Conference on Instrumentation,Measurement,Circuits and Systems,2006:246-251.
[10]Wang L Y,Xia Y S.A fast algorithm for multi-level mixed-polarity Reed-Muller functions optimization[C].11th IEEE International Conference on Communication Technology,2008:509-512.
[11]Wang L Y,Xia Y S,Chen X X,et al.Reed-Muller function optimization techniques with onset table[J].Journal of Zhejiang University Science C:Computer&Electronics,2011,12(4):288-296.
[12]Papakonstantinou G.A parallel algorithm for minimizing ESOP expressions[J].Journal of Circuits Systems&Computers,2014,23(1):72-85.
[13]Papakonstantinou G.Exclusive or sum of complex terms expressions minimization[J].Integration,the VLSIJournal,2017,56:44-52.
[14]Zhang Q W,Wang P J,Hu J,et al.Cube-based synthesis of ESOPs for large functions[J].Chinese Journal of Electronics,2018,27(3):527-534.
[15]Brayton R K,Redull R,Vincentelli A S.MIS:A multiplelevel logic optimization system[J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,1987,6(6):1062-1081.
[16]Brayton R K,Hachtel G,Vincentelli A S.Multilevel logic synthesis[J].Proceedings of the IEEE,1990,78(2):264-300.
[2]He Z X,Xiao L M,Gu F,et al.An efficient and fast polarity optimization approach for mixed polarity ReedMuller logic circuits[J].Frontiers of Computer Science,2017,11(4):728-742.
[3]Al Jassani B A,Urquhart N,Almaini A E A.Manipulation and optimisation techniques for Boolean logic[J].IETComputers&Digital Techniques.2010,4(3):227-239.
[4]王玉花,王伦耀,夏银水.基于不相交项并行列表技术的FPRM实现[J].电子与信息学报,2014,36(9):2258-2264.
[5]Apangshu D,Sambhu N P.Thermal aware FPRM based AND-XOR network synthesis of logic circuits[C].IEEE2nd International Conference on Recent Trends in Information Systems,2015:497-502.
[6]李辉,汪鹏君,王振海.混合极性列表技术及其在MPRM电路面积优化中的应用[J].计算机辅助设计与图形学学报,2011,32(3):527-533.
[7]卜登立.基于混合遗传算法的MPRM最小化[J].浙江大学学报(理学版),2016,43(2):184-189.
[8]符强,汪鹏君,童楠,等.基于多策略离散粒子群算法的MPRM电路延时与面积优化[J].电子学报,2016,44(5):1202-1207.
[9]Xia Y S,Wang L Y,Meng Y,et al.Onset based optimization of multi-level mixed polarity Reed-Muller Functions[C].Proceedings of the 5th WSEAS International Conference on Instrumentation,Measurement,Circuits and Systems,2006:246-251.
[10]Wang L Y,Xia Y S.A fast algorithm for multi-level mixed-polarity Reed-Muller functions optimization[C].11th IEEE International Conference on Communication Technology,2008:509-512.
[11]Wang L Y,Xia Y S,Chen X X,et al.Reed-Muller function optimization techniques with onset table[J].Journal of Zhejiang University Science C:Computer&Electronics,2011,12(4):288-296.
[12]Papakonstantinou G.A parallel algorithm for minimizing ESOP expressions[J].Journal of Circuits Systems&Computers,2014,23(1):72-85.
[13]Papakonstantinou G.Exclusive or sum of complex terms expressions minimization[J].Integration,the VLSIJournal,2017,56:44-52.
[14]Zhang Q W,Wang P J,Hu J,et al.Cube-based synthesis of ESOPs for large functions[J].Chinese Journal of Electronics,2018,27(3):527-534.
[15]Brayton R K,Redull R,Vincentelli A S.MIS:A multiplelevel logic optimization system[J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,1987,6(6):1062-1081.
[16]Brayton R K,Hachtel G,Vincentelli A S.Multilevel logic synthesis[J].Proceedings of the IEEE,1990,78(2):264-300.