基于公共子表达式的大规模集成电路设计优化方法与流程

1.本发明属于电路数据处理的技术领域，更具体地，涉及基于公共子表达式的大规模集成电路设计优化方法。


背景技术：

2.现代大规模集成电路设计资源优化方法广泛应用于电子工程领域，其目的是在保证电路功能的前提下，优化电路设计，减少电路中所需的硬件资源，降低功耗和成本，提高电路的性能和可靠性。在实际应用中，大规模集成电路资源优化可以采用多种方法，例如：逻辑综合、布局布线、时序优化、功耗优化、面向应用的特定集成电路设计等等。随着电子工程技术的不断发展，大规模集成电路资源优化技术也在不断地进化和完善，为电子工程领域的发展做出了重要的贡献。
3.中国专利文献cn115577662a公开了一种基于多fanout逻辑的时序器件资源优化方法，基于多fanout逻辑的模块分组，通过合并多输出fanout结构，对大规模电路设计进行精简 ,遍历查找组合逻辑中模块间最低耦合度，即输入个数或输出个数最少，确定时序器件的最佳放置位置，在此位置创建最低耦合度数量个相同时序器件来减少时序器件的数量。
4.然而，随着芯片制造工艺的不断进步，集成电路设计的复杂度也在不断提高，同时，不同的设计目标之间往往也会相互制约，需要在多目标间进行权衡和决策。另一方面，随着芯片制造工艺的进步，软硬件协同设计的需求越来越强烈。与此同时，在当前电子产品以低功耗为设计目标的背景下，还应该考虑在保证电路性能的前提下，实现功耗优化的目标。为了实现大规模集成电路资源优化的目标，需要在综合考虑多种设计方法的基础上，采取有效措施来降低电路中逻辑门的数量，降低功耗和成本，同时提高电路的性能和可靠性。
5.综上，现有技术是将同一层级的器件视为整体看待，对即时序器件进行优化，而大规模集成电路资源优化设计的核心问题是综合考虑多个因素以降低电路中逻辑器件的数量、优化电路设计资源，该问题的复杂性导致了目前研究困难，需要持续探索和调研，以提高大规模集成电路设计的效率和质量。


技术实现要素：

