CN107526860B - VLSI Standard Cell Layout Method Based on Electric Field Energy Modeling Technology - Google Patents

Abstract

The invention relates to a VLSI standard unit layout method based on electric field energy modeling technology. The method solves the VLSI standard unit global layout problem by establishing an electric field energy model of the problem and using the analytical solution of the global density function and the Poisson equation. The key points of the technical solution are as follows: (1) By analogizing the layout problem to the electrostatic system and comparing the unit to the charge, the original density constraint is transformed into a zero potential energy constraint. A differential equation is constructed, and the potential energy constraints are more accurately described by solving explicit expressions for it. Then, the penalty function method is used to transform the line length objective and potential energy constraints of the VLSI global layout into an unconstrained nonlinear programming problem, and an appropriate optimization technique is selected for optimization. (2) Unlike the previous method of uniformly dividing the bins to obtain discrete density function values, this invention calculates the global density expression constrained by the overlap between cells and the entire layout area, so as to more accurately describe the distribution of cells on the layout area.

Description

VLSI Standard Cell Layout Method Based on Electric Field Energy Modeling Technology

technical field

The invention relates to the technical field of VLSI physical design automation, in particular to a VLSI standard cell layout method based on electric field energy modeling technology.

Background technique

In the current VLSI layout, the scale of integrated circuits continues to increase and the requirements for technology are getting higher and higher, which puts forward higher requirements for the optimization goals and optimization methods of VLSI layout, and the quality of the layout results directly affects the quality of the entire chip. performance. With the rapid growth of the number of units on a chip, especially the widespread application of millions of gate chips, it poses a huge challenge to the automation of VLSI layout design. Therefore, it is of great significance to seek more efficient and practical integrated circuit layout algorithms

Algorithms used to solve VLSI placement problems can be divided into the following three categories: partition-based placement methods, partition-based technology-based methods, and analysis-based placement methods. Among these three types of directions, the layout method based on analysis achieves better layout effects, so it has become the method adopted by the current mainstream layout tools. Due to the large scale of the VLSI layout problem, it is difficult for existing analytical-based layout tools to solve it directly. In the VLSI placement algorithm of the analysis method, it is mainly divided into three steps: global placement, legalization and detailed placement. In the global layout, when a few cells are allowed to overlap with each other, the best position of each cell is found to make the bus length the shortest. Global layout is considered to be the most important step in the analysis method, since it largely determines the quality of the layout.

At present, the global layout algorithms based on analytical methods can be divided into two categories: (1) direct method, which is applied to layout tools such as Kraftwerk2, FastPlace3, RQL, SimPL, etc.; (2) nonlinear method, which is applied to APLace2, NTUplace3, mPL6, ePlace and other layout tools. According to the comparison of academic and industrial placers, the placement tools based on nonlinear programming methods achieve the best experimental results.

However, the existing global layout methods based on analytical methods have the following two problems: (1) In the process of global layout, the method of uniformly dividing the layout area into bins is used for approximate calculation of density, because the density function is non-smooth , a smoothing approximation is also required. Therefore, there is a large error between the density constraint calculated after approximation and the actual density distribution, which is not a good reflection of the actual density of the layout, so that the quality of the layout cannot be guaranteed; (2) The existing layout tools use the Poisson equation to solve , but the numerical solution method is used, which also has a certain influence on the quality of the solution.

Contents of the invention

In view of this, the purpose of the present invention is to provide a VLSI standard cell layout method based on electric field energy modeling technology, which will abandon the method of discrete calculation density distribution and numerical solution of differential equations, adopt global density function and obtain analytical results for differential equations untie. Then choose the Nesterov's method of Lipsis step size prediction to solve it to get high-quality layout results. Its basic idea is to combine the global density function and Nesterov's method of Lipsis step size prediction without line search, and use the idea of electric field energy modeling to construct Poisson equation and solve it, so as to obtain an analysis-based method of the global layout method.

The present invention adopts the following schemes to realize: a VLSI standard cell layout method based on electric field energy modeling technology, a VLSI standard cell layout method based on electric field energy modeling technology, the circuit is first represented as a hypergraph; The layout problem is modeled as an electric field energy problem by analogy with an electrostatic system; then, the global density function of the problem is calculated, the Poisson equation is constructed and the analytical solution is obtained. In this method, the idea of penalty function is used to combine line length and density as the objective function, and then Nesterov’s algorithm is used to optimize the solution in each iteration, including the following steps:

Step S1: Express the circuit as a hypergraph H={V,E};

Step S2: modeling the circuit based on electric field energy technology;

Step S3: Calculate the global density function, construct the Poisson equation and solve it;

Step S4: Initialize the position of the unit with an unconstrained quadratic programming method;

Step S5: set parameter k=1;

Step S6: Calculate the line length and line length gradient;

Step S7: using a penalty function method to convert the line length objective and density constraints of the VLSI global layout into an unconstrained nonlinear programming problem;

Step S8: using an optimization method to solve the nonlinear programming problem in step S7 to obtain a new unit location;

Step S9: Modify the penalty parameter in the penalty function in the step S7;

Step S10: k=k+1;

Step S11: return to step S6, and loop from step S6 to step S10 until the overflow rate meets the requirement.

Further, the implementation of the step S1 is as follows: expressing the circuit as a hypergraph model H={V,E}, wherein, V={v ₁ ,v ₂ ,...,v _n } represents a circuit element (unit) The set of , E={e ₁ ,e ₂ ,…,e _n } represents the line network set;

Further, in the step S2, the entire layout problem is modeled as a two-dimensional electrostatic system, and the distribution of potential and electric field is determined by all elements in the system; each node i is converted into a positive charge as a standard unit, and the electric charge q _i is determined by the area A _i of the node; the movement of the unit is driven by the electric field force F _i = q _i ξ _i , where ξ _i is the local electric field; the potential energy N _i of the unit is calculated by N _i = q _i ψ _i , where ψ _i is the potential of cell i;

According to Coulomb's law, the electric field and potential at unit i are superimposed by the contributions of all remaining units in the system. If the constraints of the global layout and the density distribution are connected with the electrostatic equilibrium state of the system, the electric field force directly causes the charge to move to equilibrium. state; by Gauss' law, the electric field is equal to the negative gradient of the potential

The charge density is equal to the divergence of the electric field

The total potential energy of the system is defined as

Since the energy of the system is equal to the sum of the mutual energies of all pairs of charges, there is a factor of 1/2 for the energies of all single charges.

Among them, for the distribution of a given unit (the distribution of charge), it will generate an electric potential field, and the potential function on the plane will be subtracted from its average value, which can have the following effects:

(1) A function minus its mean, then its integral over its region is zero.

(2) The total potential energy of the system is Since the charge is fixed, each ψ _i minus the average value of the function over the entire area is equivalent to N(v) minus a constant. It will not affect the solution of the unconstrained minimization problem constructed later.

(3) Electric field is the gradient of electric potential, which is a vector. Subtracting a constant from the entire function at the same time has no effect on its gradient;

Thus, subtracting the potential function from its mean yields _∫∫R ψ(x,y)=0.

Further, in the step S3, unlike the previous layout device that uses bin division to obtain a discrete density function, a continuous global density function is used to obtain the coefficients of the Fourier transform, and the density function ρ(x, y) Expressed as follows:

Let θ _i (x) denote the overlap of cell i and the entire layout area, then

The definition in the Y direction is the same, then

By Gauss' law, the distribution of the electric potential is combined by the Poisson equation and the density function as follows

make Indicates the outer normal vector of the layout region R, Represents the boundary. When the unit moves to the boundary of the layout area, it should slow down and stop the movement to prevent the unit from running out, that is, the electric field force should be reduced to zero when approaching the boundary, so the following Neumann boundary conditions are required

Since the integral of the potential function over the entire layout area R is equal to 0,

_∫∫R ψ(x,y)＝0 (7)

Based on the above equations, a partial differential equation with a unique solution is obtained

Solve the above PDE equation:

First solve the homogeneous equation, let but

get

When τ<0, the general solution is

In order to satisfy the boundary conditions, then This gives C ₁ =C ₂ .

And by Available contradiction;

When τ=0, but No non-trivial solution can be obtained;

When τ>0

get a cluster of non-zero solutions In the same way,

Doing linear combinations of the particular solutions to find the solution to the problem yields:

From _∫∫R ψ(x,y)dxdy=0, it can be seen that a _0,0 =0.

in

