CN101872377A - A Method of Using Decoupling Capacitors to Suppress Noise in Integrated Circuit Power Supply Network - Google Patents

Abstract

Translated fromChinese

使用去耦合电容抑制集成电路供电网络瞬态电压降噪声的方法属于超大规模集成电路物理设计领域，尤其是瞬态电源线地线网络噪声优化的技术范畴；其特点在于，创新之处在于(1)提出了一种在布局阶段估计去耦合电容需求的快速方法；(2)提出表示芯片中去耦合电容需求的一个二维函数；(3)利用这个二维函数，对去耦合电容的需求建立一个“供需系统”，用来引导布局过程朝着有利于减小去耦合电容需求的方向进行；(4)通过将上面的模型和方法集成到一个力指向布局中，提出了一种添加去耦合电容的布局算法；实验证明，本发明的方法非常有效，能够获得在线长增长0.5％左右的代价下，使得去耦合电容总量减小35％左右的布局结果。

The method of using decoupling capacitors to suppress the transient voltage drop noise of the integrated circuit power supply network belongs to the field of VLSI physical design, especially the technical category of transient power line ground network noise optimization; its characteristic is that the innovation lies in ( 1) A fast method for estimating the decoupling capacitor requirement in the layout stage is proposed; (2) A two-dimensional function is proposed to represent the decoupling capacitor requirement in the chip; (3) Using this two-dimensional function, the decoupling capacitor requirement Establish a "supply and demand system" to guide the layout process in a direction that is conducive to reducing the demand for decoupling capacitors; (4) By integrating the above models and methods into a force-pointed layout, an additive decoupling capacitor is proposed. Layout algorithm of coupling capacitors; experiments have proved that the method of the present invention is very effective, and can obtain a layout result in which the total amount of decoupling capacitors is reduced by about 35% at the cost of increasing the line length by about 0.5%.

Description

Use decoupling capacitance to suppress the method for integrated circuit electricity supply network noise

Technical field

The method of using decoupling capacitance to suppress integrated circuit electricity supply network noise belongs to the technology category of transient state power lead earth cord network noise optimization in VLSI (very large scale integrated circuit) (VLSI) physical Design field, especially the physical Design field.

Background technology

The supply network of integrated circuit comprises power-line network and earth cord network (being collectively referred to as the power ground network).The power ground Network Design belongs to the distinct line screen cloth line in the integrated circuit physical Design.Mainly need to solve supply voltage noise reduction sound problem in the power ground network design.Along with the continuous progress of integrated circuit technology, the chip feature size is constantly dwindled, and the integrated level and the frequency of operation of chip increase substantially, and the operating voltage of chip constantly reduces.These all cause the power ground network noise to increase and noise margin reduces, thereby make power ground network noise reduction problem become the major issue of VLSI (very large scale integrated circuit) (VLSI) in designing.Unsuitable power ground network design can produce excessive voltage drop and voltage fluctuation, greatly influences the performance of circuit, even causes circuit malfunction, and chip can't operate as normal.Therefore, the power ground network is analyzed accurately and optimization is very important.

The voltage drop noise mainly comprises two types on the ic power earth cord network: a kind of static state or dc voltage drop (IR Drop) of being called, this voltage drop are caused by the dead resistance of power supply gauze on the power ground network.Another is called transient voltage and falls (Transient Voltage Drop), and this voltage drop is caused by stray inductance on transistorized transient current variation and the power ground network.When the elimination quiescent voltage falls, usually can adopt power ground topology optimization (Singh J., Sapatnekar S.S., Topology optimization of structured power/ground networks.Proceedings ofInternational Symposium on Physical Design, 2004.116-123.), live width optimization (Wu Xiaohai. VLSI (very large scale integrated circuit) power ground network design and optimized Algorithm research: [PhD dissertation]. Beijing: Computer Science and Technology Department of Tsing-Hua University, 2001) etc. method solve.When problem fell in transient voltage on solving the power ground network, effective method was to add decoupling capacitance the most.Along with the modern integrated circuits design becomes increasingly complex, in order to eliminate more and more serious transient voltage noise reduction sound, the decoupling capacitance amount that need add on chip is more and more.And too much decoupling capacitance can produce many adverse influences to the performance of integrated circuit (IC) chip and stability: the transistor that (1) is used for making decoupling capacitance can produce leakage current, thereby adds the quiescent dissipation that decoupling capacitance can increase entire chip significantly too much; (2) too much decoupling capacitance causes chip yield to descend cost up; (3) too much decoupling capacitance can take a large amount of chip areas, produces resource contention with other device.For a long time, the research and design personnel are seeking a kind ofly to place decoupling capacitance less as far as possible and solve the method for transient voltage noise reduction sound always.

In traditional design cycle, decoupling capacitance is generally after layout finishes, determined after the position of each module or unit, again design result is carried out the transient analysis of power ground network, as the transient voltage noise reduction sound of finding not meet design requirement, adopt method noise reduction (the Dharchoudhury A that adds decoupling capacitance, Panda R, Blaauw D, et al.Design and analysis of powerdistribution networks in PowerPC microprocessors.Proceedings of DesignAutomation Conference, 1998.738-743.).In the process of adding decoupling capacitance, for fear of the adverse effect of a large amount of decoupling capacitances, need the placement location of decoupling capacitance be optimized chip performance, use minimum decoupling capacitance to solve transient voltage noise reduction sound problem as far as possible.In order to obtain optimum decoupling capacitance laying method, the researchist has carried out deep research to this problem: document (FuJ, Luo Z, Hong X, et al.A fast decoupling capacitor budgeting algorithm for robuston-chip power delivery.Proceedings of Asia and South Pacific Design AutomationConference, 2004.505-510.) utilization is carried out the optimization of decoupling capacitance based on the mathematic programming methods of sensitivity.But this often more consuming time based on sensitivity of method, can not be applied to larger circuit.Therefore, more new algorithm is suggested to improve the efficient of decoupling capacitance optimized Algorithm.For example, document (Li H, Fan J, Qi Z, et al.Partitioning-Based Approach to Fast On-ChipDecoupling Capacitor Budgeting and Minimization.IEEE Transactions onComputer-Aided Design of Integrated Circuits and Systems, 2006,25 (11): 2402-2412.) algorithm that has proposed a kind of circuit piecemeal comes huge circuit is carried out decoupling capacitance optimization; And document (Kang L, Cai Y, Zou Y, et al.Fast Decoupling CapacitorBudgeting for Power/Ground Network Using Random Walk Approach.Proceedings of Asia and South Pacific Design Automation Conference 2007.751-756.) has further improved the efficient of algorithm by the method (Random Walk) of using random walk.Document (Zhao M, Panda R, Sundareswaran S, et al.A fast on-chip decouplingcapacitance budgeting algorithm using macromodeling and linear programming.Proceedings of Design Automation Conference 2006.217-222.) has proposed the algorithm of finding the solution the decoupling capacitance optimization problem with macro model (Macro-model) and linear programming method.In addition, also be used to quicken process (the Fan J that decoupling capacitance is optimized based on the convex programming algorithm, Liao I F, Tan S XD, et al.Localized on-chip power delivery network optimization via sequence oflinear programming.Proceedings of 7th International Symposium on QualityElectronic Design, 2006.6pp.-277.).

It is pointed out that it all is after layout is finished that the inhibition method falls in above-mentioned various transient voltage, found by the power ground network simulation that transient voltage falls and do not satisfied after the power requirement, just carry out decoupling capacitance and place and optimize.Yet,,, all be difficult to the situation of the excessive transient voltage noise reduction sound of elimination in any case add decoupling capacitance after tending to appear at layout along with receiving electric current constantly to increase in the chip and supply voltage constantly reduces.At this moment, can only return layout stage even floor planning stage, the layout of chip is adjusted, repeat the transient analysis of power ground network and the process of adding decoupling capacitance then, expectation solves the problem that transient voltage falls by this design iteration.Such design iteration often will carry out several times repeatedly, has increased the design cost and the design time of chip greatly.

The reason that this design iteration occurs does not consider that just because of above-mentioned decoupling capacitance optimized Algorithm different layout result (being the different putting position in module or unit) is to power ground network power supply Effect on Performance.Module on the chip or unit need receive electric current, are the loads of power ground network.Their different putting positions obviously can cause tangible influence to the power supply performance of power ground network.Recently the researchist has had realized that this point, and has proposed some solutions.Document (Zhao S, Roy K, Koh C K.Decoupling capacitance allocation and its application to powersupply noise-aware floorplanning.IEEE Transactions on Computer-Aided Designof Integrated Circuits and Systems, 2002,21 (1): 81-92.) proposed in floor planning, to consider the method that decoupling capacitance is placed, to reduce the total area of floor planning and decoupling capacitance.And document (Kahng A B, Liu B, Wang Q.Supply voltage degradation aware analyticalplacement.Proceedings of IEEE International Conference on Computer Design, 2005.437-443.) in, quiescent voltage on the supply network falls of being used as in the layout stage optimization aim function and is integrated in the process of whole layout, falls littler layout in order to obtain quiescent voltage.But, also do not consider that at layout stage problem falls in the transient voltage of power ground network at present, and the research of decoupling capacitance optimization problem report.

The present invention proposes a kind of method that suppresses the voltage drop of power ground network transients at layout stage with decoupling capacitance.Use the layout result that this method produces, can use minimum decoupling capacitance to eliminate transient voltage noise reduction sound on the power ground network.In the present invention, at first, decoupling capacitance placement problem is converted into a linear programming problem (Zhao M by macro model (Macro-model), PandaR, Sundareswaran S, et al.A fast on-chip decoupling capacitance budgetingalgorithm using macromodeling and linear programming.Proceedings of DesignAutomation Conference, 2006.217-222.), in order to determine the demand of different layout result to decoupling capacitance.Secondly, the linear programming problem of placing by the research decoupling capacitance is shown one " electric density " (" Electric Density ") function on the chip with the demand schedule of decoupling capacitance.In fact, " electric density " function representation the size of the power supply capacity of diverse location on the chip.In general, when excessive, just illustrate that this zone needs to use decoupling capacitance further strengthen power supply capacity as " the electric density " in certain zone on the fruit chip.Therefore, " electric density " function can represent that zones of different is to the decoupling capacitance demand on the chip.And balance " electric density " function will help placing decoupling capacitance still less.Next further set up one " supply and demand system " (" Supply and Demand System ") for " electric density " function, be used for producing the power of mobile module in the layout or mobile unit, make the unit move towards the direction that helps reducing decoupling capacitance.This power and original power are pointed to layout device (Spindler P, Schlichtmann U, Johannes F M.Kraftwerk2-A Fast Force-Directed Quadratic Placement Approach Using anAccurate Net Model.IEEE Transactions on Computer-Aided Design of IntegratedCircuits and Systems, 2008,27 (8): other power is taken all factors into consideration together 1398-1411.), just can obtain existing optimized line length, can reduce layout result again the decoupling capacitance demand.So-called power is pointed to the layout device, and its basic thought is to be the equivalence of the interconnection line between any two unit or the module spring, and each unit (or module) is subjected to the effect of the attractive force that other interconnecting unit (or module) applies by spring; According to Hooke's law as can be known, the size of this attractive force is directly proportional with distance between unit (or module), and the stiffness factor of spring then is the direct weight sum of phase connecting diagram between the unit (or module); Under the effect of attractive force, all interconnecting units (or module) will move along the direction of power, reach the state of energy minimum up to total system, i.e. equilibrium state, and the size of making a concerted effort that each unit this moment (or module) is subjected to is zero; And power sensing layout device allows unit (or module) move along its suffered resultant direction exactly, makes a concerted effort to reduce to till zero up to this; The placement algorithm that points to principle based on power is through for a long time development, and one is pointed to the placement algorithm flow process as shown in Figure 9 than complete modern power.Generally speaking, the present invention can produce rational layout, and need not to place too much decoupling capacitance and just can eliminate transient voltage noise reduction sound on the power ground network, reduces design iteration, reduces design cost and shortens the purpose of design time thereby reach.

We adopt the actual design example of industry member that the inventive method is tested, and table with test results is understood validity of the present invention: the present invention can make the decoupling capacitance total amount reduce about 35% under total line length only increases cost about 0.5%.And the present invention only needs short working time, can be used as the practical approach that the layout stage decoupling capacitance is optimized.

Summary of the invention

The present invention has designed a kind of method of using decoupling capacitance to suppress ic power earth cord network transient voltage noise reduction sound efficiently, in layout process, consider the placement of conventional in layout performance index (line length) and decoupling capacitance simultaneously, can obtain to help improving the layout result of power supply performance effectively.Application macro model (Macro-model) is converted into a linear programming problem with the decoupling capacitance optimization problem, thereby can determine the different demands of different layout result to decoupling capacitance apace; Use the power supply capacity of diverse location on " electric density " (" Electric Density ") function representation layout process chips, thereby the power supply load reasonably can be distributed according to power supply capacity; " supply and demand system " (" Supply andDemand System ") is used for producing the power of adjusting unit in the layout or module position, thereby makes the power supply load to move to the position of setting effectively; Power is pointed to layout device (Force-Directed Placer) and is used for traditional layout index (line length), unit or module is overlapping and the decoupling capacitance placement integrates and is optimized, thereby can keep reducing the use amount of decoupling capacitance effectively under line length and unit or the non-overlapping prerequisite of module.The decoupling capacitance that the present invention is based on these four kinds of methods realizations suppresses ic power earth cord network transient voltage noise reduction sound and has obtained good effect.

Below " electric density " function of decoupling capacitance and " supply and demand system " are illustrated.To help the layout result that decoupling capacitance is placed in order accessing, must in layout process, to produce a power of representing the decoupling capacitance demand.And, just must in the iteration each time of layout process, can both estimate the demand of decoupling capacitance in order to produce this power.The basic step of the method for quick estimating of the decoupling capacitance total amount of Ti Chuing is in the present invention:

1) method (the Zhao M of use macro model, Panda R, Sundareswaran S, et al.A faston-chip decoupling capacitance budgeting algorithm using macromodeling andlinear programming.Proceedings of Design Automation Conference, 2006.217-222.), earlier the decoupling capacitance problem of placing is converted into linear programming problem by a nonlinear optimal problem; By with the circuit equation in the decoupling capacitance optimization problem

