CN1523662A

Movatterモバイル変換

Info

Publication number: CN1523662A
Application number: CNA031570526A
Authority: CN
Inventors: 洪先龙; 蔡懿慈; 傅静静; 骆祖莹; 潘著; 谭向东
Original assignee: Tsinghua University
Current assignee: Tsinghua University
Priority date: 2003-09-12
Filing date: 2003-09-12
Publication date: 2004-08-25
Anticipated expiration: 2023-09-12
Also published as: CN1305127C

Abstract

用去耦合电容对集成电路供电网络进行噪声优化的方法属于VLSI物理设计领域，尤其是布局布线领域中RLC电源线/地线网络噪声优化的技术范畴。其特点在于：它是一种利用计算机针对基于标准单元布图模式的专用集成电路(ASIC)的布图结构特点及其供电网络的结构特点，对供电网络的优化问题进行建模，并采用非线性规划方法对问题进行有效求解的过程。发明中，新颖之处是将去耦电容的面积作为优化的目标，使优化后得到的去耦电容面积尽可能小，为后面阶段的工作，例如插buffer，留下了充足的空白面积。求解过程中我们利用了以前工作中的优秀成果——等效电路的方法，使求解规模大大降低，很大提高了求解速度并且节省了大量的计算机内存。实验证明，本发明可以快速有效的对供电网络进行优化，并具有优化大规模集成电路供电网络的能力。

The method for noise optimization of integrated circuit power supply network by decoupling capacitor belongs to the field of VLSI physical design, especially the technical category of noise optimization of RLC power line/ground line network in the field of layout and wiring. Its characteristics are: it is a method of modeling the optimization problem of the power supply network by using the computer to target the layout structure characteristics of the application-specific integrated circuit (ASIC) based on the standard cell layout mode and the structure characteristics of the power supply network, and adopts non- The linear programming method is the process of efficiently solving the problem. In the invention, the novelty is to take the area of the decoupling capacitor as the target of optimization, so that the area of the decoupling capacitor obtained after optimization is as small as possible, leaving a sufficient blank area for the work in the later stage, such as inserting a buffer. In the process of solving, we used the excellent results in the previous work - the method of equivalent circuit, which greatly reduced the scale of the solution, greatly improved the solution speed and saved a lot of computer memory. Experiments prove that the invention can quickly and effectively optimize the power supply network, and has the ability to optimize the large scale integrated circuit power supply network.

Description

Translated fromChinese

用去耦合电容实现集成电路供电网络噪声优化的快速方法A Fast Method for Noise Optimization of IC Power Supply Network Using Decoupling Capacitors

技术领域technical field

用去耦合电容对集成电路供电网络进行噪声优化的方法属于VLSI物理设计领域，尤其是布局布线领域中RLC电源线/地线网络噪声优化的技术范畴。The method for noise optimization of integrated circuit power supply network by decoupling capacitor belongs to the field of VLSI physical design, especially the technical category of noise optimization of RLC power line/ground line network in the field of layout and wiring.

背景技术Background technique

集成电路物理设计中的布线阶段可以分为两个部分：特殊线网布线和信号线网布线。电源/地线网络设计就包含在特殊线网布线部分。随着超大规模集成电路集成度和工作频率的提高，其电源/地线网络的设计与优化问题变得越来越重要，它直接影响整个电路的性能。由于电源/地线网络的线宽比信号线大得多，并且可以变化，占用了很多芯片面积，因此，它在布线阶段被赋予了最高的优先级。The routing stage in the physical design of integrated circuits can be divided into two parts: special net routing and signal net routing. The power/ground network design is included in the special network routing section. With the increase of VLSI integration and operating frequency, the design and optimization of its power/ground network becomes more and more important, which directly affects the performance of the entire circuit. Since the line width of the power/ground network is much larger than that of the signal line and can be varied, it takes up a lot of chip area, so it is given the highest priority in the routing stage.

随着工艺的不断进步，超大规模集成电路的特征线宽在不断缩小，同时芯片的密度和工作频率也相应有大幅度的提高。从而使芯片的供电问题成为VLSI深亚微米(DSM)和超深亚微米(VDSM)集成电路设计中的一个重要问题。不适当的电源/地线网络设计会产生过大的电压降和电压波动，极大地影响电路的性能，甚至使电路失效，芯片无法正常工作。因此，对供电网络进行精确的分析并在此基础上做适当的优化就变得非常必要。With the continuous advancement of technology, the characteristic line width of VLSI is continuously shrinking, and at the same time, the density and operating frequency of the chip are also greatly improved. Therefore, the power supply of the chip becomes an important issue in the design of VLSI deep submicron (DSM) and very deep submicron (VDSM) integrated circuits. Improper power/ground network design will produce excessive voltage drop and voltage fluctuation, which will greatly affect the performance of the circuit, and even make the circuit invalid and the chip cannot work normally. Therefore, it becomes very necessary to analyze the power supply network accurately and make proper optimization on this basis.

引起供电网络中电压波动的原因有线上电阻引起的IR电压降和线上电感引起的Ldi/dt电压降。供电网络和电路元器件中的寄生电容也会对网络中各节点的电压产生影响。传统的电源/地线网络分析主要考虑了供电网络中的电阻的影响，也就是将供电网络建模为电阻网络并对它进行直流分析。然而，随着工作频率和电路中电流的不断增大，供电网络中的电容和电感的影响日益显著。因此，我们需要对供电网络建立更精确的RLC模型，并对其进行瞬态分析，以获得电路中各节点上更准确的电压波动信息。The cause of the voltage fluctuation in the power supply network is the IR voltage drop caused by the resistance on the line and the Ldi/dt voltage drop caused by the inductance on the line. The parasitic capacitance in the power supply network and circuit components will also affect the voltage of each node in the network. Traditional power/ground network analysis mainly considers the influence of resistance in the power supply network, that is, the power supply network is modeled as a resistor network and DC analysis is performed on it. However, as the operating frequency and the current in the circuit continue to increase, the influence of capacitance and inductance in the power supply network becomes more and more significant. Therefore, we need to establish a more accurate RLC model for the power supply network and conduct transient analysis on it to obtain more accurate voltage fluctuation information on each node in the circuit.

随着芯片的密度和工作频率的大幅度提高，供电网络的噪声阈值显著降低。供电网络上的噪声会降低器件的驱动能力，甚至使电路失效，芯片无法正常工作。因此，在供电网络瞬态分析的基础上我们必须对其进行优化，将各节点的电压噪声限定在允许的范围之内，并且使得供电网络占用的芯片面积资源尽可能少。With the substantial increase in chip density and operating frequency, the noise threshold of the power supply network is significantly reduced. The noise on the power supply network will reduce the driving ability of the device, and even make the circuit invalid, and the chip cannot work normally. Therefore, based on the transient analysis of the power supply network, we must optimize it, limit the voltage noise of each node within the allowable range, and make the chip area resources occupied by the power supply network as small as possible.

在标准单元布图模式下，电源/地线的拓扑结构一般采用网状(MESH)结构。在这种MESH的拓扑结构中，电源/地线可分为两种：预布线和“供电加强总线”。如图1所示。其中，预布线包括外围电源总线，供电压焊块和供电轨道。单元被放置在单元行上，通过供电轨道对它们进行供电。由于电路的规模越来越大，单靠供电轨道已经远远不能满足供电要求，因此，供电加强总线的概念被提出来以增加供电的可靠性和性能。In the standard unit layout mode, the topology of the power supply/ground wire generally adopts a mesh (MESH) structure. In this MESH topology, power/ground wires can be divided into two types: pre-wired and "power-enhanced bus". As shown in Figure 1. Among them, the pre-wiring includes peripheral power bus, power supply solder bumps and power supply rails. Units are placed on rows of units and they are powered via supply rails. As the scale of the circuit is getting larger and larger, the power supply rail alone is far from being able to meet the power supply requirements. Therefore, the concept of power supply strengthening bus is proposed to increase the reliability and performance of power supply.

首先，我们对电源/地线网络建立精确的RCL模型。如图2所示。考虑网络中的寄生电阻，电容和电感的影响，并将各电路模块的吸纳电流看作时变的电流源并将其分段线性表示(如图3和图4)。其次，我们将每个时钟周期分成若干个时间步长，在每个固定的时间点对网络进行求解，以得到每个节点的电压在时钟周期内的变化波形。上述过程就是对电源/地线网络进行瞬态分析的过程。针对基于标准单元设计的ASIC电路，考虑其电源网络的规整性特点，我们在先前的工作中构造并设计实现了精确、高效的基于等效电路的集成电路电源网络瞬态分析求解器，在不损失精确性与节约内存的前提下，大幅度提高了分析求解的速度，扩大了分析求解的芯片规模，对于处理大规模的芯片，得到迄今为止最好的结果。First, we build an accurate RCL model for the power/ground network. as shown inpicture 2. Consider the influence of parasitic resistance, capacitance and inductance in the network, and regard the sink current of each circuit module as a time-varying current source and express it segmentally and linearly (as shown in Figure 3 and Figure 4). Secondly, we divide each clock cycle into several time steps, and solve the network at each fixed time point to obtain the waveform of the voltage change of each node within the clock cycle. The above process is the process of performing transient analysis on the power/ground network. Considering the regularity of the power supply network of the ASIC circuit based on the standard cell design, we constructed and designed an accurate and efficient transient analysis solver for the integrated circuit power supply network based on the equivalent circuit in our previous work. Under the premise of losing accuracy and saving memory, the speed of analysis and solution has been greatly improved, and the scale of chips for analysis and solution has been expanded. For processing large-scale chips, the best results have been obtained so far.

