CN116029254B - 一种基于路径优化的集成电路版图自动布线方法及系统 - Google Patents
一种基于路径优化的集成电路版图自动布线方法及系统 Download PDFInfo
- Publication number
- CN116029254B CN116029254B CN202310018144.9A CN202310018144A CN116029254B CN 116029254 B CN116029254 B CN 116029254B CN 202310018144 A CN202310018144 A CN 202310018144A CN 116029254 B CN116029254 B CN 116029254B
- Authority
- CN
- China
- Prior art keywords
- path
- port
- area
- wiring
- temporary
- 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.)
- Active
Links
- 238000000034 method Methods 0.000 title claims abstract description 37
- 238000005457 optimization Methods 0.000 title claims abstract description 16
- 238000010586 diagram Methods 0.000 claims abstract description 30
- 238000005520 cutting process Methods 0.000 claims abstract description 29
- 238000004804 winding Methods 0.000 claims description 9
- 238000012545 processing Methods 0.000 claims description 5
- 230000008569 process Effects 0.000 claims description 3
- 238000009827 uniform distribution Methods 0.000 claims description 2
- 239000002184 metal Substances 0.000 description 48
- 229910052751 metal Inorganic materials 0.000 description 48
- 230000004888 barrier function Effects 0.000 description 5
- 238000013461 design Methods 0.000 description 3
- 230000009286 beneficial effect Effects 0.000 description 2
- 238000012986 modification Methods 0.000 description 2
- 230000004048 modification Effects 0.000 description 2
- 230000011218 segmentation Effects 0.000 description 2
- 238000012163 sequencing technique Methods 0.000 description 2
- 238000006467 substitution reaction Methods 0.000 description 2
- 230000002776 aggregation Effects 0.000 description 1
- 238000004220 aggregation Methods 0.000 description 1
- 238000004458 analytical method Methods 0.000 description 1
- 238000004364 calculation method Methods 0.000 description 1
- 238000009960 carding Methods 0.000 description 1
- 238000011161 development Methods 0.000 description 1
- 230000018109 developmental process Effects 0.000 description 1
- 238000005516 engineering process Methods 0.000 description 1
- 230000007613 environmental effect Effects 0.000 description 1
- 238000007689 inspection Methods 0.000 description 1
- 150000002739 metals Chemical class 0.000 description 1
- 230000000452 restraining effect Effects 0.000 description 1
- 239000002699 waste material Substances 0.000 description 1
Landscapes
- Design And Manufacture Of Integrated Circuits (AREA)
Abstract
本发明公开了一种基于路径优化的集成电路版图自动布线方法及系统,该方法包括:通过最大矩形切割法对可布线区域进行切割与解析,得到区域图;基于区域图,设置待连接端口并进行路径择优处理,得到寻路路径;结合区域图与寻路路径,根据预设临时端口生成规则,设置临时端口;通过自动布线函数对待连接端口与临时端口进行连接,得到布线结果。该系统包括:切割模块、择优模块、生成模块和连接模块。通过使用本发明,能够预测布线路径通过的矩形区域并沿途径区域放置临时端口提高布线成功率。本发明作为一种基于路径优化的集成电路版图自动布线方法及系统,可广泛应用于集成电路自动布线技术领域。
Description
技术领域
本发明涉及集成电路自动布线技术领域,尤其涉及一种基于路径优化的集成电路版图自动布线方法及系统。
背景技术
随着集成电路工艺的发展及设计的复杂度增加,器件的特征尺寸进一步缩小,集成电路的版图规模愈发庞大,版图布局布线在集成电路设计中的耗时越来越长,为了解决人工布线高耗时的问题,利用计算机辅助进行自动布线需求越来越重要,主流的自动布线算法为有网格布线,难以调整线宽和实现非整数倍线长的布线,对端口位置和大小要求严格。对于一些性能要求高的电路,自动布线难以优化性能,这类电路的版图需要手动布线,在高性能版图与自动布线部分结合时,高性能版图部分需要进行屏蔽,但一般的自动布线难以进行电路屏蔽,此外,手动布线与自动布线结合时,手动布线部分的金属相当于自动布线部分的障碍物,这类障碍物无法通过布线规划进行位置优化,已有金属区域的障碍物往往繁多,区域的环境复杂,在不做限制的情况下,如果这类区域本身难以通过甚至无法通过,布线进入这些区域会导致布线压力增加,并且浪费大量计算;此外主流的布线函数一般未对布线趋势进行约束,这会导致长排线布线不紧凑,浪费面积,也会导致匹配版图的对外走线失配,严重影响电路性能。
发明内容
为了解决上述技术问题,本发明的目的是提供一种基于路径优化的集成电路版图自动布线方法及系统,能够预测布线路径通过的矩形区域并沿途径区域放置临时端口提高布线成功率。
本发明所采用的第一技术方案是:一种基于路径优化的集成电路版图自动布线方法,包括以下步骤:
通过最大矩形切割法对可布线区域进行切割与解析,得到区域图;
基于区域图,设置待连接端口并进行路径择优处理,得到寻路路径;
结合区域图与寻路路径,根据预设临时端口生成规则,设置临时端口;
通过自动布线函数对待连接端口与临时端口进行连接,得到布线结果。
进一步,所述通过最大矩形切割法对可布线区域进行切割与解析,得到区域图这一步骤,其具体包括:
设置可布线区域,所述可布线区域为多边形PIN层;
对可布线区域进行最大矩形切割,得到对应的待处理子区域,所述待处理子区域不能通过移动任意边进行扩大面积;
对所有待处理子区域的位置关系进行判断;
对判断到存在交叠关系的待处理子区域进行标记,得到交叠区域;
对判断到存在空间上下位置关系相同的待处理子区域进行合并,得到子区域;
将子区域作为顶点,交叠区域作为连接边,构建区域图。
进一步,所述基于区域图,设置待连接端口并进行路径择优处理,得到寻路路径这一步骤,其具体包括:
对可布线区域进行Label节点标记,设置待连接端口;
对待连接端口的位置信息进行判断;
对判断到位于同一区域图的待连接端口,进行直线连接处理,得到同区域路径;
对判断到位于不同区域图的带连接端口,进行跨区域最优路径连接处理,得到跨区域最优路径;
整合同区域路径与跨区域最优路径,得到寻路路径。
进一步,所述跨区域最优路径连接的具体步骤包括:
构造区域图的生成树;
访问终点节点对应的子叶,从子叶递归访问父节点,获取终点顶点到起点顶点的路径;
对待连接端口之间存在的路径数目进行判断;
判断到待连接端口之间存在多条路径,选取所述路径经过区域图的中心点坐标,分别计算对应区域图中心点坐标之间的曼哈顿距离;
选取曼哈顿距离最小的路径作为跨区域最优路径。
进一步,所述结合区域图与寻路路径,根据预设临时端口生成规则,设置临时端口这一步骤,其具体包括:
对交叠区域内通过的寻路路径数进行判断;
判断到交叠区域内存在一条寻路路径,在寻路路径进入或离开交叠区域内或交叠区域边界产生的交点处放置临时端口;
判断到交叠区域内存在多条寻路路径;
根据待连接端口位置和进入离开情况确定第一个和最后一个交叠区域中两路径的位置顺序,所述两交叠区域相同则根据临时端口位置顺序法放置临时端口;
根据两路径从相同的边界进入交叠区域,从另一相同的边界离开交叠区域,对离开的交叠区域进行判断;
判断到离开的交叠区域未存在跳线情况,沿交叠区域边界放置临时端口。
进一步,所述临时端口位置顺序法,其具体包括:
根据跳线安排和待连接端口相对位置坐标,确定任意临时端口之间的相对位置关系,获得所有临时端口的排序;
所述临时端口的位置包括在该交叠区域当前临时端口所属路径的另一临时端口位于当前临时端口所在边界的顺时针位置的边界;该交叠区域当前临时端口所属路径的另一临时端口位于当前临时端口所在边界的逆时针位置的边界;该交叠区域当前临时端口所属路径的另一临时端口位于当前端口所在边界的对边位置的边界;临时端口在交叠区域中。
进一步,所述通过自动布线函数对待连接端口与临时端口进行连接,得到布线结果这一步骤,其具体包括:
设置起点节点,所述起点节点满足DRC规则且未超出布线区域;
根据起点节点向终点节点进行延伸布线,直至所有端口均布线完成;
选取满足DRC规则的布线,得到布线结果。
进一步,所述延伸布线过程还包括:
对于存在障碍物的延伸布线,根据布线路径选取跳层方案或绕线方案进行延伸布线,所述跳层方案为在回退后的端口处进行跳层,每个跳层成功的端口视为新的起点节点,所述绕线方案为更改延伸布线方向,新布线方向为回退端口布线方向左转或右转,更改方向后的端口一直延申至在布线方向上越过障碍物。
本发明所采用的第二技术方案是:一种基于路径优化的集成电路版图自动布线系统,包括:
切割模块,用于通过最大矩形切割法对可布线区域进行切割与解析,得到区域图;
择优模块,基于区域图,设置待连接端口并进行路径择优处理,得到寻路路径;
生成模块,用于结合区域图与寻路路径,根据预设临时端口生成规则,设置临时端口;
连接模块,用于通过自动布线函数对待连接端口与临时端口进行连接,得到布线结果。
本发明方法及系统的有益效果是:本发明通过设置可布线区域,可以屏蔽一些需要保护的版图区域,降低布线对这些区域带来的干扰,提高电路关键部分的性能,设置可布线区域时,可以避开复杂的已有环境,防止走线进入,降低布线函数的压力,增加布线通过率。在处理排线或者匹配线时,使用可布线区域区域约束这类线的走势,让走线整体趋势保持一致,提高电路性能,进一步通过合理的区域分割和临时端口的放置,将多边形区域布线问题简化为矩形区域,避免走线在多边形凹角区域的聚集,降低了布线产生的金属增加的环境复杂度,降低了先布线路径对后布线路径的影响,减小了布线次序带来的布线差异,且对跨区域的路径进行了临时端口规划,对跳线情况和位置进行了规划,减小了走线互相缠绕的概率,提高了布线通过率,并且在少金属层的情况下显著降低布线压力,本发明的布线算法为无网格算法,可以自定义线宽,并能按DRC要求避障。
附图说明
图1是本发明一种基于路径优化的集成电路版图自动布线方法的步骤流程图;
图2是本发明一种基于路径优化的集成电路版图自动布线系统的结构框图;
图3是本发明集成电路版图自动布线的步骤流程示意图;
图4是本发明用层号标记区域示意图;
图5是本发明矩形切割方式对比的结果示意图;
图6是本发明可布线区域示例的说明图;
图7是本发明将可布线区域示例的说明图转换成区域图的结果示意图;
图8是本发明设置可布线区域和标记端口金属的示意图;
图9是本发明放置临时端口的示意图;
图10是本发明跨区域布线的结果示意图。
具体实施方式
下面结合附图和具体实施例对本发明做进一步的详细说明。对于以下实施例中的步骤编号,其仅为了便于阐述说明而设置,对步骤之间的顺序不做任何限定,实施例中的各步骤的执行顺序均可根据本领域技术人员的理解来进行适应性调整。
参照图1和图3,本发明提供了一种基于路径优化的集成电路版图自动布线方法,该方法包括以下步骤:
S1、使用金属层对应的PIN层标记布线区域和需要连接的端口;
具体地,在本发明中提出可布线区域概念,自动布线需要在指定的可布线区域内进行,可布线区域为多个直径多边形,每个多边形可以分别指定布线层,若相同布线层的两个区域相交(两个多边形至少一条边相交也视为区域相交),视为同一个区域,使用金属层对应的PIN层在已有版图中标记对应金属层的可布线区域,如M1PIN标记的区域表示在该区域可以用M1DRW布线,当两个相邻层的可布线区域重叠时,布线过程中可在两层之间通过通孔跳线,以图4为例,区域1和区域2分别用M1PIN和M2PIN标记,并且存在交叠,交叠部分为区域3,则在区域3,M1DRW和M2DRW的金属可以通过通孔层VIA1DRW实现连接;
需要布线的端口在端口金属上用金属层对应的PIN层Label标记,Label中的文本为节点名,该文本也即是端口的节点名,相同节点名的端口需要相连;标记端口金属的Label需要与金属有交叠,标记端口的金属需要至少与某个可布线区域有交叠;
为了减少算法对原始版图的干扰,所有标记放入一个临时cell中,cell命名为“PIN_NAME”,放入的标记包括标记可布线区域的多边形PIN层和标记端口的Label。
S2、区域分割,子区域建立联系;
具体地,本发明提出一种多边形区域分割方法,该方法将每个多边形分割成多个矩形,每个矩形需要为多边形的最大切割,每个矩形均不能通过移动某一条边扩大矩形面积,每个多边形切割产生的多边形合并后与原多边形相同;如图5所示,(a)中切割方案中,区域2上边可以继续往上延伸,形成(b)中的大小,而(b)中区域1和区域2任意一边均不能通过移动扩大区域面积,因此(a)为非最大矩形切割方案,(b)中区域1和区域2合并将得到原图形,为最大矩形切割方案;
切割产生的每个矩形视为一个子区域,若两个子区域位置相同但不同层,合并区域,该区域视为一个多层区域;
当两个子区域存在交叠时,两个区域建立联系,互相记录为相邻状态,并记录该交叠区域,解析全部子区域后,将子区域视为顶点,交叠区域视为连接边,将形成区域图,如图6所示,区域1和区域2存在交叠,形成交叠区域1,全部解析后将形成图7所示的区域图。
S3、端口跨区域寻路;
具体地,当两个需要端口分属不同的布线子区域时,需要通过预寻路确定该端口对对应的路径将经过哪些子区域和交叠区域,将区域解析成区域图后,端口将位于区域图中的某个顶点内,通过构造区域图的生成树,所述生成树的起始终止节点为起点和终点所在的区域,起点终点端口等价,可以交换,其所在区域均可被选作起始节点,访问终点节点对应的子叶,从子叶递归访问父节点即可获得终点顶点到起点顶点的路径,路径经过的顶点和边即为该对端口预计经过的子区域和交叠区域;
当区域图中存在多个路径时,则需要进行路径择优。本发明取路径经过的区域的中心点坐标为参考坐标,经过多个区域时,依次计算两个相邻区域中心坐标之间的曼哈顿距离,每条路径分别计算总的曼哈顿距离和,取曼哈顿距离和最小的路径为寻路路径;
如需要将图6所示区域中端口1和端口2相连,端口1位于区域1,端口2位于区域5,跨区域寻路问题则变化为在图5中从区域1到区域5的寻路,构建搜索树则形成区域1->区域2->区域3->区域4->区域5这样的链式结构,该顺序也即是路径经过区域的顺序。
S4、临时端口规划;
具体地,当一条路径经过一个交叠区域时,路径会在进入或离开交叠区域时与交叠区域边界产生交点,在交点处可以放置一个临时端口,临时端口为正方形,边长为走线线宽,端口中心位于所在交叠区域边界,可以沿边界移动或者根据边界可用金属层切换层号,临时端口一定位于某一子区域中,如在图6中,端口1到端口2的路径从区域1出发经过交叠区域1进入区域2,则该路径在交叠区域1的左边界和下边界将分别产生一个临时端口,这两个临时端口同时也位于区域1和区域2;
当两条路径同时经过某一交叠区域时,则可能在该区域的同一边界上分别产生临时端口,为了减少跳线,或者是在必须跳线的情况下规划跳线位置,所述跳线即为通过判断两条路径同走势部分的起点和终点情况,可以判断两条路径是否一定会发生交叉,若发生交叉,则选择一个利用布线的区域进行跳线,其余区域则不跳线,这两个临时端口则需要用该发明提出的规划方法确定相对位置关系,所述确定方法如下:
(1)确定两条路径共同通过的交叠区域;
(2)根据端口位置和进入离开情况确定第一个和最后一个交叠区域中两路径的位置顺序,若两区域相反则不需要安排跳线区域,否则则需要;确定位置顺序方法:
情况1:两路径都是端口与交叠区域相邻,即端口不再交叠区域内,但到达交叠区域不需要经过其他交叠区域,比较端口坐标和端口进入交叠区域的边界,确定两条路径相对位置关系。如两个路径通过左边界进入交叠区域,则相对该边界,纵坐标大的端口将位于纵坐标小的端口顺时针位置,对应的路径产生顺时针位置关系;
情况2:两路径的端口都已在交叠区域中,比较端口左边和端口离开交叠区域的边界,确定两条路径相对位置关系。如两个路径通过下边界离开交叠区域,则相对该边界,横坐标大的端口将位于横坐标小的端口逆时针位置,对应的路径产生逆时针位置关系;
情况3:两路径端口其中一个已在交叠区域中,另一个完全通过该交叠区域,根据完全通过该交叠区域的路径进入和离开交叠区域的边界和另一路径离开交叠区域的边界来确定两条路径相对位置关系。如完全通过交叠区域的路径通过左边界进入区域和下边界离开区域,另一路径通过下边界离开区域,则相对下边界,完全通过区域的路径位于另一路径的顺时针方向;
情况4:两路径通过不同的边界进入交叠区域,通过相同的边界离开区域,则根据这3个边界确定路径相对位置关系。如路径1从左边界进入、下边界离开,路径2从右边界进入、下边界离开,则相对下边界,路径1位于路径2顺时针方向;
以上和后续进入离开边界概念为相对概念,即根据具体情况可以互换进入离开的边界;
(3)在一般的交叠区域,两路径从相同的边界进入交叠区域,从另一相同的边界离开交叠区域。从第一交叠区域开始梳理,后续的交叠区域继承上一个交叠区域的两路径的相对位置关系,直至到达跳线区域或最后一个区域。到达跳线区域时,在离开跳线区域时交换路径相对位置关系,实现跳线。无跳线的情况下,沿边界遍历4个临时端口,同路径的两个临时端口相邻,有跳线情况则交叉出现;
综上所述,对于路径两两进行路径规划,则能确定每个交叠区域中的每个边界上任意两个临时端口的相对位置关系,若有n个临时端口,则有C_n^2=\frac{n\left(n-1\right)}{2}个相对位置关系,跟据这些位置关系,可以对每个临时端口分别统计某一方向(顺时针或者逆时针)上临时端口数量,根据数量排序可以,可以获得该边界上这些端口的排序(顺时针或者逆时针)。
S5、确定临时端口位置;
具体地,在每个交叠区域的每个边界上,可以将临时端口分为4个部分,具体如下所示:
(1)在该交叠区域当前端口所属路径的另一临时端口位于当前端口所在边界的顺时针位置的边界;
(2)该交叠区域当前端口所属路径的另一临时端口位于当前端口所在边界的逆时针位置的边界;
(3)该交叠区域当前端口所属路径的另一临时端口位于当前端口所在边界的对边位置的边界;
(4)或者端口在交叠区域中;
对于上述(1)(2)类端口将靠近角落依次尝试放置,如左边界的端口,同路径另一临时端口位于上边界,则该类端口放置在左上角,从左边界的上端点开始依次往下尝试放置。(3)(4)类端口会一起规划,均放在(1)(2)类端口中间,对于(4)类端口,会优先考虑位置,让临时端口与原始端口对齐,减少原始端口到临时端口的绕线;
端口的层号不能超出所在区域可用金属层范围。端口层号根据距离起点终点的距离优先选择离起点或终点层号差小的金属层,端口需要避开障碍物,后放置的端口不能越过同层先放置端口在放置方向上的位置,即从上往下放置端口时,后放置的端口不能位于同层先放置端口的上方,端口之间需要保持一定的安全距离,该安全距离需要大于设计规则检查(design rulecheck,DRC)提供的值,避免走线金属扩大端口金属导致无法通过DRC检查,端口需要与边界的两端口保持一定间距,保证相邻边最近的两个临时端口能有空间互联。
S6、每个区域布线。
具体地,每条路径将在每个交叠区域留下1-2个临时端口,在每个矩形区域和交叠区域分别调用自动布线函数,则能实现对路径原始端口和临时端口之间的互联,总的布线金属会将路径的起点和终点连接;
矩形区域内使用以下所述的快速布线算法:
(1)在起点位置处尽可能跳层,每一个跳层成功的金属和原始金属均视为起点节点。跳层成功条件:无DRC错误,未超出布线区域有效金属层;
(2)每个起点金属往终点方向延申金属,若起点与终点水平或竖直方向上投影无交叠,则两个靠近终点的方向均尝试延申,金属的宽度为走线线宽,金属延申至与终点在延申方向上投影长度超过一倍线宽;
(3)对延申金属进行DRC检查,若有DRC错误,则回缩金属至无DRC错误,并将产生最大回缩的金属记录为当前金属的障碍物。若无DRC错误,尝试直连终点,直连金属仍进行该步骤的检查。完全通过DRC检查的情况下,即视为连线成功;
(4)遇见障碍物情况,产生绕线和跳层的避障方案,跳层方案:在回退后的金属末端尽可能跳层,每个跳层成功的金属视为新的起点节点,绕线方案:更改走线方向,新方向为回退金属走线方向左转或者右转,更改方向后的金属一直延申至在走线方向上越过障碍物,超出距离需要保障按原线宽沿着障碍物走线,与障碍物无DRC错误;或者在延申方向上与终点投影长度超出一倍线宽,绕线产生的金属需要进行步骤(3)的检查,回缩的情况重新进入步骤(4),每个绕线方案完成后产生新的金属视为新的起点节点,两个方案产生的起点节点重新进入步骤(2);
(5)布线完成后将产生的金属输出成新的gds文件,该文件中包含一个顶层cell,所有金属位于该cell中;
综上所述,本发明基于软件进行的具体步骤如下所示:
(1)在原有版图中加入新cell,新cell命名为“PIN_NAME”;
(2)如图8所示,在cell“PIN_NAME”中使用M1PIN,M2PIN…M7PIN画出对应金属层的可布线区域,使用上述PIN层在需要作为端口的金属上打上Label,Label的层为端口金属层对应的PIN层;
(3)读取版图,识别布线区域,端口金属,障碍物金属;
(4)对每个可布线区域进行分割,分割产生多个矩形子区域,将不同层坐标接近的区域合并成一个区域。有交叠的子区域之间建立联系,构成区域图;
(5)确定每个端口所在的区域,确定路径关系,同节点内需要每两个相连的端口将构成一条路径;
(6)每天路径根据步骤4产生的区域图跨区域寻路,获取每条路径需要经过的区域;
(7)确定每条路径经过交叠区域的哪些边界,确定临时端口所在边界,每两条路径进行一次路径规划,确定每一对路径是否需要安排跳线区域;当两条路径的临时端口位于同一区域的同一边界时,根据端口位置和路径走势确定端口位置关系。获取全部临时端口位置关系,在每个交叠区域边界整体该边界上临时端口的排序,获得完整的排序;
(8)如图9所示,在交叠区域的每个边界尝试放置端口,放置顺序与端口的排序一致。端口放置的结果需要满足DRC要求,靠近边界两端的临时端口需要预留布线的空间;
(9)在每个区域分别调用布线函数,布线函数需要将相同节点的端口金属连接,这些端口包括输入的原有端口,路径经过交叠区域边界产生的临时端口;
(10)如图10所示,将布线产生的金属导出为gds,gds名和顶层cell可自定义;
(11)将步骤(10)产生的gds导入到原始版图。
参照图2,一种基于路径优化的集成电路版图自动布线系统,包括:
切割模块,用于通过最大矩形切割法对可布线区域进行切割与解析,得到区域图;
择优模块,基于区域图,设置待连接端口并进行路径择优处理,得到寻路路径;
生成模块,用于结合区域图与寻路路径,根据预设临时端口生成规则,设置临时端口;
连接模块,用于通过自动布线函数对待连接端口与临时端口进行连接,得到布线结果。
上述方法实施例中的内容均适用于本系统实施例中,本系统实施例所具体实现的功能与上述方法实施例相同,并且达到的有益效果与上述方法实施例所达到的有益效果也相同。
以上是对本发明的较佳实施进行了具体说明,但本发明创造并不限于所述实施例,熟悉本领域的技术人员在不违背本发明精神的前提下还可做作出种种的等同变形或替换,这些等同的变形或替换均包含在本申请权利要求所限定的范围内。
Claims (3)
1.一种基于路径优化的集成电路版图自动布线方法,其特征在于,包括以下步骤:
通过最大矩形切割法对可布线区域进行切割与解析,得到区域图;
基于区域图,设置待连接端口并进行路径择优处理,得到寻路路径;
结合区域图与寻路路径,根据预设临时端口生成规则,设置临时端口;
通过自动布线函数对待连接端口与临时端口进行连接,得到布线结果;
所述通过最大矩形切割法对可布线区域进行切割与解析,得到区域图这一步骤,其具体包括:
设置可布线区域,所述可布线区域为多边形PIN层;
对可布线区域进行最大矩形切割,得到对应的待处理子区域,所述待处理子区域面积固定;
对所有待处理子区域的位置关系进行判断;
对判断到存在交叠关系的待处理子区域进行标记,得到交叠区域;
对判断到存在空间上下位置关系相同的待处理子区域进行合并,得到子区域;
将子区域作为顶点,交叠区域作为连接边,构建区域图;
所述基于区域图,设置待连接端口并进行路径择优处理,得到寻路路径这一步骤,其具体包括:
对可布线区域进行Label节点标记,设置待连接端口;
对待连接端口的位置信息进行判断;
对判断到位于同一区域图的待连接端口,进行直线连接处理,得到同区域路径;
对判断到位于不同区域图的待连接端口,进行跨区域最优路径连接处理,得到跨区域最优路径;
整合同区域路径与跨区域最优路径,得到寻路路径;
所述跨区域最优路径连接处理的具体步骤包括:
构造区域图的生成树;
访问终点节点对应的子叶,从子叶递归访问父节点,获取终点顶点到起点顶点的路径;
对待连接端口之间存在的路径数目进行判断;
判断到待连接端口之间存在多条路径,选取所述路径经过区域图的中心点坐标,分别计算对应区域图中心点坐标之间的曼哈顿距离;
选取曼哈顿距离最小的路径作为跨区域最优路径;
所述结合区域图与寻路路径,根据预设临时端口生成规则,设置临时端口这一步骤,其具体包括:
对交叠区域内通过的寻路路径数进行判断;
判断到交叠区域内存在一条寻路路径,在寻路路径进入或离开交叠区域内或交叠区域边界产生的交点处放置临时端口;
判断到交叠区域内存在多条寻路路径;
根据待连接端口位置和进入离开情况确定第一个和最后一个交叠区域中两路径的位置顺序,若两交叠区域相同则根据临时端口位置顺序法放置临时端口;
根据两路径从相同的边界进入交叠区域,从另一相同的边界离开交叠区域,对离开的交叠区域进行判断;
判断到离开的交叠区域未存在跳线情况,沿交叠区域边界放置临时端口;
所述临时端口位置顺序法,其具体包括:
根据跳线安排和待连接端口相对位置坐标,确定任意临时端口之间的相对位置关系,获得所有临时端口的排序;
所述临时端口的位置包括在该交叠区域当前临时端口所属路径的另一临时端口位于当前临时端口所在边界的顺时针位置的边界;该交叠区域当前临时端口所属路径的另一临时端口位于当前临时端口所在边界的逆时针位置的边界;该交叠区域当前临时端口所属路径的另一临时端口位于当前临时端口所在边界的对边位置的边界;临时端口在交叠区域中;
所述通过自动布线函数对待连接端口与临时端口进行连接,得到布线结果这一步骤,其具体包括:
设置起点节点,所述起点节点满足DRC规则且未超出布线区域;
根据起点节点向终点节点进行延伸布线,直至所有端口均布线完成;
选取满足DRC规则的布线,得到布线结果。
2.根据权利要求1所述一种基于路径优化的集成电路版图自动布线方法,其特征在于,所述延伸布线过程还包括:
对于存在障碍物的延伸布线,根据布线路径选取跳层方案或绕线方案进行延伸布线,所述跳层方案为在回退后的端口处进行跳层,每个跳层成功的端口视为新的起点节点,所述绕线方案为更改延伸布线方向,新布线方向为回退端口布线方向左转或右转,更改方向后的端口一直延申至在布线方向上越过障碍物。
3.一种基于路径优化的集成电路版图自动布线系统,其特征在于,用于执行如权利要求1所述的基于路径优化的集成电路版图自动布线方法,包括以下模块:
切割模块,用于通过最大矩形切割法对可布线区域进行切割与解析,得到区域图;
择优模块,基于区域图,设置待连接端口并进行路径择优处理,得到寻路路径;
生成模块,用于结合区域图与寻路路径,根据预设临时端口生成规则,设置临时端口;
连接模块,用于通过自动布线函数对待连接端口与临时端口进行连接,得到布线结果。
Priority Applications (1)
Application Number | Priority Date | Filing Date | Title |
---|---|---|---|
CN202310018144.9A CN116029254B (zh) | 2023-01-06 | 2023-01-06 | 一种基于路径优化的集成电路版图自动布线方法及系统 |
Applications Claiming Priority (1)
Application Number | Priority Date | Filing Date | Title |
---|---|---|---|
CN202310018144.9A CN116029254B (zh) | 2023-01-06 | 2023-01-06 | 一种基于路径优化的集成电路版图自动布线方法及系统 |
Publications (2)
Publication Number | Publication Date |
---|---|
CN116029254A CN116029254A (zh) | 2023-04-28 |
CN116029254B true CN116029254B (zh) | 2024-04-12 |
Family
ID=86070309
Family Applications (1)
Application Number | Title | Priority Date | Filing Date |
---|---|---|---|
CN202310018144.9A Active CN116029254B (zh) | 2023-01-06 | 2023-01-06 | 一种基于路径优化的集成电路版图自动布线方法及系统 |
Country Status (1)
Country | Link |
---|---|
CN (1) | CN116029254B (zh) |
Families Citing this family (4)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
CN117217156B (zh) * | 2023-08-31 | 2024-05-28 | 中山大学 | 基于贝叶斯优化的射频电路版图迭代方法、设备和介质 |
CN117077611B (zh) * | 2023-10-13 | 2024-01-23 | 青岛展诚科技有限公司 | 一种集成电路版图图形切割方法 |
CN117783841B (zh) * | 2023-12-27 | 2024-07-19 | 苏州异格技术有限公司 | 一种fpga布线覆盖率测试方法、装置、设备及介质 |
CN117829084B (zh) * | 2024-03-04 | 2024-05-14 | 杭州广立微电子股份有限公司 | 一种三维网格绕线方法 |
Citations (7)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
JP2008047562A (ja) * | 2006-08-10 | 2008-02-28 | Fukuoka Pref Gov Sangyo Kagaku Gijutsu Shinko Zaidan | 回路基板の配線方法及び配線支援装置 |
CN101944149A (zh) * | 2010-09-15 | 2011-01-12 | 清华大学 | 基于无网格模型的集成电路点到点的布线方法 |
CN102663169A (zh) * | 2012-03-21 | 2012-09-12 | 领佰思自动化科技(上海)有限公司 | 集成电路版图设计规则检查的方法及其系统 |
US10424096B1 (en) * | 2019-02-08 | 2019-09-24 | Jordan Raykov | Technique for orthogonal edge routing of directed layered graphs with edge crossings reduction |
CN111737810A (zh) * | 2020-08-27 | 2020-10-02 | 科大讯飞(苏州)科技有限公司 | 寻路方法、装置、设备及存储介质 |
CN112241998A (zh) * | 2020-10-16 | 2021-01-19 | 信成网络科技(阳江)有限公司 | 基于点云的快速剖切方法、智能终端及云平台 |
CN114707451A (zh) * | 2022-04-21 | 2022-07-05 | 海光信息技术股份有限公司 | 数字电路的版图规划方法、装置、电子设备、存储介质 |
Family Cites Families (1)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
US20230071424A1 (en) * | 2019-10-30 | 2023-03-09 | Cerebras Systems Inc. | Placement of compute and memory for accelerated deep learning |
-
2023
- 2023-01-06 CN CN202310018144.9A patent/CN116029254B/zh active Active
Patent Citations (7)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
JP2008047562A (ja) * | 2006-08-10 | 2008-02-28 | Fukuoka Pref Gov Sangyo Kagaku Gijutsu Shinko Zaidan | 回路基板の配線方法及び配線支援装置 |
CN101944149A (zh) * | 2010-09-15 | 2011-01-12 | 清华大学 | 基于无网格模型的集成电路点到点的布线方法 |
CN102663169A (zh) * | 2012-03-21 | 2012-09-12 | 领佰思自动化科技(上海)有限公司 | 集成电路版图设计规则检查的方法及其系统 |
US10424096B1 (en) * | 2019-02-08 | 2019-09-24 | Jordan Raykov | Technique for orthogonal edge routing of directed layered graphs with edge crossings reduction |
CN111737810A (zh) * | 2020-08-27 | 2020-10-02 | 科大讯飞(苏州)科技有限公司 | 寻路方法、装置、设备及存储介质 |
CN112241998A (zh) * | 2020-10-16 | 2021-01-19 | 信成网络科技(阳江)有限公司 | 基于点云的快速剖切方法、智能终端及云平台 |
CN114707451A (zh) * | 2022-04-21 | 2022-07-05 | 海光信息技术股份有限公司 | 数字电路的版图规划方法、装置、电子设备、存储介质 |
Non-Patent Citations (5)
Title |
---|
"A Compact On-Chip Pad Structure With an Embedded Capacitor for Broadband Millimeter-Wave Bond-Wire Interconnection";Junyang Chen 等;《IEEE Transactions on Components, Packaging and Manufacturing Technology》;第12卷(第12期);第1949-1958 * |
"基于多层路径规划的自动布线优化研究";王永忠 等;王永忠 等;第21卷(第10期);第169-174页 * |
"详细布线中的快速重布线及设计规则处理方法研究";张竞翀;《中国优秀硕士学位论文全文数据库(信息科技辑)》;第1-76页 * |
"适用于平面多边形区域的定阻值自动布线算法";景东 等;《自动化与信息工程》;第42卷(第06期);第18-23页 * |
基于遗传算法的区域配电网单线图的自动布局算法;葛成余;周博曦;朱颂怡;张俊玲;孙联喜;王金亮;张浩;刘书阁;韩先鹤;;中国电力(12);全文 * |
Also Published As
Publication number | Publication date |
---|---|
CN116029254A (zh) | 2023-04-28 |
Similar Documents
Publication | Publication Date | Title |
---|---|---|
CN116029254B (zh) | 一种基于路径优化的集成电路版图自动布线方法及系统 | |
US6002857A (en) | Symbolic constraint-based system for preroute reconstruction following floorplan incrementing | |
US6519751B2 (en) | Method and apparatus for accurate crosspoint allocation in VLSI area routing | |
US5801960A (en) | Layout method of wiring pattern for semiconductor integrated circuit | |
US20010038612A1 (en) | Automatic routing system for circuit layout | |
JPH10270563A (ja) | 集積回路の自動概略配線方法 | |
CN111125993B (zh) | 一种满足最小Cut数量约束的布线方法 | |
CN111553125A (zh) | 一种考虑先进技术的超大规模集成电路详细布线方法 | |
CN113987996A (zh) | 模拟芯片电路绕线方法 | |
JP2010198466A (ja) | 配線基板の配線設計方法 | |
KR100910421B1 (ko) | 집적회로를 자동으로 배선하는 방법 및 시스템, 집적회로를 자동으로 배선하기 위한 하나 이상의 명령어로 구성된 하나 이상의 시퀀스를 갖는 프로그램을 기록한 컴퓨터로 읽을 수 있는 기록매체 및 집적회로 레이아웃을 자동으로 검증하는 방법 | |
JPH04142060A (ja) | 半導体集積装置の配線方法 | |
US6567954B1 (en) | Placement and routing method in two dimensions in one plane for semiconductor integrated circuit | |
JP5900540B2 (ja) | レイアウト設計方法及びレイアウト設計支援プログラム | |
CN112989751B (zh) | 基于分支定界法的电路通道布线方法、装置及电子设备 | |
JP3157732B2 (ja) | 対話型配線パターン作成システム | |
US7797649B1 (en) | Method and system for implementing an analytical wirelength formulation | |
US5825659A (en) | Method for local rip-up and reroute of signal paths in an IC design | |
Tomioka et al. | Routability driven modification method of monotonic via assignment for 2-layer ball grid array packages | |
JP5672341B2 (ja) | レイアウト設計方法、装置及びプログラム | |
CN117688895B (zh) | 电路图生成方法、计算机设备及存储介质 | |
Hamachi et al. | Magic's obstacle-avoiding global router | |
JP2000057175A (ja) | 半導体集積回路装置の自動配線方式 | |
JPH05160375A (ja) | 自動配線方法 | |
JP5187217B2 (ja) | 半導体レイアウトシステム、方法、及び、プログラム |
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 |