With voltage drop constraint V 〉=V_Thre(wherein: C represents supply network node capacitor matrix, and G represents the node conductance matrix, and V represents the node voltage matrix, and J represents that node receives current matrix, V to carry out linearization_ThreThe voltage drop threshold value of expression user appointment), thus the decoupling capacitance optimization problem is converted into a linear programming problem.This distortion mainly comprises following three steps: at first, and note V_2sBe the voltage vector on the violation area sampling point, and [t₀, t₁] for violating the time window of voltage drop constraint, so, can be with improved nodal voltage equation piecemealAnd it is carried out integration obtains:

$\left(\begin{array}{cc}{G}_{11}& G_{12}\\ G_{12}^T& G_{22}\end{array}\right)\&CenterDot;\left(\begin{array}{c}{\&Integral;}_{t_0}^{t_1}{V}_{1s}\mathrm{dt}\\ {\&Integral;}_{t_0}^{t_1}{V}_{2s}\mathrm{dt}\end{array}\right)=\left(\begin{array}{c}{\&Integral;}_{t_0}^{t_1}{\mathrm{<figure-callout\; label="J"\; filenames="HSA00000165093800032.png,HSA00000165093800041.png"\; state="\{\{state\}\}">J</figure-callout>}}_1\mathrm{dt}\\ {\&Integral;}_{t_0}^{t_1}{\mathrm{<figure-callout\; label="J"\; filenames="HSA00000165093800032.png,HSA00000165093800041.png"\; state="\{\{state\}\}">J</figure-callout>}}_2\mathrm{dt}+{\&Integral;}_{t_0}^{{\mathrm{<figure-callout\; label="t"\; filenames="HSA00000165093800032.png,HSA00000165093800041.png"\; state="\{\{state\}\}">t</figure-callout>}}_1}\mathrm{Idt}\end{array}\right)$

Wherein: V_1sBe power supply network internal node voltages vector, J₁For the power supply network internal node receives current vector, J₂Be the current vector that receives of power supply network fringe node, I is the supply current vector of power pad Pad, G₁₁Be the electric derived vector of power supply network internal node, G₁₂Be the conductance matrix between power supply network internal node and the power pad Pad, G₂₂Conductance matrix for power pad Pad.

Secondly, use macro model to obtain the electric weight equation of transfer to above-mentioned formula

Q＝H·W+B

Wherein:

Be the electric weight that need provide from decoupling capacitance,

Be admittance matrix, W is the voltage waveform integration

And

Equivalent electric quantity for load current source; At last, transient voltage is fallen constraint V 〉=V_ThreBe converted into linear restriction by integration about voltage waveform integration W.As shown in Figure 1, the transient voltage waveform that falls constraint requirements voltage after having added decoupling capacitance can not be lower than voltage drop threshold value V_ThreAccordingly, voltage waveform integration W should be less than the area of dash area among the figure.The trapezoidal area of the area of dash area under by a dotted line is similar among the figure.This is because before adding optimum decoupling capacitance, can't know the voltage curve that surrounds the dash area area.So constraint V 〉=V falls in transient voltage_ThreJust be converted into the voltage waveform integral constraint, thereby decoupling capacitance optimization is converted into a following linear optimization problem;

$\mathrm{mi}\underset{i\&Element;S}{\mathrm{\&Sigma;}}{c}_i$

s.t. ------(1)

$M^{\&prime;}\&CircleTimes;C\&GreaterEqual;H\&CenterDot;W+B$

W≥L

0≤c_i≤c_max，i

Wherein: S is the sampling set of node in violation of rules and regulations, and m=|S| represents the element number in the S set, vectorial C=[c₁, c₂..., c_m], c_iBe illustrated in decoupling capacitor and stray capacitance sum that i sampling node adds, c_{Max, i}Be illustrated near the maximum decoupling capacitor value that is allowed i the sampling node, symbol

Expression is multiplied each other item by item, and a T=(t clocks₁-t₀)/2, M ' in the following formula and L can be calculated by following formula:

$M^{\&prime;}=\left(\begin{array}{c}{V}_1\left(t_0\right)-V_1\left(t_1\right)\\ V_2\left(t_0\right)-V_2\left(t_1\right)\\ .\\ .\\ .\\ V_m\left(t_0\right)-V_m\left(t_1\right)\end{array}\right),L=\left(\begin{array}{c}(V_{\mathrm{thre}}+V_1\left(t_0\right))\&CenterDot;T\\ (V_{\mathrm{thre}}+V_2\left(t_0\right))\&CenterDot;T\\ .\\ .\\ .\\ (V_{\mathrm{thre}}+V_m\left(t_0\right))\&CenterDot;T\end{array}\right)---\left(2\right)$

2) linear programming problem of above-mentioned decoupling capacitance is converted into its dual problem (DualProblem).Because though the decoupling capacitance optimization problem so far has been converted into a linear programming problem, obtained simplifying greatly,, it is still unclear to produce what kind of influence to the decoupling capacitance total amount when chip upper module or unit are in diverse location actually.Cause the reason of this situation be module or unit on chip the position directly influence be the equivalent electric quantity B of load current source, and in the Linear Programming Problem (1), the equivalent electric quantity B of load current source has appeared at intrafascicular approximately, causes being difficult to setting up contacting directly between the position of module or unit and the decoupling capacitance total amount.For the position and the relation between the decoupling capacitance total amount that can make chip upper module or unit is more clear, the linear programming problem (1) of decoupling capacitance is converted into its dual problem

$\max {(L-W)}^T\&CenterDot;C^{\&prime;}-C_{\max }^T\&CenterDot;C^{\&prime;\&prime;}$

s.t.

$M^{\&prime;}\&CircleTimes;(H^{-1}\&CenterDot;C^{\&prime;})-C^{\&prime;\&prime;}\&le;E---\left(3\right)$

H^-1·C′≥0

C′≥0，C″≥0

Wherein: W=-B^TH^-1, C ' and C " and represent the dual variable of C respectively,

The maximum decoupling capacitor vector that allows adding of expression, constant vector E=[1,1 ..., 1]^TDuality principle according to linear programming knows that dual problem (3) has identical separating with the former linear programming problem (1) that decoupling capacitance is optimized, and has all represented the decoupling capacitance total amount of needs.And can see that from the objective function of dual problem (3) the total amount of decoupling capacitance is proportional to norm ‖ L-W ‖₁In fact, vectorial L-W has represented the integration of the gap between voltage waveform in violation of rules and regulations and the legal voltage waveform in the physical sense just, as shown in Figure 2.

3) the decoupling capacitance electric weight that need provide can be used as a standard weighing the decoupling capacitance demand, and the demand of decoupling capacitance is modeled as " electric density function " on the chip.In fact, with the supply and demand system class of chip upper module or cell distribution seemingly, it is the integration of the required voltage waveform of module or unit that L and W have also represented the supply and demand of supply voltage: W; L is the integration of the power ground network voltage waveform that can provide; And the decoupling capacitance part that will remedy just of the gap between the two.And can be further by respectively to W and L interpolation obtain on entire chip " electric density function " W (x, y) and L (x, y).By paired observation, can find " electric density function " and " cell density function "

Between similarity

$W(x,y)\&LeftRightArrow;D_{\mathrm{mod}}^{\mathrm{dem}}(x,y)$

$L(x,y)\&LeftRightArrow;D_{\mathrm{mod}}^{\sup }(x,y)$

4) set up corresponding supply and demand system by " electric density function " for the demand of decoupling capacitance at last.This supply and demand system by Poisson equation (shape as

Oval partial differential equation) define potential-energy function Ψ (x, y) expression:

$(\frac{{\&PartialD;}^2}{\&PartialD;x^2}+\frac{{\&PartialD;}^2}{{\&PartialD;y}^2})\mathrm{\&Psi;}(x,y)=L(x,y)-W(x,y)$

Satisfy the Newman boundary condition

Use decoupling capacitance to suppress in the method for integrated circuit electricity supply network noise, comprise and produce the standard cell placement step that helps improving power supply performance, minimizing decoupling capacitance placement total amount, it be with the area of decoupling capacitance and conventional in layout index (line length, module or cells overlap) simultaneously as optimization aim, effective method for solving that power ground network noise and layout line length are optimized is simultaneously come in the position of adopting the method for iteration constantly to adjust module in the layout or unit.It gets up method synthesis such as macro model, electric density function, supply and demand system, power sensing layout, produces to help using a small amount of decoupling capacitance to suppress the layout result of integrated circuit electricity supply network noise, obtains good optimization effect.Specifically may further comprise the steps:

Step (1), computing machine are read in the file that comprises power ground network design parameter and cell layout's design parameter, and power ground network design parameter comprises: the position of power ground and line width, the position of energization pins Pin; Determine the relational structure between the node on it, initial resistivity value, capacitance and cell current source model between the node according to the position of power ground network and width, promptly the time dependent current waveform that receives of each unit correspondence is represented with PWL; In computing machine, set up the circuit model of power ground network in view of the above; Described cell layout design parameter comprises: whether the initial position that the side-play amount of pin, unit are placed on the size of each unit, the unit, the direction of unit, the zone of layout, the position and the unit of cell row can move;

Step (2), the power ground network is carried out static analysis, if falling, quiescent voltage do not meet the demands, then the power ground network is carried out whole live width adjustment, make dc voltage drop meet design requirement, add decoupling capacitance with this as next step and carry out the pacing items that elimination falls in transient voltage;

Step (3) is carried out initialization to layout, at first all transportable unit is placed into the center of layout areas, repeats following initialization step (3.1)-(3.3) five times then;

Step (3.1), use the bounding box linear model to obtain the quadratic expression of line length:

${\mathrm{\&Gamma;}}_x=\frac{1}{2}{x}^T{C}_{x}x+d_x^{T}x+\mathrm{<figure-callout\; label="const"\; filenames="HSA00000165093800032.png,HSA00000165093800041.png"\; state="\{\{state\}\}">const</figure-callout>}1$

${\mathrm{\&Gamma;}}_y=\frac{1}{2}{y}^T{C}_{y}y+d_y^{T}y+\mathrm{const}2$

Wherein:

Γ_xAnd Γ_yBe respectively the semi-perimeter line length of X-direction and Y direction,

X represents the vector that each unit center constitutes in the cartesian coordinate system on X-direction,

Y represents the vector that each unit center constitutes in the cartesian coordinate system on X-direction,

(x, y) expression residing position, unit,

d_xBe a vector, represent the annexation on X-direction between removable unit and the fixed cell, if they have annexation, then they are at d_xThe element of middle relevant position is 1, otherwise is 0,

d_yBe a vector, represent the annexation on Y direction between removable unit and the fixed cell, if they have annexation, then they are at d_yThe element of middle relevant position is 1, otherwise is 0,

C_xBe a title matrix that positive semidefinite is right, be used for representing the annexation on X-direction between the removable unit, if between two removable unit annexation is arranged, then they are at C_xThe element of middle relevant position is 1, otherwise is 0,

C_yBe a title matrix that positive semidefinite is right, be used for representing the annexation on Y direction between the removable unit, if between two removable unit annexation is arranged, then they are at C_yThe element of middle relevant position is 1, otherwise is 0,

Const1 represents the line length constant term of directions X,

Const2 represents the line length constant term of Y direction,

The bounding box linear model is meant a minimum rectangle that comprises all summits of gauze, and its girth can be expressed as

L_n＝2(x_max-x_min+y_max-y_min)

(x wherein_Min, y_Min) be the apex coordinate in this rectangle frame lower left corner, (x_Max, y_Max) be the apex coordinate in its upper right corner;

Step (3.2), find the solution system of linear equations respectively about x and y:

C_xx＝d_x

C_yy＝d_y

This equation is two systems of linear equations, and that matrix of coefficients has is sparse, the character of positive definite, symmetry, uses the method for ICCG to find the solution, and obtains x and y;

Step (3.3), x and y according to step (3.2) obtains make x '=x and y '=y, and the reposition that changes the unit is (x ', y ');

Step (4) is added the total arrangement of decoupling capacitance;

Step (4.1), initializes weights parameter and weight matrix:

Step (4.1.1), the initializes weights parameter beta

$\mathrm{\&beta;}=\frac{2}{V_{\mathrm{dd}}-V_{\mathrm{thre}}}$

V wherein_DdBe supply voltage, V_ThreIt is the voltage drop threshold value of user's appointment;

Step (4.1.2), the initializes weights matrix

Wherein

Be layout quality control weight parameter matrix, by the area parameters A of each unit_iCalculate, m represents the total quantity of unit, i=1, and 2 ..., m;

Step (4.1.3), initialization electric weight weight matrix

Wherein

Be electric weight weight coefficient matrix in the time t, receive electric weight J by each unit_iIntegral and calculating to time t obtains;

Step (4.2), the Duplication Ω of computing unit, overlapping unit overlapping and the unit of comprising overlaps two kinds of situations, the implication of Duplication is the number percent that the element number that overlaps accounts for total element number, if Duplication is less than 10%, then layout finishes, otherwise repeats following steps;

Step (4.3), the distribution density function of computing unitWith

Step (4.3.1) is calculated the object element distribution density function

$D_{\mathrm{mod}}^{\sup }(x,y)=\frac{\underset{i=1}{\overset{m}{\mathrm{\&Sigma;}}}{A}_i}{A_{\mathrm{chip}}}$

The object element distribution density function

The i.e. cell distribution density function that obtains of expectation after finishing layout, wherein: A_ChipThe area of expression entire chip, A_iThe area of representing each unit;

Step (4.3.2) is calculated the density function of cell distribution in the current layout

In order to calculate

Here introduce a rectangular window function

Represented whether select active cell, wherein (x, y) expression active cell position, (x_Ll, y_Ll) coordinate on summit, the lower left corner of expression rectangle, (w h) is the width and the height of this rectangle; If note active cell center is

The width of active cell and highly be (w_i, h_i), then set up corresponding to above-mentioned rectangular window function following formula:

$x_{\mathrm{ll}}=x_i^{\&prime;}-\frac{{\mathrm{<figure-callout\; label="w\; i"\; filenames="HSA00000165093800032.png,HSA00000165093800041.png"\; state="\{\{state\}\}">w</figure-callout>}}_i}{2}$