在瞬态分析求解器的基础上，本发明中我们实现了一个通过添加去耦合电容对供电网络进行优化的快速算法。为了达到对供电网络进行优化的目的，目前应用最广泛的优化方法有三种。它们是网络拓扑结构的优化(topology optimization)，线宽优化(wire sizing)，和放置去耦合电容(decoupling capacitance deployment)。本发明着眼于在供电网络上添加去耦合电容这种降低供电网络中电压波动的有效方法。去耦合电容在供电网络中相当于局部的临时电压源，在器件的吸纳电流忽然增高或降低时，可以起到保持电压平稳的作用。由于去耦合电容占用了大量的芯片面积，因此还需要对去耦合电容的面积进行优化。On the basis of the transient analysis solver, we implement a fast algorithm for optimizing the power supply network by adding decoupling capacitors in the present invention. In order to achieve the purpose of optimizing the power supply network, there are three most widely used optimization methods at present. They are topology optimization, wire sizing, and decoupling capacitance deployment. The invention focuses on adding decoupling capacitors on the power supply network, which is an effective method for reducing voltage fluctuations in the power supply network. The decoupling capacitor is equivalent to a local temporary voltage source in the power supply network, and it can keep the voltage stable when the absorbing current of the device suddenly increases or decreases. Since the decoupling capacitor occupies a large amount of chip area, it is also necessary to optimize the area of the decoupling capacitor.

关于添加去耦合电容对供电网络进行优化，前人已经做了一些研究工作。有文献中提到添加去耦电容的电源/地线网络优化是一个电路模拟和调整布局的迭代过程。由于在芯片上添加去耦合电容需要占用芯片的面积，在很多情况下需要对已有的单元布局进行调整，为去耦电容腾出足够的放置空间。这样，优化过程就变成一个分析供电网络和调整芯片布局的迭代过程。有的工作中使用了电路灵敏度分析的方法确定去耦合电容的放置位置和大小，以此降低供电网络中的电压降。电路灵敏度分析可以分别在频域或时域中进行。频域的灵敏度分析避免了在各时间点上分别计算灵敏度，因此可以大大减少运算量，但时域到频域的转换及逆转换过程中会有精度的损失，所以频域分析的结果存在较大的误差。About adding decoupling capacitors to optimize the power supply network, predecessors have done some research work. It is mentioned in the literature that the power/ground network optimization of adding decoupling capacitors is an iterative process of circuit simulation and layout adjustment. Since adding a decoupling capacitor on the chip needs to occupy the area of the chip, in many cases it is necessary to adjust the existing unit layout to make enough space for the decoupling capacitor. In this way, the optimization process becomes an iterative process of analyzing the power supply network and adjusting the chip layout. In some work, the method of circuit sensitivity analysis is used to determine the placement position and size of the decoupling capacitor, so as to reduce the voltage drop in the power supply network. Circuit sensitivity analysis can be performed in frequency domain or time domain respectively. Sensitivity analysis in the frequency domain avoids calculating the sensitivity separately at each time point, so it can greatly reduce the amount of computation, but the conversion from the time domain to the frequency domain and the inverse conversion process will cause the loss of precision, so the results of the frequency domain analysis are relatively difficult. big error.

基于不同的布图模式的特点，前人也做了很多工作。有文献提到，在BBL布图模式下，采用线性规划的方法确定去耦合电容的放置位置，并用启发式方法在已确定的布局中插入空白模块来为添加去耦电容获得空间。也有文献将添加去耦合电容的供电网络优化方法应用于标准单元布图模式下的专用集成电路的设计。文中运用了伴随网络的方法求解灵敏度，并使用二次规划的方法对问题进行迭代求解。Based on the characteristics of different layout modes, predecessors have also done a lot of work. It is mentioned in the literature that in the BBL layout mode, the linear programming method is used to determine the placement position of the decoupling capacitor, and a heuristic method is used to insert a blank module in the determined layout to obtain space for adding a decoupling capacitor. There are also literatures that apply the power supply network optimization method of adding decoupling capacitors to the design of ASICs in the standard cell layout mode. In this paper, the method of adjoint network is used to solve the sensitivity, and the method of quadratic programming is used to solve the problem iteratively.

本领域前人已经做的工作中普遍存在一些问题，导致算法的时间和空间复杂度都较高，优化效果不尽人意，因此，不能应用于工业界实际的电源/地线网络优化工作。为了解决这些问题，本发明具有如下特点：There are generally some problems in the work done by predecessors in this field, which lead to high time and space complexity of the algorithm, and the optimization effect is not satisfactory. Therefore, it cannot be applied to the actual power/ground network optimization work in the industry. In order to solve these problems, the present invention has the following characteristics:

充分利用电源/地线网络结构上的特点，使用等效电路的方法，在求解节点电压方程的过程时降低了求解的规模，从而减少了运行时间和内存消耗，使时间和空间复杂度显著下降，同时优化质量也会提高。Make full use of the characteristics of the power/ground network structure and use the equivalent circuit method to reduce the scale of the solution when solving the node voltage equation, thereby reducing the running time and memory consumption, and significantly reducing the time and space complexity , and the optimization quality will increase.

罚函数法(Penalty Method)、等效电路(Equivalent Circuit)、共轭梯度法(Conjugate GradientMethod)和扩展特勒根伴随网络(Tellegen Adjoint Network)是本发明的四个主要组成部分。这四个方法有机的结合在一起，形成一个系统共同作用于电源/地线面积优化问题上，取得了很好的优化效果。Penalty Method (Penalty Method), Equivalent Circuit (Equivalent Circuit), Conjugate Gradient Method (Conjugate Gradient Method) and extended Tellegen Adjoint Network (Tellegen Adjoint Network) are four main components of the present invention. These four methods are organically combined to form a system to work together on the power/ground area optimization problem, and a good optimization effect has been achieved.

由于以上的特点，本发明具有优化大规模电路的能力并可以得到很好的优化效果。我们采用了工业界的实际电路作为测试实例。它可以在7.38个小时的时间内对具有超过一百万个节点的大电路进行优化。并且，优化后得到的放置去耦合电容的面积比启发式方法得到的面积小得多。Due to the above characteristics, the present invention has the ability to optimize large-scale circuits and can obtain good optimization effects. We have adopted the actual circuit in the industry as a test example. It can optimize large circuits with over one million nodes in 7.38 hours. Moreover, the optimized area for placing the decoupling capacitor is much smaller than the area obtained by the heuristic method.

发明内容Contents of the invention

本发明设计了一种高效的集成电路电源网络优化算法，利用存在于标准单元布局之中的空白区域添加附加的片上去耦合电容，起到对供电网络进行优化的目的。非线性规划方法在解空间内搜索最优解；等效电路的方法通过合并供电网络中存在的大量中间节点，大大降低了电路求解的规模，使求解和优化的速度显著提高；扩展特勒根伴随网络法的应用使得在迭代的每一步，只需求解原始网络和扩展特勒根网络各一次就可获得罚函数关于电导向量的梯度，节省了大量的运行时间；共轭梯度法在众多无约束优化方法当中只需要很少的内存资源，而其收敛速度又比较快。本发明基于这四种方法实现的优化算法获得了很好的优化效果。The invention designs an efficient integrated circuit power supply network optimization algorithm, and uses the blank area in the standard unit layout to add additional on-chip decoupling capacitors to achieve the purpose of optimizing the power supply network. The nonlinear programming method searches for the optimal solution in the solution space; the equivalent circuit method greatly reduces the scale of the circuit solution by merging a large number of intermediate nodes in the power supply network, and significantly improves the speed of solution and optimization; The application of the adjoint network method makes it necessary to solve the original network and the extended tellegen network once each in each iteration step to obtain the gradient of the penalty function with respect to the conductance vector, which saves a lot of running time; the conjugate gradient method is used in many infinite The constrained optimization method requires very little memory resources, and its convergence speed is relatively fast. The optimization algorithm realized by the present invention based on these four methods has obtained good optimization effect.

