基于层次化结构划分重组的多线程综合优化方法

1.本发明属于数字电路
技术领域：
：，具体涉及基于层次化结构划分重组的多线程综合优化方法。
背景技术：
：：2.逻辑综合是将用户设计的逻辑函数(即布尔代数)映射到标准器件库中的器件。逻辑综合主要包括逻辑优化和工艺映射两部分。逻辑优化是指对门级网表进行优化，消除冗余逻辑。工艺映射则是将经逻辑优化后的门级网表转化为对应工艺的库单元。3.模块(module)是电路设计中最基本的概念，代表了一个功能。每个设计系统都由若干module组成。现代的大规模集成电路都是层次化多模块设计。电路规模则可达百亿晶体管。传统的方法是将整个设计打平(flatten)至顶层模块，并对顶层模块进行综合优化。但这一方法已经很难处理超大规模的设计。目前常用的方法是保留用户设计的原始层次化结构，采用多线程方法进行多模块并行综合优化，但其缺点是综合结果对比传统方法有较大下降，综合时间没有得到很大改善。上述两种方法都难以满足现代设计的需要。本发明提出了一种基于层次化结构划分重组的多线程综合优化方法，在提升综合速度的同时保证优化质量，较好地解决了超大规模设计的综合问题。4.专有名词解释：5.逻辑综合：将用户设计的逻辑函数(即布尔代数)映射到标准器件库中的器件的过程；6.多线程：多线程技术指对于高并行度任务，同时使用多个线程进行计算，从而达到加速的目的；7.模块打平：将一个子模块合并至上层调用模块；8.模块划分：将一个模块划分为一系列子模块，并保证划分前后等价；9.兰特规则(rent’srule)：一个电路模块的输入输出端口数量与逻辑门数量的指数关系规则：p＝knr，其中p为端口数，n为逻辑单元数，k为系数，r为兰特指数。技术实现要素：10.本发明的目的在于提出一种基于层次化结构划分重组的多线程综合优化方法，以提升综合速度、保证优化质量。11.本发明通过对用户设计的层次结构进行模块划分与重组，生成大小比较均匀的多模块层次，再使用多线程调度算法对多个模块进行综合，实现对超大规模电路的高性能综合，解决目前国内外先进综合工具都难以处理的超大规模设计问题。12.本发明提出的基于层次化结构划分重组的多线程综合优化方法，具体步骤为：13.(一)将用户设计的硬件描述语言(hdl)文件，通过rtl综合,生成层次化结构模块，并转换成一个与工艺无关的门级网表；14.(二)采用跨模块全局优化算法对步骤(一)生成的门级网表进行跨模块全局优化；15.(三)采用层次化结构的部分打平算法对步骤(二)优化的网表进行部分打平操作，去除过小或逻辑深度过浅的子模块；16.(四)采用模块划分算法对步骤(三)生成的网表中的超大模块进行主动划分，生成大小较为均匀的子模块；17.(五)采用多线程调度算法进行多模块多线程并行逻辑优化和工艺映射。18.本发明中，涉及三个关键技术：面向层次化电路的跨模块全局优化算法、层次化结构重组算法以及多线程调度算法；下面分别作具体说明。19.步骤(二)中所述跨模块全局优化算法。20.主要包括进行常数消除、逻辑门逻辑简化与冗余逻辑门消除优化；在层次化设计中，算法从最顶层模块的输入端口开始遍历所有的线网；如果一个线网为常数信号(vcc或gnd)，分析这个线网连接的逻辑门是否可以简化，如何使简化后的逻辑门输出变为常数；然后进一步分析简化其连接的逻辑门；如果一个常数信号输出到一个实例单元(instance)上，则对这个实例单元的电路模块做一对一处理，生成只绑定这个实例单元的电路模块，并将这个常数信号传递到这个电路模块的对应输入端口上做进一步常数优化。21.该算法将不断进行常数信号传递与逻辑门简化，直到没有任何逻辑门可以简化为止。其中，常数信号传递可以跨模块层级，从而在层次化网表上实现全局优化。22.步骤(三)中所述部分打平算法。23.目前随着电路设计的规模越来越大，将电路用单一模块实现已不再适用，绝大部分设计都由一个顶层模块和多个子模块构成；对于原本用户设计的层次化结构，其中那些过小或平均逻辑深度较浅的子模块都不利于最终逻辑综合的质量；而且如果存在过多很小的模块，也会增加创建、关闭线程以及线程切换的开销，从而降低多线程逻辑综合的总体效率，所以，本发明对这些过小或平均逻辑深度较浅的子模块执行打平操作，具体算法如下：24.(1)遍历整个网表，为了避免重复，这里采用自下而上的遍历方式；对于每个模块，本算法采用逻辑门字符数量ln以及平均逻辑深度参数k分别来评估其规模以及平均逻辑深度；k的计算公式为：[0025][0026]式中，input_num和output_num分别表示该模块的输入/输出端口数量；[0027](2)对于ln小于φ1，或k值小于φ2的模块，调用flatten函数将其打平至上一层级；这里φ1为经验值，可以根据用户电路设计大小灵活取定，建议取值范围为1000-20000；在本发明中该参数取值可为1000；φ2为经验值，可以根据用户电路设计类型不同灵活取定，建议取值范围为1-10；在本发明中该参数可取值为5。[0028]层次化结构的部分打平算法的伪代码见附件1。[0029]步骤(四)中所述模块划分算法。[0030]经过层次化结构的部分打平算法处理后，网表中过小的模块已被全部打平到上级模块中，此时网表中可能会存在一些模块，其逻辑门数量远大于其它模块。这些过大的模块会导致其综合优化时间远超其它模块的综合优化时间，影响多线程算法的加速效果。因此，本发明提出一个主动模块划分算法，将这些过大的逻辑模块划分成若干大小较为均匀的模块，提升多线程加速效果。模块划分算法采用mffc划分算法与基于连接度的聚类算法，按照兰特规则的原则避免划分连接关系多的逻辑门，从而保证模块划分不对优化效果产生较大影响。这样，既能提升多线程优化加速效果，又能保证优化质量。[0031]本发明采用的模块划分算法，具体步骤为：[0032](1)将逻辑门以mffc(maxfanout-freecone)为基准生成初始簇，即小规模的划分，对于其他元件则单个元件生成簇；[0033](2)统计各个簇间的连接关系(各个簇间相连线的数量)，并生成一个连接关系图cm(connectivitymap)；[0034](3)在初始簇中选取一个最大的簇(即逻辑门的数量最多)；[0035](4)检查目前簇的规模是否足够大，是则进入到流程(5)，不是则将其与连接最紧密的簇合并，并同时合并这两个簇各自的连接关系统计表；[0036](5)判断是否所有的初始簇都合并完毕，不是，则重复步骤(3)，是则退出划分；[0037](6)根据划分结果生成新的模块以及层次结构。[0038]模块划分算法的伪代码见附件2；算法流程图见图2；算法示意图见图3，图4。[0039]本发明提出了一种适用于多线程加速的逻辑综合流程，同时又设计了一种对过大规模模块进行快速划分的算法，将二者结合，进一步加速了整个逻辑综合的运行速度，缩短运行时间的同时也保证了较好的优化效果。[0040]步骤(五)中所述多线程计算调度算法，述根据模块的逻辑门数量从大到小进行排序；而后，每个模块分配一个线程进行综合优化运算；对于给定的线程数量mt，从模块队列里选出mt个模块并分配mt个线程进行综合优化运行；到一个线程完成后，选一个新的未处理模块并分配一个新的线程；调度算法将执行这一过程直到所有模块都完成综合优化运算。[0041]本发明设计了适用于多线程加速的逻辑综合流程，同时又设计了对过大规模模块进行快速划分的算法，将二者结合，进一步加速了整个逻辑综合的运行速度，缩短运行时间的同时也保证了较好的优化效果。附图说明[0042]图1为本发明多线程综合优化方法流程图。[0043]图2为模块划分重组算法流程图。[0044]图3为模块划分示意图。[0045]图4为模块重组示意图。具体实施方式[0046]本发明提出了基于层次化结构模块划分重组算法。层次化结构划分重组的具体流程是：遍历整个网表，对于网表中的每个模块，采用literal数量(其逻辑函数所占用的字节大小)与元件数量来衡量其规模。对于literal数量或元件数量过小的模块，将其直接打平。对于中等规模的模块，则保留不做处理。对于过大规模的模块，采用聚类划分算法对其进行划分，划分后，生成新的模块以及层次化结构。这些新模块的大小规模都比较接近。最后，将这些模块并行进行后续的逻辑优化及工艺映射处理。[0047]表1和表2为本发明方案的实验结果(4线程)与baseline(baseline是一个工业界fpga综合软件)综合结果的对比。测试例子是一组数万到数百万lut规模的开源测试集。表中baseline一栏为baseline软件运行的结果，ours-mt4是本发明方案在8线程下的运行结果。表1使用baseline默认综合流程(整个网表打平到顶层模块中，然后对顶层模块再做逻辑优化和工艺映射)的结果作为参考，对比结果显示：在面积相当(0.19％)的情况下运行速度比原先快34.81倍，同时时序性能也有1.25％的改善。表2是baseline使用8线程层次化综合的结果。对比结果显示：在面积相当(-0.74％)的情况下运行速度比原先快6.7倍，同时时序性能也有2.9％的改善。[0048]以上具体实施方式是对本发明提出的快速逻辑综合解决方案的具体支持，不能以此限定本发明的保护范围，凡是按照本发明提出的技术思想，在本技术方案基础上所做的任何等同变化或等效的改动，均仍属于本发明技术方案保护的范围。[0049]table1：synthesisresultsofbaseline1andours[0050][0051]table2：synthesisresultsofbaseline2andours[0052][0053]附件1：层次化结构部分打平算法伪代码[0054][0055]附件2：模块划分算法的伪代码当前第1页12当前第1页12
技术特征：
1.一种基于层次化结构划分重组的多线程综合优化方法，其特征在于，具体步骤为：(一)将用户设计的硬件描述语言(hdl)文件，通过rtl综合,生成层次化结构模块，并转换成一个与工艺无关的门级网表；(二)采用跨模块全局优化算法对步骤(一)生成的门级网表进行跨模块全局优化；(三)采用层次化结构的部分打平算法对步骤(二)优化的网表进行部分打平操作，去除过小或逻辑深度过浅的子模块；(四)采用模块划分算法对步骤(三)生成的网表中的超大模块进行主动划分，生成大小较为均匀的子模块；(五)采用多线程调度算法进行多模块多线程并行逻辑优化和工艺映射。2.根据权利要求1所述的多线程综合优化方法，其特征在于，步骤(二)中所述跨模块全局优化算法，包括进行常数消除、逻辑门逻辑简化与冗余逻辑门消除优化；具体从最顶层模块的输入端口开始遍历所有的线网；如果一个线网为常数信号(vcc或gnd)，分析这个线网连接的逻辑门是否可以简化，如何使简化后的逻辑门输出变为常数；然后进一步分析简化其连接的逻辑门；如果一个常数信号输出到一个实例单元上，则对这个实例单元的电路模块做一对一处理，生成只绑定这个实例单元的电路模块，并将这个常数信号传递到这个电路模块内部的对应输入端口上进一步进行常数优化；不断进行常数信号传递与逻辑门简化，直到没有任何逻辑门可以简化为止。3.根据权利要求2所述的多线程综合优化方法，其特征在于，步骤(三)中所述部分打平算法，具体流程如下：(1)遍历整个网表，对于每个模块，采用逻辑门字符数量ln以及平均逻辑深度参数k分别来评估其规模以及平均逻辑深度；k的计算公式为：式中，input_num和output_num分别表示该模块的输入/输出端口数量；(2)对于ln小于φ1，或k值小于φ2的模块，调用flatten函数将其打平至上一层级；这里φ1为经验值，根据用户电路设计大小灵活取定，取值范围为1000-20000；φ2为经验值，根据用户电路设计类型不同取定，取值范围为1-10。4.根据权利要求3所述的多线程综合优化方法，其特征在于，步骤(四)中所述模块划分算法，具体流程为：(1)将逻辑门以mffc为基准生成初始簇，即小规模的划分，对于其他元件则单个元件生成簇；(2)统计各个簇间的连接关系，即各个簇间相连线的数量，存至cm中；(3)在初始簇中选取一个最大的簇，即即逻辑门的数量最多的簇；(4)检查目前簇的规模是否足够大，是则进入到流程(5)，不是则将其与连接最紧密的簇合并，并同时合并这两个簇各自的连接关系统计表；(5)判断是否所有的初始簇都合并完毕，不是，则重复步骤(3)，是则退出划分；(6)根据划分结果生成新的模块以及层次结构。5.根据权利要求4所述的多线程综合优化方法，其特征在于，步骤(五)中所述多线程计算调度算法，是根据模块的逻辑门数量从大到小进行排序，然后，每个模块分配一个线程进
行综合优化运算；具体地，对于给定的线程数量mt，从模块队列里选出mt个模块并分配mt个线程进行综合优化运行；一个线程完成后，选一个新的未处理模块并分配一个新的线程；执行这一过程直到所有模块都完成综合优化运算。

技术总结
本发明属于数字电路技术领域，具体为基于层次化结构划分重组的多线程综合优化方法。本发明首先对用户设计进行RTL综合，生成层次化结构模块；然后对生成的层次化结构进行划分与重组，生成大小比较均匀的多模块层次化结构；最后利用多线程调度算法同时对多个模块进行综合。本发明的关键在于提出了有效的层次化划分重组算法，对于超大规模集成电路，在保证优化效果的同时,大大提高了优化速度，从而提高了芯片开发与测试的效率。了芯片开发与测试的效率。了芯片开发与测试的效率。


技术研发人员：吴昌 张一山
受保护的技术使用者：复旦大学
技术研发日：2023.05.13
技术公布日：2023/8/14