$y_{\mathrm{ll}}=y_i^{\&prime;}-\frac{{\mathrm{<figure-callout\; label="h\; i"\; filenames="HSA00000165093800032.png,HSA00000165093800041.png"\; state="\{\{state\}\}">h</figure-callout>}}_i}{2}$

At this moment the density function of cell distributionCan calculate by following formula:

$D_{\mathrm{mod}}^{\mathrm{dem}}(x,y)=\underset{i=1}{\overset{m}{\mathrm{\&Sigma;}}}{d}_{\mathrm{mod},i}\&CenterDot;R(x,y,x_i^{\&prime;}-\frac{{\mathrm{<figure-callout\; label="w\; i"\; filenames="HSA00000165093800032.png,HSA00000165093800041.png"\; state="\{\{state\}\}">w</figure-callout>}}_i}{2},y_i^{\&prime;}-\frac{{\mathrm{<figure-callout\; label="h\; i"\; filenames="HSA00000165093800032.png,HSA00000165093800041.png"\; state="\{\{state\}\}">h</figure-callout>}}_i}{2},w_i,h_i)$

D wherein_{Mod, i}The density of expression unit i is set to 1 under the simple scenario;

Step (4.4), the Poisson equation of finding the solution the supply and demand system that description unit distributes, obtain potential-energy function Φ (x, y), Poisson equation be shape as

Oval partial differential equation, it is as follows that the supply and demand system is described as Poisson equation:

$(\frac{{\&PartialD;}^2}{{\&PartialD;x}^2}+\frac{{\&PartialD;}^2}{{\&PartialD;y}^2})\mathrm{\&Phi;}(x,y)=D_{\mathrm{mod}}^{\sup }(x,y)-D_{\mathrm{mod}}^{\mathrm{dem}}(x,y)$

Satisfy the Newman boundary condition

Wherein n represents the borderline normal vector of field of definition;

Step (4.5), computing chip power on density function W (x, y) and L (x, y)

Step (4.5.1) is utilized the method for macro model, with power ground lattice network equation

Change into following form:

$\left(\begin{array}{cc}{G}_{11}& G_{12}\\ G_{12}^T& G_{22}\end{array}\right)\&CenterDot;\left(\begin{array}{c}{\&Integral;}_{t_0}^{t_1}{V}_{1s}\mathrm{dt}\\ {\&Integral;}_{t_0}^{t_1}{V}_{2s}\mathrm{dt}\end{array}\right)=\left(\begin{array}{c}{\&Integral;}_{t_0}^{t_1}{\mathrm{<figure-callout\; label="J"\; filenames="HSA00000165093800032.png,HSA00000165093800041.png"\; state="\{\{state\}\}">J</figure-callout>}}_1\mathrm{dt}\\ {\&Integral;}_{t_0}^{t_1}{\mathrm{<figure-callout\; label="J"\; filenames="HSA00000165093800032.png,HSA00000165093800041.png"\; state="\{\{state\}\}">J</figure-callout>}}_2\mathrm{dt}+{\&Integral;}_{t_0}^{{\mathrm{<figure-callout\; label="t"\; filenames="HSA00000165093800032.png,HSA00000165093800041.png"\; state="\{\{state\}\}">t</figure-callout>}}_1}\mathrm{Idt}\end{array}\right)$

Wherein:

C represents supply network node capacitor matrix,

G represents the node conductance matrix,

V represents the node voltage matrix,

J represents that node receives current matrix,

V_2sBe the node voltage vector that needs to add decoupling capacitance,

V_1sBe supply network internal node voltages vector,

J₁For the supply network internal node receives current vector,

J₂Be the current vector that receives of supply network fringe node,

I is the supply current vector of power pad Pad,

G₁₁Be the electric derived vector of supply network internal node,

G₁₂Be the conductance matrix between supply network internal node and the power pad Pad,

G₂₂Conductance matrix for power pad Pad;

Step (4.5.2), according to following steps, calculate power consumption density function W (x, y) and power density function L (x, y):

Step (4.5.2.1), the calculating voltage integral of pulse shape

There is following formula to set up simultaneously

W＝-B^T·H^-1

WhereinThe admittance matrix of expression power ground network,

The equivalent electric quantity of expression load current source;

Step (4.5.2.2) is at T=(t₁-t₀Calculate power density function L in the time of)/2

$L=\left(\begin{array}{c}(V_{\mathrm{thre}}+V_1\left(t_0\right))\&CenterDot;T\\ (V_{\mathrm{thre}}+V_2\left(t_0\right))\&CenterDot;T\\ .\\ .\\ .\\ (V_{\mathrm{thre}}+V_m\left(t_0\right))\&CenterDot;T\end{array}\right)$

V wherein_i(t₀) be t₀The voltage vector of moment unit i;

Step (4.5.2.3), utilize step (4.5.2.1) and (4.5.2.1) in the W and the L that obtain, the method that adopts Lagrange's interpolation is at the enterprising row interpolation in layout plane, obtain power consumption density function W (x, y) and power density function L (x, y);

Step (4.6) is found the solution by adding the Poisson equation that decoupling capacitance reaches the supply and demand system balancing, obtain potential-energy function Ψ (x, y)

$(\frac{{\&PartialD;}^2}{\&PartialD;x^2}+\frac{{\&PartialD;}^2}{{\&PartialD;y}^2})\mathrm{\&Psi;}(x,y)=L(x,y)-W(x,y)$

Satisfy the Newman boundary condition

In above-mentioned Poisson equation, contract of supply L (x, y) generally can not with demand function W (x, y) complete equipilibrium, this point are that the self character by electric power system is determined, exactly because the supply and demand function can not complete equipilibrium, carry out the equilibrium of supply and demand as a supplement just need to add decoupling capacitance, and, in order to make above-mentioned Poisson equation to separate, need carry out orthogonalization to the supply and demand function

Represent orthogonalized power density function,

Represent orthogonalized power consumption density function

$\tilde{L}(x,y)=L(x,y)-\&Integral;\&Integral;\mathrm{Ldxdy}$

$\tilde{W}(x,y)=W(x,y)-\&Integral;\&Integral;\mathrm{Wdxdy}$

Step (4.7), according to the result of step (3.3), use the bounding box linear model to obtain the quadratic expression of current line length:

${\mathrm{\&Gamma;}}_x=\frac{1}{2}{x}^T{C}_x{x}^{\&prime;}+d_x^T{x}^{\&prime;}+\mathrm{<figure-callout\; label="const"\; filenames="HSA00000165093800032.png,HSA00000165093800041.png"\; state="\{\{state\}\}">const</figure-callout>}1$

${\mathrm{\&Gamma;}}_y=\frac{1}{2}{y}^T{C}_y{y}^{\&prime;}+d_y^T{y}^{\&prime;}+\mathrm{<figure-callout\; label="const"\; filenames="HSA00000165093800032.png,HSA00000165093800041.png"\; state="\{\{state\}\}">const</figure-callout>}2$

Step (4.8) is utilized difference method, the continuous variable problem is converted into the discrete variable problem so that numerical solution, obtain potential-energy function Φ (x, y) and Ψ (x, gradient function y):

${\mathrm{\&Phi;}}_x=\frac{\&PartialD;\mathrm{\&Phi;}(x,y)}{\&PartialD;x},$${\mathrm{\&Phi;}}_y=\frac{\&PartialD;\mathrm{\&Phi;}(x,y)}{\&PartialD;y}$

${\mathrm{\&Psi;}}_x=\frac{\&PartialD;\mathrm{\&Psi;}(x,y)}{\&PartialD;x},$${\mathrm{\&Psi;}}_y=\frac{\&PartialD;\mathrm{\&Psi;}(x,y)}{\&PartialD;y}$

And to Ψ_x, Ψ_yCalculate its corresponding zoom factor γ to guarantee that cells overlap can be eliminated effectively:

${\mathrm{\&gamma;}}_i=\min (\mathrm{1,0.9}\&times;\frac{<\&dtri;{\mathrm{\&Phi;}}_i\&CenterDot;\&dtri;{\mathrm{\&Phi;}}_i>}{<\&dtri;{\mathrm{\&Phi;}}_i\&CenterDot;\&dtri;{\mathrm{\&Psi;}}_i>})$

Wherein i is an element number, ▽ Φ_i, ▽ Ψ_iFor potential-energy function Φ (x, y) and Ψ (x, y) at the Grad of this unit center position, operational symbol＜expression asks the inner product of two vectors;

Step (4.9), the power pointing method of utilization is adjusted placement position, sets up equilibrium equation

$F_x^{\mathrm{net}}+F_x^{\mathrm{hold}}+(F_x^{\mathrm{move}}+F_x^{\mathrm{decap}})=0$

$F_y^{\mathrm{net}}+F_y^{\mathrm{hold}}+(F_y^{\mathrm{move}}+F_y^{\mathrm{decap}})=0---\left(4\right)$

Wherein

The pulling force of corresponding line length on the expression X-direction,

The pulling force of corresponding line length on the expression Y direction,

$F_x^{\mathrm{net}}=C_x\&CenterDot;x^{\&prime;}+d_x$

$F_y^{\mathrm{net}}=C_y\&CenterDot;y^{\&prime;}+d_y$

Expression makes the power that layout remains unchanged on the X-direction under the situation of the power of not scattering,

Expression makes the power that layout remains unchanged on the Y direction under the situation of the power of not scattering,

$F_x^{\mathrm{hold}}=-(C_x\&CenterDot;x^{\&prime;}+d_x)$

$F_y^{\mathrm{hold}}=-(C_y\&CenterDot;y^{\&prime;}+d_y)$

The center of unit in x ' and the y ' expression layout wherein,

Eliminate the power of scattering of cells overlap on the expression X-direction,

Eliminate the power of scattering of cells overlap on the expression Y direction,

$F_x^{\mathrm{move}}={\stackrel{\&CenterDot;}{C}}_x(\mathrm{\&Delta;x}+{\mathrm{\&Phi;}}_x)$

$F_y^{\mathrm{move}}={\stackrel{\&CenterDot;}{C}}_y(\mathrm{\&Delta;y}+{\mathrm{\&Phi;}}_y)$

Be a diagonal matrix, its diagonal element is represented gauze to the tension coefficient of unit on X-direction,

Be a diagonal matrix, its diagonal element is represented gauze to the tension coefficient of unit on Y direction,

The power of scattering on the expression X-direction under the decoupling capacitance influence,

The power of scattering on the expression Y direction under the decoupling capacitance influence,

$F_x^{\mathrm{decap}}=\stackrel{\&CenterDot;}{Q}(\mathrm{\&Delta;x}+\mathrm{\&beta;}\&CenterDot;\mathrm{\&gamma;}\&CenterDot;{\mathrm{\&Psi;}}_x)$

$F_y^{\mathrm{decap}}=\stackrel{\&CenterDot;}{Q}(\mathrm{\&Delta;y}+\mathrm{\&beta;}\&CenterDot;\mathrm{\&gamma;}\&CenterDot;{\mathrm{\&Psi;}}_y)$

Δ x=x-x ' wherein, Δ y=y-y ' is the adjustment amount of cell position, the computing formula substitution equation (4) above-mentioned power obtains:

$(C_x+{\stackrel{\&CenterDot;}{C}}_x+{\stackrel{\&CenterDot;}{Q}}_x)\mathrm{\&Delta;x}=-({\stackrel{\&CenterDot;}{C}}_x{\mathrm{\&Phi;}}_x+\mathrm{\&beta;}\&CenterDot;\mathrm{\&gamma;}\&CenterDot;{\mathrm{\&Psi;}}_x)$

$(C_y+{\stackrel{\&CenterDot;}{C}}_y+{\stackrel{\&CenterDot;}{Q}}_y)\mathrm{\&Delta;y}=-({\stackrel{\&CenterDot;}{C}}_y{\mathrm{\&Phi;}}_y+\mathrm{\&beta;}\&CenterDot;\mathrm{\&gamma;}\&CenterDot;{\mathrm{\&Psi;}}_y)$

In the following formula

ExpressionComponent on X-direction,

Expression

Component on Y direction is found the solution the reposition that above-mentioned equilibrium equation obtains each unit center afterwards;

Step (4.10) is calculated adjustment factor κ and is adjusted parameter matrix

$\stackrel{\&CenterDot;}{P}\&LeftArrow;\mathrm{\&kappa;}\left(\mathrm{\&mu;}\right)\&CenterDot;\stackrel{\&CenterDot;}{P}$

$\stackrel{\&CenterDot;}{Q}\&LeftArrow;\mathrm{\&kappa;}\left(\mathrm{\&mu;}\right)\&CenterDot;\stackrel{\&CenterDot;}{Q}---\left(5\right)$

κ(μ)＝1+tanh(ln(μ_T/μ))

$\mathrm{\&mu;}=\frac{1}{m}\underset{i=1}{\overset{m}{\mathrm{\&Sigma;}}}\sqrt{\mathrm{\&Delta;}{x}^2+\mathrm{\&Delta;}{\mathrm{<figure-callout\; label="y"\; filenames="HSA00000165093800032.png,HSA00000165093800041.png"\; state="\{\{state\}\}">y</figure-callout>}}^2}$

Wherein μ is the average amount of movement of all unit, μ_TCell position adjustment amount for the expectation of user's appointment;

Step (5) legalizes to the result of total arrangement

The layout of utilize the resolving method that legalizes is eliminated overlapping between the unit, and is eliminated the dislocation of unit on cell row and since in this process cell position change little, very little to the influence of power ground network performance, therefore need not to do again special processing;

Step (6) is carried out decoupling capacitance to the inequality after legalizing and is placed

Utilization is the final layout result coupling capacitance of adding up based on sensitivity of method, sensitivity is to consider that circuit node voltage is along with the sensitivity of receiving electric current to change, the adding decoupling capacitor can improve the sensitivity of circuit, make that the variation of receiving electric current is littler to the node voltage influence of supply network, finally obtain better power supply performance.

Experiment showed, that method optimal speed proposed by the invention is fast, it is effective to optimize, the internal memory of saving computing machine, have the ability of optimizing large-scale circuit.

Description of drawings:

Fig. 1: do not add decoupling capacitance and add decoupling capacitance voltage waveform afterwards.

Fig. 2: the gap between voltage waveform and the legal voltage waveform in violation of rules and regulations.

Fig. 3: the piecewise linearity in time-dependent current source was represented when the unit received electric current.