According to Gauss's law, the electric field vector is equal to the negative gradient of the potential function; based on the above ψ(x,y), ξ(x,y)=(ξ _X ,ξ _Y ) is expressed as follows:

The global density function Substituting into a _u,v , we can get

The convergence of ψ(x,y) is proved as follows:

if is convergent, then ψ(x,y) is absolutely convergent.

obviously is convergent; in actual calculation, only the former partial sum can be calculated.

Further, in the step S6, for the VLSI standard cell layout problem, the layout area is a rectangular thin plate, the coordinates of its lower left corner are (0,0), and its upper right corner is (W,H). For the unit v _i (i =1,2,…,n), record w _i as its width, h _i as its height, A _i as its area, ( _xi , y _i ) as its center coordinates, then use the semicircumference line length to calculate the bus length for:

Further, in the step S7, the global layout is a constrained optimization problem. The previous algorithm evenly divides the layout area into rectangular coordinate grid bins with equal length and width, and let ρ _b (v) represent the density of each grid , D _b (x, y) represents the total area occupied by cells in each grid, then the goal of a global layout is to satisfy the constraint that the density of all grids is less than or equal to a given target layout density ρ _t , so that the total HPWL is the smallest, and the problem model is as follows:

Using the method based on electric field energy modeling, the layout problem is transformed into an electrostatic system, and the constraint is rewritten as the total potential energy of the system N(v)=0, namely

Use the penalty method to integrate the constraints into the objective function, and convert the above constrained optimization problem into an unconstrained optimization problem through a penalty parameter λ

Differentiate the above formula to get the gradient vector as follows

Further, the implementation in the step S8 includes the following steps:

Input: solution m _k based on unit position, reference solution r _k , optimization parameter β _k ;

Output: m _k+1 , r _k+1 ;

Step S81: When k=1, r ₁ =m ₁ , r ₀ randomly takes a vector, β ₀ =1;

Step S82: gradient vector

Step S83: step size

Step S84:

Step S85:

Step S86: r _k+1 =m _k+1 +(β _k -1)(m _k+1 -m _k )/β _k+1 .

Further, the implementation of step S11 includes the following steps:

Step S111: dividing the layout area into uniform bins;

Step S112: Calculate the overflow rate

Step S113: Repeat steps S6 to S11 until overflow_ratio<overflow _min or overflow_ratio does not decrease further compared to the previous calculation result.

Compared with the prior art, the advantages of the present invention are as follows: (1) the present invention directly calculates the global density function, avoiding the quality loss caused by dividing bins; (2) the present invention uses the analogy between the layout problem and the electrostatic system to construct loose equation. Obtain analytical solution to it, avoid the error of numerical solution method; (3) the present invention utilizes differential equation to link together non-smooth global density function and zero potential energy constraint, does not need to carry out smoothing treatment, has avoided quality loss; (4 ) The present invention uses the Nesterov's method based on Lipsis step size prediction, which avoids a large number of calculations for line search, so that the present invention can solve the layout problem of large-scale integrated circuits.

Description of drawings

Fig. 1 is a flow chart of a VLSI standard cell layout method based on electric field energy modeling technology.

Figure 2 is a schematic diagram of the relationship between the layout problem and the converted electrostatic system.

Detailed ways

The present invention will be further described below in conjunction with the accompanying drawings and embodiments.

The present embodiment provides a VLSI standard cell layout method based on electric field energy modeling technology, as shown in Figure 1, comprising the following steps:

Step S1: Express the circuit as a hypergraph H={V,E};

Step S2: modeling the circuit based on electric field energy technology;

Step S3: Calculate the global density function, construct the Poisson equation and solve it;

Step S4: Initialize the position of the unit with an unconstrained quadratic programming method;

Step S5: set parameter k=1;

Step S6: Calculate the line length and line length gradient;

Step S7: using a penalty function method to convert the line length objective and density constraints of the VLSI global layout into an unconstrained nonlinear programming problem;

Step S8: using an optimization method to solve the nonlinear programming problem in step S7 to obtain a new unit location;

Step S9: Modify the penalty parameter in the penalty function in the step S7;

Step S10: k=k+1;

Step S11: return to step S6, and loop from step S6 to step S10 until the overflow rate meets the requirement.