6.本发明旨在克服上述现有技术的至少一种缺陷，提供基于公共子表达式的大规模集成电路设计优化方法，以解决现有技术在电路设计资源优化方面的不足。
7.本发明详细的技术方案如下：基于公共子表达式的大规模集成电路设计优化方法，包括以下步骤：s1、获得待分析网表，若待分析网表中存在组合逻辑器件，则进行下一步；所述组合逻辑器件是指：组合逻辑器件的输出只取决于当前的输入，与电路原本的状态无关，任何时刻，只要输入发生变化，输出会立即发生相应的变化；s2、获取待分析网表中功能类型相同的组合逻辑器件的分组；
若分组只有一个组合逻辑器件时，则无需优化，直接结束，并对下一个分组进行优化；若存在多个功能类型相同的组合逻辑器件，则根据当前组合逻辑器件组的位置，分别向输入端、输出端通过广度优先遍历方法寻找相连接的组合逻辑器件；s3、获取分组内输出端组合逻辑器件对应的输入端信号，以及输出端组合逻辑器件和输入端信号之间的连接关系；s4、计算分组内组合逻辑器件的二进制矩阵向量，二进制矩阵向量中的每一行表示一个二进制表达式方程；s5、计算二进制表达式方程中公共子表达式的出现次数，并找出出现次数最多的公共子表达式；s6、遍历所有二进制表达式方程，若二进制表达式方程中存在出现次数最多的公共子表达式，则在该二进制表达式方程中用一个新的变量代替出现次数最多的公共子表达式；若不存在，则继续遍历下一个二进制表达式方程；s7、循环s5-s6，直到在每一个二进制表达式方程中只有一个变量，或，所有二进制表达式方程不存在公共子表达式；s8、在电路中根据新的变量设置新增组合逻辑件，具体包括：s81、获得新的变量对应的输入端信号；s82、将新的变量对应的输入端信号作为新增组合逻辑件的输入，新的变量对应的输出端组合逻辑件作为新增组合逻辑件的输出指向；s9、更新电路。根据新增组合逻辑件可替换原电路中组合逻辑件，或，删除原电路中组合逻辑件，重新构建新增组合逻辑件，技术人员可根据实际需要调整更新方式。
8.进一步地，通过广度优先遍历方法获取分组内输出端与输入端组合逻辑器件之间的对应关系，具体的：从输出端组合逻辑器件出发，寻找分组内与输出端组合逻辑器件相邻且未访问的组合逻辑器件；再从组合逻辑器件出发，寻找与组合逻辑器件相邻且未访问的组合逻辑器件，直到所遍历组合逻辑器件的输入端信号所连接的组合逻辑器件不在该分组内，则记录该输出端组合逻辑器件与此输入端信号的对应关系，以及两者之间的连接关系；广度优先遍历方法的基本原则是从电路中的某个组合逻辑器件或一组组合逻辑器件开始，寻找与之相邻的且还未被访问的组合逻辑器件，所找到的组合逻辑器件数量就是访问的数量，然后将这些组合逻辑器件分别作为起点进行下一轮遍历，重复以上过程；广度优先遍历可以看作是一层一层地进行遍历，每当遍历完一层的所有组合逻辑器件时，就会继续向下一层进行遍历。这种遍历方式可以有效地查找与目标组合逻辑器件相连的所有组合逻辑器件，并且可以提高查找效率。
9.进一步地，所述变量在二进制表达式方程中指的是与输出端组合逻辑器件存在对应关系的输入端信号。
10.与现有技术相比，本发明的有益效果为：本发明提供的基于公共子表达式的大规模集成电路设计优化方法，通过遍历组合逻辑电路中的器件连接关系，构建输出组合逻辑器件与输入组合逻辑器件之间的二进制矩阵向量，并通过矩阵分析，识别出需要处理的公共子表达式，随后，在各个二进制表达式方
程中消除出现次数最频繁的公共子表达式，并将所消除的公共子表达式构建为新的模块，来实现基于公共子表达式的大规模集成电路设计优化的目标，在不影响电路功能的前提下，该方法优化了设计网表的面积，实现组合逻辑器件的资源优化，从而提高电路的性能和效率。
附图说明
11.图1是本发明所述资源优化的流程图。
12.图2是本发明实施例1中所述网表连接关系示意图。
13.图3是本发明实施例1中所述优化后网表中器件连接关系示意图。
具体实施方式
14.下面结合图与实施例对本公开做进一步说明。
15.应该指出，以下详细说明都是示例性的，旨在对本公开提供进一步的说明。除非另有指明，本文使用的所有技术和科学术语具有与本公开所属技术领域的普通技术人员通常理解的相同含义。
16.需要注意的是，这里所使用的术语仅是为了描述具体实施方式，而非意图限制根据本公开的示例性实施方式。如在这里所使用的，除非上下文另外明确指出，否则单数形式也意图包括复数形式，此外，还应当理解的是，当在本说明书中使用术语“包含”和/或“包括”时，其指明存在特征、步骤、操作、器件、组件和/或它们的组合。
17.在不冲突的情况下，本公开中的实施例及实施例中的特征可以相互组合。
18.实施例 1本实施例提供基于公共子表达式的大规模集成电路设计优化方法，本发明提供的方法可用于解决数字eda工具逻辑综合问题，实现组合逻辑器件的资源优化，从而提高电路的性能和效率：图2和图3中的0-5为信号端，为虚线框中一组功能类型相同的组合逻辑器件提供输入端信号；图2中，组合逻辑器件c、e、g和组合逻辑器件h是输出端组合逻辑器件，为虚线框中一组功能类型相同的组合逻辑器件的输出信号；本组功能类型相同的组合逻辑器件的信号端与输出端组合逻辑器件之间通过4个功能类型相同的组合逻辑器件a、b、d和组合逻辑器件f进行连接；图3中，组合逻辑器件c、e、6(g)和组合逻辑器件h是输出端组合逻辑器件，为虚线框中一组功能类型相同的组合逻辑器件的输出信号；本组功能类型相同的组合逻辑器件的信号端与输出端组合逻辑器件之间通过3个功能类型相同的组合逻辑器件b、6(g)和组合逻辑器件7进行连接；其中新构建的组合逻辑器件6(g)的输出信号既是该组功能类型相同的组合逻辑器件的输出信号，也是中间组合逻辑器件b的输入信号；组合逻辑器件7的输出信号在网表中被组合逻辑器件e和组合逻辑器件h多次利用。
19.具体方法如图1所示：s1、获得待分析网表，分析网表中是否存在组合逻辑器件；若待分析网表中存在组合逻辑器件，则进行下一步。
20.随着大规模集成电路资源优化设计技术的不断发展，在优化电路设计的过程中，通常存在大量的组合逻辑器件，故需要进行优化。所述图1中功能类型相同的组合逻辑器件a-h指的是：组合逻辑器件的输出只取决于当前的输入，与电路原本的状态无关，任何时刻，只要输入发生变化，输出会立即发生相应的变化。
21.s2、获取待分析网表中功能类型相同的组合逻辑器件的分组，如图2虚线框中所示的一组功能类型相同的组合逻辑器件；图2是一个网表连接关系的示意图，其中包含多个组合逻辑器件，其中虚线框中为一组功能类型相同的组合逻辑器件，功能类型相同的组合逻辑器件表示这些组合逻辑器件均有2个输入（fanin）和1个输出（fanout）且输出与输入信号的逻辑关系相同。例如，组合逻辑器件a的输入来自信号端0和信号端1，输出到组合逻辑器件b，其中组合逻辑器件a和组合逻辑器件b之间的连线表示它们之间的连接关系。同样地，组合逻辑器件d的输入来自信号端1和信号端2，输出到组合逻辑器件e，其中，一条连线可以到达多个组合逻辑器件，也就是说，一条连线可以有多个输出；若分组只有一个组合逻辑器件时，则无需优化，直接结束，则对下一个分组进行优化；若存在多个功能类型相同的组合逻辑器件，根据当前组合逻辑器件组的位置，分别向输入端、输出端通过广度优先遍历方法寻找相连接的组合逻辑器件。
22.s3、获取组内输出端与输入端组合逻辑器件之间的对应关系：获取分组内输出端组合逻辑器件对应的输入端信号，以及输出端组合逻辑器件和输入端信号之间的连接关系；从输出端组合逻辑器件出发，采用广度优先遍历方法，寻找分组内与输出端组合逻辑器件相邻且未访问的组合逻辑器件；再从组合逻辑器件出发，寻找与组合逻辑器件相邻且未访问的组合逻辑器件，直到所遍历组合逻辑器件的输入端信号所连接的组合逻辑器件不在该分组内，则记录该输出端组合逻辑器件与此输入端信号的对应关系，以及两者之间的连接关系；例如，图2中，从输出端组合逻辑器件c出发，采用广度优先遍历方法，可以得到与输出端组合逻辑器件c存在对应关系的输入端信号为信号端5、信号端3、信号端1和信号端0；类似的，可以得到与输出端组合逻辑器件e存在对应关系的输入端信号为信号端4、信号端2和信号端1；与输出端组合逻辑器件g存在对应关系的输入端信号为信号端3和信号端1；与输出端组合逻辑器件h存在对应关系的输入端信号为信号端4、信号端2和信号端0。
23.s4、计算分组内组合逻辑器件的二进制矩阵向量，二进制矩阵向量中的每一行表示一个二进制表达式方程，用以表示输出端器件与输入端信号的影响关系；根据s3中输出端组合逻辑器件与输入端信号之间的对应关系，计算整个网表的二进制矩阵向量；矩阵中的元素a
ij
表示第i个输出端器件受第j个信号端的影响，a
ij
=1表示输出端器件yj受信号端xi的影响，a
ij
=0表示输出端器件yj不受信号端xi的影响。二进制矩阵向量中的每一行表示一个二进制表达式方程，用以表示输出端器件与信号端的影响关系。
24.例如，公式（1）中二进制矩阵向量的第一行可以表示为yc=x0+x1+x3+x5,表明输出端器件c与信号端5、信号端3、信号端1和信号端0存在对应关系；
第二行可以表示为ye=x1+x2+x4,表明输出端器件e与信号端1、信号端2和信号端4存在对应关系；第三行可以表示为yg=x1+x3,表明输出端器件g与信号端1和信号端3存在对应关系；第四行可以表示为yh=x0+x2+x4,表明输出端器件h与信号端0、信号端2和信号端4存在对应关系；（1）。
25.s5、计算二进制表达式方程中公共子表达式的出现次数，并找出出现次数最多的公共子表达式；例如，公式（1）中子表达式x1+x3分别出现在输出端组合逻辑器件yc和输出端组合逻辑器件yg中，即公共子表达式x1+x3在所有二进制表达式方程中共出现2次，子表达式x2+x4分别出现在输出端组合逻辑器件ye和输出端组合逻辑器件yh中，即公共子表达式x2+x4在所有二进制表达式方程中共出现2次，且可以看出，公共子表达式x1+x3和x2+x4出现的次数最多，所以用新的变量x6和x7，分别用以代替出现次数最多的公共子表达式x1+x3和x2+x4。
26.s6、遍历所有二进制表达式方程，建立新的变量，若二进制表达式方程中存在出现次数最多的公共子表达式x1+x3和x2+x4，则在对应的二进制表达式方程中生成一个新的变量x6和x7，分别用以替代x1+x3和x2+x4；否则继续遍历下一个二进制表达式方程；例如，公式（1）中二进制矩阵向量的第一行yc=x0+x1+x3+x5中，用x6替代x1+x3，即为yc=x0+x6+x5；类似的，第二行ye=x1+x2+x4中，用x7替代x2+x4，即为ye=x1+x7；第三行yg=x1+x3中，用x6替代x1+x3，即为yg=x6；第四行yh=x0+x2+x4中，用x7替代x2+x4，即为yh=x0+x7。
27.s7、判断所有二进制表达式方程是否存在公共子表达式：循环s5-s6，直到在每一个二进制表达式方程中只有一个变量或，所有二进制表达式方程不存在公共子表达式；具体二进制表达式方程的迭代过程如公式（1）所示；s8、在电路中根据新的变量设置新增组合逻辑件，具体包括：s81、获得新的变量对应的输入端信号；s82、将新的变量对应的输入端信号作为新增组合逻辑件的输入，新的变量对应的输出端组合逻辑件作为新增组合逻辑件的输出指向；s9、更新电路：根据新增组合逻辑件可替换原电路中组合逻辑件，或，重新构建新
增组合逻辑件，技术人员可根据实际需要调整更新方式；重新构建新增组合逻辑件如下所述：根据所得出现次数最多的公共子表达式，取出相应的输入端信号，构建为新增组合逻辑件，例如图3中的新增组合逻辑件6(g)的构建过程，一方面，将出现次数最多的公共子表达式x1+x3包含的信号端x1和信号端x3作为新增组合逻辑件6(g)的输入端信号，另一方面，新增组合逻辑件6(g)的输出端信号作为包含出现次数最多的公共子表达式x1+x3的二进制表达式方程yc=x0+x1+x3+x5和yg=x1+x3的新的输入信号变量x6，即yc=x0+x6+x5、yg=x6；同理构建模块7，首先将出现次数最多的公共子表达式x2+x4包含的信号端x2和信号端x4作为新增组合逻辑件7的输入端信号，然后新增组合逻辑件7的输出端信号作为包含出现次数最多的公共子表达式x2+x4的二进制表达式方程ye=x1+x2+x4和yh=x0+x2+x4的新的输入信号变量x7，即ye=x1+x7、yh=x0+x7。
28.最后，在不影响电路功能的情况下，通过采用公共子表达式消除算法，原先使用8个组合逻辑器件(组合逻辑器件a-h)的电路被简化为只需要6个组合逻辑器件(组合逻辑器件6(g)、组合逻辑器件7、组合逻辑器件b、组合逻辑器件c、组合逻辑器件e和组合逻辑器件h)，其中组合逻辑器件6(g)不仅作为输出端器件，也作为组合逻辑器件b的输入端信号，节省了组合逻辑器件的使用数量；组合逻辑器件7作为组合逻辑器件e和组合逻辑器件h的公共输入端信号，通过采用本发明所提方法，预先构建该器件，降低了组合逻辑器件的使用量，减少器件的资源占用。
29.在具体应用时，例如解决数字eda工具逻辑综合问题，其中的组合逻辑器件多者可达数百个，故采用本方法可极大的降低电路中逻辑器件的数量，以提高大规模集成电路设计的效率和质量。
30.显然，本发明的上述实施例仅仅是为清楚地说明本发明技术方案所作的举例，而并非是对本发明的具体实施方式的限定。凡在本发明权利要求书的精神和原则之内所做的任何修改、等同替换和改进等，均应包含在本发明权利要求的保护范围之内。