Fig. 4: unit in the power ground grid of mesh network and the layout.

Fig. 5: the initialization layout result of example daiTest1 only being considered line length.

Fig. 6: to the 15 iteration result of example daiTest1 layout.

Fig. 7: to the total arrangement result of example daiTest1.

Fig. 8: the result after the layout of example daiTest1 legalized.

Fig. 9: traditional power is pointed to the algorithm flow of layout device and is described.

Figure 10: consider to add the power sensing placement algorithm flow process description of decoupling capacitance.

Embodiment:

The test circuit example daiTest1 of the Bookshelf form that provides with industry member does example and uses decoupling capacitance to suppress the optimization of integrated circuit electricity supply network noise with method of the present invention, now in conjunction with Figure 10 it is described in detail:

Step (1) is read in the circuit information file, makes up circuit structure

This is an input process, and the topology file of test use Bookshelf form (daiTest1.aux, daiTest1.nets, daiTes1.nodes, daiTest1.pl, daiTest1.scl, daiTest1.wts); The file daiTest1_pg.mat that receives current source of power ground physical design parameters and unit correspondence is described, the current source that becomes when wherein receiving current source to be, in the current source library file, use and receive the piecewise linearity of current source waveform to represent (PWL), as shown in Figure 3; And set up corresponding circuit model and current source model, here the power ground network using mesh network, the model of whole power supply/network and lower floor unit is as shown in Figure 4.

Step (2) is carried out STATIC SIMULATION to the power ground network

According to the circuit topological structure of setting up in the step (1), set up STATIC SIMULATION equation GV=J according to Kirchhoff's law, wherein G is a conductance matrix, and is only relevant with electric conductivity value and circuit structure in the circuit, V is a supply node voltage vector to be asked, and J is the current vector that receives of node.Because the matrix of coefficients G of this system of equations has character sparse, symmetrical, positive definite, colleges and universities' derivation algorithm of at present existing many maturations, we adopt is a kind of method of conjugate gradient ICCG (IncompleteCholesky Conjugate Gradient) that decomposes pre-excellent matrix based on incomplete Qiao Laisiji in the pre-excellent method of conjugate gradient (PCG, Precondition Conjugate Gradient).Find the solution finish after, obtain this magnitude of voltage of each node constantly, note is made vectorial V.The voltage of note power ground net power pad Pad is V_Dd, V during test_DdBe set at 1.5, then to fall be exactly V to the quiescent voltage of its internal node_Dd-V_ThreSetting quiescent voltage during test, to fall threshold value be V_Thre=1.4, if falling, this quiescent voltage surpasses 0.1, then emulation finishes; Otherwise proceed the integral layout that following steps are added decoupling capacitance.

Step (3) is carried out the layout initialization

Comprise removable unit and can not mobile unit in the layout constraint file, removable unit is exactly the unit that can change its coordinate in following layout process, can not mobile unit be exactly the unit of immutable coordinate in following layout process.Comprised 1511 unit (m=1511) in the daiTest1 topology file, 1309 of wherein removable unit place it in the center of layout areas, can not mobile unit 202, place it in assigned address according to the constraint condition in the topology file.Repeating step (3.1)-(3.3) is five times then.

Step (3.1) obtains the expression formula of secondary line length according to following formula

${\mathrm{\&Gamma;}}_x=\frac{1}{2}{x}^T{C}_{x}x+d_x^{T}x+\mathrm{<figure-callout\; label="const"\; filenames="HSA00000165093800032.png,HSA00000165093800041.png"\; state="\{\{state\}\}">const</figure-callout>}1$

${\mathrm{\&Gamma;}}_y=\frac{1}{2}{y}^T{C}_{y}y+d_y^{T}y+\mathrm{<figure-callout\; label="const"\; filenames="HSA00000165093800032.png,HSA00000165093800041.png"\; state="\{\{state\}\}">const</figure-callout>}2$

Step (3.2) is found the solution system of linear equations

C_xx＝d_x

C_yy＝d_y

This equation is two systems of linear equations, and that matrix of coefficients has is sparse, the character of positive definite, symmetry, uses the method for ICCG to find the solution, and obtains x and y;

Step (3.3), x and y according to step (3.2) obtains make x '=x and y '=y, and the reposition that changes the unit is (x ', y ');

As initialization layout of the present invention, the initialization layout result as shown in Figure 5 with the above-mentioned layout result that obtains.

Step (4) is added the total arrangement of decoupling capacitance.The Duplication of regulation unit finishes less than 10% o'clock total arrangement, allows iteration at most 200 times.

Step (4.1), according to above 4.1 saving described formula initializes weights parameter:

$\mathrm{\&beta;}=\frac{2}{V_{\mathrm{dd}}-V_{\mathrm{thre}}}=\frac{2}{1.5-1.4}=20$

The cellar area parameter that provides according to following formula and Bookshelf file and receive current parameters initiation parameter matrix

Step (4.2), the Duplication Ω of computing unit.The implication of Duplication is the number percent that the element number that overlaps accounts for total element number, if Ω＜10%, then layout finishes, otherwise carries out following process.

Step (4.3) is according to the distribution density function of following formula computing unitWith

$D_{\mathrm{mod}}^{\sup }(x,y)=\frac{\underset{i=1}{\overset{m}{\mathrm{\&Sigma;}}}{A}_i}{A_{\mathrm{chip}}}$

$D_{\mathrm{mod}}^{\mathrm{dem}}(x,y)=\underset{i=1}{\overset{m}{\mathrm{\&Sigma;}}}{d}_{\mathrm{mod},i}\&CenterDot;R(x,y,x_i^{\&prime;}-\frac{{\mathrm{<figure-callout\; label="w\; i"\; filenames="HSA00000165093800032.png,HSA00000165093800041.png"\; state="\{\{state\}\}">w</figure-callout>}}_i}{2},y_i^{\&prime;}-\frac{{\mathrm{<figure-callout\; label="h\; i"\; filenames="HSA00000165093800032.png,HSA00000165093800041.png"\; state="\{\{state\}\}">h</figure-callout>}}_i}{2},w_i,h_i)$

Step (4.4) is set up the supply and demand system of unit according to following formula, and solve potential-energy function Φ (x, y)

$(\frac{{\&PartialD;}^2}{{\&PartialD;x}^2}+\frac{{\&PartialD;}^2}{{\&PartialD;y}^2})\mathrm{\&Phi;}(x,y)=D_{\mathrm{mod}}^{\sup }(x,y)-D_{\mathrm{mod}}^{\mathrm{dem}}(x,y)$

Satisfy the Newman boundary condition

This is a Poisson equation, the method of finding the solution is a lot, here use a kind of many grids of geometry solver DiMEPACK (M.Kowarschik and C.Wei β, " DiMEPACK-A cache-optimizedmultigrid library; " in Proc.Int.Conf.Parallel Distrib.Process.Techn.Appl., H.Arabnia, Ed., pp.425-430, Jun.2001).

Step (4.5), corresponding decoupling capacitance are set up electric density function and supply and demand system

Computing chip power on density function W (x, y) and L (x y), obtains its corresponding supply and demand function.To the power ground lattice network equation that obtains with the improved nodal method of analysis

Carry out transient analysis, obtain power ground net node voltage vector V, and the voltage vector of note voltage drop node in violation of rules and regulations is V_2s, the voltage vector that satisfies the node of voltage drop constraint is V_1s, need be V therefore to node voltage_2sThe node at place adds decoupling capacitance.Utilize the macro model method, the equation of circuit correspondence is turned to

$\left(\begin{array}{cc}{G}_{11}& G_{12}\\ G_{12}^T& G_{22}\end{array}\right)\&CenterDot;\left(\begin{array}{c}{\&Integral;}_{t_0}^{t_1}{V}_{1s}\mathrm{dt}\\ {\&Integral;}_{t_0}^{t_1}{V}_{2s}\mathrm{dt}\end{array}\right)=\left(\begin{array}{c}{\&Integral;}_{t_0}^{t_1}{\mathrm{<figure-callout\; label="J"\; filenames="HSA00000165093800032.png,HSA00000165093800041.png"\; state="\{\{state\}\}">J</figure-callout>}}_1\mathrm{dt}\\ {\&Integral;}_{t_0}^{t_1}{\mathrm{<figure-callout\; label="J"\; filenames="HSA00000165093800032.png,HSA00000165093800041.png"\; state="\{\{state\}\}">J</figure-callout>}}_2\mathrm{dt}+{\&Integral;}_{t_0}^{{\mathrm{<figure-callout\; label="t"\; filenames="HSA00000165093800032.png,HSA00000165093800041.png"\; state="\{\{state\}\}">t</figure-callout>}}_1}\mathrm{Idt}\end{array}\right)$

According to following formula, calculate power consumption density function W and power density function L:

W＝-B^T·H^-1

$L=\left(\begin{array}{c}(V_{\mathrm{thre}}+V_1\left(t_0\right))\&CenterDot;T\\ (V_{\mathrm{thre}}+V_2\left(t_0\right))\&CenterDot;T\\ .\\ .\\ .\\ (V_{\mathrm{thre}}+V_m\left(t_0\right))\&CenterDot;T\end{array}\right)$

T=(t wherein₁-t₀)/2, the method that adopts Lagrange's interpolation are at the enterprising row interpolation in layout plane, obtain power consumption density function W (x, y) and power density function L (x, y).

Step (4.6), the Poisson equation of finding the solution electric density supply and demand system, obtain potential-energy function Ψ (x, y)

$(\frac{{\&PartialD;}^2}{\&PartialD;x^2}+\frac{{\&PartialD;}^2}{{\&PartialD;y}^2})\mathrm{\&Psi;}(x,y)=L(x,y)-W(x,y)$

Satisfy the Newman boundary condition

Equally, this is a Poisson equation, also the potential-energy function Ψ that obtains electric density that finds the solution with the DiMEPACK solver (x, y).

In order to make above-mentioned Poisson equation to separate, need carry out orthogonalization to the supply and demand function,Represent orthogonalized power density function,

Represent orthogonalized power consumption density function

$\tilde{L}(x,y)=L(x,y)-\&Integral;\&Integral;\mathrm{Ldxdy}$

$\tilde{W}(x,y)=W(x,y)-\&Integral;\&Integral;\mathrm{Wdxdy}$

Step (4.7), utilize difference method obtain potential-energy function Φ (x, y) and Ψ (x, gradient function y):

${\mathrm{\&Phi;}}_x=\frac{\&PartialD;\mathrm{\&Phi;}(x,y)}{\&PartialD;x},$${\mathrm{\&Phi;}}_y=\frac{\&PartialD;\mathrm{\&Phi;}(x,y)}{\&PartialD;y}$

${\mathrm{\&Psi;}}_x=\frac{\&PartialD;\mathrm{\&Psi;}(x,y)}{\&PartialD;x},$${\mathrm{\&Psi;}}_y=\frac{\&PartialD;\mathrm{\&Psi;}(x,y)}{\&PartialD;y}$

And to Ψ_x, Ψ_yCalculate its corresponding zoom factor γ to guarantee that cells overlap can be eliminated effectively:

${\mathrm{\&gamma;}}_i=\min (\mathrm{1,0.9}\&times;\frac{<\&dtri;{\mathrm{\&Phi;}}_i\&CenterDot;\&dtri;{\mathrm{\&Phi;}}_i>}{<\&dtri;{\mathrm{\&Phi;}}_i\&CenterDot;\&dtri;{\mathrm{\&Psi;}}_i>})$

Step (4.8), solving equation:

$(C_x+{\stackrel{\&CenterDot;}{C}}_x+{\stackrel{\&CenterDot;}{Q}}_x)\mathrm{\&Delta;x}=-({\stackrel{\&CenterDot;}{C}}_x{\mathrm{\&Phi;}}_x+\mathrm{\&beta;}\&CenterDot;\mathrm{\&gamma;}\&CenterDot;{\mathrm{\&Psi;}}_x)$

$(C_y+{\stackrel{\&CenterDot;}{C}}_y+{\stackrel{\&CenterDot;}{Q}}_y)\mathrm{\&Delta;y}=-({\stackrel{\&CenterDot;}{C}}_y{\mathrm{\&Phi;}}_y+\mathrm{\&beta;}\&CenterDot;\mathrm{\&gamma;}\&CenterDot;{\mathrm{\&Psi;}}_y)$

Obtain new position, unit.Above-mentioned equation remains a system of linear equations, and that matrix of coefficients has equally is sparse, the character of positive definite, symmetry, therefore uses the method for ICCG to find the solution.Layout result when Figure 6 shows that the 15 iteration, figure blue arrow is represented the displacing force that the unit is suffered.

Step (4.9), parameter control:

At first calculate adjustment factor κ and (get μ according to following formula_T=1)

κ(μ)＝1+tanh(ln(μ_T/μ))

$\mathrm{\&mu;}=\frac{1}{m}\underset{i=1}{\overset{m}{\mathrm{\&Sigma;}}}\sqrt{\mathrm{\&Delta;}{x}^2+\mathrm{\&Delta;}{\mathrm{<figure-callout\; label="y"\; filenames="HSA00000165093800032.png,HSA00000165093800041.png"\; state="\{\{state\}\}">y</figure-callout>}}^2}$

New parameter matrix is set then

$\stackrel{\&CenterDot;}{P}\&LeftArrow;\mathrm{\&kappa;}\left(\mathrm{\&mu;}\right)\&CenterDot;\stackrel{\&CenterDot;}{P}---\left(5\right)$

$\stackrel{\&CenterDot;}{Q}\&LeftArrow;\mathrm{\&kappa;}\left(\mathrm{\&mu;}\right)\&CenterDot;\stackrel{\&CenterDot;}{Q}$

Repeating step (4.1)-(4.9) are no more than 10% up to Duplication, and the result after total arrangement finishes as shown in Figure 7.

Step (5) is carried out layout and is legalized

The process that legalizes mainly is each unit is corresponded to the cell row at its place, eliminates the small dislocation on the vertical direction, simultaneously overlapping the and blank on the elimination of level direction.Here (METHOD FOR LEGALIZING THE PLACEMENT OF CELLSIN AN INTEGRATED CIRCUIT LAYOUT, 2006.8.8) the middle algorithm of describing is realized to use patent US7089521B2.After layout legalizes, export the geometric position of each unit.Result after layout legalizes as shown in Figure 8.

