从网表文件到原理图的布局布线算法是电路自动化设计技术领域的重要子问题，目的是将便于机器存储、处理的网表文件转化为便于电路设计人员理解的原理图，从而让设计人员迅速理解电路结构或排查电路错误．如何在较短的时间内生成逻辑清晰度高的原理图，具有重要的学术研究意义和工程应用价值．目前，关于此问题的公开研究成果较少．相似性的电路设计物理阶段的布局布线算法的研究起步较早、成果较多[1-4]，对本问题的研究有一定的启发作用，但其并非以生成的原理图的逻辑清晰度为优化目标，与本问题优化的目标并不符合．从网表到原理图的布局布线算法的已有研究成果可分为基于形式化方法和基于知识两类[5]．前者的代表成果中，文献[6]将问题划分为逻辑和几何两个阶段进行相应优化，不过对子阶段的实现方式未说明．文献[7-8]提出了完整的布局布线算法，但算法复杂度较高且逻辑清晰度不佳．文献[9-10]同样提出了完整的布局布线算法，但在布线阶段，文献[9]不能解决横向线冲突问题，文献[10]未说明跨越元件列的连线方法，均可能输出逻辑不正确的原理图．文献[5]对本问题的研究进行了较完整的综述，提出一个完整的算法，但未给出布局布线结果逻辑清晰度的完整展示．基于知识的算法代表成果中，文献[11-12]将基于符号主义的人工智能方法应用于此问题，得到的原理图较为美观，但运行效率较低．针对前人工作中存在的时间复杂度高、生成原理图美观度不高等问题，本研究提出以优化原理图逻辑清晰度为目标的启发式布局布线算法HALCS．在布局部分，首先引入拓扑排序算法进行初步布局，接着通过改进的双向值传播算法来优化列内布局，然后通过提出的动态规划列内伸展留白算法优化调整列内元件实际位置，最后确定元件的几何位置坐标．在布线部分，提出共用纵向线布通线算法和通线连接算法完成布线．在实际网表文件上的实验结果表明：HALCS能在较短时间内生成较高逻辑清晰度的原理图，满足了布局布线算法设计清晰性、美观性和实时性的要求．1 问题定义为更好理解HALCS算法的设计，首先结合图1给出问题的定义．10.13245/j.hust.241107.F001图1电路原理图基本结构示意图a．M为元件集合．本研究将网表文件的总输入输出假想为元件来处理，总输入都放置于最左列且仅包含一个放置于其右侧的输出端口，总输出都放于最右列且仅包含一个放置于其左侧的输入端口．如图1所示，A，B，C和D为四个元件，其中元件D为总输出线．b．P为端口集合．每个端口pi∈P可用一个二元组[m,j]表示，其中m∈M为pi所属元件，整数j表示在m的所有端口中pi的序号．端口的信号传播方向和绘图时端口放置在元件的左侧或右侧为先验知识．如图1中元件A的3号端口(红色)用[A，3]表示．c．S为线的集合．每条线si∈S为一个端口对(pj,pk),pj,pk∈P．如图1所示，([A，3]，[B，2])表示A和B元件红色端口存在连接关系．本研究将电路原理图布局布线问题的定义为确定：a．每一个元件的位置；b．每一条线的路径．同时，应满足：a．没有任何元件对的绘制区域重叠；没有任何线和其他线的路径重叠(可以交叉)；b.信号应尽量多地从左向右传递，以符合设计人员阅读习惯；c．线路交叉、转折的情况应尽可能少，连线长度尽可能短；d．布局应尽量满足中心对称或轴对称．2 算法详述HALCS的输入为网表文件，输出为原理图，算法流程由解析、布局、布线和绘图这4个部分组成．解析部分用于读入网表文件描述的元件-连线的连接关系；布局部分确定元件的行列序号，进而确定其实际几何位置；布线部分用于确定连线的实际几何位置；绘图部分生成最终的原理图．2.1　补充定义为使读者更好理解HALCS的设计思想，本研究进一步结合图1中示例对若干术语和规范进行说明．a．两列元件间的空间称为通道，两行元件间的空间称为行间隙，这些空间用来布置元件之间的连线．规定连线必须由平行于x轴或平行于y轴的若干线段连接组成．规定原理图左上角为原点，向下为x轴正值方向，向右为y轴正值方向．b．定义列号为元件所处列的序号；相对行号为列内所有真实元件自上而下排序的编号；绝对行号为列内所有真实元件和虚拟元件(图1中所示虚线框)一起排序的编号．例如：图1中元件B的列号和相对行号均为2，绝对行号为3．c．以下改称前文中的“线”为“单线”．定义复线集合C 为存在公共端口的若干条单线所涉及的所有端口的集合．如图1中，若存在单线([A,3],[B,2])，([A,3],[D,1])，([C，1],[D,1])，则可得构成复线c1={[A,3]，[B,2],[C,1],[D,1]}．定义通线为复线中的端口关于“两个端口位于同一通道两侧”这一等价关系的商集的元素．如复线c1可被划分成通线t1={[A,3],[B,2]}， t2={[C,1]}， t3= {[D，1]}．2.2　布局部分布局部分解决元件放置在什么位置的问题，具体分为拓扑排序初步布局、值传播列内布局优化、动态规划列内伸展留白和确定元件几何位置坐标4个阶段．2.2.1　拓扑排序初步布局此阶段用于确定每个元件的列号．如前所述，若生成的原理图中连线从左到右的方向为电流流向或信号传播方向，则更符合阅读习惯．为了达到这个目的，须要将元件放置在其输入端口所连接元件的更靠右的列．若将元件抽象为有向图的节点、元件间连接关系抽象为有向图的边，则逐列排布元件的过程，可通过一次拓扑排序完成．算法首先将入度为零的元件(总输入线)放入最左列，接着探查此列元件连接到所有的元件，将它们的入度减1，将入度变为0的元件放入新一列中，重复此过程，直至所有元件都已被放置到了特定列中，最后将所有总输出线放入最后一列．由于实际电路中可能是带有环路的，因此本研究设计了拆环策略，即探测到环路(找不到入度为0的元件)时随机选取一个元件放入当前列，然后继续执行上述拓扑排序算法．2.2.2　双向值传播算法优化列内布局拓扑排序初步布局阶段确定了所有元件所在列，此阶段要做的工作是确定元件在列中的相对位置．本研究改进了文献[9]提出的值传播算法．如图2所示，橙色方框代表元件，其中字母和数字的组合代表其行列位置，如“0a”代表第0列第a行．原值传播算法首先处理最左列，自上而下依次按间隔参数s为每个元件指定一个冒泡值(图2中为s=100的示例，橙色方框上面的黑色数字即为冒泡值)．对随后的每一列，每个元件的冒泡值的计算方式是取其所连接的前一列中的元件冒泡值的平均，然后按冒泡值重新排序所有元件在列内的位置．重复此过程，直至最右列元件的列内位置重排完毕．10.13245/j.hust.241107.F002图2改进前的值传播算法执行过程示例本研究对值传播算法进行了三方面的改进．a．双向值传播．在从最左列至最后一列进行一趟正向值传播过程后，从最后一列至最左列进行一趟反向值传播，如此重复多遍，最后进行一趟正向值传播．此策略是考虑最左列元件(总输入线)的初始冒泡值是随机指定的，可能使得后续列内的元件排序受到影响．通过多遍双向值传播的方式，可以缓解此问题，达到提高逻辑清晰度的效果．b．跨列传播．当计算列内元件冒泡值时，对与其连接的前面所有列而非仅前一列的元件的冒泡值取平均，从而增加对跨列连接元件的位置优化．c．冒泡值重整．在一列内元件按冒泡值排序后，将此列中冒泡值相等的元件赋予新的冒泡值，以令后续值传播中能体现这些元件的位置差异，即n=o+minu,d×is×e，(1)式中：n为新冒泡值；o为原冒泡值；s为冒泡值间隔参数，此处除以s是为了使冒泡值相等的元件组重整后的内部间隔比此元件组与其相邻元件的外部间隔明显小；u为此冒泡值相等的元件组与其上邻居元件冒泡值的差值，若其上方没有元件，则u值为s；d为与下邻居元件的差值(或s)；e为元件组包含元件的个数；i为此元件在元件组中的序号，i∈[0,e)．图3给出了改进后值传播算法执行过程示例(已经过一趟正向、一趟反向值传播后的第三趟值传播过程)．可以看到：最终结果相对于图2所示原值传播算法而言，具有连接关系的元件被“聚”到了一起(如元件1b，2a和2d；元件1a，1d和2b)，元件间连线的线长和交叉点均得到减少．10.13245/j.hust.241107.F003图3改进后的值传播算法执行过程示例2.2.3　动态规划列内伸展留白经过上述两个阶段，列内元件的相对顺序已被确定．然而此时若直接进入确定元件几何位置坐标阶段，则当不同列元件数目差距较大时，易出现如图4(a)所示情况，连线转折点数目多和布线长度长，原理图逻辑清晰度不佳，因此本研究设计了动态规划列内伸展留白算法将元件较少的列中元件“伸展”开．相邻元件的绝对行号不一定是紧密相邻的，而是如图4(b)所示进行适当“留白”，从而使得原理图更加美观．10.13245/j.hust.241107.F004图4列内伸展留白思想示意图本研究使用动态规划算法解决此问题．记O(j,k)为将当前列前j个元件顺序不打乱地放到前k行的总行差的最小值，v(j,k)为将当前列第j个元件放在第k行时该元件的行差，可得递推式分别为：当j=1时，有O(j,k)=min{v(j,1),v(j,2),⋯,v(j,k)}=min{O(1,k-1),v(1,k)};(2)当j≠1且j≤k时，有O(j,k)=min{O(j,k-1),O(j-1,k-1)+v(j,k)}.(3)根据递推式，通过动态规划算法即可求解．2.2.4　元件几何位置坐标确定对于除总输入输出之外的普通元件，元件间的行间隙大小应为复线总数/行间隙总数+1，列间距离保留为左列元件右引脚数和右列元件左引数的总和．对于总输入输出端口，从所连接元件的位置的平均值(取整)开始探查，若合法，即尚未有其他总输入或总输出端口放置在此位置，则放置在此处，否则以此处为基准依此向上、向下以一个单位为粒度进行探查，直至找到合法的放置位置．2.3　布线部分本研究提出的布线算法的总体思路是将单线合并为复线进行处理，对复线则划分为若干通线．首先对通线进行布线，然后将属于同一条复线的通线进行连接．将单线合并为复线的目的是在不违反电路图逻辑含义的前提下，用公共的线代替分离的功用相同的线．如图5(a)和5(b)所示，左列的四个元件连接到右列元件的同一个端口上，使用复线绘图将使用单线绘图所形成的公共横向、纵向线进行了合并，减少了总线长，提高了逻辑清晰度．10.13245/j.hust.241107.F005图5单线合并为复线示意图当对复线进行布线时，本研究采用将复线分解为若干通线的策略．即首先对通线进行布线，再将属于同一条复线的通线进行连接的思路．这样的好处在于：每一条通线的布线可在一条通道内完成，而通道中没有元件的遮挡，全部的空间都可用于布线．2.3.1　布通线对于每一条通线，本研究设计了直观简洁的共用纵向线布通线算法．总体思路为从通线的每一个端口所在位置为起始点引出一条水平线，引到该通线纵向线所在y坐标为止，最后对该通线布垂直的纵向线，如图6所示．这样进一步将通线抽象成了一条纵向线，此纵向线的y坐标确定了，整条通线的位置就确定了．10.13245/j.hust.241107.F006图6共用纵向线布通线示意图值得注意的是：对一条通道左右两侧同一水平线上的两个端口，若左侧端口所连接通线纵向线的y坐标大于右侧端口相应的y坐标，则会造成两条不同通线横向线的重叠，形成布线的错误．如图7(a)所示，元件A，D间和B，C间分别有一条通线连接，由于两条通线所连接端口的x坐标相等，造成了横向线重叠．而在交换了两条通线的纵向线的y坐标后，出现了新的横向线重叠情况，如图7(b)所示．10.13245/j.hust.241107.F007图7重叠避免针对此问题，本研究将横向线连到纵向线所在y坐标时增加一次检测，若会产生重叠，则在重叠之前的0.5个单位处，将横向线向上或向下偏折0.5个单位，再连到相应y坐标对应的位置，如图7(c)所示．由于除了此冲突避免过程，所有的端口、线段的x和y坐标均为整数，故此冲突避免可以有效地解决问题，且保持了较低的代价．2.3.2　通线间连接属于同一条复线的通线应被连接起来．对于每条复线，在确定几何位置坐标阶段预留出来的行间隙中选择一条来布横向跨列线，再将该复线对应的每条通线的纵向线延伸到此横向线中．其中，行间隙选择的策略为从复线所含端口的x轴坐标最小、最大值的均值取整处开始，依次向上、向下寻找，直到找到合法的(即该行间隙没有被其他复线占用)为止．对于由两条只含有一个端口的通线组成的复线来说，若两端口间没有元件遮挡，则可以直接连线，无须在行间隙中再找横向跨列线．此情况多见于输入、输出端口与元件的连接．3 实验及分析3.1　实验环境及数据实验采用C++语言编程实现，其中绘图部分使用了QT5工具．实验所使用的平台操作系统为Ubuntu Linux 20.04，其CPU为Intel Xeon 1231v3(共4核)，装有8 GiB DDR3内存；实验使用的编译器为g++ 9.4.0，编译优化等级为O2．本研究使用真实电路网表文件用于实验验证．表1给出了实验数据集的详细信息．10.13245/j.hust.241107.T001表1实验网表数据集详细信息网表名称输入输出数量元件数量复线数量R3278R10388R13595394R17248088R88620121R1676320332C49102211287C57228214426C7571361447C8484637677C90309491722C98150217343C12757238333C14581119196C14942218254C1602352370本研究采用交叉点数、转折点数和连线总长进行算法量化评估．交叉点数即在绘图区域内，绘制不同复线的线段之间的交叉点的数量；转折点数为在绘图区域内，同一复线内线段之间的交点数量之和；连线总长即在绘图区域内，所有线段的长度之和．3.2　基本性能测试实验实验首先对表1所示的16组数据进行基本性能测试．除了基本的运行时间测试外，为了充分反映布局布线结果的逻辑清晰度，实验统计了算法运行过程中输出图片中的交叉点总数、连线转折点总数和连线长度．实验结果如表2所示．10.13245/j.hust.241107.T002表2样例测试结果网表名称总耗时/ms转折点总数交叉点总数连线总长/像素R30.05161.0072.00R100.050120.00109.00R130.238136203.0028.07×102R170.190138286.0033.81×102R80.23021716.73×1021.22×104R160.99869249.94×1025.13×104C495.7022 5213.39×1042.98×105C576.2392 7327.32×1045.54×105C7521.5173 2417.51×1044.99×105C8476.4075 2042.13×1051.37×106C9041.0125 2291.68×1051.44×106C985.1892 3183.22×1042.47×105C1275.6391 9573.57×1042.44×105C1451.2771 2401.40×1049.63×104C1495.0222 0293.12×1041.96×105C16011.7771 4564.39×1041.87×105表2结果表明：本研究提出的算法HALCS当面对数个元件到数百个元件规模的布局布线任务时，都能够在100 ms内完成任务，满足了算法实时性要求．出图的交叉点总数、连线转折点总数和连线长度基本上能够与元件总数保持线性增长关系．3.3　算法消融实验本研究提出的算法HALCS是多种机制的组合，为验证本研究提出的双向值传播算法和动态规划列内伸展留白算法的有效性，本研究设置了两组消融实验．第一组实验在不使用动态规划列内伸展留白算法的情况下，对比在不采用值传播算法、采用经典值传播算法[9]和本研究提出的双向值传播算法三种情况下，算法HALCS在16组网表文件上得到的连线总长、转折点总数和交叉点数．实验结果如表3所示．10.13245/j.hust.241107.T003表3值传播算法消融实验结果(不使用动态规划列内伸展)网表名称不使用值传播算法使用经典值传播算法使用双向值传播算法转折点总数交叉点总数连线总长/像素转折点总数交叉点总数连线总长/像素转折点总数交叉点总数连线总长/像素R361.0072.0061.0072.0061.0072.00R10152.00102.00152.00102.00152.00102.00R13134190.0028.77×102134190.0028.77×102136203.0028.07×102R17140268.0043.63×102134273.0042.28×102138292.0044.29×102R821733.72×1021.47×10421732.58×1021.45×10421728.79×1021.52×104R1666440.62×1026.64×10465441.06×1026.64×10467039.22×1026.42×104C492 5196.44×1044.37×1052 5206.48×1044.44×1052 5286.59×1044.36×105C572 7299.97×1047.02×1052 7141.09×1057.54×1052 7251.04×1057.04×105C753 1759.43×1046.07×1053 1859.12×1046.03×1053 1748.58×1045.99×105C845 2052.25×1051.55×1065 2162.28×1051.55×1065 1592.26×1051.56×106C905 4262.55×1052.03×1065 3992.52×1052.08×1065 3122.55×1052.00×106C982 2494.66×1043.45×1052 2504.79×1043.53×1052 2883.57×1042.97×105C1271 9723.85×1042.76×1051 9633.68×1042.73×1051 9563.52×1042.66×105C1451 2721.98×1041.21×1051 2631.94×1041.18×1051 2341.36×1041.03×105C1492 0763.15×1042.22×1052 0853.25×1042.27×1052 0913.19×1042.20×105C1601 4915.08×1042.88×1051 4915.08×1042.88×1051 4915.08×1042.88×105为进一步直观展示数据，对以上16组数据分别计算加权平均值，其中加权平均值权重为元件个数的倒数．在不使用值传播、使用经典值传播、使用双向值传播三种情况下，转折点数加权平均值分别为294.7，294.0和293.7；交叉点数加权平均值分别为7 455.0，7 534.7和7 112.8；连线总长加权平均值分别为51 654.9，52 648.2和50 453.0．由此可见：当算法HALCS使用双向值传播算法时，获得了最优的连线总长、转折点总数和交叉点数．这表明本研究提出的双向值传播算法对于优化电路布局布线原理图的逻辑清晰度和美观度是有效的．这是因为双向值传播算法考虑了初始列元件的相对位置顺序及不同列之间的元件连接关系，因此减少了布线过程中的交叉点数，缩短了连线的总长．为验证所提出的动态规划列内伸展留白算法的有效性，第二组实验比较了是否使用动态规划列内伸展留白算法情况下的算法HALCS在16组数据集上运行得到的连线总长、转折点总数和交叉点数．实验结果如表4所示．10.13245/j.hust.241107.T004表4动态规划列内伸展留白算法消融实验结果(使用值传播)网表名称不使用动态规划伸展留白算法使用动态规划伸展留白算法转折点总数交叉点总数连线总长/像素转折点总数交叉点总数连线总长/像素R361.0072.0061.0072.00R10152.00102.00120.00109.00R13136203.0028.07×102136203.0028.07×102R17138292.0044.29×102138286.0033.81×102R821728.79×1021.52×10421716.73×1021.22×104R1667039.22×1026.42×10469249.94×1025.14×104C492 5286.60×1044.36×1052 5213.39×1042.98×105C572 7251.04×1057.05×1052 7327.33×1045.54×105C753 1748.58×1045.99×1053 2417.50×1044.99×105C845 1592.26×1051.56×1065 2042.13×1051.37×106C905 3122.55×1052.00×1065 2291.68×1051.44×106C982 2883.58×1042.97×1052 3183.21×1042.47×105C1271 9563.52×1042.66×1051 9573.57×1042.48×105C1451 2341.37×1041.03×1051 2401.40×1049.63×104C1492 0913.19×1042.20×1052 0293.12×1041.95×105C1601 4915.08×1042.88×1051 4564.40×1041.87×105进一步计算加权平均值，可知通过使用动态规划列内伸展留白算法，算法HALCS的加权平均转折点总数、交叉点总数和连线总长降低了0.4%，22.0%和20.5%．这表明通过使用动态规划列内伸展留白算法可以有效压缩有连线关系的元件的间距，降低了连线总长、转折点总数和交叉点总数，进而提升了算法HALCS生成原理图的美观度和逻辑清晰度．综上所述，本研究提出的双向值传播算法和动态规划列内伸展留白算法都能够有效地提升输出原理图的逻辑清晰度．实验结果充分说明了本算法的有效性．3.4　同类算法可视化比较实验为直观展示本研究算法和同类算法的布局布线效果，实验随机选择R17网表文件对本研究提出的优化原理图逻辑清晰度的启发式布局布线算法HALCS、文献[8]和Calibre软件[13]运行的输出原理图进行比较．实验结果(局部)如图8所示．10.13245/j.hust.241107.F008图8共用纵向线布通线示意图从图8实验结果可以看出：3种算法均将元件划分成不同的列，并按照从左至右的次序进行绘制，以符合电路设计人员的阅读习惯．文献[8]的算法划分的元件列数较多，且每列元件的数量较为一致，整体视觉效果比较规整；但这样的划分方式忽视了不同元件间的层次关系，且横向跨列线较多，一定程度上不利于电路结构的表达．Calibre软件[13]将所有元件分成了三列，本研究提出的算法同样将元件分成了三列，总体达到了接近商业闭源顶尖软件的效果．综上所述，本研究算法生成的电路原理图能够兼顾连线长度、交叉点数目和元件整体布局等方面，实现较优的逻辑清晰度．4 结语本研究在总结当前网表到原理图的布局布线算法相关研究的基础上，设计并实现了一个以优化原理图逻辑清晰度为目标的启发式布局布线算法HALCS．算法HALCS能够充分满足工程应用中对原理图逻辑清晰度的要求并保证实时性．本算法采用线性流程设计，由解析、布局、布线和绘图这4个部分组成．布局和布线是算法的核心，布局部分采用拓扑排序、双向值传播算法和动态规划列内伸展留白算法确定元件的逻辑位置关系并最终确定其物理位置；布线部分设计实现的以通线为基本布线单位的布线算法大大降低了时间复杂度．最终布局布线结果整体较为美观，拥挤度较低，元件和线路分布较为均匀．目前的算法HALCS适用于门级电路元件构成的电路网表文件，且对于更大规模的电路，算法仍有优化提升空间．在本研究工作基础上，未来研究方向包括：a．考虑对原始网表文件中的元件进行聚类划分，以更好体现电路逻辑和功能，提升原理图的美观度和清晰度；b．研究采用图神经网络提取网表文件中元件之间的连接关系，通过凝练更为具体的美观度评价因子，指导算法HALCS的优化改进；c．探索使用多核CPU和众核GPU协同加速，研究绘制布局布线原理图的并行算法．