CN117057302B - 一种电路原理图启发式布局布线方法 - Google Patents

Abstract

本发明涉及电路自动化设计技术领域，提供一种电路原理图启发式布局布线方法。该方法包括：由网表文件提取元件信息和连线信息；通过拓扑算法对元件信息进行初步布局；进行由首列元件至末列元件的正向值传播冒泡排序和由末列元件至首列元件的反向值传播冒泡排序，其中均通过计算前序列冒泡值的平均值作为当前列冒泡值；对任一列中冒泡值相等的元件赋予新冒泡值以优化元件位置关系；将元件数少的列进行伸展留白，以和基准列内元件同行；根据连线信息进行布线获得初步布线结果，通过贪心算法令多条通线共享竖轴空间；绘制电路原理图。本发明能够降低算法的时间复杂度，实时生成具有较高的美观度和逻辑清晰度的原理图。

Description

一种电路原理图启发式布局布线方法

技术领域

本发明涉及电路自动化设计技术领域，尤其涉及一种电路原理图启发式布局布线方法。

背景技术

将网表文件转化为原理图在电路自动化设计技术领域有着重要作用，它能帮助设计人员迅速理解电路结构或排查电路错误。解决此类问题要求运行速度快、生成的原理图美观度、逻辑清晰度高。目前已有的解决方法可分为基于知识的方法和基于形式化算法的方法两大类。

基于知识的方法主要利用基于符号主义的人工智能方法解决问题，通过建立一系列的规则，用专家系统进行求解。此类方法存在的问题为运行效率低，难以构建实际有效的系统。

而基于形式化算法的方法将整体问题划分为若干个子阶段，如逻辑阶段、几何阶段，布局阶段、布线阶段等，通过为每个阶段设立优化目标和求解方案来解决问题。但是此类已有的方法算法时间复杂度高且不能保证100%布通率，另外生成电路布局布线原理图也美观度较低，会影响后续使用电路原理图的使用效率及正确率。

发明内容

本发明旨在至少解决相关技术中存在的技术问题之一。为此，本发明提供一种电路原理图启发式布局布线方法。

本发明提供一种电路原理图启发式布局布线方法，包括：

S100：由网表文件提取电路图布局布线所需的元件信息和连线信息；

S200：通过拓扑算法对所述元件信息进行初步布局，获得初步布局结果；

S300：对所述初步布局结果进行由首列元件至末列元件的正向值传播冒泡排序，对所述初步布局结果进行由末列元件至首列元件的反向值传播冒泡排序，获得正反向布局结果，其中均通过计算前序列冒泡值的平均值以获取当前列所需冒泡值；

S400：对所述正反向布局结果内的任一列中冒泡值相等的元件赋予新冒泡值，通过所述新冒泡值优化所述正反向布局结果中元件的位置关系，获得重整布局结果；

S500：获取所述重整布局结果内元件数最多列为基准列，对所述重整布局结果内的其它列进行伸展留白，至所述其它列内的元件与所述基准列的元件绝对行号一一对应，获得最小行差值的最终布局结果；

S600：根据所述连线信息进行布线获得初步布线结果，通过贪心算法令所述初步布线结果中的多条通线共享竖轴空间，获得最终布线结果；

S700：根据所述最终布局结果和最终布线结果，绘制电路原理图。

根据本发明的一种电路原理图启发式布局布线方法，步骤S400中对所述正反向布局结果内的任一列中冒泡值相等的元件赋予新冒泡值的表达式为：

其中，为冒泡值相等的元件赋予的新冒泡值，/>为冒泡值相等的元件的原冒泡值，/>为冒泡值相等的元件组成的元件组与元件组上方元件的冒泡值的差值，为冒泡值相等的元件组成的元件组与元件组下方元件的冒泡值的差值，/>为当前元件在冒泡值相等的元件组成的元件组内的序号，/>为正反向布局结果内第一列元件冒泡值间隔比例系数，/>为当前元件所在的冒泡值相等的元件组成的元件组包含的元件个数。

根据本发明的一种电路原理图启发式布局布线方法，步骤S200包括：

S210：将所述元件信息内的元件抽象为有向图节点；

S220：将所述元件信息内的元件间连接关系抽象为有向图边；

S230：根据所述有向图节点和所述有向图边通过拓扑排序对元件进行列的划分，获得初步布局结果。

根据本发明的一种电路原理图启发式布局布线方法，步骤S500中所述最终布局结果的最小行差值的表达为：