Step (6) is added decoupling capacitance to the layout after legalizing

Add decoupling capacitor at the supply node place of power ground network, this is one of the main target that will optimize of the present invention.According to article (Dharchoudhury A, Panda R, Blaauw D, et al.Design andanalysis of power distribution networks in PowerPC microprocessors.Proceedingsof Design Automation Conference, 1998.738-743.) in method, carry out the interpolation of decoupling capacitor, till satisfying the voltage drop constraint, the total amount of decoupling capacitance is added in output.

The algorithm application that the present invention is proposed is in the daiTest1 circuit layout, and the decoupling capacitance total amount that needs at last to add is 358.287pf, and to the layout result of classic method, needing to add the decoupling capacitance total amount be 639.977pf.By contrast, the layout result that the present invention produced has reduced by 44.02% decoupling capacitance amount.Simultaneously, the layout result line length that produces among the present invention is that the line length 0.0860957m of 0.0858811m and conventional in layout method is more or less the same.

This algorithm realizes on the Linux server of internal memory 8G and operation that at CPU 2.33G all code utilizes C Plus Plus and Matlab hybrid programming to realize.

Claims (1)

Translated fromChinese

1.使用去耦合电容抑制集成电路供电网络噪声的方法，其特征在于，是在计算机中依次按如下步骤实现的：1. use decoupling capacitance to suppress the method for integrated circuit power supply network noise, it is characterized in that, is to realize by following steps successively in computer:步骤(1)，计算机读入包含电源地线网络设计参数和单元布局设计参数的文件，电源地线网络设计参数包括：电源地线的位置和线宽度，供电引脚Pin的位置；根据电源地线网络的位置和宽度确定其上节点之间的关联结构、节点之间的初始电阻值、电容值、以及单元电流源模型，即各个单元对应的随时间变化的吸纳电流波形，用PWL表示；据此在计算机内建立电源地线网络的电路模型；所述单元布局设计参数包括：每个单元的尺寸、单元上引脚的偏移量、单元放置的初始位置、单元的方向、布局的区域、单元行的位置以及单元是否可以移动；Step (1), the computer reads in the file containing the design parameters of the power supply ground network and the unit layout design parameters. The design parameters of the power supply ground network include: the position and line width of the power supply ground wire, the position of the power supply pin Pin; The position and width of the line network determine the correlation structure between nodes, the initial resistance value, capacitance value between nodes, and the unit current source model, that is, the time-varying absorbing current waveform corresponding to each unit, represented by PWL; Accordingly, the circuit model of the power ground network is established in the computer; the unit layout design parameters include: the size of each unit, the offset of the pins on the unit, the initial position of the unit placement, the direction of the unit, and the area of the layout , the position of the cell row and whether the cell can be moved;步骤(2)，对电源地线网络进行静态分析，如果静态电压降不满足要求，则对电源地线网络进行整体的线宽调整，使得直流电压降满足设计要求，以此作为下一步添加去耦合电容进行瞬态电压降消除的基本条件；Step (2), conduct static analysis on the power supply ground network, if the static voltage drop does not meet the requirements, then adjust the overall line width of the power supply ground network, so that the DC voltage drop meets the design requirements, and add it as the next step The basic conditions for the coupling capacitor to eliminate the transient voltage drop;步骤(3)，对布局进行初始化，首先将所有可以移动的单元放置到布局区域的中心位置，然后重复下面的初始化步骤(3.1)-(3.3)五次；Step (3), initialize the layout, first place all movable units in the center of the layout area, and then repeat the following initialization steps (3.1)-(3.3) five times;步骤(3.1)，使用边界框线长模型得到线长的二次表达式：Step (3.1), use the bounding box line length model to obtain the quadratic expression of the line length:${\mathrm{<span><span>\&Gamma;</span>\&Gamma;</span>}}_{\mathrm{<span><span>x</span>x</span>}}<span><span>=</span>=</span>\frac{\mathrm{<span><span>1</span>1</span>}}{\mathrm{<span><span>2</span>2</span>}}{\mathrm{<span><span>x</span>x</span>}}^{\mathrm{<span><span>T</span>T</span>}}{\mathrm{<span><span>C</span>C</span>}}_{\mathrm{<span><span>x</span>x</span>}}\mathrm{<span><span>x</span>x</span>}<span><span>+</span>+</span>{\mathrm{<span><span>d</span>d</span>}}_{\mathrm{<span><span>x</span>x</span>}}^{\mathrm{<span><span>T</span>T</span>}}\mathrm{<span><span>x</span>x</span>}<span><span>+</span>+</span>\mathrm{<span><span>const</span>const</span>}\mathrm{<span><span>1</span>1</span>}$${\mathrm{<span><span>\&Gamma;</span>\&Gamma;</span>}}_{\mathrm{<span><span>y</span>the\; y</span>}}<span><span>=</span>=</span>\frac{\mathrm{<span><span>1</span>1</span>}}{\mathrm{<span><span>2</span>2</span>}}{\mathrm{<span><span>y</span>the\; y</span>}}^{\mathrm{<span><span>T</span>T</span>}}{\mathrm{<span><span>C</span>C</span>}}_{\mathrm{<span><span>y</span>the\; y</span>}}\mathrm{<span><span>y</span>the\; y</span>}<span><span>+</span>+</span>{\mathrm{<span><span>d</span>d</span>}}_{\mathrm{<span><span>y</span>the\; y</span>}}^{\mathrm{<span><span>T</span>T</span>}}\mathrm{<span><span>y</span>the\; y</span>}<span><span>+</span>+</span>\mathrm{<span><span>const</span>const</span>}\mathrm{<span><span>2</span>2</span>}$其中：in:Γ_x和Γ_y分别是X轴方向和Y轴方向的半周长线长，Γ_x and Γ_y are the half-perimeter line lengths in the X-axis direction and the Y-axis direction, respectively,x表示笛卡尔坐标系中各个单元中心在X轴方向上构成的向量，x represents the vector formed by the center of each unit in the X-axis direction in the Cartesian coordinate system,y表示笛卡尔坐标系中各个单元中心在X轴方向上构成的向量，y represents the vector formed by the center of each unit in the X-axis direction in the Cartesian coordinate system,(x，y)表示单元所处的位置，(x, y) indicates the location of the unit,d_x是一个向量，表示可移动单元与固定单元之间在X轴方向上的连接关系，如果它们有连接关系，则它们在d_x中相应位置的元素为1，否则为0，d_x is a vector, which represents the connection relationship between the movable unit and the fixed unit in the X-axis direction. If they have a connection relationship, the elements at their corresponding positions in d_x are 1, otherwise they are 0.d_y是一个向量，表示可移动单元与固定单元之间在Y轴方向上的连接关系，如果它们有连接关系，则它们在d_y中相应位置的元素为1，否则为0，d_y is a vector, which represents the connection relationship between the movable unit and the fixed unit in the direction of the Y axis. If they have a connection relationship, the elements at their corresponding positions in d_y are 1, otherwise they are 0.C_x是一个半正定对的称矩阵，用来表示可移动单元之间在X轴方向上的连接关系，如果两个可移动单元之间有连接关系，则它们在C_x中相应位置的元素为1，否则为0，C_x is a symmetric matrix of positive semi-definite pairs, which is used to represent the connection relationship between the movable units in the X-axis direction. If there is a connection relationship between two movable units, the elements at their corresponding positions in C_x is 1, otherwise it is 0,C_y是一个半正定对的称矩阵，用来表示可移动单元之间在Y轴方向上的连接关系，如果两个可移动单元之间有连接关系，则它们在C_y中相应位置的元素为1，否则为0，C_y is a symmetric matrix of a positive semi-definite pair, which is used to represent the connection relationship between the movable units in the Y-axis direction. If there is a connection relationship between two movable units, the elements at their corresponding positions in C_y is 1, otherwise it is 0,const1表示X方向的线长常数项，const1 represents the line length constant item in the X direction,const2表示Y方向的线长常数项，const2 represents the line length constant item in the Y direction,边界框线长模型是指包含线网所有顶点的一个最小矩形，其周长可表示为The bounding box line length model refers to a minimum rectangle that contains all the vertices of the line network, and its perimeter can be expressed asL_n＝2(x_max-x_min+y_max-y_min)L_n ＝2(x_max -x_min +y_max -y_min )其中(x_min，y_min)是该矩形框左下角的顶点坐标，(x_max，y_max)是其右上角的顶点坐标；Wherein (x_min , y_min ) is the vertex coordinates of the lower left corner of the rectangle, (x_max , y_max ) is the vertex coordinates of the upper right corner;步骤(3.2)，分别求解关于x和y的线性方程组：Step (3.2), solve the linear equations about x and y respectively:C_xx＝d_xC_x x = d_xC_yy＝d_yC_y y = d_y该方程是两个线性方程组，系数矩阵具有稀疏、正定、对称的性质，使用ICCG的方法求解，得到x和y；The equation is a system of two linear equations, the coefficient matrix has the properties of sparse, positive definite, and symmetric, and it is solved by ICCG method to obtain x and y;步骤(3.3)，根据步骤(3.2)得到的x和y，令x′＝x和y′＝y，改变单元的新位置为(x′，y′)；Step (3.3), according to x and y that step (3.2) obtains, make x'=x and y'=y, change the new position of unit to be (x', y');步骤(4)，进行添加去耦合电容的总体布局；Step (4), carry out the overall layout of adding decoupling capacitor;步骤(4.1)，初始化权重参数和权重矩阵：Step (4.1), initialize weight parameters and weight matrix:步骤(4.1.1)，初始化权重参数βStep (4.1.1), initialize the weight parameter β$\mathrm{<span><span>\&beta;</span>\&beta;</span>}<span><span>=</span>=</span>\frac{\mathrm{<span><span>2</span>2</span>}}{{\mathrm{<span><span>V</span>V</span>}}_{\mathrm{<span><span>dd</span>dd</span>}}<span><span>-</span>-</span>{\mathrm{<span><span>V</span>V</span>}}_{\mathrm{<span><span>thre</span>there</span>}}}$其中V_dd是电源电压，V_thre是用户指定的电压降阈值；where_Vdd is the supply voltage and_Vthre is the user-specified voltage drop threshold;步骤(4.1.2)，初始化权重矩阵

Step (4.1.2), initialize the weight matrix

其中

是布局质量控制权重参数矩阵，由每个单元的面积参数A_i计算得到，m表示单元的总数量，i＝1，2，...，m；in

is the layout quality control weight parameter matrix, calculated from the area parameter A_i of each unit, m represents the total number of units, i=1, 2, ..., m;步骤(4.1.3)，初始化电量权重矩阵Step (4.1.3), initialize the power weight matrix

其中为时间t内电量权重系数矩阵，由每个单元的吸纳电量J_i对时间t的积分计算得到；in is the power weight coefficient matrix within time t, which is calculated by integrating the absorbed power J_i of each unit with respect to time t;步骤(4.2)，计算单元的重叠率Ω，重叠包括单元交叠和单元重合两种情况，重叠率的含义是发生重叠的单元数量占总单元数量的百分比，如果重叠率小于10％，则布局结束，否则重复以下步骤；Step (4.2), calculate the overlap rate Ω of the unit, overlap includes two cases of unit overlap and unit overlap, the meaning of the overlap rate is the percentage of the number of overlapping units in the total number of units, if the overlap rate is less than 10%, the layout End, otherwise repeat the following steps;步骤(4.3)，计算单元的分布密度函数和

Step (4.3), calculate the distribution density function of the unit and

步骤(4.3.1)，计算目标单元分布密度函数

Step (4.3.1), calculate the target unit distribution density function

${\mathrm{<span><span>D</span>D.</span>}}_{\mathrm{<span><span>mod</span>mod</span>}}^{\mathrm{<span><span>sup</span>sup</span>}}<span><span>(</span>(</span>\mathrm{<span><span>x</span>x</span>}<span><span>,</span>,</span>\mathrm{<span><span>y</span>the\; y</span>}<span><span>)</span>)</span><span><span>=</span>=</span>\frac{\underset{\mathrm{<span><span>i</span>i</span>}<span><span>=</span>=</span>\mathrm{<span><span>1</span>1</span>}}{\overset{\mathrm{<span><span>m</span>m</span>}}{\mathrm{<span><span>\&Sigma;</span>\&Sigma;</span>}}}{\mathrm{<span><span>A</span>A</span>}}_{\mathrm{<span><span>i</span>i</span>}}}{{\mathrm{<span><span>A</span>A</span>}}_{\mathrm{<span><span>chip</span>chip</span>}}}$目标单元分布密度函数即在完成布局后期望得到的单元分布密度函数，其中：A_chip表示整个芯片的面积，A_i表示各单元的面积；target unit distribution density function That is, the cell distribution density function expected to be obtained after the layout is completed, where: A_chip represents the area of the entire chip, and A_i represents the area of each cell;步骤(4.3.2)，计算当前布局中单元分布的密度函数Step (4.3.2), calculate the density function of the cell distribution in the current layout为了计算

这里引入一个矩形窗函数to calculate

Here introduces a rectangular window function

