基于图论模型的一类集成电路布线算法

基于图论模型的一类集成电路布线算法

刘成洋,朱文彬,李汶鸿

山东协和学院  山东济南  250109

摘要：针对具有曼哈顿模型的一类通道布线，提出了一个依据图论模型的最优轨道高度布线算法。算法根据通道上结点的水平约束图和垂直约束图，依次安排好每一个结点的布线轨道，进而通过通孔可以把所有的结点在2层轨道上布线完成。通过计算分析，该算法相对以前的算法能够达到更优的布线高度，并且其复杂性保持不变。

关键词：有向图；通道布线；最短路径

集成电路从20世纪60年代开始，到目前为止已经发展到超大规模集成电路。目前我国集成电路的发展非常迅猛，但是和发达国家的水平相比还是有很大的差距。一般来说一个国家电子工业的增长速率是国家经济增长速率的3倍，而集成电路的增长速率又可以达到电子工业的2倍。这样估算，再过几十年我国的集成电路的市场总额将达到世界集成电路市场份额的四分之一。因此，集成电路的发展任重而道远，只有把集成电路产业发展到世界先进水平，我国的经济才能在世界处于领先地位。

随着集成电路技术的飞速发展，除了工艺技术、设备和材料等方面的不断改进，设计技术的进步也起着举足轻重的作用。在集成电路设计的每个环节和整体设计中都普遍使用CAD技术，随着集成度的提高，芯片内部集成的晶体管数目越来越多，集成电路设计的复杂性也越来越高，要在几十平方毫米的硅片上完成数百万个器件的电子系统的设计，只靠人工设计是完全不可能的，借助计算机辅助设计工具进行电路设计势在必行。由于芯片及其之间的关系可以用图的结构来表示，这样图论的思想方法就可以用到超大规模集成电路设计中。组合优化和图论的方法在超大规模集成电路设计中被广泛地应用，近几十年国内外学者已经做了深入的研究，在此领域中出现了许多优秀的成果。德国波恩大学离散数学研究所一直从事这一领域的研究，该研究所的主要研究人员大多是图论和组合数学领域的专家，他们自主研发了一套EDA工具，被用于上千款IBM芯片的设计。在实际应用中常采用启发式算法。本文主要考虑图论的思想方法在超大规模集成电路布线中的应用。

2层曼哈顿模型通道布线是一类很普遍并且研究的比较多的布线类型。对于2层曼哈顿模型的通道布线问题，有很多比较有效的启发式算法解决这类问题，另外还有很多理论上比较好的改进结果。本文主要研究一类2层曼哈顿模型通道布线。

一、第一阶段

在进行第一阶段之前，首先把平凡的线网先布好，平凡的线网即是它的两个结点的位置在同一列上，这样的线网布线时就不用分配水平轨道了，就是说可以直接用一个垂直线段连接起该线网的两个结点即可。因此可以不用考虑平凡线网，也可以说通道布线问题不包含平凡线网。在后面的算法中，就不再考虑平凡线网的问题。

这里考虑的布线问题的垂直约束图中只包含有向路，首先，任意的选择一条有向路，不妨记为Pn。前面已经定义，本文的通道布线是曼哈顿模型的，就是说一层水平走线，另一层垂直走线，在这里假定上面的一层是垂直走线，而底下的一层是水平走线。根据这个假定，就可以直接布好这个有向路上的线网：对每一个线网，在它所分配到的轨道底层用水平线段处把它的两个结点连接起来，然后在顶层相应的列用垂直线段把水平线段的端点与结点连接起来。因为前面的定义，该有向路上总共有n1个线网，该有向路就占用了n1行轨道。

二、第二阶段

在第一阶段首先处理了一条有向路上的线网，在这个阶段再处理一条有向路上的线网。在剩下的有向路中，随机的选择一条有向路出来，不妨记该有向路为Pn2。现在布这条有向路上的线网，首先考虑线网。

在水平约束图HCG中，如果线网N21和N11之间没有边相连，那么就把线网．放在所在的那个轨道上，也就是第一行轨道上。的连接方式与上面的线网的连接方式一样，就是底层在轨道上用水平线段，顶层用垂直线段把水平线段的端点与结点连接起来。这样的连接是合理的，因为这两个线网即没有水平约束也没有垂直约束。如果和N21在水平约束图HCG中有边相连，那么就考虑线网和N21，如果这两个线网在水平约束图HCG中没有边相连，那么就把线网放在N21所在的那个轨道上，也就是第二行轨道上。这样就把线网布好了。

三、第三阶段

在前面两个阶段首先处理了两条有向路上的线网，在这个阶段再处理一条有向路上的线网。现在来布这条有向路上的线网。能放置的最靠近北面的轨道，因此就从第一行轨道开始考虑。目前在第一行轨道上，有可能有两个线网N21和布在该轨道上，至少也有一个线网N21布在该轨道上，是否能放置在该轨道是不确定的。所以确定线网是否能布在该轨道上，就要在水平约束图上看线网与轨道上面的线网之间的关系。如果线网和第一行轨道上的线网之间没有边相连，那么就把线网N21放在该轨道上，也就是第一行轨道上。的连接方式与上面的线网的连接方式一样，就是底层用水平线段在轨道上，顶层用垂直线段把水平线段的端点与结点连接起来。这样的连接是合理的，因为这个线网与第一行轨道上面的线网即没有水平约束也没有垂直约束。

针对一类2层曼哈顿模型的通道布线问题给出有效算法。通道布线问题的线网约束关系可用水平约束图(无向)HCG和垂直约束图(有向)VCG来表示。针对2部且垂直约束图不包含有向圈的布线问题，提出了一个依据图论模型的最优轨道高度布线算法。该算法根据通道上结点的水平约束图和垂直约束图，依次安排好每一个结点的布线轨道，进而通过通孔可以把所有的结点在2层轨道上布线完成。计算分析结果表明，相比较于目前的算法，本文算法可以得到更好的轨道高度。

参考文献：

【1】谭荣华。基于分层布线算法的半导体集成电路短路控制方法[J]。信息与电脑,2022,34(6):61-63

【2】黄志鹏,李兴权,朱文兴。超大规模集成电路布局的优化模型与算法[J]。运筹学学报,2021,25(3):15-36

【3】张宁宁,马金刚,樊昭磊,李明。基于机器学习的心电自动诊断算法综述[J]。医疗卫生装备,2022,43(5):92-97

【4】李伟强,宁政通,卢明亮,覃鹏飞。计算机视觉下的果实目标检测算法综述[J]。计算机与现代化,2022(6):87-95

作者简介: 刘成洋，男，山东协和学院学生；

      指导教师：朱文彬，女，山东协和学院基础部

指导教师：李汶鸿，女，山东协和学院基础部