基于二叉树的Verilog多路分支语句综合算法
PDF下载 (237)廖俊鸿,刘 森,马铖昱,储著飞*.基于二叉树的Verilog多路分支语句综合算法[J].宁波大学学报(理工版),2024,37(2):10-17.DOI:10.20098/j.cnki.1001-5132.2023.0602
LIAO Junhong,LIU Sen,MA Chengyu,CHU Zhufei.Binary tree-based synthesis algorithm for Verilog case statement[J].Journal of Ningbo University(Natural Science & Engineering Edition),2024,37(2):10-17.DOI:10.20098/j.cnki.1001-5132.2023.0602
| Title: | Binary tree-based synthesis algorithm for Verilog case statement |
| 作者: | 廖俊鸿, 刘 森, 马铖昱, 储著飞* |
| Author(s): | LIAO Junhong, LIU Sen, MA Chengyu, CHU Zhufei |
| 关键词: | Verilog多路分支语句; 数据选择器; 二叉树 |
| Keywords: | MAIG; Verilog case statement; multiplexer; binary tree |
| 分类号: | TP391.41 |
| DOI: | 10.20098/j.cnki.1001-5132.2023.0602 |
| 文献标识码: | A |
| 摘要: | Verilog多路分支语句是硬件描述语言的一种条件语句, 在处理器、网络交换和数字信号处理等领域应用广泛, 且可通过数据选择器(Multiplexer, MUX)实现资源的极低消耗. 现有基于And-Inverter graph结构的综合工具ABC无法有效综合此类电路. 因此, 提出了一种新型逻辑网络表达形式MAIG (MUX-And-Inverter Graph), 针对Verilog多路分支语句中的显式电路出了基于二叉树的综合算法. 为提高算法的运行效率以及综合质量, 首先提取电路特征参数并进行矩阵列变换, 进而实现MUX门的个数和层级减少; 然后根据矩阵的0、1取值, 通过二叉树优化算法划分矩阵递归生成面积小、时延低的MAIG. 与学术界综合工具ABC相比, 算法在工艺映射前电路逻辑门的个数和深度平均优化72%和52%, 工艺映射后电路面积和时延平均改善67%和33%. |
| Abstract: | Verilog case statements are conditional statements in the hardware description language. They are widely used in fields such as processors, network switches, and digital signal processing. They can optimize resource distribution in terms of efficiency through the use of multiplexers. However, the existing synthesis tool ABC which is based on the And-Inverter graph logic representation cannot effectively synthesize such circuits. Therefore, in this paper we propose a novel logic representation named MUX-And-Inverter graph (MAIG), and present a binary tree-based synthesis algorithm specifically for explicit circuits within Verilog case statements. In order to improve the efficiency of the algorithm and the quality of synthesis, the first step is to extract circuit feature parameters and perform matrix column transformation. The proposed process as a result reduces the number of MUX gates and levels. Next, depending on the 0 and 1 values of the matrix, a binary tree optimization algorithm is applied to partition the matrix which is implemented to recursively generate MAIG with a smaller area and smaller delay. Compared to ABC, the proposed algorithm achieves an average optimization by 72% in the number of logic gates and 52% in logic depth before technology mapping came into being. It also achieves an average improvement by 67% in circuit area and 33% in delay reduction after technology mapping became available |
| 参考文献 /References: | [1] 储著飞, 潘鸿洋. 基于布尔可满足性的精确逻辑综合综述[J]. 电子与信息学报, 2023, 45(1):14-23. [2] METZGEN P. A high performance 32-bit ALU for programmable logic[C]//Proceedings of the 2004 ACM/SIGDA 12th International Symposium on Field Programmable Gate Arrays. New York: ACM, 2004:61-70. [3] YANG C G, CIESIELSKI M, SINGHAL V. BDS: a BDD-based logic optimization system[C]//Proceedings of the 37th Annual Design Automation Conference. New York: ACM, 2000:92-97. [4] FEY G, DRECHSLER R. Minimizing the number of paths in BDDs: theory and algorithm[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2005, 25(1):4-11. [5] KOHUTKA L, PISTEK P. Faster synthesis of combinational logic based on multiplexer trees and binary decision diagrams[C]//2014 IEEE 12th IEEE International Conference on Emerging eLearning Technologies and Applications (ICETA), 2014:239-244. [6] METZGEN P, NANCEKIEVILL D. Multiplexer restructuring for FPGA implementation cost reduction [C]//Proceedings of the 42nd Annual Design Automation Conference. New York: ACM, 2005:421-426. [7] LI N S, HUANG J D, HUANG H J. Low power multiplexer tree design using dynamic propagation path control[C]//APCCAS 2008 - 2008 IEEE Asia Pacific Conference on Circuits and Systems, 2008:838- 841. [8] PISTEK P, KOLESÁR M, JELEMENSKÁ K. Optimization of multiplexer trees using modified truth table[C]//2010 International Conference on Applied Electronics, 2010:1- 4. [9] MITRA S, AVYA L J, MCCLUSKEY E J. Efficient multiplexer synthesis techniques[J]. IEEE Design & Test of Computers, 2000, 17(4):90-97. [10] BASIRI M M A, MAHAMMAD SK N. High speed multiplexer design using tree based decomposition algorithm[J]. Microelectronics Journal, 2016, 51:99-111. [11] HÁLECEK I, FISER P, SCHMIDT J. On XAIG rewriting [C]//Proceeding of 26th International Workshop on Logic & Synthesis (IWLS), Austin, 2017:89-96. [12] YU C X, CIESIELSKI M, CHOUDHURY M, et al. DAG-aware logic synthesis of datapaths[C]//Proceedings of the 53rd Annual Design Automation Conference, 2016: 1-6. [13] SOEKEN M, CHATTOPADHYAY A. Unlocking efficiency and scalability of reversible logic synthesis using conventional logic synthesis[C]//Proceedings of the 53rd Annual Design Automation Conference, 2016:1-6. [14] CHU Z F, HAASWIJK W, SOEKEN M, et al. Exact synthesis of Boolean functions in majority-of-five forms [C]//2019 IEEE International Symposium on Circuits and Systems (ISCAS), 2019:1-5. [15] BRYANT R E. Graph-based algorithms for Boolean function manipulation[J]. IEEE Transactions on Computers, 1986, 100(8):677-691. [16] MCCLUSKEY E J. Logic design principles with emphasis on testable semicustom circuits[M]. Englewood NJ: Prentice-Hall, Inc., 1986. [17] BRAYTON R, MISHCHENKO A. ABC: an academic industrial-strength verification tool[C]//International Conference on Computer Aided Verification, 2010:24-40. |
| 备注/Memo: | 收稿日期: 2023−06−09. 宁波大学学报（理工版）网址: http://journallg.nbu.edu.cn/ 基金项目: 国家自然科学基金（62274100）; 宁波市重点研发计划（2023Z071）. 第一作者: 廖俊鸿, 硕士研究生, 主要研究方向: 逻辑综合与优化. E-mail: liaojunhong5725@foxmail.com *通信作者: 储著飞, 教授, 主要研究方向: 逻辑综合与优化. E-mail: chuzhufei@nbu.edu.cn 宁波大学学报（理工版）网址：http://journallg.nbu.edu.cn/ |