表示了是否选择当前单元，其中(x，y)表示当前单元位置，(x_ll，y_ll)表示矩形的左下角顶点的坐标，(w，h)是该矩形的宽度和高度；如果记当前单元中心位置为当前单元的宽度和高度为(w_i，h_i)，则对应于上述矩形窗函数下式成立：Indicates whether to select the current unit, where (x, y) indicates the position of the current unit, (x_ll , y_ll ) indicates the coordinates of the lower left vertex of the rectangle, (w, h) is the width and height of the rectangle; if the current The center of the unit is The width and height of the current unit are (w_i , h_i ), then the following equation is established corresponding to the above rectangular window function:${\mathrm{<span><span>x</span>x</span>}}_{\mathrm{<span><span>ll</span>ll</span>}}<span><span>=</span>=</span>{\mathrm{<span><span>x</span>x</span>}}_{\mathrm{<span><span>i</span>i</span>}}^{<span><span>\&prime;</span>\&prime;</span>}<span><span>-</span>-</span>\frac{{\mathrm{<span><span>w</span>w</span>}}_{\mathrm{<span><span>i</span>i</span>}}}{\mathrm{<span><span>2</span>2</span>}}$${\mathrm{<span><span>y</span>the\; y</span>}}_{\mathrm{<span><span>ll</span>ll</span>}}<span><span>=</span>=</span>{\mathrm{<span><span>y</span>the\; y</span>}}_{\mathrm{<span><span>i</span>i</span>}}^{<span><span>\&prime;</span>\&prime;</span>}<span><span>-</span>-</span>\frac{{\mathrm{<span><span>h</span>h</span>}}_{\mathrm{<span><span>i</span>i</span>}}}{\mathrm{<span><span>2</span>2</span>}}$这时单元分布的密度函数可由下式计算：Then the density function of the unit distribution It can be calculated by the following formula:${\mathrm{<span><span>D</span>D.</span>}}_{\mathrm{<span><span>mod</span>mod</span>}}^{\mathrm{<span><span>dem</span>dem</span>}}<span><span>(</span>(</span>\mathrm{<span><span>x</span>x</span>}<span><span>,</span>,</span>\mathrm{<span><span>y</span>the\; y</span>}<span><span>)</span>)</span><span><span>=</span>=</span>\underset{\mathrm{<span><span>i</span>i</span>}<span><span>=</span>=</span>\mathrm{<span><span>1</span>1</span>}}{\overset{\mathrm{<span><span>m</span>m</span>}}{\mathrm{<span><span>\&Sigma;</span>\&Sigma;</span>}}}{\mathrm{<span><span>d</span>d</span>}}_{\mathrm{<span><span>mod</span>mod</span>}<span><span>,</span>,</span>\mathrm{<span><span>i</span>i</span>}}<span><span>\&CenterDot;</span>\&Center\; Dot;</span>\mathrm{<span><span>R</span>R</span>}<span><span>(</span>(</span>\mathrm{<span><span>x</span>x</span>}<span><span>,</span>,</span>\mathrm{<span><span>y</span>the\; y</span>}<span><span>,</span>,</span>{\mathrm{<span><span>x</span>x</span>}}_{\mathrm{<span><span>i</span>i</span>}}^{<span><span>\&prime;</span>\&prime;</span>}<span><span>-</span>-</span>\frac{{\mathrm{<span><span>w</span>w</span>}}_{\mathrm{<span><span>i</span>i</span>}}}{\mathrm{<span><span>2</span>2</span>}}<span><span>,</span>,</span>{\mathrm{<span><span>y</span>the\; y</span>}}_{\mathrm{<span><span>i</span>i</span>}}^{<span><span>\&prime;</span>\&prime;</span>}<span><span>-</span>-</span>\frac{{\mathrm{<span><span>h</span>h</span>}}_{\mathrm{<span><span>i</span>i</span>}}}{\mathrm{<span><span>2</span>2</span>}}<span><span>,</span>,</span>{\mathrm{<span><span>w</span>w</span>}}_{\mathrm{<span><span>i</span>i</span>}}<span><span>,</span>,</span>{\mathrm{<span><span>h</span>h</span>}}_{\mathrm{<span><span>i</span>i</span>}}<span><span>)</span>)</span>$其中d_mod，i表示单元i的密度，简单情况下设置为1；where d_{mod, i} represents the density of unit i, which is set to 1 in simple cases;步骤(4.4)，求解描述单元分布的供需系统的泊松方程，得到势能函数Φ(x，y)，泊松方程是形如

的椭圆偏微分方程，供需系统描述成泊松方程如下：Step (4.4), solving the Poisson equation describing the supply and demand system of unit distribution, and obtaining the potential energy function Φ(x, y), the Poisson equation is in the form of

The elliptic partial differential equation, the supply and demand system is described as a Poisson equation as follows:$<span><span>(</span>(</span>\frac{{<span><span>\&PartialD;</span>\&PartialD;</span>}^{\mathrm{<span><span>2</span>2</span>}}}{{<span><span>\&PartialD;</span>\&PartialD;</span>\mathrm{<span><span>x</span>x</span>}}^{\mathrm{<span><span>2</span>2</span>}}}<span><span>+</span>+</span>\frac{{<span><span>\&PartialD;</span>\&PartialD;</span>}^{\mathrm{<span><span>2</span>2</span>}}}{{<span><span>\&PartialD;</span>\&PartialD;</span>\mathrm{<span><span>y</span>the\; y</span>}}^{\mathrm{<span><span>2</span>2</span>}}}<span><span>)</span>)</span>\mathrm{<span><span>\&Phi;</span>\&Phi;</span>}<span><span>(</span>(</span>\mathrm{<span><span>x</span>x</span>}<span><span>,</span>,</span>\mathrm{<span><span>y</span>the\; y</span>}<span><span>)</span>)</span><span><span>=</span>=</span>{\mathrm{<span><span>D</span>D.</span>}}_{\mathrm{<span><span>mod</span>mod</span>}}^{\mathrm{<span><span>sup</span>sup</span>}}<span><span>(</span>(</span>\mathrm{<span><span>x</span>x</span>}<span><span>,</span>,</span>\mathrm{<span><span>y</span>the\; y</span>}<span><span>)</span>)</span><span><span>-</span>-</span>{\mathrm{<span><span>D</span>D.</span>}}_{\mathrm{<span><span>mod</span>mod</span>}}^{\mathrm{<span><span>dem</span>dem</span>}}<span><span>(</span>(</span>\mathrm{<span><span>x</span>x</span>}<span><span>,</span>,</span>\mathrm{<span><span>y</span>the\; y</span>}<span><span>)</span>)</span>$满足纽曼边界条件Satisfy the Newman boundary condition其中n表示定义域边界上的法向量；where n represents the normal vector on the boundary of the domain of definition;步骤(4.5)，计算芯片上电密度函数W(x，y)和L(x，y)Step (4.5), calculate the on-chip electric density function W(x, y) and L(x, y)步骤(4.5.1)，利用宏模型的方法，将电源地线网络电路方程

化成如下形式：In step (4.5.1), using the macro model method, the circuit equation of the power ground wire network

into the following form:$\left(\begin{array}{cc}{\mathrm{<span><span>G</span>G</span>}}_{\mathrm{<span><span>11</span>11</span>}}& {\mathrm{<span><span>G</span>G</span>}}_{\mathrm{<span><span>12</span>12</span>}}\\ {\mathrm{<span><span>G</span>G</span>}}_{\mathrm{<span><span>12</span>12</span>}}^{\mathrm{<span><span>T</span>T</span>}}& {\mathrm{<span><span>G</span>G</span>}}_{\mathrm{<span><span>22</span>twenty\; two</span>}}\end{array}\right)<span><span>\&CenterDot;</span>\&CenterDot;</span>\left(\begin{array}{c}{<span><span>\&Integral;</span>\&Integral;</span>}_{{\mathrm{<span><span>t</span>t</span>}}_{\mathrm{<span><span>0</span>0</span>}}}^{{\mathrm{<span><span>t</span>t</span>}}_{\mathrm{<span><span>1</span>1</span>}}}{\mathrm{<span><span>V</span>V</span>}}_{\mathrm{<span><span>1</span>1</span>}\mathrm{<span><span>s</span>the\; s</span>}}\mathrm{<span><span>dt</span>dt</span>}\\ {<span><span>\&Integral;</span>\&Integral;</span>}_{{\mathrm{<span><span>t</span>t</span>}}_{\mathrm{<span><span>0</span>0</span>}}}^{{\mathrm{<span><span>t</span>t</span>}}_{\mathrm{<span><span>1</span>1</span>}}}{\mathrm{<span><span>V</span>V</span>}}_{\mathrm{<span><span>2</span>2</span>}\mathrm{<span><span>s</span>the\; s</span>}}\mathrm{<span><span>dt</span>dt</span>}\end{array}\right)<span><span>=</span>=</span>\left(\begin{array}{c}{<span><span>\&Integral;</span>\&Integral;</span>}_{{\mathrm{<span><span>t</span>t</span>}}_{\mathrm{<span><span>0</span>0</span>}}}^{{\mathrm{<span><span>t</span>t</span>}}_{\mathrm{<span><span>1</span>1</span>}}}{\mathrm{<span><span>J</span>J</span>}}_{\mathrm{<span><span>1</span>1</span>}}\mathrm{<span><span>dt</span>dt</span>}\\ {<span><span>\&Integral;</span>\&Integral;</span>}_{{\mathrm{<span><span>t</span>t</span>}}_{\mathrm{<span><span>0</span>0</span>}}}^{{\mathrm{<span><span>t</span>t</span>}}_{\mathrm{<span><span>1</span>1</span>}}}{\mathrm{<span><span>J</span>J</span>}}_{\mathrm{<span><span>2</span>2</span>}}\mathrm{<span><span>dt</span>dt</span>}<span><span>+</span>+</span>{<span><span>\&Integral;</span>\&Integral;</span>}_{{\mathrm{<span><span>t</span>t</span>}}_{\mathrm{<span><span>0</span>0</span>}}}^{{\mathrm{<span><span>t</span>t</span>}}_{\mathrm{<span><span>1</span>1</span>}}}\mathrm{<span><span>Idt</span>Idt</span>}\end{array}\right)$其中：in:C表示供电网络节点电容矩阵，C represents the node capacitance matrix of the power supply network,G表示节点电导矩阵，G represents the node conductance matrix,V表示节点电压矩阵，V represents the node voltage matrix,J表示节点吸纳电流矩阵，J represents the node absorbing current matrix,V_2s是需要添加去耦合电容的节点电压向量，V_2s is the node voltage vector that needs to add decoupling capacitors,V_1s为供电网络内部节点电压向量，V_1s is the internal node voltage vector of the power supply network,J₁为供电网络内部节点吸纳电流向量，J₁ is the current vector absorbed by the internal nodes of the power supply network,J₂为供电网络边缘节点的吸纳电流向量，J₂ is the sink current vector of the edge node of the power supply network,I为供电焊盘Pad的供电电流向量，I is the supply current vector of the power supply pad Pad,G₁₁为供电网络内部节点的电导向量，G₁₁ is the conductance vector of internal nodes of the power supply network,G₁₂为供电网络内部节点与供电焊盘Pad之间的电导矩阵，G₁₂ is the conductance matrix between the internal nodes of the power supply network and the power supply pad Pad,G₂₂为供电焊盘Pad的电导矩阵；G₂₂ is the conductance matrix of the power supply pad Pad;步骤(4.5.2)，按照以下步骤，计算耗电密度函数W(x，y)和供电密度函数L(x，y)：In step (4.5.2), calculate power consumption density function W(x, y) and power supply density function L(x, y) according to the following steps:步骤(4.5.2.1)，计算电压波形积分

同时有下式成立Step (4.5.2.1), calculate the integral of the voltage waveform

At the same time, the following formula is establishedW＝-B^T·H^-1W＝-B^T H^-1其中

表示电源地线网络的导纳矩阵，

表示负载电流源的等效电量；in

represents the admittance matrix of the power ground network,

Indicates the equivalent power of the load current source;步骤(4.5.2.2)，在T＝(t1-t₀)/2时间内计算供电密度函数LStep (4.5.2.2), calculate the power supply density function L within T=(t1-t₀ )/2 time$\mathrm{<span><span>L</span>L</span>}<span><span>=</span>=</span>\left(\begin{array}{c}<span><span>(</span>(</span>{\mathrm{<span><span>V</span>V</span>}}_{\mathrm{<span><span>thre</span>there</span>}}<span><span>+</span>+</span>{\mathrm{<span><span>V</span>V</span>}}_{\mathrm{<span><span>1</span>1</span>}}<span><span>(</span>(</span>{\mathrm{<span><span>t</span>t</span>}}_{\mathrm{<span><span>0</span>0</span>}}<span><span>)</span>)</span><span><span>)</span>)</span><span><span>\&CenterDot;</span>\&Center\; Dot;</span>\mathrm{<span><span>T</span>T</span>}\\ <span><span>(</span>(</span>{\mathrm{<span><span>V</span>V</span>}}_{\mathrm{<span><span>thre</span>there</span>}}<span><span>+</span>+</span>{\mathrm{<span><span>V</span>V</span>}}_{\mathrm{<span><span>2</span>2</span>}}<span><span>(</span>(</span>{\mathrm{<span><span>t</span>t</span>}}_{\mathrm{<span><span>0</span>0</span>}}<span><span>)</span>)</span><span><span>)</span>)</span><span><span>\&CenterDot;</span>\&CenterDot;</span>\mathrm{<span><span>T</span>T</span>}\\ <span><span>.</span>.</span>\\ <span><span>.</span>.</span>\\ <span><span>.</span>.</span>\\ <span><span>(</span>(</span>{\mathrm{<span><span>V</span>V</span>}}_{\mathrm{<span><span>thre</span>there</span>}}<span><span>+</span>+</span>{\mathrm{<span><span>V</span>V</span>}}_{\mathrm{<span><span>m</span>m</span>}}<span><span>(</span>(</span>{\mathrm{<span><span>t</span>t</span>}}_{\mathrm{<span><span>0</span>0</span>}}<span><span>)</span>)</span><span><span>)</span>)</span><span><span>\&CenterDot;</span>\&Center\; Dot;</span>\mathrm{<span><span>T</span>T</span>}\end{array}\right)$其中V_i(t₀)为t₀时刻单元i的电压向量；Where V_i (t₀ ) is the voltage vector of unit i at time t₀ ;步骤(4.5.2.3)，利用步骤(4.5.2.1)和(4.5.2.1)中得到的W和L，采用拉格朗日插值的方法在布局平面上进行插值，得到耗电密度函数W(x，y)和供电密度函数L(x，y)；In step (4.5.2.3), use W and L obtained in steps (4.5.2.1) and (4.5.2.1), and use Lagrangian interpolation method to perform interpolation on the layout plane to obtain the power consumption density function W(x , y) and supply density function L(x, y);步骤(4.6)，求解通过添加去耦合电容来达到供需系统平衡的泊松方程，得到势能函数Ψ(x，y)Step (4.6), solving the Poisson equation that achieves the balance of the supply and demand system by adding decoupling capacitors, and obtaining the potential energy function Ψ(x, y)$<span><span>(</span>(</span>\frac{{<span><span>\&PartialD;</span>\&PartialD;</span>}^{\mathrm{<span><span>2</span>2</span>}}}{<span><span>\&PartialD;</span>\&PartialD;</span>{\mathrm{<span><span>x</span>x</span>}}^{\mathrm{<span><span>2</span>2</span>}}}<span><span>+</span>+</span>\frac{{<span><span>\&PartialD;</span>\&PartialD;</span>}^{\mathrm{<span><span>2</span>2</span>}}}{{<span><span>\&PartialD;</span>\&PartialD;</span>\mathrm{<span><span>y</span>the\; y</span>}}^{\mathrm{<span><span>2</span>2</span>}}}<span><span>)</span>)</span>\mathrm{<span><span>\&Psi;</span>\&Psi;</span>}<span><span>(</span>(</span>\mathrm{<span><span>x</span>x</span>}<span><span>,</span>,</span>\mathrm{<span><span>y</span>the\; y</span>}<span><span>)</span>)</span><span><span>=</span>=</span>\mathrm{<span><span>L</span>L</span>}<span><span>(</span>(</span>\mathrm{<span><span>x</span>x</span>}<span><span>,</span>,</span>\mathrm{<span><span>y</span>the\; y</span>}<span><span>)</span>)</span><span><span>-</span>-</span>\mathrm{<span><span>W</span>W</span>}<span><span>(</span>(</span>\mathrm{<span><span>x</span>x</span>}<span><span>,</span>,</span>\mathrm{<span><span>y</span>the\; y</span>}<span><span>)</span>)</span>$满足纽曼边界条件

