CN1588380A

CN1588380A - Non-linear planning layout method based minimum degree of freedom priority principle

Info

Publication number: CN1588380A
Application number: CN 200410068848
Authority: CN
Inventors: 董社勤; 杨中; 洪先龙
Original assignee: Tsinghua University
Current assignee: Tsinghua University
Priority date: 2004-07-09
Filing date: 2004-07-09
Publication date: 2005-03-02
Anticipated expiration: 2024-07-09
Also published as: CN100347709C

Abstract

The nonlinear programming layout method based on the minimum degree of freedom first principle belongs to the field of computer aided design of integrated circuits, and its specific feature is that it combines the advantages of the minimum degree of freedom first principle and the nonlinear programming method, and optimizes the area and line length at the same time. It first uses the nonlinear programming method to optimize the bus length to obtain the initial solution with the most bus length; then according to the aspect ratio and area utilization given by the user, it uses the principle of minimum degree of freedom priority to optimize the layout. It has faster speed, higher area utilization, and optimizes the bus length at the same time.

Description

A Nonlinear Planning Layout Method Based on the Least Degree of Freedom Priority Principle

技术领域technical field

基于最小自由度优先原则的非线性规划布局方法属于集成电路计算机辅助设计领域，尤其涉及BBL(Building Block Layout)领域。The nonlinear programming layout method based on the minimum degree of freedom first principle belongs to the field of computer-aided design of integrated circuits, especially the field of BBL (Building Block Layout).

背景技术Background technique

物理设计是超大规模集成电路(VLSI)设计过程中主要的一环。与此相关的计算机辅助设计技术称为自动布图。集成电路的制造工艺由目前的深亚微米(DSM)进入到超深亚微米(VDSM)，集成电路的设计规模也正由超大规模(VLSI)，甚大规模(ULSI)向G大规模(GSI)发展，电路的复杂性急剧增加使得层次式电路设计以及电路模块的重用技术受到学术和产业界的空前重视。知识产权模块的大量涌现也为集成电路布图设计提出了前所未有的挑战；层次式布图设计，模块重用技术，知识产权模块的大量应用，片上系统尤其是数模混合片上系统的设计，以及模拟电路器件级布图问题等，这些问题都可以归结为集成电路宏模块的布图规划和布局问题，即Building Block Layout：BBL模式的布图问题。Physical design is an important part of the very large scale integration (VLSI) design process. The computer-aided design technology related to this is called automatic layout. The manufacturing process of integrated circuits has entered from the current deep submicron (DSM) to ultra-deep submicron (VDSM), and the design scale of integrated circuits is also changing from very large scale (VLSI), very large scale (ULSI) to G large scale (GSI) With the rapid development of the circuit, the complexity of the circuit has increased sharply, making the hierarchical circuit design and the reuse technology of the circuit module receive unprecedented attention from the academic and industrial circles. The emergence of a large number of intellectual property modules also poses unprecedented challenges for integrated circuit layout design; hierarchical layout design, module reuse technology, a large number of applications of intellectual property modules, system-on-chip, especially the design of digital-analog hybrid system-on-chip, and analog Circuit device-level layout problems, etc., these problems can be attributed to the layout planning and layout of integrated circuit macro-modules, that is, Building Block Layout: the layout problem of BBL mode.

布局问题的任务是要确定模块在芯片上的精确位置，其目标是在保证布通的前提之下使得芯片面积尽可能小。布局算法可分为两大类，随机优化方法和确定性方法，随机优化方法通过在定义的解空间中搜索得到结果，速度较慢。确定性方法是给定一些启发策略，通过这些策略去指导布局，常见的有贪婪算法。The task of the layout problem is to determine the precise position of the module on the chip, and its goal is to make the chip area as small as possible under the premise of ensuring the layout. The layout algorithm can be divided into two categories, stochastic optimization method and deterministic method. The stochastic optimization method obtains the result by searching in the defined solution space, and the speed is relatively slow. The deterministic method is to give some heuristic strategies, and use these strategies to guide the layout. Commonly, there is a greedy algorithm.

长期以来，人们在用具有多边形平面的石块砌河岸，砌墙，铺地板时，总是最先使用受限制最多的资源，例如首先从工作区域的角部做起，首先使用面积大或长的块等等。这就是所谓的“最小自由度优先”原则。围棋中的“金角，银边，草肚皮”说的就是这一原则。基于该原则的确定性布图规划和布局算法在速度方面则是目前最快的布局算法，布局结果与人工布局结果相当，但是线长方面结果稍差。For a long time, when people use polygonal planar stones to build river banks, build walls, and lay floors, they always use the most limited resources first, such as starting from the corner of the work area first, and using large or long areas first. blocks and so on. This is the so-called "minimum degree of freedom first" principle. The "golden corner, silver edge, grass belly" in Go refers to this principle. The deterministic floorplanning and layout algorithm based on this principle is currently the fastest layout algorithm in terms of speed, and the layout results are comparable to manual layout results, but the results are slightly worse in terms of line length.