In this embodiment, the specific method of step S1 is: express the circuit as a hypergraph model H={V,E}, where V={v ₁ ,v ₂ ,...,v _n } represents the circuit element ( unit), E＝{e ₁ ,e ₂ ,…,e _n } represents the set of line nets;

In this embodiment, the step S2 is specifically: modeling the entire layout problem as a two-dimensional electrostatic system. The distribution of potentials and electric fields is determined by all elements in the system. Each node i (a standard cell or a macro cell) is converted into a positive charge, and the charge q _i is determined by the area A _i of the node. The movement of the unit is driven by the electric field force F _i =q _i ξ _i , where ξ _i is the local electric field. The potential energy N _i of a cell is calculated by N _i =q _i ψ _i , where ψ _i is the potential of cell i. The relationship of the layout problem to the converted electrostatic system is shown in Figure 2 below. By Coulomb's law, the electric field and potential at cell i are the sum of all remaining cell contributions in the system. This invention links the constraints of the global layout and the density distribution with the electrostatic equilibrium state of the system. The electric field force directly helps the charge (unit) to move to an equilibrium state. By Gauss' law, the electric field is equal to the negative gradient of the potential energy

The charge density is equal to the divergence of the electric field

The total potential energy of the system is defined as

Since the energy of the system is equal to the sum of the mutual energies of all pairs of charges, there is a factor of 1/2 for the energies of all single charges.

For a given cell distribution (distribution of charge), it will generate an electric potential field. Subtracting the average value of the potential function on the plane can have the following effects:

(1) A function minus its mean, then its integral over its region is zero.

(2) The total potential energy of the system is Since the charge is fixed, each ψ _i minus the average value of the function over the entire area is equivalent to N(v) minus a constant. It will not affect the solution of the unconstrained minimization problem constructed later.

(3) Electric field is the gradient of electric potential, which is a vector. Subtracting a constant from the whole function at the same time has no effect on its gradient.

Therefore, the average value of the potential function can be subtracted to obtain _∫∫R ψ(x,y)=0.

In this embodiment, for parts 104 and 105 in FIG. 1 , the specific manner of step S3 is as follows:

It is different from the use of bin division in the previous placer to obtain a discrete density function. This invention uses a continuous global density function to obtain the coefficients of the Fourier transform. The expression of the density function ρ(x,y) is as follows

Let θ _i (x) denote the overlap of cell i and the entire layout area, then

The definition in the Y direction is the same, then

By Gauss's law, the distribution of electric potential can be combined by Poisson's equation and density function as follows

make Indicates the outer normal vector of the layout region R, Indicates the boundary. When the cell is moving towards the boundary of the layout area, the movement should be slowed down and stopped to prevent the cell from running out, i.e. the electric field force should be reduced to zero when approaching the boundary. Therefore, the following Neumann boundary conditions are required

It can be known from the above that the integral of the potential energy function over the entire layout area R must be equal to 0,

_∫∫R ψ(x,y)＝0 (7)

Based on the above equations, a partial differential equation with a unique solution can be obtained

Solve the above PDE equation.

First solve the homogeneous equation, let but

can get

When τ<0, the general solution is

In order to satisfy the boundary conditions, then This gives C ₁ =C ₂ .

And by Available contradiction.

When τ=0, but No non-trivial solution is obtained.

When τ>0

A cluster of non-zero solutions can be obtained In the same way,

Do the linear combination of special solutions to find the solution of the problem, we can get

From _∫∫R ψ(x,y)dxdy=0, it can be seen that a _0,0 =0.

in

By Gauss' law, the electric field vector is equal to the negative gradient of the potential function. Based on the above ψ(x,y), it can be obtained that ξ(x,y)=(ξ _X ,ξ _Y ) is expressed as follows:

The global density function Substituting into a _u,v , we can get

The convergence of ψ(x,y) is proved as follows:

if is convergent, then ψ(x,y) is absolutely convergent.

obviously is convergent. Therefore, in actual calculation, we can only calculate the former partial sum.

In the present embodiment, part 108 in Fig. 1, in said step S6, for the VLSI standard cell layout problem, the layout area is a rectangular thin plate, and its lower left corner coordinates are (0,0), and its upper right corner is (W, H), for unit v _i (i=1,2,...,n), record w _i as its width, h _i as its height, A _i as its area, and ( _xi , y _i ) as its center coordinates. Then the bus length calculated by using the semicircumference line length is:

