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

Abstract

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

Description

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

技术领域

本发明涉及芯片布局技术领域，尤其涉及一种基于连线总和最小的芯片布局方法。

背景技术

芯片连线总和最小，是指在VLSI(大规模集成)芯片设计中，已知n个宽、高分别任意给定的矩形电路模块，如何确定一个大小可变矩形芯片，使得所有的矩形电路模块都能够合法地放入其中，并且要求矩形芯片中各电路模块间的连线总和尽可能小。合法是指放入任意矩形电路模块后不超出矩形芯片的边界、电路模块的边平行于矩形芯片的边，且各电路模块间两两互不重叠。连线总和是指每个矩形电路模块上有许多引脚，各个矩形电路模块从引脚处通过导线连通所需要导线的总长度；

最小化芯片连线总和问题是VLSI(大规模集成)芯片设计的一个重要步骤。在大规模集成芯片设计领域，通常需要在矩形芯片上放置一组矩形模块，并且这些模块需要通过导线连接，要考虑的目标是最小化矩形芯片的面积和最小化导线的总长度。由于芯片性能是在大规模集成芯片设计中最主要考虑的优化目标，互连线的长短是影响芯片的功耗、延时、可靠性等性能的主要因素；另一方面生产芯片的材料非常昂贵，总连线长度最小化可以节约金属导线的使用，因此材料的节约对于降低制造成本有重要的影响，特别是在大批量生产中，提高芯片材料利用率可以带来显著的经济效益；

但是目前大多算法应用在大规模集成芯片设计中主要是优化芯片的总面积，而忽略各矩形电路模块间的互连线，从而不能降低芯片的功耗和延时。针对大规模集成芯片中线长最小化问题，目前的解决方法是把各矩形电路模块的连接位置简化为模块的中心与其他模块相连接，这样使得得出的结果过于简化，不具有代表性，不能更好的运用到实际问题当中。

本发明针对最小化芯片连线总和问题提出一种基于线长最小化的芯片排布方法，该方法在大规模集成芯片设计中能够通过最小化芯片连线的总线长从而最大程度的提升集成芯片的性能，同时生成一个合理的芯片排布，还可以最大程度的节省生产矩形芯片的材料，提高材料的利用率，从而使得在大批量生产中给企业带来显著的经济效益。并且该方法优于现有方法并针对大多数经典实例改进了解决方案。

发明内容

本发明的目的在于针对背景技术中的缺陷，提出一种基于连线总和最小的芯片布局方法，实现在大规模集成芯片设计中能够通过最小化芯片连线的总线长从而最大程度的提升集成芯片的性能，同时生成一个合理的芯片排布，还可以最大程度的节省生产矩形芯片的材料，提高材料的利用率，从而使得在大批量生产中带来显著的经济效益。

为达此目的，本发明采用以下技术方案：

一种基于连线总和最小的芯片布局方法，包括如下步骤：

步骤A：将芯片总连线长初始化为最大的预设线长，初始化迭代次数；

步骤B：随机生成一个序列对，所述序列对用于表示各矩形电路模块间的上下左右位置关系，将序列对输入至模型求解，获得当前迭代次数下最小总连线长及其所对应的当前序列对；

步骤C：改变当前序列对的领域算子得到新序列对，将新的序列对输入至原始模型求解，获得新序列对及其所对应的总连线长；

步骤D：判断新序列对所对应的总连线长是否小于当前序列对所对应的总连线长，若否，则删除新序列对，保留当前序列对，重复执行步骤C；若是，则删除当前序列对，保留新序列对并将其重新标记为当前序列对；

步骤E：判断是否达到领域算子改变的迭代次数，若是，则输出当前序列对所对应的总连线长和各矩形电路模板的坐标位置，该总连线长为最小总连线长；若否，则重复执行步骤C。

优选的，在所述步骤B中还包括基于矩形电路模块确定矩形电路模块的引脚坐标信息，将各矩形模块的引脚坐标信息集合生成引脚网络集合；

随机生成一个序列对，各所述矩形电路模块之间的位置关系以该序列对的形式进行表示；

