基于布尔差分的乘法复杂度优化方法及装置

1.本公开涉及电子设计自动化逻辑综合领域，具体是一种基于布尔差分的乘法复杂度优化方法及装置。


背景技术：

2.在加密和安全应用中函数通常用(xor-and-graph xag)表示，电路的性能和质量与and门数量呈负相关，and门数量被称为乘积复杂度。在加密安全应用中减少乘法复杂度是极其重要，而工艺无关的逻辑优化是逻辑综合中重要的一步，现有的方法包括重写(rewrite)，重替换(resubstitution)以及重构(refactor)，其中resubstitution是逻辑优化技术中典型的布尔优化方法，它通过用现有节点(称为divisors)替换一些节点来简化电路中给定的逻辑网络函数。
3.重替换作为逻辑综合优化网络乘法复杂度的关键步骤，求解质量和速度均是考量的重要因素。传统的优化方案将网络中的节点进行无差别计算有效的降低了网络的乘法复杂度，虽然得到了较好的结果，但往往耗费了较多cpu时间，因此求解速度偏慢，而且为了寻求解质量和运行时间的平衡，放弃了一些优化机会，特别是随着函数复杂程度增加，无差别匹配造成求解时间非线性上升。


技术实现要素：

4.针对现有技术的不足，本发明提供一种基于布尔差分的乘法复杂度优化方法及装置，该方法使用逻辑网络中已经存在的节点表示指定节点达到降低网络乘法复杂度的目的。
5.本发明的技术方案包括：
6.一种基于布尔差分的乘法复杂度优化方法，所述方法包括：
7.获取逻辑网络中的待替换节点；其中，所述逻辑网络基于加密或安全应用中的函数构建，所述待替换节点的最大自由扇出锥中and节点数量不为零；
8.在所述逻辑网络中查找节点输入包含于或等同于待替换节点输入的节点后，将查找到的节点加入到第一候选集合；
9.将所述第一候选集合中的节点与所述待替换节点进行不同程度的异或运算，生成第二候选集合；
10.将第一候选集合中的节点与所述第二候选集合中的元素进行匹配，并在匹配成功的情况下，根据匹配成功所涉及节点的子网络组合成替换结构以代替所述待替换节点的最大自由扇出锥；
11.在对每一待替换节点进行最大自由扇出锥的代替后，清楚当前网络中悬空节点，以得到优化后的逻辑网络。
12.进一步地，所述获取逻辑网络中的待替换节点，包括：
13.解析逻辑网络的拓扑逻辑结构；
14.将所述逻辑网络中的所有节点按照拓扑顺序进行收集后，根据设定的子网络大小计算每一节点的子网络；
15.针对子网络计算该节点的最大自由扇出锥；
16.在所述最大自由扇出锥中and节点数量为零的情况下，判定该节点不是待替换节点；
17.在所述最大自由扇出锥中and节点数量不为零的情况下，判定该节点为待替换节点。
18.进一步地，所述将所述第一候选集合中的节点与所述待替换节点进行不同程度的异或运算，生成第二候选集合，包括：
19.对所述待替换节点与所述第一候选集合中的节点进行异或运算，生成异或集合d
unx
；
20.对所述待替换节点与所述第一候选集合中任两个节点的异或进行异或运算，生成异或集合d
bix
；
21.对所述待替换节点与所述第一候选集合中任两个节点的与进行异或运算，生成异或集合d
andx
；
22.对所述待替换节点与所述第一候选集合中任两个节点的或进行异或运算，生成异或集合d
orx
；
23.综合所述异或集合d
unx
、所述异或集合d
bix
、所述异或集合d
andx
和所述异或集合d
orx
，得到第二候选节点集合。
24.进一步地，所述将所述第一候选集合中的节点与所述第二候选集合中的元素进行匹配，包括：
25.判断所述第一候选集合中的节点的真值表是否等于所述第二候选集合中的元素的真值表；
26.在所述第一候选集合中的节点的真值表等于所述第二候选集合中的元素的真值表的情况下，判定匹配成功，并选择所述第一候选集合中的该节点以及所述第二候选集合中的该元素所涉及的节点为匹配成功所涉及节点；其中，该元素所涉及的节点不包含所述待替换节点；
27.在所述第一候选集合中的节点的真值表不等于所述第二候选集合中的元素的真值表的情况下，判定匹配不成功。
28.进一步地，所述根据匹配成功所涉及节点的子网络组合成替换结构以代替所述待替换节点的最大自由扇出锥，包括：
29.基于每组的匹配成功所涉及节点的子网络，组合成对应的替换结构；
30.根据所述替换结构以及所述待替换节点的最大自由扇出锥中and节点个数的双重判断构建瀑布模型，并基于该瀑布模型代替所述待替换节点的最大自由扇出锥。
31.进一步地，所述瀑布模型的结构包括：第一优先级中的仅包含一个异或节点的替换结构、第二优先级中的包含两个异或节点的替换结构、第三优先级中的包含三个异或节点的替换结构、第四优先级中的单and-xor混杂替换结构和第五优先级中的多and-xor混杂替换结构；其中多and-xor混杂替换结构包括：依次为一个异或节点与两个and节点的混杂替换结构、依次为两个或节点的混杂替换结构、依次为一个and节点与一个或节点的混杂替
换结构、和依次为一个或节点与一个and节点的混杂替换结构。
32.进一步地，，所述方法还包括：
33.根据所述逻辑网络中and节点个数与所述优化后的逻辑网络中and节点个数，计算所述优化后的逻辑网络的优化度。
34.一种基于布尔差分的乘法复杂度优化装置，所述装置包括：
35.待替换节点获取模块，用于获取逻辑网络中的待替换节点；其中，所述逻辑网络基于加密或安全应用中的函数构建，所述待替换节点的最大自由扇出锥中and节点数量不为零；
36.候选集合构建模块，用于在所述逻辑网络中查找节点输入包含于或等同于待替换节点输入的节点后，将查找到的节点加入到第一候选集合；将所述第一候选集合中的节点与所述待替换节点进行不同程度的异或运算，生成第二候选集合；
37.待替换节点替换模块，用于将第一候选集合中的节点与所述第二候选集合中的元素进行匹配，并在匹配成功的情况下，根据匹配成功所涉及节点的子网络组合成替换结构以代替所述待替换节点的最大自由扇出锥；
38.优化输出模块，用于在对每一待替换节点进行最大自由扇出锥的代替后，清楚当前网络中悬空节点，以得到优化后的逻辑网络。
39.一种计算机设备，其特征在于，所述电子设备包括：处理器以及存储有计算机程序指令的存储器；所述处理器执行所述计算机程序指令时实现上述任一项所述方法。
40.一种计算机可读存储介质，其特征在于，所述计算机可读存储介质上存储有计算机程序指令，所述计算机程序指令被处理器执行时实现上述任一项所述方法。
41.与现有技术先比，本发明通过分步处理候选节点集合，将候选节点的组合匹配过程变成了哈希表的搜索过程，布尔差分提供了该过程的转换可行性，在此基础上高复杂度的替换结构时间复杂度得到大幅优化，提高了优化搜索空间。本发明乘法复杂度优化方法能够同时兼顾求解质量和速度，不仅可以适用于密码学和安全应用的安全性提升，而且适用于逻辑综合中富含异或的网络重构。相比于其他乘法复杂度优化方法，本发明方法可大幅提升求解速度，能在更快的时间内得到更逼近函数乘法复杂度的结果，集成到密码学和安全应用的乘法复杂度优化流程中能得到更好的求解结果。本发明为逻辑综合乘法复杂度优化方法提供了一种新的思路，丰富了乘法复杂度优化自动设计优化方法，对于逻辑综合的乘法复杂度优化技术有着较强的现实意义和实践意义。
附图说明
42.图1一位全加器的xag表示，及对应节点mffc。
43.图2本发明的基于布尔差分的乘法复杂度优化方法的流程图。
44.图3复杂结构优化示意图。
45.图4优化后一位全加器的xag，乘法复杂度降为2。
具体实施方式
46.下面结合实施例及附图对本方案做详细的描述，以下实施方案只表示本发明一种可能的实施方式，不是全部可能的实施方案，不作为对本发明的限定。
47.图1所示为一位全加器的xag逻辑网络表示，其包含3个and节点用
‘
∧’表示和两个xor节点用表示，该网络的乘法复杂度为3。
48.针对上述逻辑网络的乘法复杂度优化方法，如图2所示，包括以下步骤：
49.步骤1：获取逻辑网络中的待替换节点。
50.本发明使用xag网络作为底层数据结构作为加密或安全应用中的底层数据结构来表示函数，xag仅包含异或(xor)和与(and)两种运算逻辑，使用逻辑网络中已经存在的节点表示指定节点达到降低网络乘法复杂度的目的。该方法基于给定的逻辑网络n和相关计算参数，首先计算网络的拓扑结构，将网络中的所有节点按照拓扑顺序进行收集，根据设定的子网络大学计算对应节点的对应子网络。之后，需要针对子网络计算节点的最大自由扇出锥，并在节点的最大自由扇出锥中计算and门数量，若and门个数不为0，则表示该节点存在潜在优化空间进一步根据布尔差分理论进行候选节点的匹配操作，否则跳过该节点。
51.在一个实施例中，and门的实际数量被定义为xag逻辑网络中的乘性复杂度，and门的实际数量为n
actual
，用于实现布尔函数的最小and门数量为n
real
，即函数实现的乘法复杂度及函数真实的乘法复杂度分别为n
actual
，n
real
，定义逻辑网络的乘法复杂度理论优化空间为：
52.ton＝n
actual-n
real
ꢀꢀꢀꢀ
(1)
53.计算机读入xag网络解析其拓扑逻辑结构和相关参数(cut_size，max_div)；cut_size表征网络划分时子网络的大小，max_div表示节点替换搜索集合的最大容量，用于限制计算时间。
54.之后，定义逻辑网络中包含的所有节点集合为l，对于每个节点n∈l，根据cut_size计算子网络记为cutn，在子网络中计算节点n的最大自由扇出锥(maximum fanout free cone mffc)，记录mffc中and门数量为mffc_and，若mffc_and＝0则标记为不可优化节点。
55.步骤2：在逻辑网络中查找节点输入包含于或等同于待替换节点输入的节点后，将查找到的节点加入到第一候选集合。
56.为了确定替换节点的候选节点以及替换后的优化增益，需要在接下来待替换节点的候选节点集合。与现有技术不同，本发明的候选节点集合中不仅包含了xag网络的节点(第一候选集合)，还包括这些节点的组合。
57.在一个实施例中，遍历所有节点将待替换节点定义为root，定义逻辑网络中存在其他可用于在布尔重替换中表示节点n的节点为divisor，定义divisors集合为d，即：
58.d＝{div1，div2，
…
，divn}
ꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(2)
59.计算当前节点root的divisors集合记为dr。
60.步骤3：将第一候选集合中的节点与待替换节点进行不同程度的异或运算，生成第二候选集合。
61.本发明构建第二候选集合时，先将候选集合中节点与待替换节点进行不同程度的异或运算，将运算结果保存到候选节点哈希表用于后续查找。
62.在一个实施例中，需要先计算节点root的真值表ttr，以及集合dr中所有节点真值表记真值表集合为dttr：
63.dttr＝{ttd1，ttd2，
…
，ttdn}
ꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(3)
64.将节点n与集合中的所有节点进行异或运算如下：
[0065][0066]
将节点n与集合中任意两个节点异或进行异或运算公式如下：
[0067][0068]
将节点n与集合中任意两个节点的与进行异或运算公式如下：
[0069][0070]
将节点n与集合中任意两个节点的或进行异或运算如下：
[0071][0072]
将上述四个集合分别命名为d
unx
、d
bix
、d
andx
和d
orx
，将集合中的元素(真值表)与对应节点或节点组合匹配构建哈希表，其中key为真值表，value为dr中的节点或节点运算组合。例如设a，b，c
in
输入真值表分别为00001111、00110011和01010101，unx哈希表如表一所示，其他的哈希表构建方式相同。
[0073]
表一
[0074][0075]
步骤4：将第一候选集合中的节点与第二候选集合中的元素进行匹配，并在匹配成功的情况下，根据匹配成功所涉及节点的子网络组合成替换结构以代替待替换节点的最大自由扇出锥。
[0076]
本发明根据替换结构以及mffc中and节点个数的双重判断构建瀑布模型。基于布尔差分理论将原始候选集合中节点与候选节点哈希表进行匹配，在匹配成功时按照替换结构将候选节点进行组合，取代网络中的指定节点同时释放节点的最大自由扇出锥，
[0077]
在一个实施例中，如图4所示，例如给定逻辑网络中两个布尔函数f(x1，x2...，xn)和.g(x1，x2，...，xn)表示节点f，g。定义布尔差分公式如下：
[0078][0079]
其中若则节点root可由f，.g节点表示，root节点的mffc可被释放逻辑网络乘法复杂度得到优化，可替换的判定公式如下：
[0080][0081]
其中ttf，ttg表示dr中节点f，.g的真值表。
[0082]
同时f，g可以表示为任意相关函数的布尔运算，若其相关函数存在于网络中。
[0083]
例如：如果f是p和q的与运算：可以表示为f＝p∧q，如果g是m和n的异或运算：可以表示为
[0084]
由公式(8)、(9)可知，节点root可通过p，q，m，n节点表示，以此推广包括但不限于这两种情形。
[0085]
针对节点n的mffc_and大小尝试不同替换结构，若mffc_and＞0，首先尝试xor替换，遍历集合dttr，判断集合中是否存在ttdk，存在于集合dunx若存在由式(9)可知
[0086][0087]
即root节点可由节点k，l表示。
[0088]
同理若dttr中元素ttdk在dbix可以检索的相应的value，则有等式：
[0089][0090]
或dttr中存在元素ttdk及ttdn进行异或后在dbix可以检索的相应的value，存在等式：
[0091][0092]
即节点root可有节点k、l、m或k、l、m、n通过异或组合进行替换，网络乘法复杂度减少mffc_and。
[0093]
之后，本发明按照瀑布模型依次判断，以得到该待替换节点的替换结构。本示例中，该瀑布模型的结构可以为xor-resub，xx-resub，xxx-resub，xa/o-resub，xaa/oo/ao/oa-resub。也就是说，第一优先级中的仅包含一个异或节点的替换结构、第二优先级中的包含两个异或节点的替换结构、第三优先级中的包含三个异或节点的替换结构、第四优先级中的单and-xor混杂替换结构和第五优先级中的多and-xor混杂替换结构；其中，该多and-xor混杂替换结构包括：依次为一个异或节点与两个and节点的混杂替换结构、依次为两个或节点的混杂替换结构、依次为一个and节点与一个或节点的混杂替换结构、和依次为一个或节点与一个and节点的混杂替换结构。
[0094]
在一个示例中，替换结构可以按照瀑布模型依次判断，进行xor-and-and替换判断存在等式：
[0095][0096]
即root节点可由节点a，b，n，c
in
表示，如图4所示root节点被替换成功。
[0097]
步骤5：在对每一待替换节点进行最大自由扇出锥的代替后，清除当前网络中悬空节点，以得到优化后的逻辑网络。
[0098]
本发明依照拓扑逻辑迭代计算直到网络中所有节点计算完成，扫描网络悬空节点并清除。如图4所示左侧为原始网络，右侧为本方法优化后的网络结构。
[0099]
在一个优先地实施例，可以依据上述公式(1)计算逻辑网络的优化度。如图4所示其乘法复杂度减少1，电路安全性提升。
[0100]
为验证本发明的技术效果，可以通过对epfl基准测试电路进行测试，将本发明提出的乘法复杂度方法应用到xag乘法复杂度优化中，得出的结果及cpu运行时间详情如表二所示：
[0101]
表二
[0102][0103]
可以看出，本发明所提出的基于布尔差法的乘法复杂度的优化方法比传统方案在优化结果上提高了7％，且cpu运行时间平均提升了38％，使cpu求解时间得到有效降低。因此，本发明方法在扩大搜索机会提高优化性能的同时，能有效加快优化速度，丰富了密码安全学领域乘法复杂度优化的自动设计优化方法
[0104]
本领域技术人员在考虑说明书及实践本公开后，将容易想到本公开的其它实施方案。本技术旨在涵盖本公开的任何变型、用途或者适应性变化，这些变型、用途或者适应性变化遵循本公开的一般性原理并包括本公开未公开的本技术领域中的公知常识或惯用技术手段。实施例仅被视为示例性的，本公开也并不局限于上面已经描述并在附图中示出的精确结构，并且可以在不脱离其范围进行各种修改和改变。