非线性规划的方法常用来解决一些最优化问题，但是往往需要将问题近似，直接用于布局问题的效果并不好。The nonlinear programming method is often used to solve some optimization problems, but it often needs to approximate the problem, and the effect of directly applying it to the layout problem is not good.

本发明研究了非线性规划问题和最小自由度优先原则，将它们的优势结合起来，根据用户给定的面积利用率高效的完成布局问题。The invention studies the non-linear programming problem and the minimum freedom priority principle, combines their advantages, and efficiently completes the layout problem according to the area utilization rate given by the user.

发明内容Contents of the invention

本发明的目的是在于提出基于最小自由度优先原则的非线性规划布局方法，它结合了最小自由度优先原则和非线性规划方法的优点，使布局问题更加有效。最小自由度优先原则是基于人们实际工作生活中的经验，它的主要思想就是先处理占用资源大的模块，然后处理占用资源小的模块，在具体放置的时候采用“金角银边草肚皮”的策略，先考虑将模块放置在角上，然后考虑边上，最后才是中间。这样，放置的顺序为从四个角逐渐向中间。非线性规划的方法是一种数学分析方法，它可以计算出近似模型具有最小线长的放置方案。The purpose of the present invention is to propose a nonlinear programming layout method based on the minimum degree of freedom priority principle, which combines the advantages of the minimum degree of freedom priority principle and the nonlinear programming method to make the layout problem more effective. The principle of minimum degree of freedom priority is based on the experience of people in actual work and life. Its main idea is to deal with the modules that occupy large resources first, and then process the modules that occupy small resources. strategy, consider placing modules in the corners first, then the sides, and finally the middle. In this way, the order of placement is gradually from the four corners to the middle. The method of nonlinear programming is a mathematical analysis method that can calculate the placement scheme of the approximate model with the minimum line length.

设有n个模块的布局问题：长方形模块集合B＝{B₁，B₂，B₃，...，B_n}中的每一个模块平行的放置在直角坐标系中，每个模块i的长与宽(h_i，ω_i)都已经给出，其中h_i和w_i分别是B_i的长与宽。目标是找到一种布图方案，使得在放置下所有模块的前提之下，所用的面积与线长最小。A layout problem with n modules: each module in the rectangular module set B={B ₁ , B ₂ , B ₃ ,..., B _n } is placed in parallel in the Cartesian coordinate system, and each module i Both the length and width (h _i , ω _i ) are given, where h _i and w _i are the length and width of _Bi , respectively. The goal is to find a layout scheme that minimizes the area and line length under the premise of placing all the modules.

本发明的特征在于：它依次含有以下步骤：The present invention is characterized in that: it contains following steps successively:

(1).计算机初始化(1). Computer initialization

读入所有的模块的长宽和它们之间连线的信息；Read in the length and width of all modules and the information of the connections between them;

输入用户给定的面积利用率和长宽比；Enter the area utilization rate and aspect ratio given by the user;

设定下列参数：Set the following parameters:

布局空白区域的自由度：Degrees of freedom to layout white space:

角部的自由度定义为P_c ^f，P_c ^f＝1/2，The degree of freedom of the corner is defined as P _c ^f , P _c ^f =1/2,

边上的自由度定义为P_s ^f，P_s ^f＝3/4，The degree of freedom on the edge is defined as P _s ^f , P _s ^f =3/4,

中间的自由度定义为P_h ^f，P_h ^f＝1；The middle degree of freedom is defined as P _h ^f , P _h ^f =1;

模块的自由度定义为R_i ^f：The degrees of freedom of a module are defined as R _i ^f :

R_i ^f＝{r₁*(1-B_i/A_a)+r₂*(1-max(w_i，h_i)/min(W，H))}；R _i ^f = {r ₁ *(1-B _i /A _a )+r ₂ *(1-max(w _i , h _i )/min(W, H))};

其中：r₁+r₂＝1，Where: r ₁ +r ₂ =1,

w_i、h_i分别是模块i的宽和高，B_i是模块i的面积，w _i and h _i are the width and height of module i respectively, B _i is the area of module i,

A_a是放置空间的面积，W、H分别是它的宽和高；A _a is the area of the placement space, W and H are its width and height respectively;

互连自由度定义为C_i ^f，即模块i的互连自由度，The interconnection degree of freedom is defined as C _i ^f , which is the interconnection degree of freedom of module i,

t_i ^j是模块i与相邻模块j连线数，t _i ^j is the number of connections between module i and adjacent module j,

ω_i ^j为模块i与相邻模块j连线长度，用半周长法估计；ω _i ^j is the length of the connection between module i and adjacent module j, which is estimated by the semiperimeter method;

初始解自由度S_i ^f， $S_{i}^{f} = {| x_{icur} - x_{iori} |}^{2} + {| y_{icur} - y_{iori} |}^{2}$ Initial solution degrees of freedom S _i ^f , $S_{i}^{f} = {| x_{icur} - x_{iori} |}^{2} + {| {the y}_{icur} - {the y}_{iori} |}^{2}$

x_icur，y_icur分别为模块当前所在网格的坐标，x _icur and y _icur are respectively the coordinates of the grid where the module is currently located,