将该序列对、矩形电路模块、引脚坐标信息和引脚网络集合输入至原始模型进行求解以获得当前迭代次数下总连线长最小的所对应的当前序列对。

优选的，所述序列对用于表示各矩形电路模块间的上下左右位置关系，具体包括：

基于正负两个子序列对表示各矩形电路模块之间的上下左右的位置关系；

若当前矩形电路模块在正负子序列对中的序列位置均位于另一矩形电路模块的前面，则当前矩形电路模块的实际位置位于另一矩形电路模块的左边；

若当前矩形电路模块在正负子序列对中的序列位置均位于另一矩形电路模块的后面，则当前矩形电路模块的实际位置位于另一矩形电路模块的右边；

若当前矩形电路模块在正子序列中的序列位置位于另一矩形电路模块的前面，在负子序列对中的序列位置位于另一矩形电路模块的后面，则当前矩形电路模块的实际位置位于另一矩形电路模块的上面；

若当前矩形电路模块在正子序列中的序列位置位于另一矩形电路模块的后面，在负子序列对中的序列位置位于另一矩形电路模块的前面，则当前矩形电路模块的实际位置位于另一矩形电路模块的下面。

优选的，所述步骤B还包括：

步骤B1：随机生成一个序列对，将该序列对、矩形电路模块、引脚坐标信息和引脚网络集合输入至模型进行求解，获得新序列对以及新序列所对应的总连线长；

步骤B2：判断新序列对所对应的总连线长是否小于原序列对所对应的总连线长，若是，则保留新序列对所对应的总连线长，将其替换原序列对，跳转至步骤B3；若否，则重复执行步骤B1；

步骤B3：判断是否达到迭代次数，若是，则输出步骤B2中所保留的序列对和其所对应的总连线长；若否，则重复执行步骤B1。

优选的，所述原始模型包括：

t₀-x_i≥w_i-W,t₀-y_i≥h_i-H；

y_i-y_j≥h_j+k_ij,y_j-y_i≥h_i+k_ij；

x_i-x_j≥w_j+d_ij,x_j-x_i≥w_i+d_ij；

其中：

N表示每一个引脚网络；

w(N)表示每个引脚网络的权重；

表示所有网络集合；

表示四个决策变量，四个决策变量构成每个网络N的一个最小周期长轴平行矩形

p表示引脚；

x_i(p),y_i(p)表示引脚p所在矩形电路模块r_i的横坐标和纵坐标；

x(p),y(p)表示引脚p相对它所在矩形电路模块坐标的偏移量；

t₀表示一个常数；

r_i表示矩形电路模块；

R表示所有矩形电路模块的集合；

x_i,y_i表示矩形电路模块r_i的横坐标和纵坐标；

x_j,y_j表示矩形电路模块r_j的横坐标和纵坐标；

k_ij表示矩形电路模块r_i,r_j间垂直方向上的布线间隙；

d_ij表示矩形电路模块r_i,r_j间水平方向上的布线间隙；

W表示所有矩形电路模块所要放置区域的宽，H表示所有矩形电路模块所要放置区域的高；

w_i和h_i表示矩形电路模块r_i的高和宽；

w_j和h_j表示矩形电路模块r_j的高和宽。

优选的，包括将所述原始模型转变为对偶模型以获得新序列对以及新序列所对应的总连线长；

所述对偶模型包括：

max∑b_ijf_ij；

其中：

b_ij表示原始模型约束条件的右端项；

f_ij表示原始模型约束v_j-v_i≥b_ij所对应的对偶变量；

f_jk表示原始模型约束v_k-v_j≥b_jk所对应的对偶变量；

v_j,v_i,v_k表示原始模型变量的类型，原始模型变量类型包括：

x_i,y_i,x_i(p),y_i(p)，其中x(N)^-,y(N)^-表示原始模型中

x(N)⁺,y(N)⁺表示原始模型中

本发明相对于现有技术所实现的技术效果：

本发明提出了一种优化目标为线片互连线总和最小的方法来生成一个芯片的排布，从而提高芯片的性能。该方法在考虑连线总和最小的同时还会得出一个更优的芯片排布(使得芯片中各矩形电路模块尽可能的排布紧凑，从而在一定程度上减小芯片的总面积)。与现有的方法相比，该方法更加简单和易于实施，并且将问题模型转化为其对偶模型，就变成了一个最大费用流问题，使得问题在多项式时间内可解，从而提高了效率。