技术特征：
1.一种基于布尔差分的乘法复杂度优化方法，其特征在于，所述方法包括：获取逻辑网络中的待替换节点；其中，所述逻辑网络基于加密或安全应用中的函数构建，所述待替换节点的最大自由扇出锥中and节点数量不为零；在所述逻辑网络中查找节点输入包含于或等同于待替换节点输入的节点后，将查找到的节点加入到第一候选集合；将所述第一候选集合中的节点与所述待替换节点进行不同程度的异或运算，生成第二候选集合；将第一候选集合中的节点与所述第二候选集合中的元素进行匹配，并在匹配成功的情况下，根据匹配成功所涉及节点的子网络组合成替换结构以代替所述待替换节点的最大自由扇出锥；在对每一待替换节点进行最大自由扇出锥的代替后，清除当前网络中悬空节点，以得到优化后的逻辑网络。2.如权利要求1所述的方法，其特征在于，所述获取逻辑网络中的待替换节点，包括：解析逻辑网络的拓扑逻辑结构；将所述逻辑网络中的所有节点按照拓扑顺序进行收集后，根据设定的子网络大小计算每一节点的子网络；针对子网络计算该节点的最大自由扇出锥；在所述最大自由扇出锥中and节点数量为零的情况下，判定该节点不是待替换节点；在所述最大自由扇出锥中and节点数量不为零的情况下，判定该节点为待替换节点。3.如权利要求1所述的方法，其特征在于，所述将所述第一候选集合中的节点与所述待替换节点进行不同程度的异或运算，生成第二候选集合，包括：对所述待替换节点与所述第一候选集合中的节点进行异或运算，生成异或集合d
unx
；对所述待替换节点与所述第一候选集合中任两个节点的异或进行异或运算，生成异或集合d
bix
；对所述待替换节点与所述第一候选集合中任两个节点的与进行异或运算，生成异或集合d
andx
；对所述待替换节点与所述第一候选集合中任两个节点的或进行异或运算，生成异或集合d
orx
；综合所述异或集合d
unx
、所述异或集合d
bix
、所述异或集合d
andx
和所述异或集合dorx，得到第二候选节点集合。4.如权利要求1所述的方法，其特征在于，所述将所述第一候选集合中的节点与所述第二候选集合中的元素进行匹配，包括：判断所述第一候选集合中的节点的真值表是否等于所述第二候选集合中的元素的真值表；在所述第一候选集合中的节点的真值表等于所述第二候选集合中的元素的真值表的情况下，判定匹配成功，并选择所述第一候选集合中的该节点以及所述第二候选集合中的该元素所涉及的节点为匹配成功所涉及节点；其中，该元素所涉及的节点不包含所述待替换节点；在所述第一候选集合中的节点的真值表不等于所述第二候选集合中的元素的真值表
的情况下，判定匹配不成功。5.如权利要求1所述的方法，其特征在于，所述根据匹配成功所涉及节点的子网络组合成替换结构以代替所述待替换节点的最大自由扇出锥，包括：基于每组的匹配成功所涉及节点的子网络，组合成对应的替换结构；根据所述替换结构以及所述待替换节点的最大自由扇出锥中and节点个数的双重判断构建瀑布模型，并基于该瀑布模型代替所述待替换节点的最大自由扇出锥。6.如权利要求5所述的方法，其特征在于，所述瀑布模型的结构包括：第一优先级中的仅包含一个异或节点的替换结构、第二优先级中的包含两个异或节点的替换结构、第三优先级中的包含三个异或节点的替换结构、第四优先级中的单and-xor混杂替换结构和第五优先级中的多and-xor混杂替换结构；其中，所述多and-xor混杂替换结构包括：依次为一个异或节点与两个and节点的混杂替换结构、依次为两个或节点的混杂替换结构、依次为一个and节点与一个或节点的混杂替换结构、和依次为一个或节点与一个and节点的混杂替换结构。7.如权利要求1至6任一项所述的方法，其特征在于，所述方法还包括：根据所述逻辑网络中and节点个数与所述优化后的逻辑网络中and节点个数，计算所述优化后的逻辑网络的优化度。8.一种基于布尔差分的乘法复杂度优化装置，其特征在于，所述装置包括：待替换节点获取模块，用于获取逻辑网络中的待替换节点；其中，所述逻辑网络基于加密或安全应用中的函数构建，所述待替换节点的最大自由扇出锥中and节点数量不为零；候选集合构建模块，用于在所述逻辑网络中查找节点输入包含于或等同于待替换节点输入的节点后，将查找到的节点加入到第一候选集合；将所述第一候选集合中的节点与所述待替换节点进行不同程度的异或运算，生成第二候选集合；待替换节点替换模块，用于将第一候选集合中的节点与所述第二候选集合中的元素进行匹配，并在匹配成功的情况下，根据匹配成功所涉及节点的子网络组合成替换结构以代替所述待替换节点的最大自由扇出锥；优化输出模块，用于在对每一待替换节点进行最大自由扇出锥的代替后，清楚当前网络中悬空节点，以得到优化后的逻辑网络。9.一种计算机设备，其特征在于，所述电子设备包括：处理器以及存储有计算机程序指令的存储器；所述处理器执行所述计算机程序指令时实现如权利要求1-7任一项所述方法。10.一种计算机可读存储介质，其特征在于，所述计算机可读存储介质上存储有计算机程序指令，所述计算机程序指令被处理器执行时实现如权利要求1-7任一项所述方法。

技术总结
本发明提供了一种基于布尔差分的乘法复杂度优化方法及装置，该方法包括：获取逻辑网络中的待替换节点；在逻辑网络中查找节点输入包含于或等同于待替换节点输入的节点后，将查找到的节点加入到第一候选集合；将第一候选集合中的节点与待替换节点进行不同程度的异或运算，生成第二候选集合；将第一候选集合中的节点与第二候选集合中的元素进行匹配，并在匹配成功的情况下，根据匹配成功所涉及节点的子网络组合成替换结构以代替待替换节点的最大自由扇出锥；在对每一待替换节点进行最大自由扇出锥的代替后，清除当前网络中悬空节点，以得到优化后的逻辑网络。本发明可以降低逻辑网络的乘法复杂度。络的乘法复杂度。络的乘法复杂度。


技术研发人员：蔡少伟 张昕荻
受保护的技术使用者：中国科学院软件研究所
技术研发日：2023.06.20
技术公布日：2023/9/13