x_iori，y_iofi分别为模块初始解中所在网格的坐标；x _iori and y _iofi are the coordinates of the grid in the initial solution of the module respectively;

(2).使用近似模型求具有最小线长的初始布局结果并记录每个圆的最终坐标，它依次含有以下步骤：(2). Use the approximate model to find the initial layout result with the minimum line length and record the final coordinates of each circle, which contains the following steps in turn:

(2.1).把所有的矩形模块近似成与之面积相等的圆，所有的连线都从圆心发出，各圆之间不重叠；(2.1). Approximate all the rectangular modules into circles with the same area, all the connecting lines are sent from the center of the circle, and the circles do not overlap;

(2.2).使用二次线长法近似每条连线的长度并使总线长目标函数W(x，y)最小：(2.2). Use the quadratic line length method to approximate the length of each connection and minimize the bus length objective function W(x, y):

$W W ((x x,, y the y)) = = {Σ Σ}_{i i = = 11}^{n no} {Σ Σ}_{j j = = 11}^{n no} {ω ω}_{ij ij} \cdot &Center Dot; \frac{11}{22} [[(({(({x x}_{i i} - - {x x}_{j j}))}^{22} + + {(({y the y}_{i i} - - {y the y}_{j j}))}^{22}]]$

约束条件：g(x，y)＝(r_i+r_j)²-[(x_i-x_j)²+(y_i-y_j)²]≤0Constraints: g(x, y)=(r _i +r _j ) ² -[(x _i -x _j ) ² +(y _i -y _j ) ² ]≤0

其中：n为模块数，(x_i，y_i)为第i个模块圆心的坐标，Among them: n is the number of modules, (xi _, y _i ) is the coordinates of the center of the i-th module,

ω_ij为模块i，j间的连线数ω _ij is the number of connections between modules i and j

r_i、r_j分别为模块i，j的半径r _i , r _j are the radii of modules i and j respectively

(2.3).使用罚函数的方法把问题转化成无约束目标函数P(x，y，c_k)(2.3). Use the penalty function method to convert the problem into an unconstrained objective function P(x, y, c _k )

$P P ((x x,, y the y,, {c c}_{k k})) = = W W ((x x,, y the y)) + + {c c}_{k k} {Σ Σ}_{i i = = 11}^{n no} {Σ Σ}_{j j = = 11}^{n no} Max Max ((00,, g g ((x x,, y the y))))$

其中c₀＝1，c_k+1＝10c_k，k是迭代次数计数器，从0→∞Where c ₀ =1, c _k+1 =10c _k , k is the number of iterations counter, from 0→∞

(2.4).固定其中一个模块，通过软件包matlab中的函数fmincon使用逐步二次规划法求出具有全局最优线长的初始解，即收敛子序列{(x，y)^k}的极限；(2.4). One of the modules is fixed, and the function fmincon in the software package matlab uses the stepwise quadratic programming method to find the initial solution with the global optimal line length, that is, the limit of the convergent subsequence {(x, y) ^k };

(2.5).把初始解的布局区域划分成m*m个网格，m＝4～12，记录每个圆心所在的网格；(2.5). The layout area of the initial solution is divided into m*m grids, m=4～12, and the grid where each center of circle is recorded;

(3).根据用户给定的面积利用率和长宽比，计算出布局区域的长宽，结合初始解，使用最小自由度优先原则进行布局，它依次含有如下步骤：(3). Calculate the length and width of the layout area according to the area utilization rate and aspect ratio given by the user. Combined with the initial solution, the layout is carried out using the principle of minimum degree of freedom priority. It contains the following steps in turn:

(3.1).设：UBS为未放置的模块集合，(3.1). Suppose: UBS is the set of unplaced modules,

PBS为放置好的模块集合，PBS is a set of placed modules,

PL为当前的放置状况；PL is the current placement status;

(3.2).把所有的模块按它们的模块自由度R_i ^f排序，找到R_i ^f最小的模块，先尝试放置该模块，从4个角开始，共有8种放置方案，对于每一种放置方案，在放置好第一个模块后，对于剩余模块采用已知的贪婪算法放置；(3.2). Sort all the modules according to their module degrees of freedom _R ^if , find the module with the smallest _R ^if , and try to place the module first. Starting from 4 corners, there are 8 placement schemes in total. For each placement scheme, after the first module is placed, the remaining modules are placed using a known greedy algorithm;

(3.3).计算步骤(3.2)所述8种方案按下式计算各自的总自由度F_k，共8个值：(3.3). The 8 kinds of schemes described in the calculation step (3.2) are calculated according to the following formula to calculate the respective total degrees of freedom F _k , totally 8 values:

${F f}_{k k} = = αP αP + + β β {R R}_{{k k}^{f f}} + + γ γ {C C}_{k k}^{F f} + + λ λ {S S}_{k k}^{f f}$

P为布局空白区域自由度P is the degree of freedom of the layout blank area

(3.4).选取其中F_k最小的放置方案作为上述第一个放置的模块的放置方案；(3.4). Select the placement scheme where F _k is the smallest as the placement scheme of the above-mentioned first placed module;

(3.5).把上述已放置好的第一个模块从UBS中去除，放入PBS中；(3.5). Remove the above-mentioned placed first module from UBS and put it into PBS;

(3.6).重复步骤(3.2)～(3.6)直到UBS空为止；(3.6). Repeat steps (3.2) ~ (3.6) until the UBS is empty;

(4).使用已知的模拟退火的方法调整布局，优化总线长。(4). Use the known simulated annealing method to adjust the layout and optimize the bus length.

(5).以图形和文件两种形式输出最终布局结果。(5). Output the final layout results in graphics and files.

本发明所述的基于最小自由度优先原则的非线性规划布局算法有以下几个优点：The non-linear programming layout algorithm based on the minimum degree of freedom priority principle of the present invention has the following advantages:

[1]使用最小自由度优先原则对于给定的布局区域完成布局，同时吸收非线性规划的数学分析方法得到的初始解的特征，同时优化面积和线长；[1] Use the minimum degree of freedom priority principle to complete the layout for a given layout area, and at the same time absorb the characteristics of the initial solution obtained by the mathematical analysis method of nonlinear programming, and optimize the area and line length at the same time;

[2]算法具有较快的速度、较高的面积利用率；[2] The algorithm has faster speed and higher area utilization;

[3]具有工业应用价值，可以用于集成电路设计过程中：模块级布图规划/布局中的布局问题。[3] Has industrial application value and can be used in the integrated circuit design process: layout problems in module-level floorplanning/layout.

实验结果如下：The experimental results are as follows:

表一MCNC标准实验电路参数说明电路名称模块数线网数模块总面积(mm2) Apte 9 97 46.561628 Xerox 10 203 19.350296 Hp 11 83 8.830584 Ami33 33 123 1.156449 Ami49 49 408 35.445424 Playout.xlii 62 2056 88.177016 Table 1 MCNC standard experimental circuit parameter description circuit name Number of modules Number of lines Total module area (mm2) Apte 9 97 46.561628 Xerox 10 203 19.350296 HP 11 83 8.830584 Ami33 33 123 1.156449 Ami49 49 408 35.445424 Playout.xlii 62 2056 88.177016

表二实验结果 Apte(mm) Xerox(mm) Hp(mm) Ami33 Ami49 Playout 面积利用率(％) 96.56 93.47 92.22 93.91 94.96 96.69 总线长(mm) 102.83 521.30 118.05 45.30 1021.23 6523.65 时间(s) 0.08 0.40 0.10 6.42 53.07 63.43 Table 2 Experimental results Apte(mm) Xerox(mm) HP(mm) Ami33 Ami49 Playout Area Utilization Rate (%) 96.56 93.47 92.22 93.91 94.96 96.69 bus length(mm) 102.83 521.30 118.05 45.30 1021.23 6523.65 time(s) 0.08 0.40 0.10 6.42 53.07 63.43

本发明使用的硬件是一台配置了P4 1.8G的CPU和256M内存的PC机；使用RedhatLinux7.2操作系统。The hardware that the present invention uses is a PC that has configured the CPU of P4 1.8G and 256M internal memory; Use RedhatLinux7.2 operating system.

附图说明Description of drawings

图1.本发明所述规划方法的程序结构流程图。Fig. 1. The flow chart of the program structure of the planning method of the present invention.

图2.使用非线性规划方法得到实例playout的初始解。Figure 2. Initial solution to example playout obtained using nonlinear programming methods.

图3.第一个模块布局时的8个候选位置。Figure 3. Eight candidate locations for the first module layout.

图4.计算模块的初始解自由度。Figure 4. Calculation of initial solution degrees of freedom for modules.

图5.放置第二个模块时的候选位置。Figure 5. Candidate locations when placing the second module.

图6.实例playout的最终布局结果。Figure 6. The final layout result of the example playout.

具体实施方式Detailed ways

(1).读入所有的模块以及它们之间连线信息，进行初始化工作，存储模块长宽和它们之间连线的信息(1). Read in all the modules and the connection information between them, perform initialization work, store the length and width of the modules and the connection information between them

(2).使用近似模型求具有最小线长的初始布局结果并记录每个圆的最终坐标：将所有的矩形模块近似成与之面积相等的圆，认为所有的连线都从圆心发出，圆之间不能重叠，使用二次线长法近似每条连线的长度，目标是使总连线长度最小。形式化描述如下：(2). Use the approximate model to find the initial layout result with the minimum line length and record the final coordinates of each circle: Approximate all the rectangular modules into a circle with the same area, and consider that all the connecting lines are sent from the center of the circle, and the circle Can not overlap between, using the quadratic line length method to approximate the length of each connection, the goal is to minimize the total connection length. The formal description is as follows:

约束条件：Restrictions:

g(x，y)＝(r_i+r_j)²-[(x_i-x_j)²+(y_i-y_j)²]≤0g(x,y)=(r _i +r _j ) ² -[(x _i -x _j ) ² +(y _i -y _j ) ² ]≤0

其中：in:

W为总线长目标函数W is the bus length objective function

n为模块数n is the number of modules

(x_i，y_i)为第i个模块圆心的坐标(x _i , y _i ) is the coordinates of the center of the i-th module

W_ij为模块i，j间的连线数W _ij is the number of connections between modules i and j

r_i为模块i的半径r _i is the radius of module i

使用罚函数的方法(Penalty Function Method)将问题转化成无约束目标函数Transform the problem into an unconstrained objective function using the Penalty Function Method

其中c₀＝1，c_k+1＝10c_k where c ₀ =1, c _k+1 =10c _k

为了使P(x，y，c_k)得到全局最有解，需要固定一些模块，设其中有1个模块是固定的。这时对于每一个c_k，P(x，y，c_k)的一阶导数的系数矩阵是对角优势阵(diagonally dominant matrix)，也是正定矩阵(positively definite matrix)，即P(x，y，c_k)在每一个c_k处都存在最有解，于是就可以得到收敛子序列{(x，y)^k}，序列的极限就是问题的最有解。具体的解法比较多，如牛顿法(Newton Method)，拟牛顿法(Quasi-Newton Method)，共轭梯度法(FR)，逐步二次规划法(SQP)，本方法中使用逐步二次规划法(SQP)。In order to make P(x, y, c _k ) obtain the global optimal solution, some modules need to be fixed, and one of them is assumed to be fixed. At this time, for each c _k , the coefficient matrix of the first derivative of P(x, y, c _k ) is a diagonally dominant matrix, which is also a positively definite matrix, that is, P(x, y , c _k ) has the best solution at each c _k , so the convergent subsequence {(x, y) ^k } can be obtained, and the limit of the sequence is the best solution of the problem. There are many specific solutions, such as Newton Method (Newton Method), Quasi-Newton Method (Quasi-Newton Method), Conjugate Gradient Method (FR), Stepwise Quadratic Programming (SQP), stepwise quadratic programming method is used in this method (SQP).

将初始解的布局区域划分成m*m网格，记录每个圆心所在的网格。Divide the layout area of the initial solution into m*m grids, and record the grid where each circle center is located.

(3).结合初始解，使用最小自由度优先原则进行布局：最小自由度优先(LFF)原则是基于人们日常生活和生产的经验，认为在布局的时候应该先处理最难放置，也就是占用资源最多的模块，后放置占用资源少的模块。算法进一步发展了这种思想，将自由度量化。下面是各个自由度的定义及量化公式：(3). Combining with the initial solution, use the principle of least degree of freedom first for layout: the principle of least degree of freedom first (LFF) is based on people's daily life and production experience, and believes that the most difficult placement should be dealt with first when laying out, that is, occupying The module with the most resources is placed next to the module that occupies less resources. Algorithms take this idea a step further, quantifying freedom. The following is the definition and quantification formula of each degree of freedom:

布局空白区域自由度：放置的空白区域的自由度。放在角上，只能向两个方向移动；放在边上，则有三个方向可以移动；只有放在中间，才可以上下左右的移动。因此，定义角部的自由度最低，为P_c ^f＝2/4＝1/2；边上其次，为P_s ^f＝3/4；中间则为P_h ^f＝4/4＝1Layout Blank Area Degrees of Freedom: The degrees of freedom of the placed blank area. If it is placed on the corner, it can only move in two directions; if it is placed on the side, it can move in three directions; only if it is placed in the middle, can it move up, down, left, and right. Therefore, the degree of freedom to define the corner is the lowest, which is P _c ^f =2/4=1/2; the side is next, P _s ^f =3/4; the middle is P _h ^f =4/4=1

模块自由度：由模块的大小和形状所决定，假定B_i是模块i的面积，w_i是它的宽，h_i是它的高，A_a是放置空间的面积，W是它的宽，H是它的高。则该模块的自由度可以定义为：Module degree of freedom: determined by the size and shape of the module, assume that B _i is the area of module i, w _i is its width, h _i is its height, A _a is the area of the placement space, W is its width, H is its height. Then the degrees of freedom of this module can be defined as:

其中：r₁+r₂＝1。Where: r ₁ +r ₂ =1.

互连自由度：用来反映模块之间的连线关系。假设模块B_i是将要放置的模块，互连自由度就是其在将要放置的位置上与相邻模块的连线和，那么这模块之间的自由度就可以定义为：Interconnection degree of freedom: used to reflect the connection relationship between modules. Assuming that the module B _i is the module to be placed, the interconnection degree of freedom is the sum of the connection between it and the adjacent module at the position to be placed, then the degree of freedom between the modules can be defined as:

其中ω_ij为模块i与相邻模块j连线长度，用半周长法估计，t_ij是模块i与相邻模块j连线数Where ω _ij is the length of the connection between module i and adjacent module j, which is estimated by the semiperimeter method, and t _ij is the number of connections between module i and adjacent module j

初始解自由度：用来表示模块当前放置与初始解的相对位置差：Initial solution degrees of freedom: used to indicate the relative position difference between the current placement of the module and the initial solution:

S_i ^f＝|x_icur-x_iori|²+|y_icur-y_iori|² S _i ^f ＝|x _icur -x _iori | ² +|y _icur -y _iori | ²

其中，x_icur，y_icur是模块当前所在网格的坐标，x_iori，y_iori是模块初始解中所在网格的坐标Among them, x _icur , y _icur are the coordinates of the grid where the module is currently located, x _iori , y _iori are the coordinates of the grid where the module is in the initial solution

下面是详细的流程：The detailed process is as follows:

UBS：未放置的模块集合UBS: collection of unplaced modules

PBS：已放置好的模块集合PBS: a collection of placed modules

PL：当前的放置状况PL: current placement status

(3.1).将UBS中所有的模块依次尝试放入布局区域中的每一个角，并检测与当前的放置是否有冲突，如果没有冲突(也就是没有与现有放置发生重叠，也没有超出布局区域的边界)，就计入合法放置方案中(3.1). Try to put all the modules in the UBS into each corner of the layout area in turn, and check whether there is a conflict with the current placement, if there is no conflict (that is, there is no overlap with the existing placement, and it does not exceed the layout region boundaries), count towards the legal placement scheme

(3.2).伪放置下当前模块，标记为虚拟节点，对于剩下的模块，用贪婪算法放置它们，直至无法放下新的模块为止。(3.2). Pseudo-place the current module and mark it as a virtual node. For the remaining modules, use the greedy algorithm to place them until no new modules can be placed.

(3.3).计算当前的自由度：(3.3). Calculate the current degree of freedom:

其中：α，β，γ，λ为各自由度的权重系数Among them: α, β, γ, λ are the weight coefficients of each degree of freedom

(3.4).更新PL，把拥有最小自由度的放置方案加入PBS之中，从UBS之中移去该模块。(3.4). Update the PL, add the placement scheme with the minimum degree of freedom into the PBS, and remove the module from the UBS.

(3.5).重复(3.1)～(3.4)直到UBS空为止。(3.5). Repeat (3.1) ~ (3.4) until the UBS is empty.

(4).使用模拟退火的方法调整最终布局：将已经布好的模块在水平和垂直方向进行不停的翻转，改善布局的线长。(4). Use simulated annealing method to adjust the final layout: flip the modules that have been placed in the horizontal and vertical directions continuously to improve the line length of the layout.

(5).图形和文件两种形式输出结果。(5). Output results in two forms of graphics and files.

布局问题就是根据用户给定区域长宽比和面积利用率完成模块的放置问题，并满足其他的约束，例如布局连线长度等，本布局方法的流程框图如图1，下面我们以MCNC标准实例playout的放置过程结合图1来说明本发明所述的方法。它依次有如下步骤：The layout problem is to complete the module placement problem according to the area aspect ratio and area utilization rate given by the user, and meet other constraints, such as the layout connection length. The placement process of the playout is described in conjunction with FIG. 1 to illustrate the method of the present invention. It has the following steps in order:

具体实施步骤如下：The specific implementation steps are as follows:

(1)读输入文件，记录模块的长宽和模块间的连线信息。程序首先是读入实例playout的电路描述文件：playout.yal，提取其中模块的大小以及之间的连线关系信息并存储到相应的数据结构中(1) Read the input file, record the length and width of the module and the connection information between the modules. The program first reads the circuit description file of the example playout: playout.yal, extracts the size of the modules and the connection relationship information between them and stores them in the corresponding data structure

(2)根据步骤(2)的模型使用非线性规划的方法得到具有最优线长的初始解，将每一个模块近似成与其面积大小相等的圆，将模块间的多端线网拆成2端线网，用二次线长法估计每条连线的长度，两点间连线长度二次线长法估计公式如下：(2) According to the model in step (2), use the nonlinear programming method to obtain the initial solution with the optimal line length, approximate each module as a circle with the same area, and split the multi-terminal network between modules into two-terminal lines network, use the quadratic line length method to estimate the length of each connecting line, the estimation formula of the quadratic line length method for the length of the connecting line between two points is as follows:

$W W = = \sqrt{{(({x x}_{i i} - - {x x}_{j j}))}^{22} + + {(({y the y}_{i i} - - {y the y}_{j j}))}^{22}} - - - - - - ((88))$

其中(x_i，y_i)(x_j，y_j)为线网的两个端点的坐标Where ( _xi , y _i )(x _j , y _j ) are the coordinates of the two endpoints of the line network

求解具有最小全局线长的初始解问题就转化成一个非线性规划问题，目标是所有线网长度总和，见公式(1)，约束是任意两个圆都不重叠，见公式(2)。将其转化成无约束非线性规划问题，见公式(3)，使用逐步二次规划法求解出具有最优全局线长的初始解，这一步骤可以使用数学工具matlab实现，其中的函数fmincon可以使用逐步二次规划法求解出具有全局最优线长的初始解。初始解的坐标不能直接最终布局的方案中的模块坐标相关联，所以必须用一种相对的坐标连建立它们之间的联系，将布局区域划分成m*m个网格，将每个模块圆心所在的网格坐标记录下来，从实验数据得到m的建议取值范围是4～12。针对playout这个例子将初始解划分成4*4的区域，记录每个模块的圆心所在的区域，如图2所示，其中左上角29号模块的初始解坐标为(1，1)The problem of solving the initial solution with the minimum global line length is transformed into a nonlinear programming problem. The goal is the sum of the lengths of all line networks, see formula (1), and the constraint is that any two circles do not overlap, see formula (2). Transform it into an unconstrained nonlinear programming problem, see formula (3), use the stepwise quadratic programming method to solve the initial solution with the optimal global line length, this step can be realized using the mathematical tool matlab, and the function fmincon can be An initial solution with a globally optimal line length is found using stepwise quadratic programming. The coordinates of the initial solution cannot be directly related to the module coordinates in the final layout plan, so a relative coordinate connection must be used to establish the connection between them, divide the layout area into m*m grids, and divide the center of each module The grid coordinates where it is located are recorded, and the suggested value range of m obtained from the experimental data is 4-12. For the playout example, divide the initial solution into 4*4 areas, and record the area where the center of each module is located, as shown in Figure 2, where the initial solution coordinates of module 29 in the upper left corner are (1, 1)

(3)根据用户给定的面积利用率和长宽比，计算出布局区域的长宽，例如用户希望得到95.7％的面积利用率并且布局区域的长宽比为1.5∶1，实例playout中所有模块的面积为88.177016mm²，则布局区域的面积应为88.177016/0.957＝92.151366，所有布局的长应为：11.757mm，宽应为：7.838mm。(3) Calculate the length and width of the layout area according to the area utilization rate and aspect ratio given by the user. For example, the user wants to obtain an area utilization rate of 95.7% and the aspect ratio of the layout area is 1.5:1. All in the example playout The area of the module is 88.177016mm ² , the area of the layout area should be 88.177016/0.957=92.151366, the length of all layouts should be: 11.757mm, and the width should be: 7.838mm.

接着将模块按照它们的模块自由度排序，根据公式(4)可以算出模块29的模块自由度最小，先尝试放置它，由于角的空间自由度最小，模块29从4个角开始尝试，考虑到模块可以横向和纵向放置，它有8种放置方案，见图3，对于每一种放置方案，在放置好第一个模块后，对于剩余的模块都采用贪婪算法放置。Then the modules are sorted according to their module degrees of freedom. According to the formula (4), it can be calculated that the module degrees of freedom of module 29 are the smallest. Try to place it first. Since the corners have the smallest spatial degrees of freedom, module 29 starts to try from 4 corners. Considering Modules can be placed horizontally and vertically. There are 8 placement schemes, as shown in Figure 3. For each placement scheme, after the first module is placed, the remaining modules are placed using a greedy algorithm.

使用公式(5)，(6)计算当前放置方案的互连自由度和初始解自由度。对于第一个要放置的模块，其中为没有模块，所有互连自由度为0，对于后面的模块，要使用半周长法(框住所用最小矩形周长的一半)计算当前模块周围的模块。其中针对图4初始解自由度的计算过程如下：模块29初始所在网格为(1，1)，当前所在网格为(2，4)，根据公式(6)，其初始解自由度为：|(2-1)|²+|(4-1)|²＝10。Use equations (5), (6) to calculate the interconnection degrees of freedom and initial solution degrees of freedom for the current placement scheme. For the first module to be placed, there is no module, and all interconnection degrees of freedom are 0. For the following modules, the half perimeter method (half of the perimeter of the smallest rectangle used to frame the place) is used to calculate the modules around the current module. The calculation process for the initial solution degrees of freedom in Figure 4 is as follows: the initial grid of module 29 is (1, 1), and the current grid is (2, 4). According to formula (6), its initial solution degrees of freedom are: |(2-1)| ²⁺ |(4-1)| ² =10.

最后用公式(7)计算总自由度F_i，这样对于模块29就有8个F_i值，实例playout一共有62个模块，一共有62*8个候选方案和F_i值，选取其中F_i最小的放置方案。Finally, use the formula (7) to calculate the total degree of freedom F _i , so that there are 8 F _i values for module 29, and the example playout has 62 modules in total, and there are 62*8 candidate solutions and F _i values in total, among which F _{i is} selected Minimal placement scheme.

模块29放置完毕后，会占据角1，同时生出角5和角6两个新角。新角和未被占据的角都是剩下模块的候选位置，假设模块55是接下来要放置的模块，则它有十个候选方案，见图5，将已经放好的模块从放置模块列表中删除，按照(3.1)～(3.4)的顺序循环放置完毕所有模块。After the module 29 is placed, it will occupy corner 1 and generate two new corners, corner 5 and corner 6. Both new corners and unoccupied corners are candidate positions for the remaining modules. Assuming that module 55 is the next module to be placed, it has ten candidate solutions, as shown in Figure 5. Remove the placed modules from the placed module list Delete, and place all the modules circularly in the order of (3.1)~(3.4).

(4)将已经放置完毕的模块使用模拟退火的方法进行水平和垂直的翻转，如果发现某个模块水平或垂直翻转后，总线长下降，则将该模块翻转。不停的重复这样的过程，直到布局的总线长不再下降为止。这样可以进一步优化布局的总线长。(4) Use the simulated annealing method to flip the placed modules horizontally and vertically. If it is found that the bus length decreases after a certain module is flipped horizontally or vertically, flip the module. This process is repeated continuously until the bus length of the layout no longer decreases. This can further optimize the bus length of the layout.

(5)图形文件两种形式输出最终布局结果。(5) Output the final layout results in two forms of graphic files.

Claims

1. The non-linear programming layout method based on the minimum degree of freedom priority principle is characterized in that it contains the following steps successively:

(1). Computer initialization

Read in the length and width of all modules and the information of the connections between them;

Enter the area utilization rate and aspect ratio given by the user;

Set the following parameters:

Degrees of freedom to layout white space:

The degree of freedom of the corner is defined as P _c ^f , P _c ^f =1/2

The degree of freedom on the edge is defined as P _s ^f , P _s ^f =3/4

The middle degree of freedom is defined as P _h ^f , P _h ^f =1

The degrees of freedom of a module are defined as R _i ^f :

R _i ^f = {r ₁ *(1-B _i /A _a )+r ₂ *(1-max(w _i , h _i )/min(W, H))};

Where: r ₁ +r ₂ =1,

w _i and h _i are the width and height of module i respectively, B _i is the area of module i,

A _a is the area of the placement space, W and H are its width and height respectively;

The interconnection degree of freedom is defined as C _i ^f , which is the interconnection degree of freedom of module i,

t _ij is the number of connections between module i and adjacent module j,

ω _ij is the length of the connection between module i and adjacent module j, which is estimated by the half-perimeter method;

Initial solution degrees of freedom S _i ^f ,

S_{i}^{f} = {| x_{icur} - x_{iori} |}^{2} + {| {the y}_{icur} - {the y}_{iori} |}^{2}

x _icur and y _icur are respectively the coordinates of the grid where the module is currently located,

x _iori and y _iori are the coordinates of the grid in the initial solution of the module respectively;

(2). Use the approximate model to find the initial layout result with the minimum line length and record the final coordinates of each circle, which contains the following steps in turn:

(2.1). Approximate all the rectangular modules into circles with the same area, all the connecting lines are sent from the center of the circle, and the circles do not overlap;

(2.2). Use the quadratic line length method to approximate the length of each connection and minimize the bus length objective function W(x, y):

W W ((x x,, y the y)) = = {Σ Σ}_{i i = = 11}^{n no} {Σ Σ}_{j j = = 11}^{n no} {ω ω}_{ij ij} \cdot &Center Dot; \frac{11}{22} [[(({(({x x}_{i i} - - {x x}_{j j}))}^{22} + + {(({y the y}_{i i} - - {y the y}_{j j}))}^{22}))]]

Constraints: g(x, y)=(r _i +r _j ) ² -[(x _i -x _j ) ² +(y _i -y _j ) ² ]≤0

Among them: n is the number of modules, (xi _, y _i ) is the coordinates of the center of the i-th module,

ω _{i, j} is the number of connections between modules i and j

r _i , r _j are the radii of modules i and j respectively

(2.3). Use the penalty function method to convert the problem into an unconstrained objective function P(x, y, c _k )

P P ((x x,, y the y,, {c c}_{k k})) = = W W ((x x,, y the y)) + + {c c}_{k k} {Σ Σ}_{i i = = 11}^{n no} {Σ Σ}_{j j = = 11}^{n no} Max Max ((00,, g g ((x x,, y the y))))

Where c ₀ =1, c _k+1 =10c _k , k is the number of iterations counter, from 0→∞

(2.4). One of the modules is fixed, and the function fmincon in the software package matlab uses the stepwise quadratic programming method to find the initial solution with the global optimal line length, that is, the limit of the convergent subsequence {(x, y) ^k };

(2.5). Divide the layout area of the initial solution into m*m grids, m=4~12, record the grid where each circle center is located;

(3). Calculate the length and width of the layout area according to the area utilization rate and aspect ratio given by the user. Combined with the initial solution, use the minimum degree of freedom priority principle to carry out the layout. It contains the following steps in turn:

(3.1). Suppose: UBS is the set of unplaced modules,

PBS is a set of placed modules,

PL is the current placement status;

(3.2). Sort all the modules according to their module degrees of freedom _R ^if , find the module with the smallest _R ^if , and try to place the module first. Starting from 4 corners, there are 8 placement schemes in total. For each placement scheme, after the first module is placed, the remaining modules are placed using a known greedy algorithm;

(3.3). The 8 kinds of schemes described in the calculation step (3.2) are calculated according to the following formula to calculate the respective total degrees of freedom F _k , totally 8 values:

F _k ＝αP+βR _kf +γC _k ^f +λS _k ^f

P is the degree of freedom of the layout blank area

(3.4). Select the placement scheme where F _k is the smallest as the placement scheme of the above-mentioned first placed module;

(3.5). Remove the above-mentioned placed first module from UBS and put it into PBS;

(3.6). Repeat steps (3.2) ~ (3.6) until the UBS is empty;

(4). Use the known simulated annealing method to adjust the layout and optimize the bus length.

(5). Output the final layout results in graphics and files.