附图说明

图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。

优选的，所述原始模型包括：

t₀-x_i≥w_i-W,t₀-y_i≥h_i-H；

y_i-y_j≥h_j+k_ij,y_j-y_i≥h_i+k_ij；

x_i-x_j≥w_j+d_ij,x_j-x_i≥w_i+d_ij；

其中：

N表示每一个引脚网络；

w(N)表示每个引脚网络的权重；

表示所有网络集合；

表示四个决策变量，四个决策变量构成每个网络N的一个最小周期长轴平行矩形

p表示引脚；

x_i(p),y_i(p)表示引脚p所在矩形电路模块r_i的横坐标和纵坐标；

x(p),y(p)表示引脚p相对它所在矩形电路模块坐标的偏移量；

t₀表示一个常数；

r_i表示矩形电路模块；

R表示所有矩形电路模块的集合；

x_i,y_i表示矩形电路模块r_i的横坐标和纵坐标；

x_j,y_j表示矩形电路模块r_j的横坐标和纵坐标；

k_ij表示矩形电路模块r_i,r_j间垂直方向上的布线间隙；

d_ij表示矩形电路模块r_i,r_j间水平方向上的布线间隙；

W表示所有矩形电路模块所要放置区域的宽，H表示所有矩形电路模块所要放置区域的高；

w_i和h_i表示矩形电路模块r_i的高和宽；

w_j和h_j表示矩形电路模块r_j的高和宽。

优选的，包括将所述原始模型转变为对偶模型以获得新序列对以及新序列所对应的总连线长；

所述对偶模型包括：

max∑b_ijf_ij；

其中：

b_ij表示原始模型约束条件的右端项；

f_ij表示原始模型约束v_j-v_i≥b_ij所对应的对偶变量；

f_jk表示原始模型约束v_k-v_j≥b_jk所对应的对偶变量；

v_j,v_i,v_k表示原始模型变量的类型，原始模型变量类型包括：

x_i,y_i,x_i(p),y_i(p)，其中x(N)^-,y(N)^-表示原始模型中

x(N)⁺,y(N)⁺表示原始模型中

以上结合具体实施例描述了本发明的技术原理。这些描述只是为了解释本发明的原理，而不能以任何方式解释为对本发明保护范围的限制。基于此处的解释，本领域的技术人员不需要付出创造性的劳动即可联想到本发明的其它具体实施方式，这些方式都将落入本发明的保护范围之内。

Claims (6)

1.一种基于连线总和最小的芯片布局方法，其特征在于：包括如下步骤：

步骤A：将芯片总连线长初始化为最大的预设线长，初始化迭代次数；

步骤B：随机生成一个序列对，所述序列对用于表示各矩形电路模块间的上下左右位置关系，将序列对输入至模型求解，获得当前迭代次数下最小总连线长及其所对应的当前序列对；

步骤C：改变当前序列对的领域算子得到新序列对，将新的序列对输入至原始模型求解，获得新序列对及其所对应的总连线长；

步骤D：判断新序列对所对应的总连线长是否小于当前序列对所对应的总连线长，若否，则删除新序列对，保留当前序列对，重复执行步骤C；若是，则删除当前序列对，保留新序列对并将其重新标记为当前序列对；

步骤E：判断是否达到领域算子改变的迭代次数，若是，则输出当前序列对所对应的总连线长和各矩形电路模板的坐标位置，该总连线长为最小总连线长；若否，则重复执行步骤C。

2.根据权利要求1所述一种基于连线总和最小的芯片布局方法，其特征在于：

在所述步骤B中还包括基于矩形电路模块确定矩形电路模块的引脚坐标信息，将各矩形模块的引脚坐标信息集合生成引脚网络集合；

随机生成一个序列对，各所述矩形电路模块之间的位置关系以该序列对的形式进行表示；

将该序列对、矩形电路模块、引脚坐标信息、引脚网络集合和矩形电路模块间的布线间隙输入至原始模型进行求解以获得当前迭代次数下总连线长最小的所对应的当前序列对。