技术特征：
1.基于公共子表达式的大规模集成电路设计优化方法，其特征在于，包括；s1、获得待分析网表，若待分析网表中存在组合逻辑器件，则进行下一步；所述组合逻辑器件是指：组合逻辑器件的输出只取决于当前的输入，与电路原本的状态无关，任何时刻，只要输入发生变化，输出会立即发生相应的变化；s2、获取待分析网表中功能类型相同的组合逻辑器件的分组；若分组只有一个组合逻辑器件时，则无需优化，直接结束，对下一个分组进行优化；若存在多个功能类型相同的组合逻辑器件，根据当前组合逻辑器件组的位置，分别向输入端、输出端通过广度优先遍历方法寻找相连接的组合逻辑器件；s3、获取分组内输出端组合逻辑器件对应的输入端信号，以及输出端组合逻辑器件和输入端信号之间的连接关系；s4、计算分组内组合逻辑器件的二进制矩阵向量，二进制矩阵向量中的每一行表示一个二进制表达式方程；s5、计算二进制表达式方程中公共子表达式的出现次数，并找出出现次数最多的公共子表达式；s6、遍历所有二进制表达式方程，若二进制表达式方程中存在出现次数最多的公共子表达式，则在该二进制表达式方程中用一个新的变量代替出现次数最多的公共子表达式；若不存在，则继续遍历下一个二进制表达式方程；s7、循环s5-s6，直到在每一个二进制表达式方程中只有一个变量，或，所有二进制表达式方程不存在公共子表达式；s8、在电路中根据新的变量设置新增组合逻辑件；s9、更新电路。2.根据权利要求1所述的基于公共子表达式的大规模集成电路设计优化方法，其特征在于，所述多个功能类型相同的组合逻辑器件包括输入端信号数量和输出的指向数量都相同。3.根据权利要求2所述的基于公共子表达式的大规模集成电路设计优化方法，其特征在于，所述在电路中根据新的变量设置新增组合逻辑件具体包括：s81、获得新的变量对应的输入端信号；s82、将新的变量对应的输入端信号作为新增组合逻辑件的输入，新的变量对应的输出端组合逻辑件作为新增组合逻辑件的输出指向；s83、新增组合逻辑件的输出作为直接输出或者作为输出组合逻辑件的输入。4.根据权利要求1所述的基于公共子表达式的大规模集成电路设计优化方法，其特征在于，所述获取分组内输出端组合逻辑器件对应的输入端信号，以及两者之间的连接关系具体包括：从输出端组合逻辑器件出发，寻找分组内与输出端组合逻辑器件相邻且未访问的组合逻辑器件；再从组合逻辑器件出发，寻找与组合逻辑器件相邻且未访问的组合逻辑器件，直到所遍历组合逻辑器件的输入端信号所连接的组合逻辑器件不在该分组内，则记录该输出端组合逻辑器件与此输入端信号的对应关系，以及两者之间的连接关系。

技术总结
本发明属于电路数据处理的技术领域，更具体地，涉及基于公共子表达式的大规模集成电路设计优化方法。具体包括：首先遍历查找组合逻辑中器件间的连接关系，确定输出器件与输入器件之间的相互关系，构建输出与输入之间的二进制矩阵向量；二进制矩阵向量中的每一行表示一个二进制表达式方程，通过矩阵分析，识别出需要处理的公共子表达式，并选择其中一个公共子表达式作为需要消除的项；接着消除所选公共子表达式，直到没有公共子表达式可以提取；再根据所提取出的公共子表达式信息，创建新的模块，并建立新建模块与输入端和输出端的连接关系。本发明解决了现有技术中大规模集成电路资源优化、电路的性能和效率较低的问题。电路的性能和效率较低的问题。电路的性能和效率较低的问题。


技术研发人员：郑雯雯 唐兴达 王鸿儒 李扬 党永迪
受保护的技术使用者：山东启芯软件科技有限公司
技术研发日：2023.08.04
技术公布日：2023/9/9