其中，为重整布局结果内每一列中元件序号索引值，/>为基准行行号，/>为其它列内元件不打乱顺序地置于与基准行内元件同行后计算得到的最小行差值，/>为其它列内元件伸展留白之前计算得到的行差值。

根据本发明的一种电路原理图启发式布局布线方法，步骤S300中初步布局结果中所述首列元件的初始相对位置随机指定。

本发明提供的一种电路原理图启发式布局布线方法，引入拓扑排序算法进行初步布局、引入值传播算法优化列内元件的布局、设计双向值传播算法得到较优的列内元件顺序、设计动态规划算法将列内元件伸展留白、引入通线、复线等设计思想以及设计基于贪心算法的列间隙压缩算法，因此能够降低算法的时间复杂度，实时生成具有较高的美观度和逻辑清晰度的原理图。

本发明的附加方面和优点将在下面的描述中部分给出，部分将从下面的描述中变得明显，或通过本发明的实践了解到。

附图说明

为了更清楚地说明本发明或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其它的附图。

图1是本发明实施例提供的一种电路原理图启发式布局布线方法流程图。

图2是本发明实施例提供的一种电路原理图启发式布局布线方法中步骤S500伸展留白前重整布局结果示意图。

图3是本发明实施例提供的一种电路原理图启发式布局布线方法中经步骤S500伸展留白后最终布局结果示意图。

具体实施方式

为使本发明的目的、技术方案和优点更加清楚，下面将结合本发明中的附图，对本发明中的技术方案进行清楚、完整地描述，显然，所描述的实施例是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有作出创造性劳动前提下所获得的所有其它实施例，都属于本发明保护的范围。以下实施例用于说明本发明，但不能用来限制本发明的范围。

在本发明实施例的描述中，需要说明的是，术语“中心”、“纵向”、“横向”、“上”、“下”、“前”、“后”、“左”、“右”、“竖直”、“水平”、“顶”、“底”、“内”、“外”等指示的方位或位置关系为基于附图所示的方位或位置关系，仅是为了便于描述本发明实施例和简化描述，而不是指示或暗示所指的装置或元件必须具有特定的方位、以特定的方位构造和操作，因此不能理解为对本发明实施例的限制。此外，术语“第一”、“第二”、“第三”仅用于描述目的，而不能理解为指示或暗示相对重要性。

在本发明实施例的描述中，需要说明的是，除非另有明确的规定和限定，术语“相连”、“连接”应做广义理解，例如，可以是固定连接，也可以是可拆卸连接，或一体连接；可以是机械连接，也可以是电连接；可以是直接相连，也可以通过中间媒介间接相连。对于本领域的普通技术人员而言，可以具体情况理解上述术语在本发明实施例中的具体含义。

在本发明实施例中，除非另有明确的规定和限定，第一特征在第二特征“上”或“下”可以是第一和第二特征直接接触，或第一和第二特征通过中间媒介间接接触。而且，第一特征在第二特征“之上”、“上方”和“上面”可是第一特征在第二特征正上方或斜上方，或仅仅表示第一特征水平高度高于第二特征。第一特征在第二特征“之下”、“下方”和“下面”可以是第一特征在第二特征正下方或斜下方，或仅仅表示第一特征水平高度小于第二特征。

在本说明书的描述中，参考术语“一个实施例”、“一些实施例”、“示例”、“具体示例”、或“一些示例”等的描述意指结合该实施例或示例描述的具体特征、结构、材料或者特点包含于本发明实施例的至少一个实施例或示例中。在本说明书中，对上述术语的示意性表述不必须针对的是相同的实施例或示例。而且，描述的具体特征、结构、材料或者特点可以在任一个或多个实施例或示例中以合适的方式结合。此外，在不相互矛盾的情况下，本领域的技术人员可以将本说明书中描述的不同实施例或示例以及不同实施例或示例的特征进行结合和组合。

下面结合图1描述本发明提供的实施例。

本发明提供一种电路原理图启发式布局布线方法，包括：

S100：由网表文件提取电路图布局布线所需的元件信息和连线信息；

S200：通过拓扑算法对所述元件信息进行初步布局，获得初步布局结果；

其中，步骤S200包括：

S210：将所述元件信息内的元件抽象为有向图节点；

S220：将所述元件信息内的元件间连接关系抽象为有向图边；

S230：根据所述有向图节点和所述有向图边通过拓扑排序对元件进行列的划分，获得初步布局结果。

