基于二叉树的Verilog多路分支语句综合算法

Binary tree-based synthesis algorithm for Verilog case statement

Verilog多路分支语句是硬件描述语言的一种条件语句,在处理器、网络交换和数字信号处理等领域应用广泛,且可通过数据选择器(Multiplexer,MUX)实现资源的极低消耗.现有基于And-Inverter Graph结构的综合工具ABC无法有效综合此类电路.因此,提出了一种新型逻辑网络表达形式MAIG(MUX-And-Inverter Graph),针对Verilog多路分支语句中的显式电路给出了基于二叉树的综合算法.为提高算法的运行效率以及综合质量,首先提取电路特征参数并进行矩阵列变换,进而实现MUX门的个数和层级减少;然后根据矩阵的0、1取值,通过二叉树优化算法划分矩阵递归生成面积小、时延低的MAIG.与学术界综合工具ABC相比,所提算法在工艺映射前电路逻辑门的个数和深度平均优化72%和52%,工艺映射后电路面积和时延平均改善67%和33%.

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.