关于建立原网络的伴随网络做以下解释。算法过程中我们需要对原网络建立对应于所有违反约束点的一系列伴随网络。例如，i为一个违反电压降约束的节点，建立对应于i节点的伴随网络，即其他节点的电流源开路，i节点的电流源激励取E_i(t)(E_i(t)的定义参见说明书第七页)。求解该伴随网络得到各节点的电压值，从而可以求得i节点的电压值相对于所有去耦合电容的梯度值。其它违反约束点比如p，q节点等同理。这些梯度值再应用于求目标函数相对于各去耦合电容的梯度值。这样就需要求解多个伴随网络。我们通过对各节点的电流源激励做一些变换，使得求解一次伴随网络就可以得到目标函数相对于所有去耦电容的梯度值。关于伴随网络方法可以参考以下文献：(1)L.O.Chua and P.M.Lin，Computer-Aided Analysis ofElectronic Circuits，Englewood Clifss：Prentice-Hall，Inc.1975.(2)任艮、甘淑贞，“电路的计算机辅助分析与设计”，北京理工大学出版社，1989。Regarding the establishment of the accompanying network of the original network, the following explanation is made. In the algorithm process, we need to establish a series of adjoint networks corresponding to all violation points for the original network. For example, i is a node that violates the voltage drop constraint, and the adjoint network corresponding to node i is established, that is, the current sources of other nodes are open, and the current source excitation of node i is E_i (t) (for the definition of E_i (t), see Instructions on page 7). The voltage value of each node is obtained by solving the adjoint network, so that the gradient value of the voltage value of the i node relative to all decoupling capacitors can be obtained. The same is true for other violation points such as p and q nodes. These gradient values are then applied to obtain the gradient values of the objective function with respect to the respective decoupling capacitors. This requires solving multiple adjoint networks. We make some changes to the current source excitation of each node, so that the gradient value of the objective function relative to all decoupling capacitors can be obtained by solving the adjoint network once. Regarding the adjoint network method, you can refer to the following literature: (1) LOChua and PMLin, Computer-Aided Analysis of Electronic Circuits, Englewood Clifss: Prentice-Hall, Inc. 1975. (2) Ren Gen, Gan Shuzhen, "Computer-Aided Analysis and Design of Circuits ", Beijing Institute of Technology Press, 1989.

1.用去耦合电容实现集成电路供电网络噪声优化的快速方法，含有用放置去耦合电容于布图空白面积中以提高供电网络可靠性的步骤，其特征在于，它是一种利用计算机针对基于标准单元布图模式的专用集成电路(ASIC)的布图结构特点及其供电网络的结构特点，将用以保持节点电压平稳的去耦合电容的面积作为优化的目标，采用非线性规划的方法对供电网络噪声优化问题进行有效求解的方法，它把罚函数法、等效电路、共轭梯度法和扩展特勒根伴随网络的方法形成一个整体共同作用于电源/地线网络优化上，取得很好的优化效果；具体而言，它依次含有以下步骤：1. realize the fast method of integrated circuit power supply network noise optimization with decoupling capacitance, contain the step of improving power supply network reliability with placing decoupling capacitance in the blank area of layout, it is characterized in that, it is a kind of utilizing computer to target based on The layout structure characteristics of the application-specific integrated circuit (ASIC) in the standard cell layout mode and the structure characteristics of the power supply network, the area of the decoupling capacitor used to keep the node voltage stable is taken as the optimization goal, and the non-linear programming method is used to optimize the The method of effectively solving the noise optimization problem of the power supply network, which combines the penalty function method, the equivalent circuit method, the conjugate gradient method and the method of the extended Tellegen adjoint network into a whole to work together on the power/ground network optimization, has achieved great results. A good optimization effect; specifically, it consists of the following steps in order:

(1)计算机读入包含供电网络信息和单元布局信息的文件：供电网络信息包括供电网络节点之间的关联结构；节点之间的电阻值、电感值、电感初始电压和电流值、片上固有去耦合电容值(单元模块静止时表现出的电容特性)、电容初始电压和电流值以及各个节点连接的单元模块随时间变化的吸纳电流波形(利用PWL表示)，据此在计算机内建立电路的信息，并且标记所有中间点(Middle Node)和交汇点(Cross Node)；单元布局信息包括每个单元行中的单元数目、单元坐标以及单元之间的相对位置关系，根据这些信息，我们可以得到单元之间的空白面积的信息和各单元行上空白面积的分布情况，附加的去耦合电容就添加在这些空白区域上；(1) The computer reads in the file containing the power supply network information and unit layout information: the power supply network information includes the correlation structure between the nodes of the power supply network; Coupling capacitance value (capacitance characteristics exhibited by the unit module when it is stationary), initial capacitance voltage and current value, and the absorbing current waveform (expressed by PWL) of the unit module connected to each node over time, based on which the circuit is established in the computer. , and mark all the middle points (Middle Node) and intersection point (Cross Node); the unit layout information includes the number of units in each unit row, unit coordinates and the relative positional relationship between units, according to this information, we can get the unit The information of the blank area between and the distribution of the blank area on each cell row, additional decoupling capacitors are added to these blank areas;

(2)利用输入的参数信息对供电网络进行基于等效电路的瞬态分析，得到每个节点的电压波形；(2) Use the input parameter information to perform transient analysis on the power supply network based on the equivalent circuit, and obtain the voltage waveform of each node;

(3)若各节点的电压没有违反约束的情况出现，则不需对供电网络做优化；(3) If the voltage of each node does not violate the constraints, there is no need to optimize the power supply network;

否则执行以下步骤：Otherwise perform the following steps:

(4)将各节点的电压波形分段线性纪录，用于优化过程中梯度的计算；(4) The voltage waveform of each node is linearly recorded in segments, which is used for the calculation of the gradient in the optimization process;

(5)确定优化的目标函数为添加的去耦电容的面积，在对应的约束条件下求最小值：(5) Determine the optimized objective function as the area of the added decoupling capacitor, and find the minimum value under the corresponding constraints:

$min min A A = = \underset{j j &Element; &Element; M m}{Σ Σ} (({w w}_{j j} \times \times H h)) - - - - - - - - - - - - ((11)),,$

M是允许添加去耦合电容的节点集合，M＝{1，...，m)，MN；N为供电网络中所有节点的集合，N＝{1，...，n}；H是标准单元的高，w_j是添加在节点j上的去耦电容c_j的宽度；M is the node set that allows adding decoupling capacitors, M={1,...,m), MN; N is the set of all nodes in the power supply network, N={1,...,n}; H is the height of the standard cell, w_j is the width of the decoupling capacitor c_j added on node j;

约束条件如下：The constraints are as follows:

(5.1)电压降约束：(5.1) Voltage drop constraints:

即各节点相对于电源电压的电压降，用能有效衡量电压降噪声的量值，即每个节点上低于电压阈值的电压部分的积分值S_i表示：That is, the voltage drop of each node relative to the power supply voltage is expressed by the value that can effectively measure the voltage drop noise, that is, the integral value S_i of the voltage part below the voltage threshold on each node:

${s the s}_{i i} = = {&Integral; &Integral;}_{00}^{T T} max max (({V V}_{min min} - - {v v}_{i i} ((t t)),, 00)) dt dt = = {&Integral; &Integral;}_{{t t}_{11}}^{{t t}_{22}} (({V V}_{min min} - - {v v}_{i i} ((t t)))) dt dt - - - - - - - - - - - - ((22)),,$

[t₁，t₂]为i节点违反电压降约束的时间区间，V_min为电压阈值，v_i(t)为i节点的电压值；[t₁ , t₂ ] is the time interval during which node i violates the voltage drop constraint, V_min is the voltage threshold, and v_i (t) is the voltage value of node i;

(5.2)电迁移约束：(5.2) Electromigration constraints:

用[t’₁，t’₂]时间内，供电网络分支(p，q)两端节点电压差的绝对值和工艺允许的最大电流密度为σ时在分支长度l_qp上的电压降之差的积分值来表示：In [t'₁ , t'₂ ] time, the difference between the absolute value of the node voltage difference at both ends of the power supply network branch (p, q) and the voltage drop on the branch length l_qp when the maximum current density allowed by the process is σ Integral value to represent:

${u u}_{p p,, q q} = = {&Integral; &Integral;}_{00}^{T T} max max [[((| | {v v}_{p p} ((t t)) - - {v v}_{q q} ((t t)) | | - - {ρl ρl}_{p p,, q q} σ σ)),, 00]] dt dt = = {&Integral; &Integral;}_{{t t}^{' '}_{11}}^{{t t}^{' '}_{22}} ((| | {v v}_{p p} ((t t)) - - {v v}_{q q} ((t t)) | | - - {ρl ρl}_{p p,, q q} σ σ)) dt dt - - - - - - - - - - - - ((33)),,$

其中，v_p和v_q分别是电源分枝(P，q)两端节点的电压，v_p-v_q即该分枝上的电压差；ρ是方块电阻；l_pq是分枝(p，q)的长度；Among them, v_p and v_q are the voltages of the nodes at both ends of the power supply branch (P, q) respectively, and v_p -v_q is the voltage difference on the branch; ρ is the sheet resistance; l_pq is the branch (p, q the length of q);

(5.3)去耦电容面积约束：(5.3) Decoupling capacitor area constraints:

即每单元行中，添加的去耦电容面积小于等于本单元行中的空白面积，而单元行的高度H是定值，因此可直接用宽度表示面积大小：That is, in each unit row, the area of the added decoupling capacitor is less than or equal to the blank area in the unit row, and the height H of the unit row is a fixed value, so the area size can be directly expressed by the width:

${dw dw}_{r r} = = max max ((\underset{j j &Element; &Element; ND ND ((r r))}{Σ Σ} {w w}_{r r,, y the y} - - {rw rw}_{r r},, 00)),, r r &Element; &Element; NR NR,, - - - - - - - - - - ((44)),,$

NR是单元行的集合；ND(r)是第r行中去耦电容的位置集合；w_r，y是指位于第r行y位置的去耦电容的宽度；rw_r是第r行上的空白面积的总宽度；dw_r是第r行上违反去耦电容面积约束的惩罚量，将在后面的罚函数法中应用；NR is the set of cell rows; ND(r) is the position set of decoupling capacitors in the rth row; w_{r, y} refers to the width of the decoupling capacitor at the y position of the rth row; rw_r is the r row The total width of the blank area; dw_r is the penalty amount for violating the decoupling capacitor area constraint on the rth line, which will be applied in the penalty function method later;

(5.4)去耦电容最大宽度约束：(5.4) The maximum width constraint of the decoupling capacitor:

在某单元行中添加的任意一个去耦电容的宽度小于或等于本行中最大空白面积的宽度；The width of any decoupling capacitor added in a cell row is less than or equal to the width of the largest blank area in the row;

ew_r，y＝max(w_r，y-rw_r，0)，r∈NR，y∈ND(r)，——(5)，ew_{r, y} = max(w_{r, y} − rw_r , 0), r∈NR, y∈ND(r),——(5),

ew_r，y是第r行第y个位置上违反去耦电容最大宽度约束的惩罚量，将在后面的罚函数法中应用；ew_{r, y} is the penalty amount for violating the maximum width constraint of the decoupling capacitor at the yth position of the rth row, which will be applied in the penalty function method later;

(6)构造罚函数f，将非线性约束优化问题转化为无约束优化问题：(6) Construct a penalty function f to transform the nonlinear constraint optimization problem into an unconstrained optimization problem:

$min min f f = = A A + + {p p}_{t t}$

$= = A A + + α α \cdot \cdot ((\underset{i i &Element; &Element; N N}{Σ Σ} {s the s}_{i i}^{22} + + \underset{((p p,, q q)) &Element; &Element; B B}{Σ Σ} {u u}_{} {pq pq}_{22} + + \underset{r r &Element; &Element; NR NR}{Σ Σ} {dw dw}_{} {r r}_{22} + + \underset{r r &Element; &Element; NR NR,, y the y &Element; &Element; ND ND ((r r))}{Σ Σ} {ew ew}_{r r,, y the y}^{22})),, - - - - - - - - - - - - ((66)),,$

其中，A是去耦电容总面积，B是电源网络中所有分枝的集合，P_t是罚项，α为罚因子；Among them, A is the total area of the decoupling capacitor, B is the set of all branches in the power network, P_t is the penalty item, and α is the penalty factor;

(7)设置罚因子α的初始值；每个可添加去耦电容的位置上的去耦电容初始值都设为允许的最小电容宽度，得到电容宽度向量作为下面无约束优化的初始解；另外给出误差限ε₁＞0：(7) Set the initial value of the penalty factor α; the initial value of the decoupling capacitor at each position where a decoupling capacitor can be added is set to the minimum allowed capacitor width, and the capacitor width vector is obtained as the initial solution of the unconstrained optimization below; in addition Gives the margin of error ε₁ >0:

(8)求解当前无约束优化问题，得到当前最优解电容宽度向量W^(l)；(8) solve current unconstrained optimization problem, obtain current optimal solution capacitance width vector W^(l) ;

(8.1)设当前无约束优化问题的初始解为电容宽度向量W⁽⁰⁾，误差限为ε₂＞0；(8.1) Suppose the initial solution of the current unconstrained optimization problem is the capacitance width vector W⁽⁰⁾ , and the error limit is ε₂ >0;

(8.2)初始优化方向设为罚函数关于电容宽度向量W⁽⁰⁾的负梯度方向：(8.2) The initial optimization direction is set to the negative gradient direction of the penalty function about the capacitance width vector W⁽⁰⁾ :

设初始优化方向为P⁽⁰⁾，梯度方向为f(W⁽⁰⁾)，Let the initial optimization direction be P⁽⁰⁾ and the gradient direction be f(W⁽⁰⁾ ),

得P⁽⁰⁾＝-f(W⁽⁰⁾) -(7)，Get P⁽⁰⁾ =-f(W⁽⁰⁾ )-(7),

(8.3)用扩展的伴随网络法求罚函数相对于电容宽度向量的梯度：(8.3) Find the gradient of the penalty function relative to the capacitance width vector with the extended adjoint network method:

$&dtri; &dtri; f f ((W W)) = = {[[\frac{&PartialD; &PartialD; f f}{{&PartialD; &PartialD; w w}_{11}},, \frac{&PartialD; &PartialD; f f}{&PartialD; &PartialD; {w w}_{22}},, \cdot \cdot \cdot &Center Dot; \cdot \cdot,, \frac{&PartialD; &PartialD; f f}{{&PartialD; &PartialD; w w}_{j j}},, \cdot \cdot \cdot \cdot \cdot \cdot,, \frac{&PartialD; &PartialD; f f}{{&PartialD; &PartialD; w w}_{m m}}]]}^{T T},, j j &Element; &Element; Ν Ν - - - - - - - - - - - - ((88)),,$

宽度为w_j的电容c_j连接在供电网络的节点j上，假设节点j位于第r_j行的y_j位置，则罚函数f相对于w_j的偏导数可以表示为：Capacitor c_j with width w_j is connected to node j of the power supply network, assuming node j is located at position y_j of row r_j , then the partial derivative of penalty function f with respect to w_j can be expressed as:

$\frac{&PartialD; &PartialD; f f}{&PartialD; &PartialD; {w w}_{j j}} = = H h + + 22 α α (({dw dw}_{rj r j} + + {ew ew}_{rj r j,, yj yj})) + + 22 α α [[\underset{i i &Element; &Element; N N}{Σ Σ} {s the s}_{i i} \frac{&PartialD; &PartialD; {s the s}_{i i}}{{&PartialD; &PartialD; w w}_{j j}} + + \underset{((p p,, q q)) &Element; &Element; B B}{Σ Σ} {u u}_{pq pq} \frac{{&PartialD; &PartialD; u u}_{pq pq}}{&PartialD; &PartialD; {w w}_{j j}}]],, - - - - - - ((99)),,$

fj∈NR，yj∈ND(rj)fj ∈ NR, yj ∈ ND(rj)

根据电容大小和宽度的关系：According to the relationship between capacitance size and width:

$c c = = \frac{{ϵ ϵ}_{ox ox}}{{T T}_{ox ox}} \times \times w w \times \times H h - - - - - - - - - - - - ((1010)),,$

ε_ox和T_ox分别是门氧化层的介电常数和厚度；ε_ox and T_ox are the dielectric constant and thickness of the gate oxide layer, respectively;

得 $\frac{&PartialD; f}{{&PartialD; w}_{j}} = H + 2 α ({dw}_{rj} + {ew}_{rj, yj}) + \frac{{2 αϵ}_{ox} H}{T_{ox}} [\underset{i &Element; N}{Σ} s_{i} \frac{&PartialD; s_{i}}{&PartialD; c_{j}} + \underset{(p, q) &Element; B}{Σ} u_{pq} \frac{{&PartialD; u}_{pq}}{&PartialD; c_{j}}] - - - - - (11),$ have to $\frac{&PartialD; f}{{&PartialD; w}_{j}} = h + 2 α ({dw}_{r j} + {ew}_{r j, yj}) + \frac{{2 αϵ}_{ox} h}{T_{ox}} [\underset{i &Element; N}{Σ} {the s}_{i} \frac{&PartialD; {the s}_{i}}{&PartialD; c_{j}} + \underset{(p, q) &Element; B}{Σ} u_{pq} \frac{{&PartialD; u}_{pq}}{&PartialD; c_{j}}] - - - - - (11),$

rj∈nr，yj∈ND(rj)rj ∈ nr, yj ∈ ND(rj)

通过对原电路网络建立对应电路中各节点的一系列伴随网络，并作电路灵敏度分析后，得到：By establishing a series of adjoint networks corresponding to each node in the original circuit network, and after analyzing the sensitivity of the circuit, we get:

$\frac{&PartialD; &PartialD; {s the s}_{i i}}{&PartialD; &PartialD; {c c}_{j j}} = = {&Integral; &Integral;}_{00}^{T T} {v v}_{j j,, {E E.}_{i i}}^{' '} ((t t)) \times \times {\overset{. .}{v v}}_{j j} ((T T - - t t)) dt dt - - - - - - - - - - ((1212)),,$

$\frac{&PartialD; &PartialD; {u u}_{pq pq}}{&PartialD; &PartialD; {c c}_{j j}} = = {&Integral; &Integral;}_{00}^{T T} {v v}_{j j,, {t t}_{pq pq}}^{' '} ((t t)) \times \times {\overset{. .}{v v}}_{j j} ((T T - - t t)) dt dt - - - - - - - - - - ((1313)),,$