Satisfy the Newman boundary condition

对供需函数进行正交化之后求解供需系统的泊松方程，以便于添加去耦合电容使得供需系统达到平衡，

表示正交化的供电密度函数，

表示正交化的耗电密度函数After orthogonalizing the supply and demand function, solve the Poisson equation of the supply and demand system in order to add decoupling capacitors to make the supply and demand system reach equilibrium.

Represents the orthogonalized supply density function,

Represents the orthogonalized power consumption density function$\stackrel{<span><span>~</span>~</span>}{\mathrm{<span><span>L</span>L</span>}}<span><span>(</span>(</span>\mathrm{<span><span>x</span>x</span>}<span><span>,</span>,</span>\mathrm{<span><span>y</span>the\; y</span>}<span><span>)</span>)</span><span><span>=</span>=</span>\mathrm{<span><span>L</span>L</span>}<span><span>(</span>(</span>\mathrm{<span><span>x</span>x</span>}<span><span>,</span>,</span>\mathrm{<span><span>y</span>the\; y</span>}<span><span>)</span>)</span><span><span>-</span>-</span><span><span>\&Integral;</span>\&Integral;</span><span><span>\&Integral;</span>\&Integral;</span>\mathrm{<span><span>Ldxdy</span>Ldxdy</span>}$$\stackrel{<span><span>~</span>~</span>}{\mathrm{<span><span>W</span>W</span>}}<span><span>(</span>(</span>\mathrm{<span><span>x</span>x</span>}<span><span>,</span>,</span>\mathrm{<span><span>y</span>the\; y</span>}<span><span>)</span>)</span><span><span>=</span>=</span>\mathrm{<span><span>W</span>W</span>}<span><span>(</span>(</span>\mathrm{<span><span>x</span>x</span>}<span><span>,</span>,</span>\mathrm{<span><span>y</span>the\; y</span>}<span><span>)</span>)</span><span><span>-</span>-</span><span><span>\&Integral;</span>\&Integral;</span><span><span>\&Integral;</span>\&Integral;</span>\mathrm{<span><span>Wdxdy</span>wxya</span>}$步骤(4.7)，根据步骤(3.3)的结果，使用边界框线长模型得到当前线长的二次表达式：Step (4.7), according to the result of step (3.3), use the bounding box line length model to obtain the quadratic expression of the current line length:${\mathrm{<span><span>\&Gamma;</span>\&Gamma;</span>}}_{\mathrm{<span><span>x</span>x</span>}}<span><span>=</span>=</span>\frac{\mathrm{<span><span>1</span>1</span>}}{\mathrm{<span><span>2</span>2</span>}}{\mathrm{<span><span>x</span>x</span>}}^{\mathrm{<span><span>T</span>T</span>}}{\mathrm{<span><span>C</span>C</span>}}_{\mathrm{<span><span>x</span>x</span>}}{\mathrm{<span><span>x</span>x</span>}}^{<span><span>\&prime;</span>\&prime;</span>}<span><span>+</span>+</span>{\mathrm{<span><span>d</span>d</span>}}_{\mathrm{<span><span>x</span>x</span>}}^{\mathrm{<span><span>T</span>T</span>}}{\mathrm{<span><span>x</span>x</span>}}^{<span><span>\&prime;</span>\&prime;</span>}<span><span>+</span>+</span>\mathrm{<span><span>const</span>const</span>}\mathrm{<span><span>1</span>1</span>}$${\mathrm{<span><span>\&Gamma;</span>\&Gamma;</span>}}_{\mathrm{<span><span>y</span>the\; y</span>}}<span><span>=</span>=</span>\frac{\mathrm{<span><span>1</span>1</span>}}{\mathrm{<span><span>2</span>2</span>}}{\mathrm{<span><span>y</span>the\; y</span>}}^{\mathrm{<span><span>T</span>T</span>}}{\mathrm{<span><span>C</span>C</span>}}_{\mathrm{<span><span>y</span>the\; y</span>}}{\mathrm{<span><span>y</span>the\; y</span>}}^{<span><span>\&prime;</span>\&prime;</span>}<span><span>+</span>+</span>{\mathrm{<span><span>d</span>d</span>}}_{\mathrm{<span><span>y</span>the\; y</span>}}^{\mathrm{<span><span>T</span>T</span>}}{\mathrm{<span><span>y</span>the\; y</span>}}^{<span><span>\&prime;</span>\&prime;</span>}<span><span>+</span>+</span>\mathrm{<span><span>const</span>const</span>}\mathrm{<span><span>2</span>2</span>}$步骤(4.8)，利用差分方法，将连续变量问题转化为离散变量问题以便于数值求解，得到势能函数Φ(x，y)和Ψ(x，y)的梯度函数：In step (4.8), using the difference method, the continuous variable problem is transformed into a discrete variable problem for numerical solution, and the gradient functions of the potential energy functions Φ(x, y) and Ψ(x, y) are obtained:${\mathrm{<span><span>\&Phi;</span>\&Phi;</span>}}_{\mathrm{<span><span>x</span>x</span>}}<span><span>=</span>=</span>\frac{<span><span>\&PartialD;</span>\&PartialD;</span>\mathrm{<span><span>\&Phi;</span>\&Phi;</span>}<span><span>(</span>(</span>\mathrm{<span><span>x</span>x</span>}<span><span>,</span>,</span>\mathrm{<span><span>y</span>the\; y</span>}<span><span>)</span>)</span>}{<span><span>\&PartialD;</span>\&PartialD;</span>\mathrm{<span><span>x</span>x</span>}}<span><span>,</span>,</span>$${\mathrm{<span><span>\&Phi;</span>\&Phi;</span>}}_{\mathrm{<span><span>y</span>the\; y</span>}}<span><span>=</span>=</span>\frac{<span><span>\&PartialD;</span>\&PartialD;</span>\mathrm{<span><span>\&Phi;</span>\&Phi;</span>}<span><span>(</span>(</span>\mathrm{<span><span>x</span>x</span>}<span><span>,</span>,</span>\mathrm{<span><span>y</span>the\; y</span>}<span><span>)</span>)</span>}{<span><span>\&PartialD;</span>\&PartialD;</span>\mathrm{<span><span>y</span>the\; y</span>}}$${\mathrm{<span><span>\&Psi;</span>\&Psi;</span>}}_{\mathrm{<span><span>x</span>x</span>}}<span><span>=</span>=</span>\frac{<span><span>\&PartialD;</span>\&PartialD;</span>\mathrm{<span><span>\&Psi;</span>\&Psi;</span>}<span><span>(</span>(</span>\mathrm{<span><span>x</span>x</span>}<span><span>,</span>,</span>\mathrm{<span><span>y</span>the\; y</span>}<span><span>)</span>)</span>}{<span><span>\&PartialD;</span>\&PartialD;</span>\mathrm{<span><span>x</span>x</span>}}<span><span>,</span>,</span>$${\mathrm{<span><span>\&Psi;</span>\&Psi;</span>}}_{\mathrm{<span><span>y</span>the\; y</span>}}<span><span>=</span>=</span>\frac{<span><span>\&PartialD;</span>\&PartialD;</span>\mathrm{<span><span>\&Psi;</span>\&Psi;</span>}<span><span>(</span>(</span>\mathrm{<span><span>x</span>x</span>}<span><span>,</span>,</span>\mathrm{<span><span>y</span>the\; y</span>}<span><span>)</span>)</span>}{<span><span>\&PartialD;</span>\&PartialD;</span>\mathrm{<span><span>y</span>the\; y</span>}}$并对Ψ_x，Ψ_y计算其对应的缩放因子γ以保证单元重叠能够被有效地消除：And calculate the corresponding scaling factor γ for Ψ_x , Ψ_y to ensure that unit overlap can be effectively eliminated:${\mathrm{<span><span>\&gamma;</span>\&gamma;</span>}}_{\mathrm{<span><span>i</span>i</span>}}<span><span>=</span>=</span>\mathrm{<span><span>min</span>min</span>}<span><span>(</span>(</span>\mathrm{<span><span>1,0.9</span>1,0.9</span>}<span><span>\&times;</span>\&times;</span>\frac{<span><span><</span><</span><span><span>\&dtri;</span>\&dtri;</span>{\mathrm{<span><span>\&Phi;</span>\&Phi;</span>}}_{\mathrm{<span><span>i</span>i</span>}}<span><span>\&CenterDot;</span>\&Center\; Dot;</span><span><span>\&dtri;</span>\&dtri;</span>{\mathrm{<span><span>\&Phi;</span>\&Phi;</span>}}_{\mathrm{<span><span>i</span>i</span>}}<span><span>></span>></span>}{<span><span><</span><</span><span><span>\&dtri;</span>\&dtri;</span>{\mathrm{<span><span>\&Phi;</span>\&Phi;</span>}}_{\mathrm{<span><span>i</span>i</span>}}<span><span>\&CenterDot;</span>\&CenterDot;</span><span><span>\&dtri;</span>\&dtri;</span>{\mathrm{<span><span>\&Psi;</span>\&Psi;</span>}}_{\mathrm{<span><span>i</span>i</span>}}<span><span>></span>></span>}<span><span>)</span>)</span>$其中i为单元编号，▽Φ_i，▽Ψ_i为势能函数Φ(x，y)和Ψ(x，y)在该单元中心位置处的梯度值，运算符<·>表示求两个向量的内积；Where i is the unit number, ▽Φ_i , ▽Ψ_i are the gradient values of the potential energy functions Φ(x, y) and Ψ(x, y) at the center of the unit, and the operator <·> means to find the two vectors Inner product;步骤(4.9)，利用力指向方法来调整布局位置，建立力平衡方程Step (4.9), use the force pointing method to adjust the layout position and establish the force balance equation${\mathrm{<span><span>F</span>f</span>}}_{\mathrm{<span><span>x</span>x</span>}}^{\mathrm{<span><span>net</span>net</span>}}<span><span>+</span>+</span>{\mathrm{<span><span>F</span>f</span>}}_{\mathrm{<span><span>x</span>x</span>}}^{\mathrm{<span><span>hold</span>hold</span>}}<span><span>+</span>+</span><span><span>(</span>(</span>{\mathrm{<span><span>F</span>f</span>}}_{\mathrm{<span><span>x</span>x</span>}}^{\mathrm{<span><span>move</span>move</span>}}<span><span>+</span>+</span>{\mathrm{<span><span>F</span>f</span>}}_{\mathrm{<span><span>x</span>x</span>}}^{\mathrm{<span><span>decap</span>decap</span>}}<span><span>)</span>)</span><span><span>=</span>=</span>\mathrm{<span><span>0</span>0</span>}$${\mathrm{<span><span>F</span>f</span>}}_{\mathrm{<span><span>y</span>the\; y</span>}}^{\mathrm{<span><span>net</span>net</span>}}<span><span>+</span>+</span>{\mathrm{<span><span>F</span>f</span>}}_{\mathrm{<span><span>y</span>the\; y</span>}}^{\mathrm{<span><span>hold</span>hold</span>}}<span><span>+</span>+</span><span><span>(</span>(</span>{\mathrm{<span><span>F</span>f</span>}}_{\mathrm{<span><span>y</span>the\; y</span>}}^{\mathrm{<span><span>move</span>move</span>}}<span><span>+</span>+</span>{\mathrm{<span><span>F</span>f</span>}}_{\mathrm{<span><span>y</span>the\; y</span>}}^{\mathrm{<span><span>decap</span>decap</span>}}<span><span>)</span>)</span><span><span>=</span>=</span>\mathrm{<span><span>0</span>0</span>}<span><span>-</span>-</span><span><span>-</span>-</span><span><span>-</span>-</span><span><span>(</span>(</span>\mathrm{<span><span>4</span>4</span>}<span><span>)</span>)</span>$其中

表示X轴方向上对应线长的拉力，in

Indicates the pulling force corresponding to the line length in the X-axis direction,

表示Y轴方向上对应线长的拉力，

Indicates the pulling force corresponding to the line length in the Y-axis direction,${\mathrm{<span><span>F</span>f</span>}}_{\mathrm{<span><span>x</span>x</span>}}^{\mathrm{<span><span>net</span>net</span>}}<span><span>=</span>=</span>{\mathrm{<span><span>C</span>C</span>}}_{\mathrm{<span><span>x</span>x</span>}}<span><span>\&CenterDot;</span>\&Center\; Dot;</span>{\mathrm{<span><span>x</span>x</span>}}^{<span><span>\&prime;</span>\&prime;</span>}<span><span>+</span>+</span>{\mathrm{<span><span>d</span>d</span>}}_{\mathrm{<span><span>x</span>x</span>}}$${\mathrm{<span><span>F</span>f</span>}}_{\mathrm{<span><span>y</span>the\; y</span>}}^{\mathrm{<span><span>net</span>net</span>}}<span><span>=</span>=</span>{\mathrm{<span><span>C</span>C</span>}}_{\mathrm{<span><span>y</span>the\; y</span>}}<span><span>\&CenterDot;</span>\&Center\; Dot;</span>{\mathrm{<span><span>y</span>the\; y</span>}}^{<span><span>\&prime;</span>\&prime;</span>}<span><span>+</span>+</span>{\mathrm{<span><span>d</span>d</span>}}_{\mathrm{<span><span>y</span>the\; y</span>}}$