3.根据权利要求1所述一种基于连线总和最小的芯片布局方法，其特征在于：

所述序列对用于表示各矩形电路模块间的上下左右位置关系，具体包括：

基于正负两个子序列对表示各矩形电路模块之间的上下左右的位置关系；

若当前矩形电路模块在正负子序列对中的序列位置均位于另一矩形电路模块的前面，则当前矩形电路模块的实际位置位于另一矩形电路模块的左边；

若当前矩形电路模块在正负子序列对中的序列位置均位于另一矩形电路模块的后面，则当前矩形电路模块的实际位置位于另一矩形电路模块的右边；

若当前矩形电路模块在正子序列中的序列位置位于另一矩形电路模块的前面，在负子序列对中的序列位置位于另一矩形电路模块的后面，则当前矩形电路模块的实际位置位于另一矩形电路模块的上面；

若当前矩形电路模块在正子序列中的序列位置位于另一矩形电路模块的后面，在负子序列对中的序列位置位于另一矩形电路模块的前面，则当前矩形电路模块的实际位置位于另一矩形电路模块的下面。

4.根据权利要求2所述一种基于连线总和最小的芯片布局方法，其特征在于：

所述步骤B还包括：

步骤B1：随机生成一个序列对，将该序列对、矩形电路模块、引脚坐标信息和引脚网络集合输入至模型进行求解，获得新序列对以及新序列所对应的总连线长；

步骤B2：判断新序列对所对应的总连线长是否小于原序列对所对应的总连线长，若是，则保留新序列对所对应的总连线长，将其替换原序列对，跳转至步骤B3；若否，则重复执行步骤B1；

步骤B3：判断是否达到迭代次数，若是，则输出步骤B2中所保留的序列对和其所对应的总连线长；若否，则重复执行步骤B1。

5.根据权利要求1所述一种基于连线总和最小的芯片布局方法，其特征在于：

所述原始模型包括：

t₀-x_i≥w_i-W，t₀-y_i≥h_i-H；

y_i-y_j≥h_j+k_ij，y_j-y_i≥h_i+k_ij；

x_i-x_j≥w_j+d_ij，x_j-x_i≥w_i+d_ij；

其中：

N表示每一个引脚网络；

w(N)表示每个引脚网络的权重；

表示所有网络集合；

表示四个决策变量，四个决策变量构成每个网络N的一个最小周期长轴平行矩形

p表示引脚；

x_i(p)，y_i(p)表示引脚p所在矩形电路模块r_i的横坐标和纵坐标；

x(p)，y(p)表示引脚p相对它所在矩形电路模块坐标的偏移量；

t₀表示一个常数；

r_i表示矩形电路模块；

R表示所有矩形电路模块的集合；

x_i，y_i表示矩形电路模块r_i的横坐标和纵坐标；

x_j，y_j表示矩形电路模块r_j的横坐标和纵坐标；

k_ij表示矩形电路模块r_i，r_j间垂直方向上的布线间隙；

d_ij表示矩形电路模块r_i，r_j间水平方向上的布线间隙；

W表示所有矩形电路模块所要放置区域的宽，H表示所有矩形电路模块所要放置区域的高；

w_i和h_i表示矩形电路模块r_i的高和宽；

w_j和h_j表示矩形电路模块r_j的高和宽。

6.根据权利要求5所述一种基于连线总和最小的芯片布局方法，其特征在于：

包括将所述原始模型转变为对偶模型以获得新序列对以及新序列所对应的总连线长；

所述对偶模型包括：

max∑b_ijf_ij；

其中：

b_ij表示原始模型约束条件的右端项；

f_ij表示原始模型约束v_j-v_i≥b_ij所对应的对偶变量；

f_jk表示原始模型约束v_k-v_j≥b_jk所对应的对偶变量；

v_j，v_i，v_k表示原始模型变量的类型，原始模型变量类型包括：

x_i，y_i，x_i(p)，y_i(p)，其中x(N)^-，y(N)^-表示原始模型中

x(N)⁺，y(N)⁺表示原始模型中

Images