进一步的，拓扑排序算法为将元件抽象为有向图的节点、元件间连接关系抽象为有向图的边，使用类似拓扑排序的思想对元件进行列的划分，从而达到使输出的原理图中连线从左到右的方向即为大多数实际电流的流向或信号传播方向的效果。

S300：对所述初步布局结果进行由首列元件至末列元件的正向值传播冒泡排序，对所述初步布局结果进行由末列元件至首列元件的反向值传播冒泡排序，获得正反向布局结果，其中均通过计算前序列冒泡值的平均值以获取当前列所需冒泡值；

其中，步骤S300中初步布局结果中所述首列元件的初始相对位置随机指定。

进一步的，在从第一列至最后一列进行一趟正向值传播过程后，从最后一列至第一列进行一趟反向值传播，如此重复多遍，最后进行一趟正向值传播。此策略是考虑第一列元件，也就是总输入线的初始冒泡值往往是随机指定的，而不佳的初始冒泡值可能使得后续列内的元件排序受到影响。本发明通过多遍双向值传播的方式，可以缓解第一列元件顺序不当对列内元件顺序优化的影响，从而达到提高逻辑清晰度的效果。

进一步的，在计算列内元件冒泡值时，对与其连接的前面所有列内的元件的冒泡值取平均，而不是只考虑其前一列元件，从而增加了对跨列连接元件的位置优化。

S400：对所述正反向布局结果内的任一列中冒泡值相等的元件赋予新冒泡值，通过所述新冒泡值优化所述正反向布局结果中元件的位置关系，获得重整布局结果；

进一步的，步骤S300和步骤S400的两方法均在经典值传播算法基础上改进，步骤S400中的冒泡值重整方法，是在步骤S300中的双向值传播算法过程中执行的，也就是说冒泡值重整和双向值传播两方法同步执行。

其中，步骤S400中对所述正反向布局结果内的任一列中冒泡值相等的元件赋予新冒泡值的表达式为：

其中，为冒泡值相等的元件赋予的新冒泡值，/>为冒泡值相等的元件的原冒泡值，/>为冒泡值相等的元件组成的元件组与元件组上方元件的冒泡值的差值，为冒泡值相等的元件组成的元件组与元件组下方元件的冒泡值的差值，/>为当前元件在冒泡值相等的元件组成的元件组内的序号，/>为正反向布局结果内第一列元件冒泡值间隔比例系数，/>为当前元件所在的冒泡值相等的元件组成的元件组包含的元件个数。

进一步的，在一列内元件按冒泡值排序后，将此列中冒泡值相等的元件赋予新的冒泡值，为了在前列相对位置关系的基础上，引入此列元件相对位置的信息，从而进一步优化后续列元件的位置关系。

S500：获取所述重整布局结果内元件数最多列为基准列，对所述重整布局结果内的其它列进行伸展留白，至所述其它列内的元件与所述基准列的元件绝对行号一一对应，获得最小行差值的最终布局结果；

下面结合图2至图3描述步骤S500的伸展留白过程，图2中，右列元件为重整布局结果中元件最多的列，选定为基准列，该基准列中元件编号分别为J1至J7，左列元件相对较少，为其它列，该其它列中元件编号分别为Q1至Q3，经伸展留白前，Q1与J1同行，但Q1与J2连接，Q2与J3同行，但Q2与J4连接，Q3与J5同行，但Q3与J6连接，经伸展留白后，Q1与J2同行且连接，Q2与J4同行且连接，Q3与J6同行且连接，且三条连接线平行，也就是说经过伸展留白有连接关系的元件的距离更近，电路布局图的美观程度更高。

进一步的，元件的绝对行号，为当前元件的水平方向上，与基准列内对应的元件的行号，根据图2，即Q1为该其它列内第一个元件，相对行号为1，同水平行对应基准列内的元件为J1，J1为基准列内第一个元件，J1的相对行号为1，则Q1的绝对行号为J1的相对行号，则Q1的绝对行号也为1，同理的Q2水平对应的基准列内元件为J3，则Q2的相对行号为2，绝对行号为3，其它元件同理。

在一些实施例中，可能出现一个元件与两个元件均连接的并联结构的，例如A1为其它列内元件，B1和B2为基准列内元件，A1分别并联B1和B2，此时伸展留白前，A1与B1水平对应，伸展留白后，A1可以与B1水平对应，也可以与B2水平对应，保证该列内元件行差值最小即可。

其中，步骤S500中所述最终布局结果的最小行差值的表达为：