In the present embodiment, in the part 109 in Fig. 1, the specific manner of the step S7 is as follows:

The global layout is a constrained optimization problem. The previous algorithm evenly divides the layout area into rectangular coordinate grids (bins) with equal length and width. Let ρ _b (v) represent the density of each grid, and D _b (x, y ) represents the total area occupied by cells in each grid, then the goal of a global layout is to satisfy the constraint that the density of all grids is less than or equal to a given target layout density ρ _t , so that the total HPWL is minimized. The problem model is as follows:

However, this invention adopts a method based on electric field energy modeling, transforms the layout problem into an electrostatic system, and rewrites the constraint as the total potential energy N(v)=0 of the system, namely

Use the penalty method to integrate the constraints into the objective function, and convert the above constrained optimization problem into an unconstrained optimization problem through a penalty parameter λ

Differentiate the above formula to get the gradient vector as follows

In the present embodiment, in the part 110 in Fig. 1, the specific manner of the step S8 is as follows:

Input: solution m _k based on element position, reference solution r _k , optimization parameter β _k

Output: m _k+1 , r _k+1

Step S81: when k=1, r ₁ =m ₁ , r ₀ takes a random vector, β ₀ =1;

Step S82: Gradient vector

Step S83: step size

Step S84:

Step S85:

Step S86: r _k+1 =m _k+1 +(β _k -1)(m _k+1 -m _k )/β _k+1 ;

In the present embodiment, in the part 113 in Fig. 1, the specific manner of the step S11 is as follows:

Step S111: dividing the layout area into uniform bins;

Step S112: Calculate the overflow rate

Step S113: Repeat steps S6 to S10 until overflow_ratio<overflow _min or overflow_ratio does not decrease further compared to the previous calculation result.

The above descriptions are only preferred embodiments of the present invention, and all equivalent changes and modifications made according to the scope of the patent application of the present invention shall fall within the scope of the present invention.

The above descriptions are only preferred embodiments of the present invention, and all equivalent changes and modifications made according to the scope of the patent application of the present invention shall fall within the scope of the present invention.

Claims (6)

