Nothing Special   »   [go: up one dir, main page]

CN113268946B - 一种基于连线总和最小的芯片布局方法 - Google Patents

一种基于连线总和最小的芯片布局方法 Download PDF

Info

Publication number
CN113268946B
CN113268946B CN202110644276.3A CN202110644276A CN113268946B CN 113268946 B CN113268946 B CN 113268946B CN 202110644276 A CN202110644276 A CN 202110644276A CN 113268946 B CN113268946 B CN 113268946B
Authority
CN
China
Prior art keywords
rectangular circuit
circuit module
sequence pair
current
rectangular
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
Application number
CN202110644276.3A
Other languages
English (en)
Other versions
CN113268946A (zh
Inventor
刘强
李龙
魏丽军
陈新
严都喜
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Guangdong University of Technology
Original Assignee
Guangdong University of Technology
Priority date (The priority date 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 date listed.)
Filing date
Publication date
Application filed by Guangdong University of Technology filed Critical Guangdong University of Technology
Priority to CN202110644276.3A priority Critical patent/CN113268946B/zh
Publication of CN113268946A publication Critical patent/CN113268946A/zh
Application granted granted Critical
Publication of CN113268946B publication Critical patent/CN113268946B/zh
Priority to US17/572,667 priority patent/US11347924B1/en
Active legal-status Critical Current
Anticipated expiration legal-status Critical

Links

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/39—Circuit design at the physical level
    • G06F30/392—Floor-planning or layout, e.g. partitioning or placement
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F2111/00—Details relating to CAD techniques
    • G06F2111/04—Constraint-based CAD
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F2111/00—Details relating to CAD techniques
    • G06F2111/10—Numerical modelling

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Hardware Design (AREA)
  • Physics & Mathematics (AREA)
  • Theoretical Computer Science (AREA)
  • Architecture (AREA)
  • Evolutionary Computation (AREA)
  • Geometry (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Design And Manufacture Of Integrated Circuits (AREA)

Abstract

一种基于连线总和最小的芯片布局方法，包括：将总连线长初始化为一个很大的数，再控制迭代次数，不断随机生成序列对来表示各矩形电路模块间的上下左右位置关系输入到模型求解，得出在当前迭代次数下线长最小的序列对；再通过改变该序列对的领域算子得到新的序列对带入模型，如果得出的总线长比原来的小则接收改变领域算子所得到新序列对，否则舍弃；直到达到领域算子改变的迭代次数；最后输出最小总线长，以及各矩形电路模块的坐标，得到一个基于连线总和最小的芯片排布。本发明能够通过最小化芯片连线的总线长来提升集成芯片的性能，同时生成一个合理的芯片排布，节省生产矩形芯片的材料，提高材料利用率，使得在大批量生产中带来显著经济效益。

Description

一种基于连线总和最小的芯片布局方法
技术领域
本发明涉及芯片布局技术领域，尤其涉及一种基于连线总和最小的芯片布局方法。
背景技术
芯片连线总和最小，是指在VLSI(大规模集成)芯片设计中，已知n个宽、高分别任意给定的矩形电路模块，如何确定一个大小可变矩形芯片，使得所有的矩形电路模块都能够合法地放入其中，并且要求矩形芯片中各电路模块间的连线总和尽可能小。合法是指放入任意矩形电路模块后不超出矩形芯片的边界、电路模块的边平行于矩形芯片的边，且各电路模块间两两互不重叠。连线总和是指每个矩形电路模块上有许多引脚，各个矩形电路模块从引脚处通过导线连通所需要导线的总长度；
最小化芯片连线总和问题是VLSI(大规模集成)芯片设计的一个重要步骤。在大规模集成芯片设计领域，通常需要在矩形芯片上放置一组矩形模块，并且这些模块需要通过导线连接，要考虑的目标是最小化矩形芯片的面积和最小化导线的总长度。由于芯片性能是在大规模集成芯片设计中最主要考虑的优化目标，互连线的长短是影响芯片的功耗、延时、可靠性等性能的主要因素；另一方面生产芯片的材料非常昂贵，总连线长度最小化可以节约金属导线的使用，因此材料的节约对于降低制造成本有重要的影响，特别是在大批量生产中，提高芯片材料利用率可以带来显著的经济效益；
但是目前大多算法应用在大规模集成芯片设计中主要是优化芯片的总面积，而忽略各矩形电路模块间的互连线，从而不能降低芯片的功耗和延时。针对大规模集成芯片中线长最小化问题，目前的解决方法是把各矩形电路模块的连接位置简化为模块的中心与其他模块相连接，这样使得得出的结果过于简化，不具有代表性，不能更好的运用到实际问题当中。
本发明针对最小化芯片连线总和问题提出一种基于线长最小化的芯片排布方法，该方法在大规模集成芯片设计中能够通过最小化芯片连线的总线长从而最大程度的提升集成芯片的性能，同时生成一个合理的芯片排布，还可以最大程度的节省生产矩形芯片的材料，提高材料的利用率，从而使得在大批量生产中给企业带来显著的经济效益。并且该方法优于现有方法并针对大多数经典实例改进了解决方案。
发明内容
本发明的目的在于针对背景技术中的缺陷，提出一种基于连线总和最小的芯片布局方法，实现在大规模集成芯片设计中能够通过最小化芯片连线的总线长从而最大程度的提升集成芯片的性能，同时生成一个合理的芯片排布，还可以最大程度的节省生产矩形芯片的材料，提高材料的利用率，从而使得在大批量生产中带来显著的经济效益。
为达此目的，本发明采用以下技术方案：
一种基于连线总和最小的芯片布局方法，包括如下步骤：
步骤A：将芯片总连线长初始化为最大的预设线长，初始化迭代次数；
步骤B：随机生成一个序列对，所述序列对用于表示各矩形电路模块间的上下左右位置关系，将序列对输入至模型求解，获得当前迭代次数下最小总连线长及其所对应的当前序列对；
步骤C：改变当前序列对的领域算子得到新序列对，将新的序列对输入至原始模型求解，获得新序列对及其所对应的总连线长；
步骤D：判断新序列对所对应的总连线长是否小于当前序列对所对应的总连线长，若否，则删除新序列对，保留当前序列对，重复执行步骤C；若是，则删除当前序列对，保留新序列对并将其重新标记为当前序列对；
步骤E：判断是否达到领域算子改变的迭代次数，若是，则输出当前序列对所对应的总连线长和各矩形电路模板的坐标位置，该总连线长为最小总连线长；若否，则重复执行步骤C。
优选的，在所述步骤B中还包括基于矩形电路模块确定矩形电路模块的引脚坐标信息，将各矩形模块的引脚坐标信息集合生成引脚网络集合；
随机生成一个序列对，各所述矩形电路模块之间的位置关系以该序列对的形式进行表示；
将该序列对、矩形电路模块、引脚坐标信息和引脚网络集合输入至原始模型进行求解以获得当前迭代次数下总连线长最小的所对应的当前序列对。
优选的，所述序列对用于表示各矩形电路模块间的上下左右位置关系，具体包括：
基于正负两个子序列对表示各矩形电路模块之间的上下左右的位置关系；
若当前矩形电路模块在正负子序列对中的序列位置均位于另一矩形电路模块的前面，则当前矩形电路模块的实际位置位于另一矩形电路模块的左边；
若当前矩形电路模块在正负子序列对中的序列位置均位于另一矩形电路模块的后面，则当前矩形电路模块的实际位置位于另一矩形电路模块的右边；
若当前矩形电路模块在正子序列中的序列位置位于另一矩形电路模块的前面，在负子序列对中的序列位置位于另一矩形电路模块的后面，则当前矩形电路模块的实际位置位于另一矩形电路模块的上面；
若当前矩形电路模块在正子序列中的序列位置位于另一矩形电路模块的后面，在负子序列对中的序列位置位于另一矩形电路模块的前面，则当前矩形电路模块的实际位置位于另一矩形电路模块的下面。
优选的，所述步骤B还包括：
步骤B1：随机生成一个序列对，将该序列对、矩形电路模块、引脚坐标信息和引脚网络集合输入至模型进行求解，获得新序列对以及新序列所对应的总连线长；
步骤B2：判断新序列对所对应的总连线长是否小于原序列对所对应的总连线长，若是，则保留新序列对所对应的总连线长，将其替换原序列对，跳转至步骤B3；若否，则重复执行步骤B1；
步骤B3：判断是否达到迭代次数，若是，则输出步骤B2中所保留的序列对和其所对应的总连线长；若否，则重复执行步骤B1。
优选的，所述原始模型包括：
Figure BDA0003108465340000041
Figure BDA0003108465340000042
Figure BDA0003108465340000043
Figure BDA0003108465340000044
Figure BDA0003108465340000045
Figure BDA0003108465340000046
Figure BDA0003108465340000047
Figure BDA0003108465340000048
Figure BDA0003108465340000051
Figure BDA0003108465340000052
Figure BDA0003108465340000053
Figure BDA0003108465340000054
t0-xi≥wi-W,t0-yi≥hi-H；
yi-yj≥hj+kij,yj-yi≥hi+kij；
xi-xj≥wj+dij,xj-xi≥wi+dij；
其中：
N表示每一个引脚网络；
w(N)表示每个引脚网络的权重；
Figure BDA0003108465340000055
表示所有网络集合；
Figure BDA0003108465340000056
表示四个决策变量，四个决策变量构成每个网络N的一个最小周期长轴平行矩形
Figure BDA0003108465340000057
p表示引脚；
xi(p),yi(p)表示引脚p所在矩形电路模块ri的横坐标和纵坐标；
x(p),y(p)表示引脚p相对它所在矩形电路模块坐标的偏移量；
t0表示一个常数；
ri表示矩形电路模块；
R表示所有矩形电路模块的集合；
xi,yi表示矩形电路模块ri的横坐标和纵坐标；
xj,yj表示矩形电路模块rj的横坐标和纵坐标；
kij表示矩形电路模块ri,rj间垂直方向上的布线间隙；
dij表示矩形电路模块ri,rj间水平方向上的布线间隙；
W表示所有矩形电路模块所要放置区域的宽，H表示所有矩形电路模块所要放置区域的高；
wi和hi表示矩形电路模块ri的高和宽；
wj和hj表示矩形电路模块rj的高和宽。
优选的，包括将所述原始模型转变为对偶模型以获得新序列对以及新序列所对应的总连线长；
所述对偶模型包括：
Figure BDA0003108465340000061
max∑bijfij；
其中：
bij表示原始模型约束条件的右端项；
fij表示原始模型约束vj-vi≥bij所对应的对偶变量；
fjk表示原始模型约束vk-vj≥bjk所对应的对偶变量；
vj,vi,vk表示原始模型变量的类型，原始模型变量类型包括：
Figure BDA0003108465340000062
xi,yi,xi(p),yi(p)，其中x(N)-,y(N)-表示原始模型中
Figure BDA0003108465340000063
x(N)+,y(N)+表示原始模型中
Figure BDA0003108465340000064
本发明相对于现有技术所实现的技术效果：
本发明提出了一种优化目标为线片互连线总和最小的方法来生成一个芯片的排布，从而提高芯片的性能。该方法在考虑连线总和最小的同时还会得出一个更优的芯片排布(使得芯片中各矩形电路模块尽可能的排布紧凑，从而在一定程度上减小芯片的总面积)。与现有的方法相比，该方法更加简单和易于实施，并且将问题模型转化为其对偶模型，就变成了一个最大费用流问题，使得问题在多项式时间内可解，从而提高了效率。
附图说明
图1是本发明其中一个实施例的连线总和最小的芯片布局流程图；
图2是本发明其中一个实施例的以序列对表示a、b两个矩形电路模块的位置关系表。
具体实施方式
下面结合附图并通过具体实施方式来进一步说明本发明的技术方案。
目前大多数技术应用在大规模集成芯片设计中主要是优化芯片的总面积，而忽略各矩形电路模块间的互连线，从而不能降低芯片的功耗和延时。针对大规模集成芯片中线长最小化问题，目前的解决方法是把各矩形电路模块的连接位置简化为模块的中心与其他模块相连接，这样使得得出的结果过于简化，不具有代表性，不能更好的运用到实际问题当中，为了解决上述问题，本申请提出一种基于连线总和最小的芯片布局方法，通过将总连线长初始化为一个很大的数，再控制迭代次数，不断随机生成序列对来表示各矩形电路模块间的上下左右位置关系输入到模型求解，得出在当前迭代次数下线长最小的序列对；再通过改变该序列对的领域算子得到新的序列对带入模型，如果得出的总线长比原来的小则接收改变领域算子所得到新序列对，否则舍弃；直到达到领域算子改变的迭代次数；最后输出最小总线长，以及各矩形电路模块的坐标，得到一个基于连线总和最小的芯片排布；
如图1所示，其中，图1中L表示当前总连线长度，L′表示一次求解后的总连线长度，Γ表示当前随机生成的序列对，Γ′表示求解后的序列对；具体包括如下步骤：
步骤A：将芯片总连线长初始化为最大的预设线长，初始化迭代次数；
步骤B：随机生成一个序列对，所述序列对用于表示各矩形电路模块间的上下左右位置关系，将序列对输入至模型求解，获得当前迭代次数下总连线长最小的所对应的当前序列对；
优选的，包括基于矩形电路模块确定矩形电路模块的引脚坐标信息，将各矩形模块的引脚坐标信息集合生成引脚网络集合；
随机生成一个序列对，各所述矩形电路模块之间的位置关系以该序列对的形式进行表示；
将该序列对、矩形电路模块、引脚坐标信息和引脚网络集合输入至原始模型进行求解以获得当前迭代次数下总连线长最小的所对应的当前序列对。
优选的，所述序列对用于表示各矩形电路模块间的上下左右位置关系，具体包括：
基于正负两个子序列对表示各矩形电路模块之间的上下左右的位置关系；
若当前矩形电路模块在正负子序列对中的序列位置均位于另一矩形电路模块的前面，则当前矩形电路模块的实际位置位于另一矩形电路模块的左边；
若当前矩形电路模块在正负子序列对中的序列位置均位于另一矩形电路模块的后面，则当前矩形电路模块的实际位置位于另一矩形电路模块的右边；
若当前矩形电路模块在正子序列中的序列位置位于另一矩形电路模块的前面，在负子序列对中的序列位置位于另一矩形电路模块的后面，则当前矩形电路模块的实际位置位于另一矩形电路模块的上面；
若当前矩形电路模块在正子序列中的序列位置位于另一矩形电路模块的后面，在负子序列对中的序列位置位于另一矩形电路模块的前面，则当前矩形电路模块的实际位置位于另一矩形电路模块的下面。
如图2所示，本申请以a、b两个矩形电路模块为例进行说明，两两模块之间进行比较；有两个模块a、b，如果a在正负序列中都在b的前面则表示a在b的左边；如果a在正负序列中都在b的后面则表示a在b的右边；如果在正序列中a在b的前面，在负序列中a在b的后面，则表示a在b的上面；如果在正序列中a在b的后面，在负序列中a在b的前面，则表示a在b的下面。例如有一个序列对(Γ+,Γ-)＝(124,214)，可以看出在正负序列中1都在4的前面，则表示1在4左边；在正序列中1在2的前面，在负序列中1在2的后面，则表示1在2的上面；在正负序列中2都在4的前面，则表示2在4的左边；这就是这个序列对(Γ+,Γ-)＝(124,214)表示的这三个模块间的位置关系；
优选的，所述步骤B还包括：
步骤B1：随机生成一个序列对，将该序列对、矩形电路模块、引脚坐标信息和引脚网络集合输入至模型进行求解，获得新序列对以及新序列所对应的总连线长；
步骤B2：判断新序列对所对应的总连线长是否小于原序列对所对应的总连线长，若是，则保留新序列对所对应的总连线长，将其替换原序列对，跳转至步骤B3；若否，则重复执行步骤B1；
步骤B3：判断是否达到迭代次数，若是，则输出步骤B2中所保留的序列对和其所对应的总连线长；若否，则重复执行步骤B1。
步骤C：改变当前序列对的领域算子得到新序列对，将新的序列对输入至原始模型求解，获得新序列对所对应的总连线长；
步骤D：判断新序列对所对应的总连线长是否小于当前序列对所对应的总连线长，若否，则删除新序列对，保留当前序列对，重复执行步骤C；若是，则删除当前序列对，保留新序列对并将其重新标记为当前序列对；
步骤E：判断是否达到领域算子改变的迭代次数，若是，则输出当前序列对所对应的总连线长和各矩形电路模板的坐标位置，该总连线长为最小总连线长；若否，则重复执行步骤C。
优选的，所述原始模型包括：
Figure BDA0003108465340000101
Figure BDA0003108465340000102
Figure BDA0003108465340000103
Figure BDA0003108465340000104
Figure BDA0003108465340000105
Figure BDA0003108465340000106
Figure BDA0003108465340000107
Figure BDA0003108465340000108
Figure BDA0003108465340000109
Figure BDA00031084653400001010
Figure BDA00031084653400001011
Figure BDA00031084653400001012
t0-xi≥wi-W,t0-yi≥hi-H；
yi-yj≥hj+kij,yj-yi≥hi+kij；
xi-xj≥wj+dij,xj-xi≥wi+dij；
其中：
N表示每一个引脚网络；
w(N)表示每个引脚网络的权重；
Figure BDA0003108465340000111
表示所有网络集合；
Figure BDA0003108465340000112
表示四个决策变量，四个决策变量构成每个网络N的一个最小周期长轴平行矩形
Figure BDA0003108465340000113
p表示引脚；
xi(p),yi(p)表示引脚p所在矩形电路模块ri的横坐标和纵坐标；
x(p),y(p)表示引脚p相对它所在矩形电路模块坐标的偏移量；
t0表示一个常数；
ri表示矩形电路模块；
R表示所有矩形电路模块的集合；
xi,yi表示矩形电路模块ri的横坐标和纵坐标；
xj,yj表示矩形电路模块rj的横坐标和纵坐标；
kij表示矩形电路模块ri,rj间垂直方向上的布线间隙；
dij表示矩形电路模块ri,rj间水平方向上的布线间隙；
W表示所有矩形电路模块所要放置区域的宽，H表示所有矩形电路模块所要放置区域的高；
wi和hi表示矩形电路模块ri的高和宽；
wj和hj表示矩形电路模块rj的高和宽。
优选的，包括将所述原始模型转变为对偶模型以获得新序列对以及新序列所对应的总连线长；
所述对偶模型包括：
Figure BDA0003108465340000121
max∑bijfij；
其中：
bij表示原始模型约束条件的右端项；
fij表示原始模型约束vj-vi≥bij所对应的对偶变量；
fjk表示原始模型约束vk-vj≥bjk所对应的对偶变量；
vj,vi,vk表示原始模型变量的类型，原始模型变量类型包括：
Figure BDA0003108465340000122
xi,yi,xi(p),yi(p)，其中x(N)-,y(N)-表示原始模型中
Figure BDA0003108465340000123
x(N)+,y(N)+表示原始模型中
Figure BDA0003108465340000124
以上结合具体实施例描述了本发明的技术原理。这些描述只是为了解释本发明的原理，而不能以任何方式解释为对本发明保护范围的限制。基于此处的解释，本领域的技术人员不需要付出创造性的劳动即可联想到本发明的其它具体实施方式，这些方式都将落入本发明的保护范围之内。

Claims (4)

1.一种基于连线总和最小的芯片布局方法，其特征在于：包括如下步骤：
步骤A：将芯片总连线长初始化为最大的预设线长，初始化迭代次数；
步骤B：随机生成一个序列对，所述序列对用于表示各矩形电路模块间的上下左右位置关系，将序列对输入至模型求解，获得当前迭代次数下最小总连线长及其所对应的当前序列对；
步骤C：改变当前序列对的领域算子得到新序列对，将新的序列对输入至原始模型求解，获得新序列对及其所对应的总连线长；
步骤D：判断新序列对所对应的总连线长是否小于当前序列对所对应的总连线长，若否，则删除新序列对，保留当前序列对，重复执行步骤C；若是，则删除当前序列对，保留新序列对并将其重新标记为当前序列对；
步骤E：判断是否达到领域算子改变的迭代次数，若是，则输出当前序列对所对应的总连线长和各矩形电路模板的坐标位置，该总连线长为最小总连线长；若否，则重复执行步骤C；
所述步骤C中，所述原始模型包括：
Figure 239315DEST_PATH_IMAGE001
；
Figure 608986DEST_PATH_IMAGE002
；
Figure 591985DEST_PATH_IMAGE003
；
Figure 174145DEST_PATH_IMAGE004
；
Figure 113151DEST_PATH_IMAGE005
；
Figure 873297DEST_PATH_IMAGE006
；
Figure 327281DEST_PATH_IMAGE007
；
Figure 854077DEST_PATH_IMAGE008
；
Figure 726218DEST_PATH_IMAGE009
；
Figure 906532DEST_PATH_IMAGE010
；
Figure 598545DEST_PATH_IMAGE011
；
Figure 124024DEST_PATH_IMAGE012
，
Figure 585092DEST_PATH_IMAGE013
；
Figure 467467DEST_PATH_IMAGE014
；
Figure 646775DEST_PATH_IMAGE015
；
Figure 249795DEST_PATH_IMAGE016
；
其中：
N表示每一个引脚网络；
Figure 80217DEST_PATH_IMAGE017
表示每个引脚网络的权重；
Figure 353066DEST_PATH_IMAGE018
表示所有网络集合；
Figure 268938DEST_PATH_IMAGE019
表示四个决策变量，四个决策变量构成每个网络N的一个最小周期长轴平行矩形
Figure 285436DEST_PATH_IMAGE020
；
p表示引脚；
Figure 580151DEST_PATH_IMAGE021
表示引脚p所在矩形电路模块
Figure 538749DEST_PATH_IMAGE022
的横坐标和纵坐标；
x(p),y(p)表示引脚p相对它所在矩形电路模块坐标的偏移量；
Figure 427070DEST_PATH_IMAGE023
表示一个常数；
Figure 496526DEST_PATH_IMAGE022
表示矩形电路模块；
R表示所有矩形电路模块的集合；
Figure 786693DEST_PATH_IMAGE024
表示矩形电路模块
Figure 650613DEST_PATH_IMAGE022
的横坐标和纵坐标；
Figure 760651DEST_PATH_IMAGE025
表示矩形电路模块
Figure 368219DEST_PATH_IMAGE026
的横坐标和纵坐标；
Figure 512893DEST_PATH_IMAGE027
表示矩形电路模块
Figure 813293DEST_PATH_IMAGE028
间垂直方向上的布线间隙；
Figure 535261DEST_PATH_IMAGE029
表示矩形电路模块
Figure 697252DEST_PATH_IMAGE028
间水平方向上的布线间隙；
W表示所有矩形电路模块所要放置区域的宽，H表示所有矩形电路模块所要放置区域的高；
Figure 945700DEST_PATH_IMAGE030
和
Figure 167734DEST_PATH_IMAGE031
表示矩形电路模块
Figure 767211DEST_PATH_IMAGE022
的高和宽；
Figure 732893DEST_PATH_IMAGE032
和
Figure 101427DEST_PATH_IMAGE033
表示矩形电路模块
Figure 963203DEST_PATH_IMAGE026
的高和宽；
将所述原始模型转变为对偶模型以获得新序列对以及新序列所对应的总连线长；
所述对偶模型包括：
Figure 49977DEST_PATH_IMAGE034
；
Figure 288191DEST_PATH_IMAGE035
；
其中：
Figure 776810DEST_PATH_IMAGE036
表示原始模型约束条件的右端项；
Figure 75068DEST_PATH_IMAGE037
表示原始模型约束
Figure 649137DEST_PATH_IMAGE038
所对应的对偶变量；
Figure 550097DEST_PATH_IMAGE039
表示原始模型约束
Figure 112797DEST_PATH_IMAGE040
所对应的对偶变量；
Figure 831223DEST_PATH_IMAGE041
表示原始模型变量的类型，原始模型变量类型包括：
Figure 112163DEST_PATH_IMAGE042
,
Figure 82393DEST_PATH_IMAGE043
，其中
Figure 14445DEST_PATH_IMAGE044
表示原始模型中
Figure 654505DEST_PATH_IMAGE045
，
Figure 672009DEST_PATH_IMAGE046
表示原始模型中
Figure 180351DEST_PATH_IMAGE047
。
2.根据权利要求1所述一种基于连线总和最小的芯片布局方法，其特征在于：
在所述步骤B中还包括基于矩形电路模块确定矩形电路模块的引脚坐标信息，将各矩形模块的引脚坐标信息集合生成引脚网络集合；
随机生成一个序列对，各所述矩形电路模块之间的位置关系以该序列对的形式进行表示；
将该序列对、矩形电路模块、引脚坐标信息、引脚网络集合和矩形电路模块间的布线间隙输入至原始模型进行求解以获得当前迭代次数下总连线长最小的所对应的当前序列对。
3.根据权利要求1所述一种基于连线总和最小的芯片布局方法，其特征在于：
所述序列对用于表示各矩形电路模块间的上下左右位置关系，具体包括：
基于正负两个子序列对表示各矩形电路模块之间的上下左右的位置关系；
若当前矩形电路模块在正负子序列对中的序列位置均位于另一矩形电路模块的前面，则当前矩形电路模块的实际位置位于另一矩形电路模块的左边；
若当前矩形电路模块在正负子序列对中的序列位置均位于另一矩形电路模块的后面，则当前矩形电路模块的实际位置位于另一矩形电路模块的右边；
若当前矩形电路模块在正子序列中的序列位置位于另一矩形电路模块的前面，在负子序列对中的序列位置位于另一矩形电路模块的后面，则当前矩形电路模块的实际位置位于另一矩形电路模块的上面；
若当前矩形电路模块在正子序列中的序列位置位于另一矩形电路模块的后面，在负子序列对中的序列位置位于另一矩形电路模块的前面，则当前矩形电路模块的实际位置位于另一矩形电路模块的下面。
4.根据权利要求2所述一种基于连线总和最小的芯片布局方法，其特征在于：
所述步骤B还包括：
步骤B1：随机生成一个序列对，将该序列对、矩形电路模块、引脚坐标信息和引脚网络集合输入至模型进行求解，获得新序列对以及新序列所对应的总连线长；
步骤B2：判断新序列对所对应的总连线长是否小于原序列对所对应的总连线长，若是，则保留新序列对所对应的总连线长，将其替换原序列对，跳转至步骤B3；若否，则重复执行步骤B1；
步骤B3：判断是否达到迭代次数，若是，则输出步骤B2中所保留的序列对和其所对应的总连线长；若否，则重复执行步骤B1。
CN202110644276.3A 2021-06-09 2021-06-09 一种基于连线总和最小的芯片布局方法 Active CN113268946B (zh)

Priority Applications (2)

Application Number Priority Date Filing Date Title
CN202110644276.3A CN113268946B (zh) 2021-06-09 2021-06-09 一种基于连线总和最小的芯片布局方法
US17/572,667 US11347924B1 (en) 2021-06-09 2022-01-11 Chip layout method based on minimum total wire length

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
CN202110644276.3A CN113268946B (zh) 2021-06-09 2021-06-09 一种基于连线总和最小的芯片布局方法

Publications (2)

Publication Number Publication Date
CN113268946A CN113268946A (zh) 2021-08-17
CN113268946B true CN113268946B (zh) 2021-10-15

Family

ID=77234827

Family Applications (1)

Application Number Title Priority Date Filing Date
CN202110644276.3A Active CN113268946B (zh) 2021-06-09 2021-06-09 一种基于连线总和最小的芯片布局方法

Country Status (2)

Country Link
US (1) US11347924B1 (zh)
CN (1) CN113268946B (zh)

Families Citing this family (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN114548020B (zh) * 2022-04-25 2022-07-08 成都复锦功率半导体技术发展有限公司 一种多型号芯片的版图设计方法及其制备的芯片、终端
CN115392178B (zh) * 2022-08-10 2023-04-25 广东工业大学 芯片布局方法、芯片布局设备和计算机可读存储介质

Citations (8)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN87102679A (zh) * 1986-04-11 1987-11-11 美国电话电报公司 高效能资源分配方法和装置
CN1449017A (zh) * 2002-03-29 2003-10-15 清华大学 基于模块变形的集成电路宏模块布图规划和布局方法
CN1560771A (zh) * 2004-02-20 2005-01-05 清华大学 基于模块变形和概率局部搜索的集成电路模块级布局方法
CN1588380A (zh) * 2004-07-09 2005-03-02 清华大学 基于最小自由度优先原则的非线性规划布局方法
CN1708032A (zh) * 2004-05-28 2005-12-14 朗迅科技公司 独立于通信量模式可变性的有效且稳健的路由选择
CN112084704A (zh) * 2020-08-19 2020-12-15 浙江工业大学 柔性车间的多工艺路线与布局联合优化方法
CN112199920A (zh) * 2020-12-04 2021-01-08 南京集成电路设计服务产业创新中心有限公司 一种布局方法、电子设备及计算机可读存储介质
CN112232545A (zh) * 2020-09-01 2021-01-15 东南大学 基于模拟退火算法的agv任务调度方法

Family Cites Families (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6968524B2 (en) 2000-03-31 2005-11-22 Cadence Design Systems, Inc. Method and apparatus to optimize an integrated circuit design using transistor folding
US7904865B2 (en) * 2008-01-23 2011-03-08 International Business Machines Corporation Placement driven routing
JP5282649B2 (ja) 2008-09-25 2013-09-04 富士通株式会社 レイアウト評価装置、レイアウト評価プログラム、ダミールール生成装置及びダミールール生成プログラム
CN103164552B (zh) 2011-12-13 2015-08-05 中芯国际集成电路制造(上海)有限公司 芯片版图的检测方法

Patent Citations (8)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN87102679A (zh) * 1986-04-11 1987-11-11 美国电话电报公司 高效能资源分配方法和装置
CN1449017A (zh) * 2002-03-29 2003-10-15 清华大学 基于模块变形的集成电路宏模块布图规划和布局方法
CN1560771A (zh) * 2004-02-20 2005-01-05 清华大学 基于模块变形和概率局部搜索的集成电路模块级布局方法
CN1708032A (zh) * 2004-05-28 2005-12-14 朗迅科技公司 独立于通信量模式可变性的有效且稳健的路由选择
CN1588380A (zh) * 2004-07-09 2005-03-02 清华大学 基于最小自由度优先原则的非线性规划布局方法
CN112084704A (zh) * 2020-08-19 2020-12-15 浙江工业大学 柔性车间的多工艺路线与布局联合优化方法
CN112232545A (zh) * 2020-09-01 2021-01-15 东南大学 基于模拟退火算法的agv任务调度方法
CN112199920A (zh) * 2020-12-04 2021-01-08 南京集成电路设计服务产业创新中心有限公司 一种布局方法、电子设备及计算机可读存储介质

Non-Patent Citations (2)

* Cited by examiner, † Cited by third party
Title
《An open space based heuristic for the 2D strip packing problem with unloading constraints》;lijun wei等;《Applied Mathematical Modelling》;20191231;全文 *
《一种支持整线定制设计的知识库构建方法》;林贵祥等;《机电工程技术》;20201231;第49卷(第07期);全文 *

Also Published As

Publication number Publication date
US11347924B1 (en) 2022-05-31
CN113268946A (zh) 2021-08-17

Similar Documents

Publication Publication Date Title
CN113268946B (zh) 一种基于连线总和最小的芯片布局方法
CN111339726B (zh) 考虑电压转换速率的X结构Steiner树构造方法
CN111310409B (zh) 一种优化时分复用技术的多阶段fpga布线方法
CN111709205B (zh) Fpga布线方法
CN107908884B (zh) 一种通过调整时钟树分支改善时序的交互式eco方法
CN112733484B (zh) 基于多策略优化的Slew约束下的X结构Steiner树构造方法
CN101055606A (zh) 多时钟系统的集成电路平面布局规划方法
CN112395549B (zh) 一种用于矩阵乘法密集型算法的可重构矩阵乘法加速系统
CN115470747B (zh) 一种实现时序快速收敛的时钟树综合方法
CN103235849A (zh) 电流驱动的集成电路自动布线方法及装置
CN111259614B (zh) 优化鱼骨型时钟树金属走线的设计方法
CN112183001B (zh) 一种基于超图的集成电路的多级聚类方法
CN110032815B (zh) 基于文化基因的八角形斯坦纳树构建方法
CN112800547A (zh) 电动汽车电机控制器的布局优化方法、装置及存储介质
CN113239652B (zh) 一种基于异质型fpga全局布局的坐标转换方法
CN113407153B (zh) 16位加法器及其实现方法、运算电路及芯片
CN104578054A (zh) 一种基于多稀疏矢量道路集的电力系统暂态稳定仿真方法
CN106027032A (zh) 一种单位延时模型下rm逻辑电路延时优化方法
TWI471751B (zh) Ic設計之自動佈置系統及其方法
CN113821951A (zh) Igbt功率模块焊料层空洞识别与合并的智能化方法
CN117057302B (zh) 一种电路原理图启发式布局布线方法
CN112926281B (zh) 一种数字集成电路的智能模块分析方法
CN108319796B (zh) 一种直纹面的快速设计方法
JPH0830655A (ja) 半導体装置の同期回路レイアウト設計方法
CN106984790A (zh) 一种基于曲线集的2d压铸模浇道快速成型系统

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