其中，为重整布局结果内每一列中元件序号索引值，/>为基准行行号，/>为其它列内元件不打乱顺序地置于与基准行内元件同行后计算得到的最小行差值，/>为其它列内元件伸展留白之前计算得到的行差值。

进一步的，步骤S500的算法定义为动态规划算法，设定元件数最多的列为基准列，根据动态规划算法，对其余每一列元件进行“伸展”，即求该列内每个元件的绝对行号，在满足对一列内任意两元件，若第一元件的相对行号小于第二元件的相对行号，则第一元件的绝对行号小于第二元件的绝对行号小于基准列内元件的个数，也就是保持列内元件相对顺序不变的情况下，使得该列行差值最小。

进一步的，元件的行差为对元件绝对行号-基准列方向与其相连的已确定绝对行号元件的绝对行号求和，列的行差为对列内元件行差求和。

S600：根据所述连线信息进行布线获得初步布线结果，通过贪心算法令所述初步布线结果中的多条通线共享竖轴空间，获得最终布线结果；

进一步的，布线算法为根据元件的连线情况和共用纵向线的思想布通线并与元件连接，多个通线组成一条复线，其中的复线为多组两个[元件,端口]组成的集合；通线为复线“关于[元件,端口]位置位于同一通道两侧”这一等价关系商集的元素。

进一步的具体布线时，将多组两个[元件,端口]组成的集合合并为复线进行处理，对复线则划分为若干通线，即首先对通线进行布线，再将属于同一条复线的通线进行连接。

进一步的，本发明还提出一种基于贪心算法的列间隙压缩算法压缩列间隙，列间隙压缩算法为通过贪心算法，使得多条通线可以共享同一条y轴空间，从而减少列间的距离，提升原理图美观度。

S700：根据所述最终布局结果和最终布线结果，绘制电路原理图。

进一步的，上述绘图算法使用了QT工具，将布局布线结果中通过文本文件表示的元件、连线的位置信息，转化为JPG、PNG或SVG格式的文件。

在一些实施例中，本发明采用实际集成电路设计中产生的真实电路网表文件用于评估验证，采用10个不同的网表文件作为输入，这些文件来自两个不同电路设计项目，包含元件数目从7到637个、最大度数从4到641不等，表1给出了本实施例采用的网表文件的详细信息。

表1 网表文件详细信息

本实施例对启发式布局布线系统进行基本性能测试，本实施例为了充分反映布局布线结果的逻辑清晰度，统计了输出图片中的交叉点总数、连线转折点总数以及连线长度并给出本系统完成布局布线的运行时间。实验结果如表2所示。

表2 本发明提供的电路原理图启发式布局布线方法在表1中所示的网表文件上运行得到的性能指标结果

通过表2的性能指标结果可以看出，启发式布局布线系统在对数个元件到数百个元件规模的网表文件进行布局布线时，都能够在100ms内完成任务，满足了实时性的要求，且出图的交叉点总数、连线转折点总数和连线长度基本能够与元件总数保持线性增长关系。

另外在一些实施例中，本发明是多种机制的组合，这些机制共同保证了输出结果具有较高的逻辑清晰度，本实施例评估验证了双向值传播算法和动态规划列内伸展留白算法的有效性。

进一步的，实施例中第一部分在不使用动态规划列内伸展留白算法的情况下，对比在不采用值传播算法、采用经典值传播算法和采用双向值传播算法三种情况下，本发明在10组网表文件上得到的连线总长、转折点总数和交叉点数，实验结果如表3所示，表中加权平均值权重为元件个数的倒数。

表3 不使用动态规划列内伸展时值传播算法消融实验结果

表3中Avg1表示上述不使用动态规划列内伸展时值传播算法消融实验结果的平均值，同理的Wavg1为上述不使用动态规划列内伸展时值传播算法消融实验结果的加权平均值，通过表3的测试结果可以看出，当本发明使用双向值传播算法时，无论是在加权还是平均情况下，均获得了最优的连线总长、转折点总数和交叉点数，这表明双向值传播算法对于提升启发式布局布线系统生成原理图的逻辑清晰度和美观度是有效的，双向值传播算法考虑了初始列元件的相对位置顺序以及不同列之间的元件连接关系，因此减少了布线过程中的交叉点数，缩短了连线的总长。

进一步的，实施例第二部分比较了是否使用动态规划列内伸展留白算法的情况下，本发明在10组数据集上运行得到的连线总长、转折点总数和交叉点数，实验结果如表4所示。

表4使用值传播算法时动态规划列内伸展留白算法消融实验结果

