基于Majority逻辑门映射的电路面积优化
PDF下载 (569)吴达斌,王伦耀,夏银水.基于Majority逻辑门映射的电路面积优化[J].宁波大学学报(理工版),2019,32(1):26-31.DOI:
WU Da-bin,WANG Lun-yao,XIA Yin-shui.Area optimization using Majority logic gate mapping[J].Journal of Ningbo University(Natural Science & Engineering Edition),2019,32(1):26-31.DOI:
| Title: | Area optimization using Majority logic gate mapping |
| 作者: | 吴达斌, 王伦耀, 夏银水 |
| Author(s): | WU Da-bin, WANG Lun-yao, XIA Yin-shui |
| 关键词: | Majority逻辑门; 映射算法; 逻辑优化 |
| Keywords: | Majority logic gate; mapping algorithm; logic optimization |
| 分类号: | TP331 |
| 文献标识码: | A |
| 摘要: | 提出了一种采用三输入Majority逻辑门(M门)和反相器实现电路逻辑功能的电路面积优化算法. 该算法首先用动态规划策略完成电路的AIG(And-Inverter Graph)切割, 然后通过搜索适合M门覆盖的AIG子结构以及与门和M门之间的等效替代, 将AIG转换为适合M门映射的MIG (Majority-Inverter Graph), 最后用Ω法则和Ψ法则对MIG进行简化, 得到节点数更少的MIG, 从而实现基于M门映射的电路面积优化. 优化算法用C语言实现, 并用MCNC电路测试. 结果表明, 相比于逻辑综合工具ABC的结果, 用M门映射后电路面积可得到平均约12%左右的优化. |
| Abstract: | An area optimization algorithm for logic circuits using 3-inputs Majority logic gate (M gate) and inverter mapping is proposed in this paper. By cutting the AIG with a data structure for logic circuit into sub-AIGs, searching the patterns in sub-AIGs which is suitable for M gate mapping and replacing the “AND” nodes with M nodes, the algorithm converts an AIG to an MIG (Majority-Inverter Graph). Furthermore, by employing the Ω and Ψ rules, a more compacted MIG with fewer nodes is obtained, which facilitates further area reduction. The proposed algorithm is implemented in C programming language and tested under MCNC benchmarks. The experimental results show that compared with the result of ABC, the average area reduction of the tested circuits is about 12% using the M gates mapping. |
| 参考文献 /References: | [1] De Marchi M, Sacchetto D, Frache S, et al. Polarity control in double-gate, gate-all-around vertically stacked silicon nanowire FETs[EB/OL]. [2017-10-15]. https://si2.epfl.ch/~demichel/publications/archive/2012/S08P04.pdf. [2] Marchi M D, Zhang J, Frache S, et al. Configurable logic gates using polarity-controlled silicon nanowire gate-all-around FETs[J]. IEEE Electron Device Letters, 2014, 35(8):880-882. [3] Appenzeller J. Carbon nanotubes for high-performance electronics: Progress and prospect[J]. Proceedings of the IEEE, 2008, 96(2):201-211. [4] Yang H, Heo J, Park S, et al. Graphene barristor, a triode device with a gate-controlled Schottky barrier[J]. Science, 2012, 336(6085):1140-1143. [5] Li S L, Miyazaki H, Lee M V, et al. Complementary-like graphene logic gates controlled by electrostatic doping[J]. Small, 2011, 7(11):1552-1556. [6] Fackenthal R, Kitagawa M, Otsuka W, et al. 19.7 A 16Gb ReRAM with 200 MB/s write and 1 GB/s read in 27 nm technology[C]. IEEE, Solid-State Circuits Conference Digest of Technical Papers, 2014:338-339. [7] Amlani I, Orlov A O, Toth G, et al. Digital logic gate using quantum-dot cellular automata[J]. Science, 1999, 284(5412):289-291. [8] Cornil J, Brédas J, Zaumseil J, et al. Ambipolar transport in organic conjugated materials[J]. Advanced Materials, 2010, 19(14):1791-1799. [9] Gaillardon P E, Micheli G D. Majority-inverter graph: A novel data-structure and algorithms for efficient logic optimization[C]. ACM Design Automation Conference, 2014:1-6. [10] Amaru L, Gaillardon P E, Micheli G D. Majority-inverter graph: A new paradigm for logic optimization[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2016, 35(5):806-819. [11] Amaru L, Petkovska A, Gaillardon P E, et al. Majority-inverter graph for FPGA synthesis[C]. The Workshop on Synthesis & System Integration of Mixed Information Technologies, 2015. [12] 岑旭梦, 王伦耀, 夏银水. 基于逻辑复合门映射的电路面积优化[J]. 宁波大学学报(理工版), 2016, 29(4):38-43. [13] 岑旭梦, 王伦耀, 夏银水, 等. Library-free映射在电路面积优化中的应用[J]. 计算机辅助设计与图形学学报, 2017, 29(11):2147-2152. [14] Soeken M, Roetteler M, Wiebe N, et al. Design automation and design space exploration for quantum computers[EB/OL]. [2017-05-10]. http://www.microsoft.com/en-us/research/wp-content/uploads/2017/05/1612.00631.pdf. [15] Chen Y C, Wang C Y. Logic restructuring using node addition and removal[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2012, 31(2):260-270. [16] Berkeley Logic Synthesis and Verification Group. ABC: A system for sequential synthesis and verification[EB/OL]. [2017-04-12]. https://bitbucket.org/alanmi/abc. |
| 备注/Memo: | 收稿日期: 2018－01－16. 宁波大学学报（理工版）网址: http://journallg.nbu.edu.cn/基金项目: 国家自然科学基金（61471211）.第一作者: 吴达斌（1993－）, 男, 安徽宿松人, 在读硕士研究生, 主要研究方向: 逻辑综合与优化. E-mail: 1611082561@nbu.edu.cn*通信作者: 王伦耀（1972－）, 男, 浙江宁波人, 教授, 主要研究方向: 逻辑综合与优化. E-mail: wanglunyao@nbu.edu.cn 宁波大学学报（理工版）网址：http://journallg.nbu.edu.cn/ |