表示X轴方向上使得布局在没有散开力的情况下保持不变的力，

Indicates the force in the X-axis direction that keeps the layout constant without spreading out,

表示Y轴方向上使得布局在没有散开力的情况下保持不变的力，

Indicates the force in the Y-axis direction that keeps the layout constant without spreading out,${\mathrm{<span><span>F</span>f</span>}}_{\mathrm{<span><span>x</span>x</span>}}^{\mathrm{<span><span>hold</span>hold</span>}}<span><span>=</span>=</span><span><span>-</span>-</span><span><span>(</span>(</span>{\mathrm{<span><span>C</span>C</span>}}_{\mathrm{<span><span>x</span>x</span>}}<span><span>\&CenterDot;</span>\&Center\; Dot;</span>{\mathrm{<span><span>x</span>x</span>}}^{<span><span>\&prime;</span>\&prime;</span>}<span><span>+</span>+</span>{\mathrm{<span><span>d</span>d</span>}}_{\mathrm{<span><span>x</span>x</span>}}<span><span>)</span>)</span>$${\mathrm{<span><span>F</span>f</span>}}_{\mathrm{<span><span>y</span>the\; y</span>}}^{\mathrm{<span><span>hold</span>hold</span>}}<span><span>=</span>=</span><span><span>-</span>-</span><span><span>(</span>(</span>{\mathrm{<span><span>C</span>C</span>}}_{\mathrm{<span><span>y</span>the\; y</span>}}<span><span>\&CenterDot;</span>\&Center\; Dot;</span>{\mathrm{<span><span>y</span>the\; y</span>}}^{<span><span>\&prime;</span>\&prime;</span>}<span><span>+</span>+</span>{\mathrm{<span><span>d</span>d</span>}}_{\mathrm{<span><span>y</span>the\; y</span>}}<span><span>)</span>)</span>$其中x′和y′表示布局中单元的中心位置，where x' and y' represent the center position of the cell in the layout,表示X轴方向上消除单元重叠的散开力， Indicates the spreading force to eliminate element overlap in the X-axis direction,

表示Y轴方向上消除单元重叠的散开力，

Indicates the spreading force to eliminate cell overlap in the Y-axis direction,${\mathrm{<span><span>F</span>f</span>}}_{\mathrm{<span><span>x</span>x</span>}}^{\mathrm{<span><span>move</span>move</span>}}<span><span>=</span>=</span>{\stackrel{<span><span>\&CenterDot;</span>\&Center\; Dot;</span>}{\mathrm{<span><span>C</span>C</span>}}}_{\mathrm{<span><span>x</span>x</span>}}<span><span>(</span>(</span>\mathrm{<span><span>\&Delta;x</span>\&Delta;x</span>}<span><span>+</span>+</span>{\mathrm{<span><span>\&Phi;</span>\&Phi;</span>}}_{\mathrm{<span><span>x</span>x</span>}}<span><span>)</span>)</span>$${\mathrm{<span><span>F</span>f</span>}}_{\mathrm{<span><span>y</span>the\; y</span>}}^{\mathrm{<span><span>move</span>move</span>}}<span><span>=</span>=</span>{\stackrel{<span><span>\&CenterDot;</span>\&Center\; Dot;</span>}{\mathrm{<span><span>C</span>C</span>}}}_{\mathrm{<span><span>y</span>the\; y</span>}}<span><span>(</span>(</span>\mathrm{<span><span>\&Delta;y</span>\&Delta;y</span>}<span><span>+</span>+</span>{\mathrm{<span><span>\&Phi;</span>\&Phi;</span>}}_{\mathrm{<span><span>y</span>the\; y</span>}}<span><span>)</span>)</span>$是一个对角矩阵，其对角元素表示线网对单元在X轴方向上的拉力系数， is a diagonal matrix, and its diagonal elements represent the tension coefficients of the line-network pair elements in the X-axis direction,是一个对角矩阵，其对角元素表示线网对单元在Y轴方向上的拉力系数， is a diagonal matrix, and its diagonal elements represent the tension coefficients of the line-network pair elements in the Y-axis direction,

表示X轴方向上去耦合电容影响下的散开力，

Indicates the spreading force under the influence of the decoupling capacitor in the X-axis direction,

表示Y轴方向上去耦合电容影响下的散开力，

Indicates the spreading force under the influence of the decoupling capacitor in the Y-axis direction,${\mathrm{<span><span>F</span>f</span>}}_{\mathrm{<span><span>x</span>x</span>}}^{\mathrm{<span><span>decap</span>decap</span>}}<span><span>=</span>=</span>\stackrel{<span><span>\&CenterDot;</span>\&Center\; Dot;</span>}{\mathrm{<span><span>Q</span>Q</span>}}<span><span>(</span>(</span>\mathrm{<span><span>\&Delta;x</span>\&Delta;x</span>}<span><span>+</span>+</span>\mathrm{<span><span>\&beta;</span>\&beta;</span>}<span><span>\&CenterDot;</span>\&CenterDot;</span>\mathrm{<span><span>\&gamma;</span>\&gamma;</span>}<span><span>\&CenterDot;</span>\&Center\; Dot;</span>{\mathrm{<span><span>\&Psi;</span>\&Psi;</span>}}_{\mathrm{<span><span>x</span>x</span>}}<span><span>)</span>)</span>$${\mathrm{<span><span>F</span>f</span>}}_{\mathrm{<span><span>y</span>the\; y</span>}}^{\mathrm{<span><span>decap</span>decap</span>}}<span><span>=</span>=</span>\stackrel{<span><span>\&CenterDot;</span>\&Center\; Dot;</span>}{\mathrm{<span><span>Q</span>Q</span>}}<span><span>(</span>(</span>\mathrm{<span><span>\&Delta;y</span>\&Delta;y</span>}<span><span>+</span>+</span>\mathrm{<span><span>\&beta;</span>\&beta;</span>}<span><span>\&CenterDot;</span>\&Center\; Dot;</span>\mathrm{<span><span>\&gamma;</span>\&gamma;</span>}<span><span>\&CenterDot;</span>\&Center\; Dot;</span>{\mathrm{<span><span>\&Psi;</span>\&Psi;</span>}}_{\mathrm{<span><span>y</span>the\; y</span>}}<span><span>)</span>)</span>$其中Δx＝x-x′，Δy＝y-y′为单元位置的调整量，把上述力的计算公式代入方程(4)，得到：Among them, Δx=x-x′, Δy=y-y′ is the adjustment amount of the unit position, and the calculation formula of the above force is substituted into equation (4) to obtain:$<span><span>(</span>(</span>{\mathrm{<span><span>C</span>C</span>}}_{\mathrm{<span><span>x</span>x</span>}}<span><span>+</span>+</span>{\stackrel{<span><span>\&CenterDot;</span>\&Center\; Dot;</span>}{\mathrm{<span><span>C</span>C</span>}}}_{\mathrm{<span><span>x</span>x</span>}}<span><span>+</span>+</span>{\stackrel{<span><span>\&CenterDot;</span>\&CenterDot;</span>}{\mathrm{<span><span>Q</span>Q</span>}}}_{\mathrm{<span><span>x</span>x</span>}}<span><span>)</span>)</span>\mathrm{<span><span>\&Delta;x</span>\&Delta;x</span>}<span><span>=</span>=</span><span><span>-</span>-</span><span><span>(</span>(</span>{\stackrel{<span><span>\&CenterDot;</span>\&CenterDot;</span>}{\mathrm{<span><span>C</span>C</span>}}}_{\mathrm{<span><span>x</span>x</span>}}{\mathrm{<span><span>\&Phi;</span>\&Phi;</span>}}_{\mathrm{<span><span>x</span>x</span>}}<span><span>+</span>+</span>\mathrm{<span><span>\&beta;</span>\&beta;</span>}<span><span>\&CenterDot;</span>\&CenterDot;</span>\mathrm{<span><span>\&gamma;</span>\&gamma;</span>}<span><span>\&CenterDot;</span>\&CenterDot;</span>{\mathrm{<span><span>\&Psi;</span>\&Psi;</span>}}_{\mathrm{<span><span>x</span>x</span>}}<span><span>)</span>)</span>$$<span><span>(</span>(</span>{\mathrm{<span><span>C</span>C</span>}}_{\mathrm{<span><span>y</span>the\; y</span>}}<span><span>+</span>+</span>{\stackrel{<span><span>\&CenterDot;</span>\&Center\; Dot;</span>}{\mathrm{<span><span>C</span>C</span>}}}_{\mathrm{<span><span>y</span>the\; y</span>}}<span><span>+</span>+</span>{\stackrel{<span><span>\&CenterDot;</span>\&Center\; Dot;</span>}{\mathrm{<span><span>Q</span>Q</span>}}}_{\mathrm{<span><span>y</span>the\; y</span>}}<span><span>)</span>)</span>\mathrm{<span><span>\&Delta;y</span>\&Delta;y</span>}<span><span>=</span>=</span><span><span>-</span>-</span><span><span>(</span>(</span>{\stackrel{<span><span>\&CenterDot;</span>\&Center\; Dot;</span>}{\mathrm{<span><span>C</span>C</span>}}}_{\mathrm{<span><span>y</span>the\; y</span>}}{\mathrm{<span><span>\&Phi;</span>\&Phi;</span>}}_{\mathrm{<span><span>y</span>the\; y</span>}}<span><span>+</span>+</span>\mathrm{<span><span>\&beta;</span>\&beta;</span>}<span><span>\&CenterDot;</span>\&Center\; Dot;</span>\mathrm{<span><span>\&gamma;</span>\&gamma;</span>}<span><span>\&CenterDot;</span>\&CenterDot;</span>{\mathrm{<span><span>\&Psi;</span>\&Psi;</span>}}_{\mathrm{<span><span>y</span>the\; y</span>}}<span><span>)</span>)</span>$上式中

表示

在X轴方向上的分量，

表示

在Y轴方向上的分量，求解上述力平衡方程之后得到各单元中心的新位置；In the above formula

express

component in the x-axis direction,

express

For the component in the Y-axis direction, the new position of the center of each unit is obtained after solving the above force balance equation;步骤(4.10)，计算调整因子κ来调整参数矩阵Step (4.10), calculate the adjustment factor κ to adjust the parameter matrix$\stackrel{<span><span>\&CenterDot;</span>\&CenterDot;</span>}{\mathrm{<span><span>P</span>P</span>}}<span><span>\&LeftArrow;</span>\&LeftArrow;</span>\mathrm{<span><span>\&kappa;</span>\&kappa;</span>}<span><span>(</span>(</span>\mathrm{<span><span>\&mu;</span>\&mu;</span>}<span><span>)</span>)</span><span><span>\&CenterDot;</span>\&CenterDot;</span>\stackrel{<span><span>\&CenterDot;</span>\&Center\; Dot;</span>}{\mathrm{<span><span>P</span>P</span>}}$$\stackrel{<span><span>\&CenterDot;</span>\&Center\; Dot;</span>}{\mathrm{<span><span>Q</span>Q</span>}}<span><span>\&LeftArrow;</span>\&LeftArrow;</span>\mathrm{<span><span>\&kappa;</span>\&kappa;</span>}<span><span>(</span>(</span>\mathrm{<span><span>\&mu;</span>\&mu;</span>}<span><span>)</span>)</span><span><span>\&CenterDot;</span>\&Center\; Dot;</span>\stackrel{<span><span>\&CenterDot;</span>\&Center\; Dot;</span>}{\mathrm{<span><span>Q</span>Q</span>}}<span><span>-</span>-</span><span><span>-</span>-</span><span><span>-</span>-</span><span><span>(</span>(</span>\mathrm{<span><span>5</span>5</span>}<span><span>)</span>)</span>$κ(μ)＝1+tanh(ln(μ_T/μ))κ(μ)＝1+tanh(ln(μ_T /μ))$\mathrm{<span><span>\&mu;</span>\&mu;</span>}<span><span>=</span>=</span>\frac{\mathrm{<span><span>1</span>1</span>}}{\mathrm{<span><span>m</span>m</span>}}\underset{\mathrm{<span><span>i</span>i</span>}<span><span>=</span>=</span>\mathrm{<span><span>1</span>1</span>}}{\overset{\mathrm{<span><span>m</span>m</span>}}{\mathrm{<span><span>\&Sigma;</span>\&Sigma;</span>}}}\sqrt{\mathrm{<span><span>\&Delta;</span>\&Delta;</span>}{\mathrm{<span><span>x</span>x</span>}}^{\mathrm{<span><span>2</span>2</span>}}<span><span>+</span>+</span>\mathrm{<span><span>\&Delta;</span>\&Delta;</span>}{\mathrm{<span><span>y</span>the\; y</span>}}^{\mathrm{<span><span>2</span>2</span>}}}$其中μ为所有单元的平均移动量，μ_T为用户指定的期望的单元位置调整量；Among them, μ is the average movement of all units, and μ_T is the expected unit position adjustment specified by the user;步骤(5)，对总体布局的结果进行合法化Step (5), legalize the result of the overall layout利用解析的布局合法化方法，消除单元之间的重叠，并且消除单元在单元行上的错位；Eliminate the overlap between cells and the misalignment of cells on the cell row by using the analytical layout legalization method;步骤(6)，对合法化后的不均进行去耦合电容放置Step (6), place a decoupling capacitor on the legalized unevenness利用基于灵敏度的方法为最终的布局结果加上去耦合电容，灵敏度是考虑电路节点电压随着吸纳电流变化的敏感程度，加入去耦电容可以改善电路的灵敏度，使得吸纳电流的变化对供电网络的节点电压影响更小，最终得到更好的供电性能。Use the method based on sensitivity to add decoupling capacitors to the final layout results. Sensitivity is to consider the sensitivity of the circuit node voltage to the change of the absorbing current. Adding decoupling capacitors can improve the sensitivity of the circuit, so that the change of absorbing current will affect the nodes of the power supply network. The voltage effect is less, resulting in better power delivery performance.

Images