$= = {&Integral; &Integral;}_{00}^{T T} [[{v v}_{j j,, {E E.}_{p p}}^{' '} ((t t)) - - {v v}_{j j,, {E E.}_{p p}}^{' '} ((t t))]] \times \times {\overset{. .}{v v}}_{j j} ((T T - - t t)) dt dt$

其中， ${\dot{v}}_{j} (T - t) = \frac{{dv}_{j} (T - t)}{dt}$ 是原电路网络中j节点的电压对时间t的导数；v′_j，Ei(t)是对应于节点i建立的伴随网络中j节点的电压(v′_j，Ep(t)，v′_j，Eq(t)同理)，它可以表示如下：in, ${\dot{v}}_{j} (T - t) = \frac{{dv}_{j} (T - t)}{dt}$ is the voltage derivative of node j in the original circuit network with respect to time t; v′_{j, Ei} (t) is the voltage of node j in the accompanying network established corresponding to node i (v′_{j, Ep} (t), v′_{j , Eq} (t) is the same), it can be expressed as follows:

${v v}_{j j,, {E E.}_{i i}}^{' '} ((t t)) = = Z Z ((j j)) {v v}_{{E E.}_{i i}}^{' '} ((t t)) = = Z Z ((j j)) {G G}^{- - 11} [[{E E.}_{i i} ((t t)) + + {EC EC}_{i i} ((t t)) + + {EL EL}_{i i} ((t t))]] - - - - - - - - - - ((1414)),,$

其中，Z(j)是一个位置选择向量，该向量除了j位置上的元素取值为1，其它元素全部为0，即Z(j)＝[0，0，…，0，1，0，…，0]；Among them, Z(j) is a position selection vector, the value of the vector is 1 except for the element at position j, and all other elements are 0, that is, Z(j)=[0,0,...,0,1,0, ...,0];

G是节点电压方程组G*V＝I中的关系矩阵；G is the relationship matrix in the node voltage equation group G*V=I;

E_i(t)是电流源向量，它的值是除节点i对应的元素值之外，其余的元素值全部为0，节点i对应的元素值当该节点违反电压降约束时为-1，当该节点不违反约束时为0；E_i (t) is the current source vector, its value is all 0 except the element value corresponding to node i, and the element value corresponding to node i is -1 when the node violates the voltage drop constraint, 0 when the node does not violate the constraint;

EG_i(t)和EL_i(t)是对应于节点i建立的伴随网络中的电容和电感元素做等效后得到的电流源向量；EG_i (t) and EL_i (t) are the current source vectors obtained after equivalent capacitance and inductance elements in the accompanying network established corresponding to node i;

于是得到：So get:

$\underset{i i &Element; &Element; N N}{Σ Σ} {s the s}_{i i} \frac{&PartialD; &PartialD; {s the s}_{i i}}{&PartialD; &PartialD; {c c}_{j j}} + + \underset{((p p,, q q)) &Element; &Element; B B}{Σ Σ} {u u}_{pq pq} \frac{&PartialD; &PartialD; {u u}_{pq pq}}{&PartialD; &PartialD; {c c}_{j j}}$