1. a VLSI standard cell layout method based on electric field energy modeling technology, is characterized in that: comprise the steps: Step S1: Express the circuit as a hypergraph H={V,E}; Step S2: modeling the circuit based on electric field energy technology; Step S3: Calculate the global density function, construct the Poisson equation and solve it; Step S4: Initialize the position of the unit with an unconstrained quadratic programming method; Step S5: set parameter k=1; Step S6: Calculate the line length and line length gradient; Step S7: using a penalty function method to convert the line length objective and density constraints of the VLSI global layout into an unconstrained nonlinear programming problem; Step S8: using an optimization method to solve the nonlinear programming problem in step S7 to obtain a new unit location; Step S9: Modify the penalty parameter in the penalty function in the step S7; Step S10: k=k+1; Step S11: return to step S6, loop step S6 to step S10, until the overflow rate meets the requirements; Wherein, in the step S2, the entire layout problem is modeled as a two-dimensional electrostatic system, and the distribution of the potential and the electric field is determined by all elements in the system; each node i is used as a standard unit and converted into a positive charge, the electric quantity q _i Determined by the area A _i of the node; the movement of the unit is driven by the electric field force F _i =q _i ξ _i , where ξ _i is the local electric field; the potential energy N _i of the unit is calculated by N _i =q _i ψ _i , where ψ _i is the unit the electric potential of i; According to Coulomb's law, the electric field and potential at unit i are superimposed by the contribution of all remaining units in the system; if the constraints of the global layout and the density distribution are connected with the electrostatic equilibrium state of the system, the electric field force directly causes the charge to move to equilibrium state; by Gauss' law, the electric field is equal to the negative gradient of the potential The charge density is equal to the divergence of the electric field The total potential energy of the system is defined as Because the energy of the system is equal to the sum of the mutual energies of all pairs of charges, there is a factor of 1/2 for all single charge energies; Wherein, in the step S3, different from the previous layout device using bin division to obtain a discrete density function, a continuous global density function is used to obtain the coefficients of the Fourier transform, and the density function ρ(x, y) represents as follows: Let θ _i (x) denote the overlap of cell i and the entire layout area, then The definition in the Y direction is the same, then By Gauss' law, the distribution of the electric potential is combined by the Poisson equation and the density function as follows make Indicates the outer normal vector of the layout region R, Represents the boundary. When the unit moves to the boundary of the layout area, it should slow down and stop the movement to prevent the unit from running out, that is, the electric field force should be reduced to zero when approaching the boundary, so the following Neumann boundary conditions are required Since the integral of the potential function over the entire layout area R is equal to 0, _∫∫R ψ(x,y)＝0 (7) Based on formula (5) to formula (7), a partial differential equation with a unique solution is obtained, that is, the PDE equation; Solve the above PDE equation: First solve the homogeneous equation, let ψ(x,y)=φ(x)η(y), then get When τ<0, the general solution is In order to satisfy the boundary conditions, then Obtain C ₁ =C ₂ ; And by Available contradiction; When τ=0, but No non-trivial solution can be obtained; When τ>0, get a cluster of non-zero solutions In the same way, Doing linear combinations of the particular solutions to find the solution to the problem yields: From ∫∫ _R ψ(x,y)dxdy=0, we know that a _0,0 =0; in According to Gauss's law, the electric field vector is equal to the negative gradient of the potential function; based on the above ψ(x,y), ξ(x,y)=(ξ _X ,ξ _Y ) is expressed as follows: The global density function Substituting into a _u,v , we can get The convergence of ψ(x,y) is proved as follows: if is convergent, then ψ(x,y) is absolutely convergent; obviously is convergent; in actual calculation, only the former partial sum can be calculated. 2. a kind of VLSI standard cell layout method based on electric field energy modeling technology according to claim 1, is characterized in that: the realization mode of described step S1 is specifically: circuit is represented as hypergraph model H={V, E}, wherein, V={v ₁ , v ₂ ,...,v _n } represents a set of circuit elements, and E={e ₁ , e ₂ ,...,e _n } represents a set of wire nets. 3. a kind of VLSI standard cell layout method based on electric field energy modeling technology according to claim 2, is characterized in that: in described step S6, for VLSI standard cell layout problem, layout area is a rectangular thin plate, its The coordinates of the lower left corner are (0,0), and the upper right corners are (W,H). For unit v _i , i=1,2,...,n, record w _i as its width, h _i as its height, and A _i as Its area, (x _i , y _i ) is its center coordinates; then the total length calculated by using the semicircumference line length is: 4. a kind of VLSI standard cell layout method based on electric field energy modeling technology according to claim 3, is characterized in that: in described step S7, global layout is a constrained optimization problem, and previous algorithm divides layout area evenly is a rectangular coordinate network bin with equal length and width, let ρ _b (v) represent the density of each grid, and D _b (x, y) represent the total area occupied by cells in each grid, then a global layout The goal is to satisfy the constraint that the density of all grids is less than or equal to a given target layout density ρ _t , so that the total HPWL is minimized. The problem model is as follows: Using the method based on electric field energy modeling, the layout problem is transformed into an electrostatic system, and the constraint is rewritten as the total potential energy of the system N(v)=0, namely Use the penalty method to integrate the constraints into the objective function, and convert the above constrained optimization problem into an unconstrained optimization problem through a penalty parameter λ Differentiate the above formula to get the gradient vector as follows 5. a kind of VLSI standard cell layout method based on electric field energy modeling technology according to claim 4, is characterized in that: in described step S8, implementation comprises the following steps: Input: solution m _k based on unit position, reference solution r _k , optimization parameter β _k ; Output: m _k+1 , r _k+1 ; Step S81: When k=1, r ₁ =m ₁ , r ₀ randomly takes a vector, β ₀ =1; Step S82: gradient vector Step S83: step size Step S84: Step S85: Step S86: r _k+1 =m _k+1 +(β _k -1)(m _k+1 -m _k )/β _k+1 . 6. a kind of VLSI standard cell layout method based on electric field energy modeling technology according to claim 4, is characterized in that: the realization of described step S11 comprises the following steps: Step S111: dividing the layout area into uniform bins; Step S112: Calculate the overflow rate Step S113: Repeat steps S6 to S11 until overflow_ratio<overflow _min or overflow_ratio does not decrease further compared to the previous calculation result.