CN115204076A - 集成电路的逻辑优化方法、装置、电子设备及可读介质 - Google Patents
集成电路的逻辑优化方法、装置、电子设备及可读介质 Download PDFInfo
- Publication number
- CN115204076A CN115204076A CN202210859016.2A CN202210859016A CN115204076A CN 115204076 A CN115204076 A CN 115204076A CN 202210859016 A CN202210859016 A CN 202210859016A CN 115204076 A CN115204076 A CN 115204076A
- Authority
- CN
- China
- Prior art keywords
- integrated circuit
- node
- matrix
- level
- nodes
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Granted
Links
- 238000000034 method Methods 0.000 title claims abstract description 62
- 238000005457 optimization Methods 0.000 title claims abstract description 62
- 239000011159 matrix material Substances 0.000 claims abstract description 113
- 238000004364 calculation method Methods 0.000 claims abstract description 31
- 230000011218 segmentation Effects 0.000 claims description 20
- 238000004590 computer program Methods 0.000 claims description 3
- 230000000750 progressive effect Effects 0.000 claims description 3
- 230000009467 reduction Effects 0.000 claims description 2
- 238000013461 design Methods 0.000 description 17
- 238000010586 diagram Methods 0.000 description 14
- 230000015654 memory Effects 0.000 description 11
- 230000008569 process Effects 0.000 description 9
- 238000012545 processing Methods 0.000 description 9
- 238000004422 calculation algorithm Methods 0.000 description 8
- 230000006870 function Effects 0.000 description 8
- 230000015572 biosynthetic process Effects 0.000 description 5
- 238000003786 synthesis reaction Methods 0.000 description 5
- 238000012546 transfer Methods 0.000 description 5
- 230000003287 optical effect Effects 0.000 description 4
- 230000006399 behavior Effects 0.000 description 3
- 238000011960 computer-aided design Methods 0.000 description 2
- 238000012986 modification Methods 0.000 description 2
- 230000004048 modification Effects 0.000 description 2
- 239000013307 optical fiber Substances 0.000 description 2
- 230000000644 propagated effect Effects 0.000 description 2
- 238000010845 search algorithm Methods 0.000 description 2
- 239000004065 semiconductor Substances 0.000 description 2
- 238000012795 verification Methods 0.000 description 2
- 238000003491 array Methods 0.000 description 1
- 238000004891 communication Methods 0.000 description 1
- 238000009833 condensation Methods 0.000 description 1
- 230000005494 condensation Effects 0.000 description 1
- 238000010276 construction Methods 0.000 description 1
- 238000011161 development Methods 0.000 description 1
- 230000018109 developmental process Effects 0.000 description 1
- 238000011982 device technology Methods 0.000 description 1
- 238000005516 engineering process Methods 0.000 description 1
- 230000010354 integration Effects 0.000 description 1
- 230000002093 peripheral effect Effects 0.000 description 1
- 230000003252 repetitive effect Effects 0.000 description 1
- 238000004088 simulation Methods 0.000 description 1
- 230000001360 synchronised effect Effects 0.000 description 1
Images
Classifications
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F30/00—Computer-aided design [CAD]
- G06F30/30—Circuit design
- G06F30/32—Circuit design at the digital level
- G06F30/327—Logic synthesis; Behaviour synthesis, e.g. mapping logic, HDL to netlist, high-level language to RTL or netlist
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F30/00—Computer-aided design [CAD]
- G06F30/30—Circuit design
- G06F30/32—Circuit design at the digital level
- G06F30/337—Design optimisation
-
- Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
- Y02—TECHNOLOGIES OR APPLICATIONS FOR MITIGATION OR ADAPTATION AGAINST CLIMATE CHANGE
- Y02D—CLIMATE CHANGE MITIGATION TECHNOLOGIES IN INFORMATION AND COMMUNICATION TECHNOLOGIES [ICT], I.E. INFORMATION AND COMMUNICATION TECHNOLOGIES AIMING AT THE REDUCTION OF THEIR OWN ENERGY USE
- Y02D10/00—Energy efficient computing, e.g. low power processors, power management or thermal management
Landscapes
- Engineering & Computer Science (AREA)
- Computer Hardware Design (AREA)
- Physics & Mathematics (AREA)
- Theoretical Computer Science (AREA)
- Evolutionary Computation (AREA)
- Geometry (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Design And Manufacture Of Integrated Circuits (AREA)
Abstract
本公开涉及一种集成电路的逻辑优化方法、装置、电子设备及计算机可读介质。该方法包括：获取集成电路的多级逻辑网络，所述多级逻辑网络中包括节点和有向边；基于所述多级逻辑网络中的节点和有向边生成所述集成电路的邻接矩阵；基于所述邻接矩阵和矩阵操作对所述集成电路进行逻辑优化。本申请涉及的集成电路的逻辑优化方法、装置、电子设备及计算机可读介质，能够将集成电路逻辑网络中节点之间的关系由原有的链接式更新为矩阵形式，并通过矩阵计算方式，快速准确的对集成电路进行优化。
Description
技术领域
本公开涉及集成电路设计领域，具体而言，涉及一种集成电路的逻辑优化方法、装置、电子设备及计算机可读介质。
背景技术
通常，在给定了电路规格与设计要求之后，电路设计工程师会利用硬件描述语言(Hardware Description Language,HDL)对电路的行为进行设计。HDL可以描述数字电路的逻辑功能，这样电路设计工程师可以把更多精力投入功能方面的设计，而避免在一开始就研究可能极其复杂的电路连线。通过HDL可将逻辑电路功能转换成电路结构描述，电路结构一般通过网表(netlist)来表示和保存，网表本质上就是电路连线关系的描述。如今，具有实用逻辑功能的电路通常使用多级逻辑网络(multi-level logic networks)来表示。
对于一个确定功能的集成电路而言，由于在编写过程中编写代码不同，其可能对应着不同的实际电路，复杂度也差异很大。由于这个原因，在实际设计阶段，经常会对集成电路对应的逻辑网络进行优化，以减轻实际电路的复杂度。可在此阶段采取一些与具体半导体器件工艺无关的计算机技术，来简化集成电路对应的逻辑函数，从而让所用的逻辑门数减少，并满足一定的时序、面积、功耗要求。
优化过后的逻辑门网表将进一步接受各种验证，保证其功能符合设计人员的预期。然后，网表将被送往集成电路硬件厂商，在那里技术人员将采用器件与具体器件工艺相关的技术，根据逻辑门网表制造真实的电路，如专用集成电路。
在所述背景技术部分公开的上述信息仅用于加强对本申请的背景的理解，因此它可以包括不构成对本领域普通技术人员已知的现有技术的信息。
发明内容
有鉴于此，本申请提供一种集成电路的逻辑优化方法、装置、电子设备及计算机可读介质，能够将集成电路逻辑网络中节点之间的关系由原有的链接式更新为矩阵形式，并通过矩阵计算方式，快速准确的对集成电路进行优化。
本申请的其他特性和优点将通过下面的详细描述变得显然，或部分地通过本申请的实践而习得。
根据本申请的一方面，提出一种集成电路的逻辑优化方法，该方法包括：获取集成电路的多级逻辑网络，所述多级逻辑网络中包括节点和有向边；基于所述多级逻辑网络中的节点和有向边生成所述集成电路的邻接矩阵；基于所述邻接矩阵和矩阵操作对所述集成电路进行逻辑优化。
在本申请的一种示例性实施例中，基于所述多级逻辑网络中的节点有向边生成所述集成电路的邻接矩阵，包括：基于所述多级逻辑网络中的节点和有向边对应的链表关系或代码数据生成所述集成电路的邻接矩阵。
在本申请的一种示例性实施例中，基于所述邻接矩阵和矩阵操作对所述集成电路进行逻辑优化，包括：对所述邻接矩阵进行矩阵计算以生成所述集成电路的多个最大独立扇出锥；基于所述多个最大独立扇出锥对所述集成电路进行逻辑优化。
在本申请的一种示例性实施例中，对所述邻接矩阵进行矩阵计算以生成所述集成电路的多个最大独立扇出锥，包括：由所述多级逻辑网络中提取所述集成电路的输入节点和输出节点；由所述输入节点开始基于前向波逐级向输出节点推进；在每一级前向波中对所述邻接矩阵进行矩阵计算以更新当前级别的前向波中节点和其父节点之间的从属关系；在前向波推进到输出节点之后，根据每个节点和其父节点之间的从属关系生成所述集成电路的所述多个最大独立扇出锥。
在本申请的一种示例性实施例中，在每一级前向波中对所述邻接矩阵进行矩阵计算以更新当前级别的前向波中节点和其父节点之间的从属关系，包括：在每一级前向波中基于所述邻接矩阵并行对当前级别的前向波中的节点进行矢量乘法计算；在每一级前向波的矢量乘法计算中，在待计算的节点的根节点和当前级别的前向波对应的根节点相同时，维持所述待计算的节点的根节点标记以保持从属关系。
在本申请的一种示例性实施例中，在每一级前向波中对所述邻接矩阵进行矩阵计算以更新当前级别的前向波中节点和其父节点之间的从属关系，还包括：在待计算的节点的根节点和当前级别的前向波对应的根节点不同时，取消所述待计算的节点的根节点标记以将所述待计算的节点视为孤立节点。
在本申请的一种示例性实施例中，在前向波推进到输出节点之后，根据每个节点和其父节点之间的从属关系生成所述集成电路的所述多个最大独立扇出锥，包括：在前向波推进到输出节点之后，通过仅属于同一个根节点的节点生成所述根节点的最大独立扇出锥。
在本申请的一种示例性实施例中，基于所述多个最大独立扇出锥对所述集成电路进行逻辑优化，包括：生成所述多个最大独立扇出锥中的每个最大独立扇出锥的多个切分集合；基于所述多个最大独立扇出锥对应的多个切分集合进行逻辑简化。
在本申请的一种示例性实施例中，基于所述多个最大独立扇出锥对应的多个切分集合进行逻辑简化，包括：由所述多个最大独立扇出锥对应的多个切分集合中提取目标切分集合；对所述目标切分集合中的节点进行节点改写。
根据本申请的一方面，提出一种集成电路的逻辑优化装置，该装置包括：网络模块，用于获取集成电路的多级逻辑网络，所述多级逻辑网络中节点之间的边为有向边；矩阵模块，用于基于所述多级逻辑网络中的节点和其对应的有向边生成所述集成电路的邻接矩阵；优化模块，用于基于所述邻接矩阵和矩阵操作对所述集成电路进行逻辑优化。
根据本申请的一方面，提出一种电子设备，该电子设备包括：一个或多个处理器；存储装置，用于存储一个或多个程序；当一个或多个程序被一个或多个处理器执行，使得一个或多个处理器实现如上文的方法。
根据本申请的一方面，提出一种计算机可读介质，其上存储有计算机程序，该程序被处理器执行时实现如上文中的方法。
根据本申请的集成电路的逻辑优化方法、装置、电子设备及计算机可读介质，通过获取集成电路的多级逻辑网络，所述多级逻辑网络中包括节点和有向边；基于所述多级逻辑网络中的节点和有向边生成所述集成电路的邻接矩阵；基于所述邻接矩阵和矩阵操作对所述集成电路进行逻辑优化的方式，能够将集成电路逻辑网络中节点之间的关系由原有的链接式更新为矩阵形式，并通过矩阵计算方式，快速准确的对集成电路进行优化。
应当理解的是，以上的一般描述和后文的细节描述仅是示例性的，并不能限制本申请。
附图说明
通过参照附图详细描述其示例实施例，本申请的上述和其它目标、特征及优点将变得更加显而易见。下面描述的附图仅仅是本申请的一些实施例，对于本领域的普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。
图1是集成电路的多级逻辑网络示意图。
图2是根据一示例性实施例示出的一种集成电路的逻辑优化方法的流程图。
图3是根据一示例性实施例示出的一种集成电路的逻辑优化方法中矩阵运算示意图。
图4是根据一示例性实施例示出的一种集成电路的逻辑优化方法中最大独立扇出锥示意图。
图5是根据另一示例性实施例示出的一种集成电路的逻辑优化方法的流程图。
图6是根据另一示例性实施例示出的一种集成电路的逻辑优化方法的示意图。
图7是根据另一示例性实施例示出的一种集成电路的逻辑优化方法的流程图。
图8是根据一示例性实施例示出的一种集成电路的逻辑优化装置的框图。
图9是根据一示例性实施例示出的一种电子设备的框图。
图10是根据一示例性实施例示出的一种计算机可读介质的框图。
具体实施方式
现在将参考附图更全面地描述示例实施例。然而，示例实施例能够以多种形式实施，且不应被理解为限于在此阐述的实施例；相反，提供这些实施例使得本申请将全面和完整，并将示例实施例的构思全面地传达给本领域的技术人员。在图中相同的附图标记表示相同或类似的部分，因而将省略对它们的重复描述。
此外，所描述的特征、结构或特性可以以任何合适的方式结合在一个或更多实施例中。在下面的描述中，提供许多具体细节从而给出对本申请的实施例的充分理解。然而，本领域技术人员将意识到，可以实践本申请的技术方案而没有特定细节中的一个或更多，或者可以采用其它的方法、组元、装置、步骤等。在其它情况下，不详细示出或描述公知方法、装置、实现或者操作以避免模糊本申请的各方面。
附图中所示的方框图仅仅是功能实体，不一定必须与物理上独立的实体相对应。即，可以采用软件形式来实现这些功能实体，或在一个或多个硬件模块或集成电路中实现这些功能实体，或在不同网络和/或处理器装置和/或微控制器装置中实现这些功能实体。
附图中所示的流程图仅是示例性说明，不是必须包括所有的内容和操作/步骤，也不是必须按所描述的顺序执行。例如，有的操作/步骤还可以分解，而有的操作/步骤可以合并或部分合并，因此实际执行的顺序有可能根据实际情况改变。
应理解，虽然本文中可能使用术语第一、第二、第三等来描述各种组件，但这些组件不应受这些术语限制。这些术语乃用以区分一组件与另一组件。因此，下文论述的第一组件可称为第二组件而不偏离本申请概念的教示。如本文中所使用，术语“及/或”包括相关联的列出项目中的任一个及一或多者的所有组合。
本领域技术人员可以理解，附图只是示例实施例的示意图，附图中的模块或流程并不一定是实施本申请所必须的，因此不能用于限制本申请的保护范围。
本申请涉及的技术缩略语解释如下：
HDL（Hardware Description Language，硬件描述语言），是用来描述数字电路功能、行为的语言，可以在寄存器传输级、行为级、逻辑门级等对数字电路系统进行描述。随着自动化逻辑综合工具的发展，硬件描述语言可以被这些工具识别，并自动转换到逻辑门级网表，使得硬件描述语言可以被用来进行电路系统设计，并能通过逻辑仿真的形式验证电路功能。设计完成后，可以使用逻辑综合工具生成低抽象级别（门级）的网表（即连线表）。
EDA（Electronic Design Automation，电子设计自动化）是指利用计算机辅助设计（CAD）工业自动化化软件，来完成超大规模集成电路（VLSI）芯片的功能设计、综合、验证、物理设计（包括布局、布线、版图、设计规则检查等）等流程的设计方式。
RTL（Register Transaction Level，寄存器传输级）在数位电路设计中，RTL是一种对同步数位电路的抽象模型，这种模型是根据数字信号在硬件寄存器、存储器、组合逻辑装置和总线等逻辑单元之间的流动，以及其逻辑代数运作方式来确定的。寄存器传输级抽象模型在诸如Verilog和VHDL的硬件描述语言中被用于创建对实际电路的高层次描述，而低层次描述甚至实际电路可以通过高层次描述导出。在现代的数位设计中，寄存器传输级上的设计是最典型的工作流程。逻辑合成工具可以根据寄存器传输级的描述构建更低级别的电路描述。
BFS（Breadth First Search，广度优先搜索算法），又译作宽度优先搜索，或横向优先搜索，是一种基于图结构的搜索算法。简单地说，BFS是从根节点(root)开始，沿着树的宽度向下遍历树的节点。如果所有节点均被访问，或者目标节点被搜索到，则算法中止。广度优先搜索的实现一般采用open-closed表来记录已经处理过的节点（标记为closed）或者是已在队列中等待处理（标记为open）。
DP（Dynamic Programming，动态规划），通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指數增長时特别有用。
PI（Primary Input，主输入），一个电路逻辑网络最外层的输入端，所有没有fanin的节点都是PI。
PO（Primary Output，主输出），一个电路逻辑网络最外层的输出端，所有没有fanout的节点都是PO。
AIG（And-Inverter Graph，与非图）。
MFFC(Maximum Fanout-Free Cone，最大独立扇出锥)是指该系统结构中模块可以直接调用的下级模块最大数目。
图1是集成电路的多级逻辑网络示意图。目前，常见的集成电路逻辑优化算法是对电路节点的代数改写(algebraic rewriting)，对应的用于优化的电路网表或者电路的多级逻辑网络是通过AIG(And-Inverter Graph)搭建的有向图，AIG有向图本身的存储数据结构是通过链表构成。在多级逻辑网络中，每个节点代表一个逻辑门，节点之间用有向边连接。有向边在AIG中使用链表表示的，有向边根据其对应的不同的物理含义，有着不同的属性。如图1所示，o1，o2节点为输入节点，a，b，c，d，e为输出节点，节点1,2,3,4,5,6,7,8可称为网站中的节点。
图2是根据一示例性实施例示出的一种集成电路的逻辑优化方法的流程图。集成电路的逻辑优化方法20至少包括步骤S202至S206。
如图2所示，在S202中，获取集成电路的多级逻辑网络，所述多级逻辑网络中包括节点和有向边。获取待进行优化的集成电路的逻辑网络相关数据。
在S204中，基于所述多级逻辑网络中的节点和有向边生成所述集成电路的邻接矩阵。如上文所述，在现有技术中，AIG本身的数据结构是通过链表构成，对结构的修改需要进行复杂的链表指针操作，效率较低。所以，在本申请中，将链表形式的数据转化为矩阵形式的数据进行后续计算。
在一个实施例中，可基于所述多级逻辑网络中的节点和有向边对应的链表关系或代码数据生成所述集成电路的邻接矩阵。
更具体的，可逐一读取多级逻辑网络中的节点，根据节点和有向边之间的对应关系，生成待优化的集成电路的邻接矩阵。
在S206中，基于所述邻接矩阵和矩阵操作对所述集成电路进行逻辑优化。
在本申请中，将图算法中的各个操作处理抽象为线性代数运算（矩阵运算），通过矩阵运算提高图算法中各个操作处理的效率，进而提高集成电路的逻辑优化的效率。
图3是根据一示例性实施例示出的一种集成电路的逻辑优化方法中矩阵运算示意图。如图3所示，以动态规划DP为例，从某节点出发到其子节点的消息传递通过线性代数表达为一次邻接矩阵(adjacency matrix)和距离矢量(distance vector)的操作，类比矩阵与矢量乘法类比矩阵与矢量乘法Ci,j=∑kAi,k×Bk,j，可将∑k (•)替换成mink (•)，“×”运算替换成“+”，则新的公式Ci,j=mink (Ai,k+ Bk,j) 同构，这个新的公式在动态规划DP运算中相当于从节点i对下一层所有有连接关系的节点k传递自己的值，然后每个节点k计算其到i节点的距离(+)，节点j再从所有结果中选取最小值(min)更新自己到i的距离值。
对应于图1中的网络结构，可进一步抽象成矩阵表达式为
，OP1执行逐元操作（elment wise operation），OP2为缩合（reduction），模拟出矩阵乘。那么动态规划DP的一步就可以表达成
。通过图算法与稀疏矩阵运算结合，运用在逻辑综合算法本身的优化上，能够提高算法的计算效率和减少不必要的开销。
在一个实施例中，可对所述邻接矩阵进行矩阵计算以生成所述集成电路的多个最大独立扇出锥（MFFC）；基于所述多个最大独立扇出锥对所述集成电路进行逻辑优化。
图4是根据一示例性实施例示出的一种集成电路的逻辑优化方法中最大独立扇出锥示意图。MFFC用于计算或搜索在有向图结构中与一个节点n（或在电路网络中的一个逻辑门gate）相关联的其他节点（逻辑门）所传输数据流只对节点n的输出结果产生影响或变化。图4是对如图1所示的网络进行MFFC运算之后，得到的结果。其中，节点8的MFFC包含在阴影部分中，节点5的MFFC只有它自己也用阴影标注。
在一个实施例中，对所述邻接矩阵进行矩阵计算以生成所述集成电路的多个最大独立扇出锥，包括：由所述多级逻辑网络中提取所述集成电路的输入节点和输出节点；由所述输入节点开始基于前向波逐级向输出节点推进；在每一级前向波中对所述邻接矩阵进行矩阵计算以更新当前级别的前向波中节点和其父节点之间的从属关系；在前向波推进到输出节点之后，根据每个节点和其父节点之间的从属关系生成所述集成电路的所述多个最大独立扇出锥。
“对所述邻接矩阵进行矩阵计算以生成所述集成电路的多个最大独立扇出锥”对应的详细内容将在后文中进行详细描述。
根据本申请的集成电路的逻辑优化方法，通过获取集成电路的多级逻辑网络，所述多级逻辑网络中包括节点和有向边；基于所述多级逻辑网络中的节点和有向边生成所述集成电路的邻接矩阵；基于所述邻接矩阵和矩阵操作对所述集成电路进行逻辑优化的方式，能够将集成电路逻辑网络中节点之间的关系由原有的链接式更新为矩阵形式，并通过矩阵计算方式，快速准确的对集成电路进行优化。
应清楚地理解，本申请描述了如何形成和使用特定示例，但本申请的原理不限于这些示例的任何细节。相反，基于本申请公开的内容的教导，这些原理能够应用于许多其它实施例。
图5是根据另一示例性实施例示出的一种集成电路的逻辑优化方法的流程图。图5所示的流程50是对图2所示的流程中S206“对所述邻接矩阵进行矩阵计算以生成所述集成电路的多个最大独立扇出锥”的详细描述。
如图5所示，在S502中，由所述多级逻辑网络中提取所述集成电路的输入节点和输出节点。
在S504中，由所述输入节点开始基于前向波逐级向输出节点推进。
在S506中，在每一级前向波中对所述邻接矩阵进行矩阵计算以更新当前级别的前向波中节点和其父节点之间的从属关系。可在每一级前向波中基于所述邻接矩阵并行对当前级别的前向波中的节点进行矢量乘法计算；在每一级前向波的矢量乘法计算中，在待计算的节点的根节点和当前级别的前向波对应的根节点相同时，维持所述待计算的节点的根节点标记以保持从属关系。
在一个实施例中，在待计算的节点的根节点和当前级别的前向波对应的根节点不同时，取消所述待计算的节点的根节点标记以将所述待计算的节点视为孤立节点。
在S508中，在前向波推进到输出节点之后，根据每个节点和其父节点之间的从属关系生成所述集成电路的所述多个最大独立扇出锥。在前向波推进到输出节点之后，通过仅属于同一个根节点的节点生成所述根节点的最大独立扇出锥。
图6是根据另一示例性实施例示出的一种集成电路的逻辑优化方法的示意图。可借助于图6的内容，对图5所述的流程进行详细的说明。如图6所示，有向图结构中的一个level最为一个前向波（wavefront，图中虚线表示），根节点（root）的标记（在各个节点的旁边小正方形中）推送至下一层的节点，在每层的前向波wavefront里所有节点的计算都可以是并行处理的，当遇到有标记过的节点且标记的根节点的值与当前的不同时，该节点是给多个父节点提供信号的，所以它不能属于独立的一个MFFC，即将其对应的父节点标记去除。最后，所有只记录了一个根节点（root）信息的节点都属于该根节点的MFFC（多因子流程图）。
上述MFFC计算可以采用下面的代码实例的执行来实现：
在实际计算过程中，每一个wavefront相当于图算法BFS中遍历一层，对应线性代数一次矩阵运算，即为Aá+1.get_root()ñv。
在现有技术中，AIG有向图本身的数据结构是通过链表构成，链表类的数据结构只能按照链表的顺序逐一进行计算，对于复杂的集成电路而言，链表结构的图数据计算效率极低。也正是由于计算效率低下的原因，在目前基于链表形式的图数据而进行的集成电路逻辑优化大部分是局部性的，无法进行图数据网络的全局探索。
根据本申请中的集成电路的逻辑优化方法，将原有的链表形式的集成电路网络数据转换为矩阵形式的数据，并且将原有的链表形式的逐一进行数据计算的方式，更改为矩阵并行计算的方式，能够大大的提高了集成电路逻辑优化的效率。
图7是根据另一示例性实施例示出的一种集成电路的逻辑优化方法的流程图。图7所示的流程70是对图2所示的流程中S206“基于所述多个最大独立扇出锥对所述集成电路进行逻辑优化”的详细描述。
如图7所示，在S702中，生成所述多个最大独立扇出锥中的每个最大独立扇出锥的多个切分集合。
切分集合（Cutenumeration）是逻辑综合里面用于计算准备替换的节点（或逻辑门）的开销（cost）和替换后的盈余（gain）的。切分集合是以一个节点（或逻辑门）为root的逻辑锥（logiccone）的边界点集合（或叫作leaves叶节点），他们使得每一条从PI到根节点root的通路（path）必经过至少切分集合中的一个节点。切分是为了找出电路逻辑网络的每个节点作为区域的根节点root时的可能的切分集合，对于一个节点其切分集合不唯一。
在S704中，由所述多个最大独立扇出锥对应的多个切分集合中提取目标切分集合。可根据所述集成电路的优化目标确定优化节点数；根据所述优化节点数提取目标切分集合。
在一个具体的实施例中，可根据集成电路的优化目标指定要将包含4个节点的切分集合优化为含有3个节点的切分集合，即为将每个含有4个节点的切分集合尝试减小为3个节点。可将所有包含4个节点的切分集合作为目标集合，当然，还可以设置其他的优化目标，比如，将包含最多节点的切分集合进行优化等等，本申请不以此为限。
在S706中，对所述目标切分集合中的节点进行节点改写。可获取集成电路的多级逻辑网络数据；基于所述多级逻辑网络数据中的节点和其对应的有向边生成所述集成电路的邻接矩阵；基于所述邻接矩阵生成所述多个切分集合对应的切分矩阵；基于多个切分矩阵和矩阵计算进行节点改写。
在现有技术中，基于链表形式的图数据中，在对切分集合进行节点优化时，需要进行复杂的链表指针操作，根据本申请中的集成电路的逻辑优化方法，采用矩阵计算的方式，能够大大提高运算效率。
本领域技术人员可以理解实现上述实施例的全部或部分步骤被实现为由CPU 执行的计算机程序。在该计算机程序被CPU 执行时，执行本申请提供的上述方法所限定的上述功能。所述的程序可以存储于一种计算机可读存储介质中，该存储介质可以是只读存储器，磁盘或光盘等。
此外，需要注意的是，上述附图仅是根据本申请示例性实施例的方法所包括的处理的示意性说明，而不是限制目的。易于理解，上述附图所示的处理并不表明或限制这些处理的时间顺序。另外，也易于理解，这些处理可以是例如在多个模块中同步或异步执行的。
下述为本申请装置实施例，可以用于执行本申请方法实施例。对于本申请装置实施例中未披露的细节，请参照本申请方法实施例。
图8是根据一示例性实施例示出的一种集成电路的逻辑优化装置的框图。如图8所示，集成电路的逻辑优化装置80包括：网络模块802，矩阵模块804，优化模块806。
网络模块802用于获取集成电路的多级逻辑网络，所述多级逻辑网络中节点之间的边为有向边；
矩阵模块804用于基于所述多级逻辑网络中的节点和其对应的有向边生成所述集成电路的邻接矩阵；矩阵模块804还用于基于所述多级逻辑网络中的节点和有向边对应的链表关系或代码数据生成所述集成电路的邻接矩阵。
优化模块806用于基于所述邻接矩阵和矩阵操作对所述集成电路进行逻辑优化。优化模块806还用于对所述邻接矩阵进行矩阵计算以生成所述集成电路的多个最大独立扇出锥；基于所述多个最大独立扇出锥对所述集成电路进行逻辑优化。
根据本申请的集成电路的逻辑优化装置，通过获取集成电路的多级逻辑网络，所述多级逻辑网络中包括节点和有向边；基于所述多级逻辑网络中的节点和有向边生成所述集成电路的邻接矩阵；基于所述邻接矩阵和矩阵操作对所述集成电路进行逻辑优化的方式，能够将集成电路逻辑网络中节点之间的关系由原有的链接式更新为矩阵形式，并通过矩阵计算方式，快速准确的对集成电路进行优化。
图9是根据一示例性实施例示出的一种电子设备的框图。
下面参照图9来描述根据本申请的这种实施方式的电子设备900。图9显示的电子设备900仅仅是一个示例，不应对本申请实施例的功能和使用范围带来任何限制。
如图9所示，电子设备900以通用计算设备的形式表现。电子设备900的组件可以包括但不限于：至少一个处理单元910、至少一个存储单元920、连接不同系统组件（包括存储单元920和处理单元910）的总线930、显示单元940等。
其中，所述存储单元存储有程序代码，所述程序代码可以被所述处理单元910执行，使得所述处理单元910执行本说明书中描述的根据本申请各种示例性实施方式的步骤。例如，所述处理单元910可以执行如图2，图5，图7中所示的步骤。
所述存储单元920可以包括易失性存储单元形式的可读介质，例如随机存取存储单元（RAM）9201和/或高速缓存存储单元9202，还可以进一步包括只读存储单元（ROM）9203。
所述存储单元920还可以包括具有一组（至少一个）程序模块9205的程序/实用工具9204，这样的程序模块9205包括但不限于：操作系统、一个或者多个应用程序、其它程序模块以及程序数据，这些示例中的每一个或某种组合中可能包括网络环境的实现。
总线930可以为表示几类总线结构中的一种或多种，包括存储单元总线或者存储单元控制器、外围总线、图形加速端口、处理单元或者使用多种总线结构中的任意总线结构的局域总线。
电子设备900也可以与一个或多个外部设备900’（例如键盘、指向设备、蓝牙设备等）通信，使得用户能与该电子设备900交互的设备通信，和/或该电子设备900能与一个或多个其它计算设备进行通信的任何设备（例如路由器、调制解调器等等）通信。这种通信可以通过输入/输出（I/O）接口950进行。并且，电子设备900还可以通过网络适配器960与一个或者多个网络（例如局域网（LAN），广域网（WAN）和/或公共网络，例如因特网）通信。网络适配器960可以通过总线930与电子设备900的其它模块通信。应当明白，尽管图中未示出，可以结合电子设备900使用其它硬件和/或软件模块，包括但不限于：微代码、设备驱动器、冗余处理单元、外部磁盘驱动阵列、RAID系统、磁带驱动器以及数据备份存储系统等。
通过以上的实施方式的描述，本领域的技术人员易于理解，这里描述的示例实施方式可以通过软件实现，也可以通过软件结合必要的硬件的方式来实现。因此，如图10所示，根据本申请实施方式的技术方案可以以软件产品的形式体现出来，该软件产品可以存储在一个非易失性存储介质（可以是CD-ROM，U盘，移动硬盘等）中或网络上，包括若干指令以使得一台计算设备（可以是个人计算机、服务器、或者网络设备等）执行根据本申请实施方式的上述方法。
所述软件产品可以采用一个或多个可读介质的任意组合。可读介质可以是可读信号介质或者可读存储介质。可读存储介质例如可以为但不限于电、磁、光、电磁、红外线、或半导体的系统、装置或器件，或者任意以上的组合。可读存储介质的更具体的例子（非穷举的列表）包括：具有一个或多个导线的电连接、便携式盘、硬盘、随机存取存储器（RAM）、只读存储器（ROM）、可擦式可编程只读存储器（EPROM或闪存）、光纤、便携式紧凑盘只读存储器(CD-ROM)、光存储器件、磁存储器件、或者上述的任意合适的组合。
所述计算机可读存储介质可以包括在基带中或者作为载波一部分传播的数据信号，其中承载了可读程序代码。这种传播的数据信号可以采用多种形式，包括但不限于电磁信号、光信号或上述的任意合适的组合。可读存储介质还可以是可读存储介质以外的任何可读介质，该可读介质可以发送、传播或者传输用于由指令执行系统、装置或者器件使用或者与其结合使用的程序。可读存储介质上包含的程序代码可以用任何适当的介质传输，包括但不限于无线、有线、光缆、RF等等，或者上述的任意合适的组合。
可以以一种或多种程序设计语言的任意组合来编写用于执行本申请操作的程序代码，所述程序设计语言包括面向对象的程序设计语言—诸如Java、C++等，还包括常规的过程式程序设计语言—诸如“C”语言或类似的程序设计语言。程序代码可以完全地在用户计算设备上执行、部分地在用户设备上执行、作为一个独立的软件包执行、部分在用户计算设备上部分在远程计算设备上执行、或者完全在远程计算设备或服务器上执行。在涉及远程计算设备的情形中，远程计算设备可以通过任意种类的网络，包括局域网（LAN）或广域网（WAN），连接到用户计算设备，或者，可以连接到外部计算设备（例如利用因特网服务提供商来通过因特网连接）。
上述计算机可读介质承载有一个或者多个程序，当上述一个或者多个程序被一个该设备执行时，使得该计算机可读介质实现如下功能：获取集成电路的多级逻辑网络，所述多级逻辑网络中包括节点和有向边；基于所述多级逻辑网络中的节点和有向边生成所述集成电路的邻接矩阵；基于所述邻接矩阵和矩阵操作对所述集成电路进行逻辑优化。
本领域技术人员可以理解上述各模块可以按照实施例的描述分布于装置中，也可以进行相应变化唯一不同于本实施例的一个或多个装置中。上述实施例的模块可以合并为一个模块，也可以进一步拆分成多个子模块。
通过以上的实施例的描述，本领域的技术人员易于理解，这里描述的示例实施例可以通过软件实现，也可以通过软件结合必要的硬件的方式来实现。因此，根据本申请实施例的技术方案可以以软件产品的形式体现出来，该软件产品可以存储在一个非易失性存储介质（可以是CD-ROM，U盘，移动硬盘等）中或网络上，包括若干指令以使得一台计算设备（可以是个人计算机、服务器、移动终端、或者网络设备等）执行根据本申请实施例的方法。
以上具体地示出和描述了本申请的示例性实施例。应可理解的是，本申请不限于这里描述的详细结构、设置方式或实现方法；相反，本申请意图涵盖包含在所附权利要求的精神和范围内的各种修改和等效设置。
Claims (12)
1.一种集成电路的逻辑优化方法，其包括：
获取集成电路的多级逻辑网络，所述多级逻辑网络中包括节点和有向边；
基于所述多级逻辑网络中的节点和有向边生成所述集成电路的邻接矩阵；
基于所述邻接矩阵和矩阵操作对所述集成电路进行逻辑优化。
2.如权利要求1所述的方法，其特征在于，基于所述多级逻辑网络中的节点有向边生成所述集成电路的邻接矩阵，包括：
基于所述多级逻辑网络中的节点和有向边对应的链表关系或代码数据生成所述集成电路的邻接矩阵。
3.如权利要求1所述的方法，其特征在于，基于所述邻接矩阵和矩阵操作对所述集成电路进行逻辑优化，包括：
对所述邻接矩阵进行矩阵计算以生成所述集成电路的多个最大独立扇出锥；
基于所述多个最大独立扇出锥对所述集成电路进行逻辑优化。
4.如权利要求3所述的方法，其特征在于，对所述邻接矩阵进行矩阵计算以生成所述集成电路的多个最大独立扇出锥，包括：
由所述多级逻辑网络中提取所述集成电路的输入节点和输出节点；
由所述输入节点开始基于前向波逐级向输出节点推进；
在每一级前向波中对所述邻接矩阵进行矩阵计算以更新当前级别的前向波中节点和其父节点之间的从属关系；
在前向波推进到输出节点之后，根据每个节点和其父节点之间的从属关系生成所述集成电路的所述多个最大独立扇出锥。
5.如权利要求4所述的方法，其特征在于，在每一级前向波中对所述邻接矩阵进行矩阵计算以更新当前级别的前向波中节点和其父节点之间的从属关系，包括：
在每一级前向波中基于所述邻接矩阵并行对当前级别的前向波中的节点进行矢量乘法计算；
在每一级前向波的矢量乘法计算中，在待计算的节点的根节点和当前级别的前向波对应的根节点相同时，维持所述待计算的节点的根节点标记以保持从属关系。
6.如权利要求5所述的方法，其特征在于，在每一级前向波中对所述邻接矩阵进行矩阵计算以更新当前级别的前向波中节点和其父节点之间的从属关系，还包括：
在待计算的节点的根节点和当前级别的前向波对应的根节点不同时，取消所述待计算的节点的根节点标记以将所述待计算的节点视为孤立节点。
7.如权利要求4所述的方法，其特征在于，在前向波推进到输出节点之后，根据每个节点和其父节点之间的从属关系生成所述集成电路的所述多个最大独立扇出锥，包括：
在前向波推进到输出节点之后，通过仅属于同一个根节点的节点生成所述根节点的最大独立扇出锥。
8.如权利要求3所述的方法，其特征在于，基于所述多个最大独立扇出锥对所述集成电路进行逻辑优化，包括：
生成所述多个最大独立扇出锥中的每个最大独立扇出锥的多个切分集合；
基于所述多个最大独立扇出锥对应的多个切分集合进行逻辑简化。
9.如权利要求8所述的方法，其特征在于，基于所述多个最大独立扇出锥对应的多个切分集合进行逻辑简化，包括：
由所述多个最大独立扇出锥对应的多个切分集合中提取目标切分集合；
对所述目标切分集合中的节点进行节点改写。
10.一种集成电路的逻辑优化装置，其特征在于，包括：
网络模块，用于获取集成电路的多级逻辑网络，所述多级逻辑网络中节点之间的边为有向边；
矩阵模块，用于基于所述多级逻辑网络中的节点和其对应的有向边生成所述集成电路的邻接矩阵；
优化模块，用于基于所述邻接矩阵和矩阵操作对所述集成电路进行逻辑优化。
11.一种电子设备，其特征在于，包括：
一个或多个处理器；
存储装置，用于存储一个或多个程序；
当所述一个或多个程序被所述一个或多个处理器执行，使得所述一个或多个处理器实现如权利要求1-9中任一所述的方法。
12.一种计算机可读介质，其上存储有计算机程序，其特征在于，所述程序被处理器执行时实现如权利要求1-9中任一所述的方法。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202210859016.2A CN115204076B (zh) | 2022-07-21 | 2022-07-21 | 集成电路的逻辑优化方法、装置、电子设备及可读介质 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202210859016.2A CN115204076B (zh) | 2022-07-21 | 2022-07-21 | 集成电路的逻辑优化方法、装置、电子设备及可读介质 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN115204076A true CN115204076A (zh) | 2022-10-18 |
| CN115204076B CN115204076B (zh) | 2023-04-18 |
Family
ID=83582943
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN202210859016.2A Active CN115204076B (zh) | 2022-07-21 | 2022-07-21 | 集成电路的逻辑优化方法、装置、电子设备及可读介质 |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN115204076B (zh) |
Cited By (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN115879404A (zh) * | 2022-11-07 | 2023-03-31 | 华南理工大学 | 基于视觉Transform电路网表仿真加速优化方法 |
| CN116911224A (zh) * | 2023-09-07 | 2023-10-20 | 芯行纪科技有限公司 | 用于优化数字逻辑电路的方法、计算机设备及存储介质 |
| CN118350325A (zh) * | 2024-06-18 | 2024-07-16 | 芯行纪科技有限公司 | 用于优化数字逻辑电路的方法、计算机设备及存储介质 |
| WO2024178761A1 (zh) * | 2023-02-27 | 2024-09-06 | 上海科技大学 | 基于gpu的逻辑重写加速方法 |
| CN119720910A (zh) * | 2025-02-27 | 2025-03-28 | 中国科学院大学 | 与非图优化方法、装置、计算机设备和可读存储介质 |
Citations (8)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5392221A (en) * | 1991-06-12 | 1995-02-21 | International Business Machines Corporation | Procedure to minimize total power of a logic network subject to timing constraints |
| CN103745061A (zh) * | 2014-01-16 | 2014-04-23 | 南通大学 | 基于最小项的多输入输出逻辑函数优化系统的处理方法 |
| CN105912811A (zh) * | 2016-05-03 | 2016-08-31 | 山东大学 | 一种模拟数字混合电路的仿真方法 |
| US10740517B1 (en) * | 2017-09-08 | 2020-08-11 | Synopsys, Inc. | Integrated circuit (IC) optimization using Boolean resynthesis |
| CN112749522A (zh) * | 2019-10-29 | 2021-05-04 | 深圳市中兴微电子技术有限公司 | 一种rtl输出级数获取方法、装置、设备和存储介质 |
| CN114073007A (zh) * | 2019-05-10 | 2022-02-18 | 阿和罗尼克斯半导体公司 | 可编程集成电路中的片上网络 |
| CN114371553A (zh) * | 2021-01-29 | 2022-04-19 | 台湾积体电路制造股份有限公司 | 用于产生光栅耦合器的物理布局的方法 |
| CN114741996A (zh) * | 2022-05-25 | 2022-07-12 | 中南大学 | 一种基于反向搜索和遗传算法的电路划分方法 |
-
2022
- 2022-07-21 CN CN202210859016.2A patent/CN115204076B/zh active Active
Patent Citations (8)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5392221A (en) * | 1991-06-12 | 1995-02-21 | International Business Machines Corporation | Procedure to minimize total power of a logic network subject to timing constraints |
| CN103745061A (zh) * | 2014-01-16 | 2014-04-23 | 南通大学 | 基于最小项的多输入输出逻辑函数优化系统的处理方法 |
| CN105912811A (zh) * | 2016-05-03 | 2016-08-31 | 山东大学 | 一种模拟数字混合电路的仿真方法 |
| US10740517B1 (en) * | 2017-09-08 | 2020-08-11 | Synopsys, Inc. | Integrated circuit (IC) optimization using Boolean resynthesis |
| CN114073007A (zh) * | 2019-05-10 | 2022-02-18 | 阿和罗尼克斯半导体公司 | 可编程集成电路中的片上网络 |
| CN112749522A (zh) * | 2019-10-29 | 2021-05-04 | 深圳市中兴微电子技术有限公司 | 一种rtl输出级数获取方法、装置、设备和存储介质 |
| CN114371553A (zh) * | 2021-01-29 | 2022-04-19 | 台湾积体电路制造股份有限公司 | 用于产生光栅耦合器的物理布局的方法 |
| CN114741996A (zh) * | 2022-05-25 | 2022-07-12 | 中南大学 | 一种基于反向搜索和遗传算法的电路划分方法 |
Cited By (7)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN115879404A (zh) * | 2022-11-07 | 2023-03-31 | 华南理工大学 | 基于视觉Transform电路网表仿真加速优化方法 |
| WO2024178761A1 (zh) * | 2023-02-27 | 2024-09-06 | 上海科技大学 | 基于gpu的逻辑重写加速方法 |
| CN116911224A (zh) * | 2023-09-07 | 2023-10-20 | 芯行纪科技有限公司 | 用于优化数字逻辑电路的方法、计算机设备及存储介质 |
| CN116911224B (zh) * | 2023-09-07 | 2023-12-05 | 芯行纪科技有限公司 | 用于优化数字逻辑电路的方法、计算机设备及存储介质 |
| CN118350325A (zh) * | 2024-06-18 | 2024-07-16 | 芯行纪科技有限公司 | 用于优化数字逻辑电路的方法、计算机设备及存储介质 |
| CN118350325B (zh) * | 2024-06-18 | 2024-09-17 | 芯行纪科技有限公司 | 用于优化数字逻辑电路的方法、计算机设备及存储介质 |
| CN119720910A (zh) * | 2025-02-27 | 2025-03-28 | 中国科学院大学 | 与非图优化方法、装置、计算机设备和可读存储介质 |
Also Published As
| Publication number | Publication date |
|---|---|
| CN115204076B (zh) | 2023-04-18 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN115204076B (zh) | 集成电路的逻辑优化方法、装置、电子设备及可读介质 | |
| CN110192192B (zh) | 用于电路设计的基于神经网络的物理综合 | |
| EP1964266B1 (en) | A method for multi-cycle clock gating | |
| US11599700B2 (en) | Structural matching for fast re-synthesis of electronic circuits | |
| US11361133B2 (en) | Method of reporting circuit performance for high-level synthesis | |
| US8635579B1 (en) | Local clock skew optimization | |
| CN115293078B (zh) | 集成电路的节点改写方法、装置、电子设备及介质 | |
| Su et al. | Performance optimization using variable-latency design style | |
| Bairamkulov et al. | Graphs in vlsi circuits and systems | |
| US6560571B1 (en) | Method and apparatus for prioritizing the order in which checks are performed on a node in an integrated circuit | |
| JP2022536648A (ja) | 平坦化されたネットリストからの挙動設計回復 | |
| US9892227B1 (en) | Systems, methods and storage media for clock tree power estimation at register transfer level | |
| Lee et al. | External don’t cares in logic synthesis | |
| US9798843B2 (en) | Statistical timing using macro-model considering statistical timing value entry | |
| CN115204077B (zh) | 集成电路的节点优化方法、装置、电子设备及可读介质 | |
| US9852259B2 (en) | Area and/or power optimization through post-layout modification of integrated circuit (IC) design blocks | |
| Lin et al. | A design framework for hardware approximation of deep neural networks | |
| US7730437B1 (en) | Method of full semiconductor chip timing closure | |
| Bommu et al. | Retiming-based factorization for sequential logic optimization | |
| Minkovich et al. | Mapping for better than worst-case delays in LUT-based FPGA designs | |
| US20080172639A1 (en) | Methods and apparatus for validating design changes | |
| US20210103637A1 (en) | Efficient projection based adjustment evaluation in static timing analysis of integrated circuits | |
| CN117540670B (zh) | 用于数字电路的全局真值表生成方法及装置 | |
| US11928409B2 (en) | Dynamic abstract generation and synthesis flow with area prediction | |
| US11663384B1 (en) | Timing modeling of multi-stage cells using both behavioral and structural models |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| GR01 | Patent grant | ||
| GR01 | Patent grant |