$= = \underset{i i &Element; &Element; N N}{Σ Σ} {s the s}_{i i} (([[{&Integral; &Integral;}_{00}^{T T} {v v}_{j j,, {E E.}_{i i}}^{' '} ((t t)) \times \times {\overset{. .}{v v}}_{j j} ((T T - - t t)) dt dt)) + + \underset{((p p,, q q)) &Element; &Element; B B}{Σ Σ} {u u}_{pq pq} (({&Integral; &Integral;}_{00}^{T T} [[{v v}_{j j,, {E E.}_{i i}}^{' '} ((t t)) - - {v v}_{j j,, {E E.}_{i i}}^{' '} ((t t))]] \times \times {\overset{. .}{v v}}_{j j} ((T T - - t t)) dt dt)) - - - - - - - - ((1515)),,$

${= = &Integral; &Integral;}_{00}^{T T} {{{\overset{. .}{v v}}_{j j} ((T T - - t t)) \times \times {{\underset{i i &Element; &Element; N N}{Σ Σ} (({s the s}_{i i} \times \times {v v}_{j j,, {E E.}_{i i}}^{' '} ((t t)))) + + \underset{((p p,, q q)) &Element; &Element; B B}{Σ Σ} {{{u u}_{pq pq} \times \times [[{v v}_{j j,, {E E.}_{p p}}^{' '} ((t t)) - - {v v}_{j j,, {E E.}_{p p}}^{' '} ((t t))]]}}}}}} dt dt$

依据式(14)，(15)得到：According to formula (14), (15) get:

$\underset{i i &Element; &Element; N N}{Σ Σ} {s the s}_{i i} \frac{&PartialD; &PartialD; {s the s}_{i i}}{{&PartialD; &PartialD; c c}_{j j}} + + \underset{((p p,, q q)) &Element; &Element; B B}{Σ Σ} {u u}_{pq pq} \frac{{&PartialD; &PartialD; u u}_{pq pq}}{&PartialD; &PartialD; {c c}_{j j}} = = Z Z ((j j)) {G G}^{- - 11} {I I}_{total total} ((t t)) - - - - - - - - - - - - ((1616)),,$

其中I_total＝I_new(t)+EC(t)+EL(t) ——(17)，Wherein I_total = I_new (t) + EC (t) + EL (t) - (17),

${I I}_{new new} ((t t)) = = \underset{i i &Element; &Element; N N}{Σ Σ} [[{s the s}_{i i} \times \times {E E.}_{i i} ((t t))]] + + \underset{((p p,, q q)) &Element; &Element; B B}{Σ Σ} {{{u u}_{pq pq} \times \times [[{E E.}_{p p} ((t t)) - - {E E.}_{q q} ((t t))]]}} - - - - - - - - ((1818)),,$

其中，EC(t)和EL(t)是将I_new作为伴随网络的电流激励时，电容和电感元素做等效后得到的电流源向量；Among them, EC(t) and EL(t) are the current source vectors obtained after the capacitance and inductance elements are equivalent when I_new is used as the current excitation of the accompanying network;

从而得到：and thus get:

$\frac{&PartialD; &PartialD; f f}{{&PartialD; &PartialD; w w}_{j j}} = = H h + + 22 α α (({dw dw}_{rj r j} + + {ew ew}_{rj r j,, yj yj})) + + \frac{{22 αϵ αϵ}_{ox ox} H h}{{T T}_{ox ox}} {&Integral; &Integral;}_{00}^{T T} {{[[Z Z ((j j)) \times \times {G G}^{- - 11} \times \times {I I}_{total total} ((t t))]] \times \times {\overset{. .}{v v}}_{j j} ((T T - - t t))}} dt dt - - - - - - - - ((1919)),,$

rj∈NR，yj∈ND(rj)，j∈Mrj ∈ NR, yj ∈ ND(rj), j ∈ M

(8.4)设迭代已经进行到了第k步，当前电容宽度向量和优化方向分别是为w^(k)和P^(k)，沿P^(k)进行一维搜索，找到非负一维搜索因子λ_k，使罚函数在P^(k)方向上达到最优，即：(8.4) Assuming that the iteration has reached the kth step, the current capacitor width vector and optimization direction are w^(k) and P^(k) respectively, conduct a one-dimensional search along P^(k) , and find a non-negative one-dimensional search factor λ_k , making the penalty function optimal in the direction of P^(k) , that is:

f(W^(k)+λ_kP^(k))＝minf(W^(k)+λP^(k)) ——(20)，f(W^(k) +_λkP^(k) )=minf(W^(k) +λP^(k) )——(20),

(8.5)根据下式更新电容宽度向量W^(k+l)：(8.5) Update the capacitance width vector W^(k+l) according to the following formula:

W^(k+1)＝W^(k)+λ_kP^(k) ——(21)，W^(k+1) =W^(k) +_λkP^(k) ——(21),

(8.6)如果‖f(W^(k+1))‖＜ε₂，本次无约束优化结束退出，转步骤9；(8.6) If ‖f(W^(k+1) )‖<ε₂ , exit this unconstrained optimization and go to step 9;

否则设电容宽度向量的维数是m，Otherwise, let the dimension of the capacitor width vector be m,

如果k＝m，则W⁽⁰⁾＝W^(k+1)，f(G⁽⁰⁾)＝f(G^(k+1))，转向步骤8.2；If k=m, then W⁽⁰⁾ = W^(k+1) , f(G⁽⁰⁾ ) = f(G^(k+1) ), turn to step 8.2;

如果k＜m，根据下式更新优化方向，回到步骤8.4继续优化；If k<m, update the optimization direction according to the following formula, and return to step 8.4 to continue the optimization;

(9)根据优化结果计算罚项的值，如果p_t＜ε₁，当前电容宽度向量即是所求最优解，算法结束退出；否则更新罚因子α，设l＝l+1，回到步骤8继续优化；(9) Calculate the value of the penalty item according to the optimization result. If p_t <ε₁ , the current capacitance width vector is the optimal solution, and the algorithm ends and exits; otherwise, update the penalty factor α, set l=l+1, and return to Step 8 continues to optimize;

(10)由于实际可以添加的去耦电容值不是连续的，具有最小单位数值的限制，我们对最终得到的优化结果进行调整；若某位置添加的去耦电容值小于最小数值则将其合并到邻近的节点上，以形成较大的电容，并将这些电容调整为最小单位数值的倍数；(10) Since the actual decoupling capacitor value that can be added is not continuous and has the limitation of the minimum unit value, we adjust the final optimization result; if the decoupling capacitor value added at a certain position is less than the minimum value, it will be merged into adjacent nodes to form larger capacitances and adjust these capacitances to multiples of the smallest unit value;

其中，i节点代表网络中违反电压降约束的任意节点。p，q节点代表违反电流密度约束的分支的两端节点。j节点代表网络中可以添加去耦合电容的任意节点。我们在计算目标函数相对于j节点上添加的去耦合电容大小的梯度值时，由于目标函数与s_i和t_pq有关，所以计算梯度时需要用到i，p，q节点的电压等参数。j节点的位置与i，p，q节点的位置没有关系。Among them, i-node represents any node in the network that violates the voltage drop constraint. The p, q nodes represent the nodes at both ends of the branch that violates the current density constraint. Node j represents any node in the network where decoupling capacitors can be added. When we calculate the gradient value of the objective function relative to the decoupling capacitor added on node j, since the objective function is related to s_i and t_pq , parameters such as the voltage of nodes i, p, and q need to be used when calculating the gradient. The position of the j node has no relationship with the positions of the i, p, q nodes.

将整个供电网络中的节点进行编号，共有n个节点。去耦合电容c_j位于供电网络的j节点位置，j∈M.M是允许添加去耦合电容的节点集合，M＝{1，...，m}，MN；N为供电网络中所有节点的集合，N＝{1，...，n}；同时j节点又位于供电网络中第rj行的yj位置，其中，yj是rj行内的节点编号，与j不同。The nodes in the entire power supply network are numbered, and there are n nodes in total. The decoupling capacitor c_j is located at node j of the power supply network, j∈MM is the set of nodes that allow adding decoupling capacitors, M={1,...,m}, MN; N is the number of nodes in the power supply network Set, N={1,...,n}; at the same time, node j is located at position yj of row rj in the power supply network, where yj is the node number in row rj, which is different from j.

在描述去耦电容面积约束条件时，用r行y位置表示了所有添加了去耦合电容的位置，是一种表示方法，不特指某一个去耦合电容的位置。而rj行yj位置是添加在节点j上的去耦电容c_j的确切位置。When describing the constraints on the area of decoupling capacitors, the r row y position is used to represent all the positions where decoupling capacitors are added, which is a representation method and does not specifically refer to the position of a certain decoupling capacitor. And the rj row yj position is the exact position of the decoupling capacitor c_j added on the node j.

实验证明，本发明所提出的方法优化速度快，优化结果优，并且节省计算机的内存，具有优化大规模电路的能力。Experiments prove that the method proposed by the invention has fast optimization speed, excellent optimization results, saves computer memory, and has the ability to optimize large-scale circuits.

附图说明：Description of drawings:

图1：集成电路的电源线网模型，Figure 1: Power line network model of an integrated circuit,

1-供电环，1-Power supply ring,

2-供电加强总线，2- Power supply strengthens the bus,

3-供电轨，3-supply rail,

4-标准单元模块(cell)。4-Standard unit module (cell).

图2：电源线网络的RLC分析模型。Figure 2: RLC analysis model of a power line network.

图3：单元吸纳电流的时变电流源模型。Figure 3: Time-varying current source model for cell sink current.

图4：时变电流源的分段线性表示。Figure 4: Piece-wise linear representation of a time-varying current source.

图5：供电网络节点的电压波形以及违反约束的情况。Figure 5: Voltage waveforms at nodes of the supply network and constraints violations.

图6：求罚函数相对电容宽度向量的梯度时，伴随网络中i节点上的电流激励。Figure 6: Finding the gradient of the penalty function with respect to the capacitance width vector, with the current excitation on node i in the adjoint network.

图7：添加去耦电容后的芯片布局，Figure 7: Chip layout after adding decoupling capacitors,

5-标准单元模块(cell)，5-standard cell module (cell),

6-去耦合电容(deccp)。6-Decoupling capacitor (deccp).

图8：本发明的主程序流程图。Fig. 8: The main program flow chart of the present invention.

图9：本发明中用到的求解无约束优化问题的程序流程图。Fig. 9: A flow chart of a program for solving an unconstrained optimization problem used in the present invention.

图10：对实例u_cnt100进行瞬态分析后得到的结果，存在91个违规点。图中的白色节点即违规点。Figure 10: The results obtained after the transient analysis of the instance u_cnt100, there are 91 violation points. The white nodes in the figure are the violation points.

图11：实例u_cnt100优化后最终得到的单元布局和去耦合电容分布情况。Figure 11: The final cell layout and decoupling capacitor distribution obtained after optimization of the example u_cnt100.

具体实施方式：Detailed ways:

用工业界提供的def，1ef格式的测试电路例子u_cnt100做实例结合图8用本发明的方法进行添加去耦合电容的优化。Use the test circuit example u_cnt100 in def and 1ef formats provided by the industry as an example in conjunction with FIG. 8 to optimize the addition of decoupling capacitors with the method of the present invention.

1.读入文件——包含库单元信息的u_cnt100.lef，包含单元互连信息的u_cnt100.def，参数文件power.params和包含吸纳电流信息的文件current.dat。根据读入的信息建立电路的结构；1. Read in files - u_cnt100.lef containing library unit information, u_cnt100.def containing unit interconnection information, parameter file power.params and file current.dat containing sink current information. Establish the structure of the circuit according to the information read in;

2.对建立的供电网络进行基于等效电路的瞬态分析，得到网络上806个节点的电压波形；2. Transient analysis based on the equivalent circuit is carried out on the established power supply network, and the voltage waveforms of 806 nodes on the network are obtained;

3.对此供电网络进行瞬态分析的结果是存在91个违反约束点，如图10所示，需要对该网络进行添加去耦合电容的优化；3. The result of transient analysis of this power supply network is that there are 91 violation points, as shown in Figure 10, it is necessary to optimize the network by adding decoupling capacitors;

4.将744个叶子节点上的电压波形分段线性记录，用于优化过程中梯度的计算；4. The voltage waveforms on the 744 leaf nodes are segmented and linearly recorded for gradient calculation during the optimization process;

5.确定优化目标和约束条件；5. Determine the optimization goals and constraints;

6.构造罚函数，将非线性约束优化问题转化为无约束优化问题；6. Construct a penalty function to transform the nonlinear constrained optimization problem into an unconstrained optimization problem;

7.设置罚因子初始值为α＝2；在每个可添加去耦合电容的位置上，也就是叶子节点的位置上将去耦合电容的初始值设为允许的最小电容宽度，在本例子中是最小单元宽度的三分之一，得到电容宽度向量作为初始解；给出误差限ε₁＝1e-6；7. Set the initial value of the penalty factor to α=2; set the initial value of the decoupling capacitor to the allowable minimum capacitance width at each position where a decoupling capacitor can be added, that is, the position of the leaf node, in this example is one-third of the minimum unit width, and the capacitance width vector is obtained as the initial solution; the error limit ε₁ =1e-6 is given;

8.设本次无约束优化问题的求解为第l次，求解当前无约束优化问题，得到当前最优解电容宽度向量W^(l)；8. Let the solution of this unconstrained optimization problem be the lth time, solve the current unconstrained optimization problem, and obtain the current optimal solution capacitance width vector W^(l) ;

8.1设初始解为W⁽⁰⁾，误差限为ε₂＝1e-2；8.1 Let the initial solution be W⁽⁰⁾ and the error limit be ε₂ =1e-2;

8.2初始优化方向设为罚函数关于电容宽度向量的负梯度方向；8.2 The initial optimization direction is set to the negative gradient direction of the penalty function about the capacitance width vector;

8.3建立原供电网络的伴随网络，具体方法是伴随网络的拓扑结构与原网络相同；各电阻、电容和电感支路保持不变；原有的独立电压源短路，独立电流源开路；各叶子节点上的电流激励如图6所示取值。对伴随网络进行瞬态求解，得到各节点上的电压波形，结合原网络求解得到的各节点电压波形，带入公式19中解出罚函数对于电容宽度向量的梯度；8.3 Establish the accompanying network of the original power supply network. The specific method is that the topology of the accompanying network is the same as that of the original network; the resistance, capacitance and inductance branches remain unchanged; the original independent voltage source is short-circuited, and the independent current source is open; each leaf node The current excitation above takes values as shown in Figure 6. Perform a transient solution to the adjoint network to obtain the voltage waveform on each node, combine the voltage waveform of each node obtained by solving the original network, and bring it intoformula 19 to solve the gradient of the penalty function for the capacitance width vector;

8.4沿所求的当前优化方向进行一维搜索，找到非负一维搜索因子，使罚函数的值在当前优化方向上达到最优；8.4 Carry out a one-dimensional search along the desired current optimization direction, find a non-negative one-dimensional search factor, and make the value of the penalty function optimal in the current optimization direction;

8.5根据公式21更新电容宽度向量；8.5 Update the capacitance width vector according to formula 21;

8.6如果‖f(W^(k+1))‖＜ε₂，本次无约束优化结束推出，转步骤9；8.6 If ‖f(W^(k+1 ))‖<ε₂ , this unconstrained optimization is finished and launched, go to step 9;

本例子中，电容宽度向量的维数m＝744，In this example, the dimension of the capacitance width vector m=744,

如果k＝744，则W⁽⁰⁾＝W^(k+1)，f(G⁽⁰⁾)＝f(G^(k+1))，转向步骤8.2；If k=744, then W⁽⁰⁾ =W^(k+1) , f(G⁽⁰⁾ )=f(G^(k+1) ), turn to step 8.2;

如果k＜744，根据公式22更新优化方向，回到步骤8.4继续优化；If k<744, update the optimization direction according to formula 22, and return to step 8.4 to continue optimization;

9.根据优化结果计算p_t的值，如果p_t＜ε₁，当前电容宽度向量即是所求最优解，算法结束退出；否则更新罚因子α，设l＝l+1，回到步骤8继续优化；本实例中一共求解了13次无约束优化问题；9. Calculate the value of p_t according to the optimization result. If p_t <ε₁ , the current capacitance width vector is the optimal solution, and the algorithm ends and exits; otherwise, update the penalty factor α, set l=l+1, and return to the step 8 Continue to optimize; in this example, a total of 13 unconstrained optimization problems were solved;

10.最终进行电容数值调整；经过调整，优化后得到的744个去耦合电容最终调整为195个；10. Finally adjust the capacitance value; after adjustment, the 744 decoupling capacitors obtained after optimization are finally adjusted to 195;

11.适当调整每行中的单元布局，使添加的去耦合电容可以放置于布局的空白区域中，最后得到的单元布局和去耦合电容分布情况如图11所示。11. Properly adjust the cell layout in each row, so that the added decoupling capacitors can be placed in the blank area of the layout. The final cell layout and decoupling capacitor distribution are shown in Figure 11.

本算法是在CPU 450M，内存2G的Sun Solaris V880工作站上实现并运行的，全部代码利用C语言和C++编写。This algorithm is realized and run on a Sun Solaris V880 workstation with CPU 450M and memory 2G, and all codes are written in C language and C++.

Claims

Translated fromChinese

否则执行以下步骤：Otherwise perform the following steps:

min min A A = = \underset{j j &Element; &Element; M m}{Σ Σ} (({w w}_{j j} \times \times H h)) - - - - ((11)),,

M是允许添加去耦合电容的节点集合，M＝{1，...，m}，MN；N为供电网络中所有节点的集合，N＝{1，...，n}；H是标准单元的高，w_j是添加在节点j上的去耦电容c_j的宽度；M is the node set that allows adding decoupling capacitors, M={1,...,m}, MN; N is the set of all nodes in the power supply network, N={1,...,n}; H is the height of the standard cell, w_j is the width of the decoupling capacitor c_j added on node j;

约束条件如下：The constraints are as follows:

(5.1)电压降约束：(5.1) Voltage drop constraints:

{s the s}_{i i} = = {&Integral; &Integral;}_{00}^{T T} max max (({V V}_{min min} - - {v v}_{i i} ((t t)),, 00)) dt dt = = {&Integral; &Integral;}_{{t t}_{11}}^{{t t}_{22}} (({V V}_{min min} - - {v v}_{i i} ((t t)))) dt dt - - - - ((22))

[t₁，t₂]为i节点违反电压降约束的时间区间，V_min为电压闽值，v_i(t)为i节点的电压值；[t₁ , t₂ ] is the time interval during which node i violates the voltage drop constraint, V_min is the voltage threshold, and v_i (t) is the voltage value of node i;

(5.2)电迁移约束：(5.2) Electromigration constraints:

用[t’₁，t’₂]时间内，供电网络分支(p，q)两端节点电压差的绝对值和工艺允许的最大电流密度为σ时在分支长度l_pq上的电压降之差的积分值来表示：In [t'₁ , t'₂ ] time, the difference between the absolute value of the node voltage difference at both ends of the power supply network branch (p, q) and the voltage drop on the branch length l_pq when the maximum current density allowed by the process is σ Integral value to represent:

{u u}_{p p,, q q} = = {&Integral; &Integral;}_{00}^{T T} max max [[(({| | v v}_{p p} ((t t)) {- - v v}_{q q} ((t t)) | | - - ρ ρ {l l}_{p p,, q q} σ σ)),, 00]] dt dt = = {&Integral; &Integral;}_{{t t}^{' '}_{11}}^{{t t}^{' '}_{22}} ((| | {v v}_{p p} ((t t)) - - {v v}_{q q} ((t t)) | | - - ρ ρ {l l}_{p p,, q q} σ σ)) dt dt - - - - ((33))

其中，v_p和v_q分别是电源分枝(p，q)两端节点的电压，v_p-v_q即该分枝上的电压差；ρ是方块电阻；l_pq是分枝(p，q)的长度；Among them, v_p and v_q are the voltages of the nodes at both ends of the power branch (p, q) respectively, and v_p -v_q is the voltage difference on the branch; ρ is the sheet resistance; l_pq is the branch (p, q) the length of q);

(5.3)去耦电容面积约束：(5.3) Decoupling capacitor area constraints:

{dw dw}_{r r} = = max max ((\underset{y the y &Element; &Element; ND ND ((r r))}{Σ Σ} {w w}_{r r,, y the y} - - {rw rw}_{r r},, 00)),, r r &Element; &Element; NR NR - - - - ((44))

min min f f = = A A + + {p p}_{t t}

= = A A + + α α \cdot &Center Dot; ((\underset{i i &Element; &Element; N N}{Σ Σ} {s the s}_{i i}^{22} + + \underset{((p p,, q q)) &Element; &Element; B B}{Σ Σ} {u u}_{pq pq}^{22} + + \underset{r r &Element; &Element; NR NR}{Σ Σ} d d {w w}_{r r}^{22} + + \underset{r r &Element; &Element; NR NR,, y the y &Element; &Element; ND ND ((r r))}{Σ Σ} e e {w w}_{r r,, y the y}^{22})),, - - - - ((66)),,

(7)设置罚因子α的初始值；每个可添加去耦电容的位置上的去耦电容初始值都设为允许的最小电容宽度，得到电容宽度向量作为下面无约束优化的初始解；另外给出误差限ε₁＞0；(7) Set the initial value of the penalty factor α; the initial value of the decoupling capacitor at each position where a decoupling capacitor can be added is set to the minimum allowed capacitor width, and the capacitor width vector is obtained as the initial solution of the unconstrained optimization below; in addition Given error limits ε₁ >0;

(8)求解当前无约束优化问题，得到当前最优解电容宽度向量W⁽¹⁾；(8) Solving the current unconstrained optimization problem to obtain the current optimal solution capacitor width vector W⁽¹⁾ ;

得P⁽⁰⁾＝-f(W⁽⁰⁾) —(7)，Get P⁽⁰⁾ =-f(W⁽⁰⁾ )-(7),

(8.3)用扩展的伴随网络法求罚函数相对于电容宽度向量的梯度：(8.3) Find the gradient of the penalty function relative to the capacitor width vector with the extended adjoint network method:

&dtri; &dtri; f f ((W W)) = = [[\frac{&PartialD; &PartialD; f f}{{&PartialD; &PartialD; w w}_{11}},, \frac{&PartialD; &PartialD; f f}{{&PartialD; &PartialD; w w}_{22}},, \cdot &Center Dot; \cdot &Center Dot; \cdot &Center Dot;,, \frac{&PartialD; &PartialD; f f}{{&PartialD; &PartialD; w w}_{j j}},, \cdot &Center Dot; \cdot &Center Dot; \cdot &Center Dot;,, \frac{&PartialD; &PartialD; f f}{{&PartialD; &PartialD; w w}_{m m}} {]]}^{T T},, j j &Element; &Element; M m - - - - ((88)),,

宽度为w_j的电容c_j连接在供电网络的节点j上，假设节点j位于第rj行的yj位置，则罚函数f相对于w_j的偏导数可以表示为：Capacitor c_j with width w_j is connected to node j of the power supply network, assuming node j is located at position yj in row rj, then the partial derivative of penalty function f with respect to w_j can be expressed as:

\frac{&PartialD; &PartialD; f f}{{&PartialD; &PartialD; w w}_{j j}} = = H h + + 22 α α (({dw dw}_{rj r j} + + {ew ew}_{rj r j,, yj yj})) + + 22 α α [[\underset{i i &Element; &Element; N N}{Σ Σ} {s the s}_{i i} \frac{{&PartialD; &PartialD; s the s}_{i i}}{{&PartialD; &PartialD; w w}_{j j}} + + \underset{((p p,, q q)) &Element; &Element; B B}{Σ Σ} {u u}_{pq pq} \frac{{&PartialD; &PartialD; u u}_{pq pq}}{{&PartialD; &PartialD; w w}_{j j}}]] - - - - ((99)),,

rj∈NR，yj∈ND(rj)rj∈NR,yj∈ND(rj)

c c = = \frac{{ϵ ϵ}_{ox ox}}{{T T}_{ox ox}} \times \times w w \times \times H h - - - - - - ((1010)),,

得

\frac{&PartialD; f}{{&PartialD; w}_{j}} = H + 2 α ({dw}_{rj} + {ew}_{rj, yj}) + \frac{2 α ϵ_{ox} H}{T_{ox}} [\underset{i &Element; N}{Σ} s_{i} \frac{{&PartialD; s}_{i}}{{&PartialD; c}_{j}} + \underset{(p, q) &Element; B}{Σ} u_{pq} \frac{{&PartialD; u}_{pq}}{{&PartialD; c}_{j}}] - - (11),

have to

\frac{&PartialD; f}{{&PartialD; w}_{j}} = h + 2 α ({dw}_{r j} + {ew}_{r j, yj}) + \frac{2 α ϵ_{ox} h}{T_{ox}} [\underset{i &Element; N}{Σ} {the s}_{i} \frac{{&PartialD; the s}_{i}}{{&PartialD; c}_{j}} + \underset{(p, q) &Element; B}{Σ} u_{pq} \frac{{&PartialD; u}_{pq}}{{&PartialD; c}_{j}}] - - (11),

rj∈NR，yj∈ND(rj)rj∈NR,yj∈ND(rj)

通过对原电路网络建立对应电路中各节点的一系列伴随网络，并作电路灵敏度分析后，得到：By establishing a series of adjoint networks corresponding to each node in the original circuit network and analyzing the sensitivity of the circuit, we get:

\frac{{&PartialD; &PartialD; s the s}_{i i}}{{&PartialD; &PartialD; c c}_{j j}} = = {&Integral; &Integral;}_{00}^{T T} {v v}_{j j,, {E E.}_{i i}}^{' '} ((t t)) \times \times {\overset{. .}{v v}}_{j j} ((T T - - t t)) dt dt - - - - ((1212)),,

\frac{{&PartialD; &PartialD; u u}_{pq pq}}{{&PartialD; &PartialD; c c}_{j j}} = = {&Integral; &Integral;}_{00}^{T T} {v v}_{j j,, {t t}_{pq pq}}^{' '} ((t t)) \times \times {\overset{. .}{v v}}_{j j} ((T T - - t t)) dt dt - - - - ((1313)),,

= = {&Integral; &Integral;}_{00}^{T T} [[{v v}_{j j,, {E E.}_{p p}}^{' '} ((t t)) - - {v v}_{j j,, {E E.}_{q q}}^{' '} ((t t))]] \times \times {\overset{. .}{v v}}_{j j} ((T T - - t t)) dt dt

其中，

{\dot{v}}_{j} (T - t) = \frac{{dv}_{j} (T - t)}{dt}

是原电路网络中j节点的电压对时间t的导数；v′_j，Ei(t)是对应于节点i建立的伴随网络中j节点的电压(v′_j，Ep(t)，v′_j，Eq(t)同理)，它可以表示如下：in,

{\dot{v}}_{j} (T - t) = \frac{{dv}_{j} (T - t)}{dt}

is the voltage derivative of node j in the original circuit network with respect to time t; v′_{j, Ei} (t) is the voltage of node j in the accompanying network established corresponding to node i (v′_{j, Ep} (t), v′_{j , Eq} (t) is the same), it can be expressed as follows:

{v v}_{j j,, {E E.}_{i i}}^{' '} ((t t)) = = Z Z ((j j)) {v v}_{{E E.}_{i i}}^{' '} ((t t)) = = Z Z ((j j)) {G G}^{- - 11} [[{E E.}_{i i} ((t t)) + + {EC EC}_{i i} ((t t)) + + {EL EL}_{i i} ((t t))]] - - - - ((1414)),,

EC_i(t)和EL_i(t)是对应于节点i建立的伴随网络中的电容和电感元素做等效后得到的电流源向量；EC_i (t) and EL_i (t) are current source vectors obtained after equivalent capacitance and inductance elements in the accompanying network established corresponding to node i;

于是得到：So get:

\underset{i i &Element; &Element; N N}{Σ Σ} {s the s}_{i i} \frac{{&PartialD; &PartialD; s the s}_{i i}}{{&PartialD; &PartialD; c c}_{j j}} + + \underset{((p p,, q q)) &Element; &Element; B B}{Σ Σ} {u u}_{pq pq} \frac{{&PartialD; &PartialD; u u}_{pq pq}}{{&PartialD; &PartialD; c c}_{j j}}

= = \underset{i i &Element; &Element; N N}{Σ Σ} {s the s}_{i i} (({&Integral; &Integral;}_{00}^{T T} {v v}_{j j,, {E E.}_{i i}}^{' '} ((t t)) \times \times {\overset{. .}{v v}}_{j j} ((T T - - t t)) dt dt)) + + \underset{((p p,, q q)) &Element; &Element; B B}{Σ Σ} {u u}_{pq pq} (({&Integral; &Integral;}_{00}^{T T} [[{v v}_{j j,, {E E.}_{p p}}^{' '} ((t t)) - - {v v}_{j j,, {E E.}_{q q}}^{' '} ((t t))]] \times \times {\overset{. .}{v v}}_{j j} ((T T - - t t)) dt dt)) - - - - ((1515)),,

= = {&Integral; &Integral;}_{00}^{T T} {{{\overset{. .}{v v}}_{j j} ((T T - - t t)) \times \times {{\underset{i i &Element; &Element; N N}{Σ Σ} (({s the s}_{i i} \times \times {v v}_{j j,, {E E.}_{i i}}^{' '} ((t t)))) + + \underset{((p p,, q q)) &Element; &Element; B B}{Σ Σ} {{{u u}_{pq pq} \times \times [[{v v}_{j j,, {E E.}_{p p}}^{' '} ((t t)) - - {v v}_{j j,, {E E.}_{q q}}^{' '} ((t t))]]}}}}}} dt dt

依据式(14)，(15)得到：According to formula (14), (15) get:

\underset{i i &Element; &Element; N N}{Σ Σ} {s the s}_{i i} \frac{{&PartialD; &PartialD; s the s}_{i i}}{{&PartialD; &PartialD; c c}_{j j}} + + \underset{((p p,, q q)) &Element; &Element; B B}{Σ Σ} {u u}_{pq pq} \frac{{&PartialD; &PartialD; u u}_{pq pq}}{{&PartialD; &PartialD; c c}_{j j}} = = Z Z ((j j)) {G G}^{- - 11} {I I}_{total total} ((t t)) - - - - ((1616)),,

{I I}_{new new} ((t t)) = = \underset{i i &Element; &Element; N N}{Σ Σ} [[{s the s}_{i i} + + {E E.}_{i i} ((t t))]] + + \underset{((p p,, q q)) &Element; &Element; B B}{Σ Σ} {{{u u}_{pq pq} \times \times [[{E E.}_{p p} ((t t)) - - {E E.}_{q q} ((t t))]]}} - - - - ((1818)),,

从而得到：and thus get:

\frac{&PartialD; &PartialD; f f}{{&PartialD; &PartialD; w w}_{j j}} = = H h + + 22 α α (({dw dw}_{rj r j} + + {ew ew}_{rj r j,, yj yj})) + + \frac{22 {αϵ αϵ}_{ox ox} H h}{{T T}_{ox ox}} {&Integral; &Integral;}_{00}^{T T} {{[[Z Z ((j j)) \times \times {G G}^{- - 11} \times \times {I I}_{total total} ((t t))]] \times \times {\overset{. .}{v v}}_{j j} ((T T - - t t))}} dt dt - - - - ((1919)),,

rj∈NR，yj∈ND(rj)，j∈Mrj ∈ NR, yj ∈ ND(rj), j ∈ M

(8.4)设迭代已经进行到了第k步，当前电容宽度向量和优化方向分别是为W^(k)和P^(k)，沿P^(k)进行一维搜索，找到非负一维搜索因子λ_k，使罚函数在P^(k)方向上达到最优，即：(8.4) Assuming that the iteration has reached the kth step, the current capacitance width vector and optimization direction are respectively W^(k) and P^(k) , and a one-dimensional search is performed along P^(k) to find a non-negative one-dimensional search factor λ_k , making the penalty function optimal in the direction of P^(k) , that is:

(8.5)根据下式更新电容宽度向量W^(k+1)：(8.5) Update the capacitor width vector W^(k+1) according to the following formula:

W^(k+1)＝W^(k)+λ_kP^(k) ——(21)，W^(k+1) =W^(k) +_λkP^(k) ——(21),

(10)由于实际可以添加的去耦电容值不是连续的，具有最小单位数值的限制，我们对最终得到的优化结果进行调整；若某位置添加的去耦电容值小于最小数值则将其合并到邻近的节点上，以形成较大的电容，并将这些电容调整为最小单位数值的倍数。(10) Since the actual decoupling capacitor value that can be added is not continuous and has the limitation of the minimum unit value, we adjust the final optimization result; if the decoupling capacitor value added at a certain position is less than the minimum value, it will be merged into adjacent nodes to form larger capacitances and adjust these capacitances to multiples of the smallest unit value.