基于矩形覆盖的FPRM电路多级面积优化
PDF下载 (331)陈治文,张会红,汪鹏君,张跃军,张晓伟.基于矩形覆盖的FPRM电路多级面积优化[J].宁波大学学报(理工版),2019,32(4):32-37.DOI:
CHEN Zhiwen,ZHANG Huihong,WANG Pengjun,ZHANG Yuejun,ZHANG Xiaowei.Rectangular overlays based multi-level area optimization of FPRM circuit[J].Journal of Ningbo University(Natural Science & Engineering Edition),2019,32(4):32-37.DOI:
| Title: | Rectangular overlays based multi-level area optimization of FPRM circuit |
| 作者: | 陈治文, 张会红, 汪鹏君, 张跃军, 张晓伟 |
| Author(s): | CHEN Zhiwen, ZHANG Huihong, WANG Pengjun, ZHANG Yuejun, ZHANG Xiaowei |
| 关键词: | 逻辑优化; Reed-Muller函数; 多级 |
| Keywords: | Kernels; logic optimization; Reed-Muller function; multi-level |
| 分类号: | TN41 |
| 文献标识码: | A |
| 摘要: | Reed-Muller(RM)逻辑因其优越的性能而广泛应用于数字电路, 本文提出一种固定极性RM(Fixed Polarity RM, FPRM)逻辑函数的多级优化方法. 首先将电路表示成XOR/AND形式的FPRM逻辑函数, 再计算函数的kernels和co-kernels, 并由其生成矩阵, 然后从矩阵中搜索尽可能多的矩形覆盖, 利用矩阵分块和贪心策略逐步提取公共变量, 最后生成多级逻辑表达式. MCNC Benchmarks测试后的结果表明, 本方法得到的表达式比原RM逻辑表达式减少66%的文字(literals)数目, 比onset表方法的优化结果减少19%. |
| Abstract: | 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. |
| 参考文献 /References: | [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 Reed-Muller 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]. IET Computers & 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]. IEEE 2nd 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 VLSI Journal, 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 multiple-level 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. |
| 备注/Memo: | 收稿日期: 2019－01－21. 宁波大学学报（理工版）网址: http://journallg.nbu.edu.cn/基金项目: 国家自然科学基金（61871244, 61704094）; 宁波市自然科学基金（2018A610039）; 宁波大学研究生科研创新基金.第一作者: 陈治文（1993－）, 男, 安徽池州人, 在读硕士研究生, 主要研究方向: 集成电路逻辑优化. E-mail: 1184369543@qq.com*通信作者: 张会红（1976－）, 女, 河北定州人, 博士/副教授, 主要研究方向: 低功耗、高信息密度集成电路. E-mail: zhanghuihong@nbu.edu.cn 宁波大学学报（理工版）网址：http://journallg.nbu.edu.cn/ |