表4中Avg2表示上述使用值传播算法时动态规划列内伸展留白算法消融实验结果的平均值，同理的Wavg2为上述使用值传播算法时动态规划列内伸展留白算法消融实验结果的加权平均值，通过表4的系统测试结果可以看出，使用动态规划列内伸展留白算法，使得启发式布局布线系统的加权平均连线总长、转折点总数和交叉点数降低了0.4%、20.4%和19.7%，这进一步表明通过使用动态规划列内伸展留白算法可以有效压缩有连线关系的元件的间距，降低连线总长、转折点总数和交叉点总数，进而提升了启发式布局布线系统生成原理图的美观度和逻辑清晰度。

本发明提供的一种电路原理图启发式布局布线方法，由于引入拓扑排序算法进行初步布局、引入值传播算法优化列内元件的布局、设计双向值传播算法得到较优的列内元件顺序、设计动态规划算法将列内元件伸展留白、引入通线、复线等设计思想以及设计基于贪心算法的列间隙压缩算法，能够实时生成具有较高的美观度和逻辑清晰度的原理图，运行效率高，可以构建实际有效的系统，同时降低了时间复杂度的同时，还保证了布通率，另外生成电路布局布线原理图美观度高，能够间接的提升后续使用电路原理图的使用效率及正确率。

最后应说明的是：以上实施例仅用以说明本发明的技术方案，而非对其限制；尽管参照前述实施例对本发明进行了详细的说明，本领域的普通技术人员应当理解：其依然可以对前述各实施例所记载的技术方案进行修改，或者对其中部分技术特征进行等同替换；而这些修改或者替换，并不使相应技术方案的本质脱离本发明各实施例技术方案的精神和范围。

Claims (4)

1.一种电路原理图启发式布局布线方法，其特征在于，包括：

S100：由网表文件提取电路图布局布线所需的元件信息和连线信息；

S200：通过拓扑算法对所述元件信息进行初步布局，获得初步布局结果；

S300：对所述初步布局结果进行由首列元件至末列元件的正向值传播冒泡排序，对所述初步布局结果进行由末列元件至首列元件的反向值传播冒泡排序，获得正反向布局结果，其中均通过计算前序列冒泡值的平均值以获取当前列所需冒泡值；

S400：对所述正反向布局结果内的任一列中冒泡值相等的元件赋予新冒泡值，通过所述新冒泡值优化所述正反向布局结果中元件的位置关系，获得重整布局结果；

其中，步骤S400中对所述正反向布局结果内的任一列中冒泡值相等的元件赋予新冒泡值的表达式为：

其中，为冒泡值相等的元件赋予的新冒泡值，/>为冒泡值相等的元件的原冒泡值，/>为冒泡值相等的元件组成的元件组与元件组上方元件的冒泡值的差值，为冒泡值相等的元件组成的元件组与元件组下方元件的冒泡值的差值，/>为当前元件在冒泡值相等的元件组成的元件组内的序号，/>为正反向布局结果内第一列元件冒泡值间隔比例系数，/>为当前元件所在的冒泡值相等的元件组成的元件组包含的元件个数；

S500：获取所述重整布局结果内元件数最多列为基准列，对所述重整布局结果内的其它列进行伸展留白，至所述其它列内的元件与所述基准列的元件绝对行号一一对应，获得最小行差值的最终布局结果；

S600：根据所述连线信息进行布线获得初步布线结果，通过贪心算法令所述初步布线结果中的多条通线共享竖轴空间，获得最终布线结果；

S700：根据所述最终布局结果和最终布线结果，绘制电路原理图。

2.根据权利要求1所述的一种电路原理图启发式布局布线方法，其特征在于，步骤S200包括：

S210：将所述元件信息内的元件抽象为有向图节点；

S220：将所述元件信息内的元件间连接关系抽象为有向图边；

S230：根据所述有向图节点和所述有向图边通过拓扑排序对元件进行列的划分，获得初步布局结果。

3.根据权利要求1所述的一种电路原理图启发式布局布线方法，其特征在于，步骤S500中所述最终布局结果的最小行差值的表达为：

其中，为重整布局结果内每一列中元件序号索引值，/>为基准行行号，/>为其它列内元件不打乱顺序地置于与基准行内元件同行后计算得到的最小行差值，/>为其它列内元件伸展留白之前计算得到的行差值。

4.根据权利要求1所述的一种电路原理图启发式布局布线方法，其特征在于，步骤S300中初步布局结果中所述首列元件的初始相对位置随机指定。