面向标准单元布局的自适应加权平均线长模型

A Self-adaptive Weighted-average Wirelength Model for Global Placement

摘要

现有EDA工具通过在密度约束条件下使半周长线长（half-perimeter wirelength， HPWL）总和最小化方法来解决集成电路物理版图设计中标准单元的全局布局问题.然而，HPWL 的不可导性使得基于梯度的先进求解方法无法直接应用于全局布局.因此，布局中通常使用加权平均线长（weighted-average wirelength， WAWL）模型来近似 HPWL，但无法兼顾平滑度和精度.因此，本文提出了一种改进的自适应加权平均线长（SaWAWL）模型，通过每条连线实际长度自适应地调整各自的加权因子γ，在保证平滑度的同时使拟合HPWL的误差更小，提高了标准单元全局布局质量.基于所提出的模型实现了一个全局布局器，并完成了在DAC 2012 开源基准上的验证.结果表明，该模型可以使半周长线长总和减少3.69%.

Abstract

The existing EDA tools address the global placement problem of very large scale integration （VLSI） physical design by minimizing the sum of half-perimeter wirelength （HPWL） under density constraints. However， the non-differentiability of HPWL renders gradient-based advanced optimization methods inapplicable directly to global placement. Consequently， the weighted-average wirelength （WAWL） model is often employed to approximate HPWL， but it struggles to achieve a balance between smoothness and accuracy. This paper introduces an improved self-adaptive weighted-average wirelength （SaWAWL） model. It dynamically adjusts the weighted factors γ for each wire’s actual length， ensuring both smoothness and reduced error in fitting HPWL. The proposed model enhances the quality of global placement. A global placer based on this model is implemented and validated on the DAC 2012 open benchmark. The results indicate a 3.69% reduction in the total sum of half-perimeter wirelength.

Graphical abstract

关键词

集成电路 / 版图 / 物理设计 / 布局算法

Key words

integrated circuits / layout / physical design / placement algorithm

布局（placement）决定超大规模集成电路（very large scale integration， VLSI）物理设计中的标准单元在版图中的位置，其结果直接影响设计质量，包括功耗、时序收敛、信号完整性等各项性能指标，是物理设计的基石，可以说，如果不能实现高质量的布局结果，物理设计的后续步骤（如时钟树综合和布线）是没必要进行的.因此，寻求一种高效的方法来解决布局问题对整个物理设计来说意义重大.然而，布局是一个难以直接求解的NP 困难问题 ^［1］，其求解方法经历了三个阶段，依次分别是模拟退火算法^［2］、基于划分的布局方法^［3-4］和解析布局方法，其中解析布局是目前解决 VLSI 布局问题最先进的方法^［5-14］，也是当下主流自动布局布线工具（电子设计自动化，electronic design automation， EDA）如Innovus采用的方法.解析布局将整个布局过程分为三个步骤，依次为全局布局（global placement， GP）、合法化（legalization， LG）和详细布局（detailed placement， DP）.在这三个步骤中，全局布局是最重要的一步，因为它大致决定了所有标准单元的位置，而这直接决定了解析布局的结果^［15］；LG 负责在GP的基础上将标准单元合理摆放，主要任务是消除它们之间的重叠；DP则在前述两个步骤的基础上进行增量优化，进一步提高布局的质量.

总体来讲，在VLSI物理设计中，总线长，即所有单元互连的总半周长线长（HPWL）与设计的各关键指标呈正相关关系，更短的线长意味着更低的功耗、更小的串扰、更短的延时、更小的压降等.因此，在GP阶段采用线长驱动的布局算法（wirelength-driven placement， WDP）是提高电路整体性能的常用方法.

WDP通过在密度约束下，最小化设计中所有单元的半周长线长（HPWL）之和的方式来确定标准单元的位置^［16］.由于 HPWL 不可导，提出了许多可导的线长模型来逼近HPWL，如长和指数（long-sum-Exp，LSE）线长模型^［17］、二次线长模型^［18］、CHKS 线长模型^［19］、加权平均线长（weighted-average wirelength， WAWL）模型^［20］等.在所有模型中，WAWL虽然最初是为了解决三维布局问题而提出的，但其性能优异且同样适用于二维，几乎所有当下领先的布局器如 RePlace^［13］、NTUPlace^［8-9］和DREAMPlace ^［21］都采用了WAWL这一模型.然而WAWL这一当下最先进的模型仍存在一个问题——无法平衡精度和模型平滑度之间的关系.这是因为WAWL的性能由系数 \gamma 控制，\gamma 的值越大，函数越平滑，但相应的拟合误差也越大.

本文旨在解决前述WAWL线长模型不能兼顾精度与平滑度的问题.为此，首先推导了 WAWL与标准HPWL模型之间的拟合误差函数，研究了该误差随 \gamma 和线长的变化.并在此基础上，提出了一种改进的自适应加权平均线长模型.不同于传统的WAWL为所有连线设置统一的\gamma值，新模型在布局过程中使得每根连线可根据其自身实际长度自适应地调整各自的\gamma值.这样，由加权平均模型计算得到的线长的误差就能稳定在一个很小的值上，且保证了较好的模型平滑度.接着，我们将提出的线长模型集成到当前最先进的线长驱动的全局布局器 DREAMPlace^［21］中，得到了一个新的全局布局器.最后，在广受认可的开源数据集DAC 2012基准套件上进行了布局实验.实验结果显示，相比于文献［21］，基于本文所提模型的布局算法能在全局布局中使HPWL目标降低3.69%，证明了提出的自适应加权平均线长模型的优越性.

本文第1节介绍解析布局中全局布局的基础知识与加权平均线长模型；第2节推导并分析加权平均线长模型的误差函数；第3节提出本文核心的自适应加权平均线长模型，并将其集成到先进的 DREAMPlace上，实现了一个新的全局布局器；第4节介绍了实验环境与实验结果；第5节总结.

1 解析布局

GP将物理设计中的所有标准单元分散摆放，大致决定每个标准单元在版图中的位置，是解析布局中最重要，也是耗时最长的一步^［21］.一般来说，GP分为两类，一类称为二次布局（quadratic placement）^［22-24］，另一类称为非线性布局（nonlinear placement）^{［8-9，25］}. 二次布局由于采用了平方项的目标函数，效率相对更高；而非线性布局则能获得更高的布局质量^［21］，本文主要探究性能更优的非线性布局.如前文所述，非线性布局通过在密度约束下最小化线长目标来解决布局问题，如式（1）所示：

\mathrm{m}\mathrm{i}\mathrm{n}\sum _{e\in \mathit{E}}WL(e;x,y)（1）

\mathrm{s}.\mathrm{t}.d\left(x,y\right)\le d_t

式中：x,y分别表示单元在版图中的横、纵坐标；\mathrm{W}\mathrm{L}(\bullet ;\bullet )表示设计中所有单元（包括标准单元和宏单元）的总的连线长度； d_t是预先设定的目标密度，用于规范全局布局后单元间的重叠.采用拉格朗日松弛法将密度约束放宽到线长目标，作为密度惩罚，即得到全局布局算法的目标函数，如式（2）所示^［7-9］：

\mathrm{m}\mathrm{i}\mathrm{n}\left(\sum _{e\in E}\mathrm{W}\mathrm{L}\left(e;x,y\right)\right)+\lambda D(x,y)（2）

式中：D(\bullet ) 是避免布局过于集中的密度惩罚函数；\lambda表示密度约束的权重.要利用当下先进的梯度方法解决式（2）的非线性优化问题，\mathrm{W}\mathrm{L}(\bullet ;\bullet )目标必须是可微分的，但HPWL的表达式如式（3）^［15］所示，显然是不可导的.

\begin{array}{l}\mathrm{W}\mathrm{L}{(x,y)}_{\mathrm{h}\mathrm{p}\mathrm{w}\mathrm{l}}=\sum _{eϵE}\left(\mathrm{m}\mathrm{a}{\mathrm{x}}_{v_i,v_jϵe}\left|x_i-x_j\right|+\right.\\ \left.\mathrm{m}\mathrm{a}{\mathrm{x}}_{v_i,v_jϵe}\left|y_i-y_j\right|\right)\end{array}（3）

因此，非线性布局需要采用平滑的线长模型来近似HPWL.式（4）^［10］介绍了当前最先进的平滑模型 WAWL，此模型已被广泛应用于非线性布线.

\mathrm{W}\mathrm{L}{(x,y)}_{\mathrm{w}\mathrm{a}\mathrm{w}\mathrm{l}}=\left(\frac{\sum _{i\in e}{x}_i{\mathrm{e}}^{\frac{x_i}{\gamma }}}{\sum _{i\in E}{\mathrm{e}}^{\frac{x_i}{\gamma }}}-\frac{\sum _{i\in e}{x}_i{\mathrm{e}}^{-\frac{x_i}{\gamma }}}{\sum _{i\in E}{\mathrm{e}}^{-\frac{x_i}{\gamma }}}\right)（4）

在WAWL中，\gamma是预定义的参数，用于调节 WAWL的性能.文献［21］指出，WAWL的平滑度和精度相互冲突，由\gamma控制，但未给出相应的数学推导. 因此，为了更好地探究WAWL的平滑度与精度之间的关系，并更好地发挥WAWL在布局问题中的作用，我们推导了WAWL与标准的HPWL的误差函数，并详细研究了其数学特性.

2 误差函数

在不失一般性的前提下，考虑两个单元在 x 方向上连接的情况（y方向的分析完全相同）.假设两个单元的横坐标分别为 x_{\mathrm{1}}、x_{\mathrm{2}}，将坐标分别代入两种线长模型的表达式（3） 和（4），可以得到如下公式：

\mathrm{W}\mathrm{A}\mathrm{W}\mathrm{L}\left(x\right)=\frac{x_{\mathrm{1}}{\mathrm{e}}^{\frac{x_{\mathrm{1}}}{\gamma }}+x_{\mathrm{2}}{\mathrm{e}}^{\frac{x_{\mathrm{2}}}{\gamma }}}{{\mathrm{e}}^{\frac{x_{\mathrm{1}}}{\gamma }}+{\mathrm{e}}^{\frac{x_{\mathrm{2}}}{\gamma }}}-\frac{x_{\mathrm{1}}{\mathrm{e}}^{-\frac{x_{\mathrm{1}}}{\gamma }}+x_{\mathrm{2}}{\mathrm{e}}^{-\frac{x_{\mathrm{2}}}{\gamma }}}{{\mathrm{e}}^{-\frac{x_{\mathrm{1}}}{\gamma }}+{\mathrm{e}}^{-\frac{x_{\mathrm{2}}}{\gamma }}}（5）

\mathrm{H}\mathrm{P}\mathrm{W}\mathrm{L}\left(x\right)=\left|x_{\mathrm{1}}-x_{\mathrm{2}}\right|（6）

\mathrm{式中}:\mathrm{W}\mathrm{A}\mathrm{W}{\mathrm{L}}_x和\mathrm{H}\mathrm{P}\mathrm{W}{\mathrm{L}}_x分别表示由WAWL和 HPWL计算得出的连线长度.假设x_{\mathrm{1}}>x_{\mathrm{2}}，可以将 式（6）重写为式（7）：

\mathrm{H}\mathrm{P}\mathrm{W}\mathrm{L}\left(x\right)=x_{\mathrm{1}}-x_{\mathrm{2}}（7）

然后，从式（7）中减去式（5）， 即可计算出误差：

\Delta =\mathrm{H}\mathrm{P}\mathrm{W}\mathrm{L}\left(x\right)-\mathrm{W}\mathrm{A}\mathrm{W}\mathrm{L}\left(x\right)（8）

式中：\Delta表示误差函数.将\mathrm{H}\mathrm{P}\mathrm{W}{\mathrm{L}}_x和\mathrm{W}\mathrm{A}\mathrm{W}{\mathrm{L}}_x的具体表达式代入式（8），误差函数可表述如下：

\Delta =x_{\mathrm{1}}-x_{\mathrm{2}}-\frac{x_{\mathrm{1}}{\mathrm{e}}^{\frac{x_{\mathrm{1}}}{\gamma }}+x_{\mathrm{2}}{\mathrm{e}}^{\frac{x_{\mathrm{2}}}{\gamma }}}{{\mathrm{e}}^{\frac{x_{\mathrm{1}}}{\gamma }}+{\mathrm{e}}^{\frac{x_{\mathrm{2}}}{\gamma }}}+\frac{x_{\mathrm{1}}{\mathrm{e}}^{-\frac{x_{\mathrm{1}}}{\gamma }}+x_{\mathrm{2}}{\mathrm{e}}^{-\frac{x_{\mathrm{2}}}{\gamma }}}{{\mathrm{e}}^{-\frac{x_{\mathrm{1}}}{\gamma }}+{\mathrm{e}}^{-\frac{x_{\mathrm{2}}}{\gamma }}}（9）

简化式（9）即可得到：

\Delta =x-\frac{x{\mathrm{e}}^{\frac{x}{\gamma }}-x{\mathrm{e}}^{-\frac{x}{\gamma }}}{\mathrm{2}+{\mathrm{e}}^{\frac{x}{\gamma }}+{\mathrm{e}}^{-\frac{x}{\gamma }}}（10）

式中：x=x_{\mathrm{1}}-x_{\mathrm{2}}.

为了进一步探讨\gamma、x和\Delta之间的关系，求\Delta关于x的导数，得到式（11）：

{\Delta }^{\text{'}}=\frac{\mathrm{2}({\mathrm{e}}^{-\frac{x}{\gamma }}{)}^{\mathrm{2}}+\mathrm{2}{\mathrm{e}}^{\frac{x}{\gamma }}+\mathrm{6}{\mathrm{e}}^{-\frac{x}{\gamma }}-\mathrm{2}\frac{x}{\gamma }{\mathrm{e}}^{-\frac{x}{\gamma }}-\mathrm{2}\frac{x}{\gamma }{\mathrm{e}}^{\frac{x}{\gamma }}+\mathrm{6}-\mathrm{4}\frac{x}{\gamma }}{(\mathrm{2}+{\mathrm{e}}^{\frac{x}{\gamma }}+{\mathrm{e}}^{-\frac{x}{\gamma }}{)}^{\mathrm{2}}}（11）

注意到式（11） 的分母恒为正值，且对于导函数我们只关注其值的正负，因此，可提取{\Delta }^{\text{'}}的分子作为一个新函数g(t)，并研究其取值变化情况.

g\left(t\right)=\mathrm{2}({\mathrm{e}}^{-t}{)}^{\mathrm{2}}+\mathrm{2}{\mathrm{e}}^t+\mathrm{6}{\mathrm{e}}^{-t}-\mathrm{2}t{\mathrm{e}}^t-\mathrm{2}t{\mathrm{e}}^{-t}+\mathrm{6}-\mathrm{4}t（12）

其中t=x/\gamma且t>\mathrm{0}.然后，求出g（t）关于t的导数：

g{(t)}^{\mathrm{\text{'}}}=-\mathrm{4}{\left({\mathrm{e}}^{-t}+\mathrm{1}\right)}^{\mathrm{2}}-\mathrm{2}t({\mathrm{e}}^t-{\mathrm{e}}^{-t})（13）

显然，当t>\mathrm{0}时，g{(t)}^{\mathrm{\text{'}}}总是负值，即g(t)在区间[\mathrm{0},+\mathrm{\infty })内是单调递减的.因此，{\Delta }^{\text{'}}也是[\mathrm{0},+\mathrm{\infty })的单调减函数.又因为{{\Delta }^{\text{'}}}_{(\mathrm{0})}=\mathrm{1}且{{\Delta }^{\text{'}}}_{(+\mathrm{\infty })}=-\mathrm{\infty }，所以有且仅有一个满足{{\Delta }_{(x_{\mathrm{0}})}}^{\text{'}}=\mathrm{0}的点x_{\mathrm{0}}，使得误差函数\Delta在 [\mathrm{0},x_{\mathrm{0}}]内单调递增，在[x_{\mathrm{0}},+\mathrm{\infty })内单调递减，即误差函数在x=x_{\mathrm{0}}处取得最大值.在Matlab的帮助下，可以求得x_{\mathrm{0}}的近似值.

当x\approx \mathrm{1.275}\gamma时，{\Delta }^{\text{'}}\approx \mathrm{0}，{\Delta }_{\mathrm{m}\mathrm{a}\mathrm{x}}=\mathrm{0.557}\gamma.即误差函数\Delta在区间［0，1.275\gamma）内单调递增，在［x₀，+∞）内单调递减.

3 自适应加权平均线长模型与全局布局器

3.1 自适应加权平均线长模型

如式（14）所示，连线长度越接近\mathrm{1.275}\gamma，误差就越大，且最大误差与\gamma的取值成正比.当连线长度接近式（14）的极大值点\mathrm{1.275}\gamma时，若\gamma的值越小，误差就会越小；但\gamma的值不能过小，以免影响WAWL的平滑度.基于此，考虑提出一个自适应的{\gamma }^{\text{'}}，其值可以根据连线长度实现自调节：在实际线长接近极大值点时将\gamma调节到较小的值以减小误差；在远离极大值点时，\gamma调节至较大的值以保证平滑度和收敛性能.

基于上述推导，考虑具有以下特性的函数式（14）（如表1所示），该函数具有有限的取值区间，一个极小值点，在极限值点两侧与误差函数相反的增减性，借助该函数可以通过适当的k取值来构造满足需求的自适应\gamma表达式.

f\left(x\right)=x/{\mathrm{e}}^{kx}（14）

构造的自适应\gamma的表达式见式（15），其中{\gamma }_{\mathrm{m}\mathrm{a}\mathrm{x}}、{\gamma }_{\mathrm{m}\mathrm{i}\mathrm{n}}是为平衡精度和平滑度而预先设定的\gamma取值上限和下限，\gamma的取值只会在两者之间变化；x表示连线的实际长度.\gamma随x变化的情况见图1，可见借助 式（15），\gamma可以实现基于x的自适应调节.

\begin{array}{l}\gamma =-x\left({\gamma }_{\mathrm{m}\mathrm{a}\mathrm{x}}-{\gamma }_{\mathrm{m}\mathrm{i}\mathrm{n}}\right)\times \\ \mathrm{e}\mathrm{x}\mathrm{p}\left\{-x/\left[\mathrm{1.275}({\gamma }_{\mathrm{m}\mathrm{a}\mathrm{x}}+{\gamma }_{\mathrm{m}\mathrm{i}\mathrm{n}})\right]\right\}+{\gamma }_{\mathrm{m}\mathrm{a}\mathrm{x}}\end{array}（15）

将式（15）应用到加权平均线长模型中，即可得到一种新的自适应加权平均线长（self-adaptive weighted-average wirelength， SaWAWL）模型.不同于传统的加权平均线长模型为所有连线设置一个统一的 \gamma，本模型给设计中的每根连线分配一个独立的\gamma，其值由连线根据其实际长度自适应调整，从而在全局布局过程中始终以较小误差拟合HPWL的同时保持模型的平滑度.具体的算法实现如表 2 所示.

3.2 基于SaWAWL的全局布局器

基于本文提出的SaWAWL 模型和文献［21］中实现的目前最先进的 DREAMPlace 框架，实现了新的全局布局器，具体的算法结构如表3所示.在每轮迭代中，进行线长的前向传播和反向传播运算时，会调用算法1更新\gamma的值，并计算相应的加权平均线长，直至整个布局达到预设的收敛条件.

4 实验环境与实验结果

4.1 实验环境

本文所有实验基于配有英伟达RTX3090显卡的英特尔2.7GHz Linux 服务器完成，代码则由Python和CUDA联合编程实现.布局实验在广受认可的开源数据集 DAC 2012 基准套件^［26］上进行.

对本文布局器与当前最先进的全局布局器 DREAMPlace进行一系列对比实验，以验证所提出的线长模型的优越性.DREAMPlace有不同的版本，本实验采用的是DREAMPlace-Master.为了直观展示线长模型对全局布局结果的影响，关闭具有增量优化效果的DP，并设置与DREAMPlace完全相同的停止迭代的密度溢出条件（stop overflow），从而保证相同的LG影响.

4.2 模型仿真结果

SaWAWL的模型仿真结果如图2所示，图中曲线展示了WAWL和SaWAWL对HPWL的拟合结果.从图中可以看见，在红虚线标注区间内，WAWL不能很好地近似HPWL，而SaWAWL则实现了对HPWL较好的拟合，这是因为其通过将此区间内的\gamma调整到较小值（如图1），减小了模型的拟合误差.图3显示了两种线长模型相对HPWL的误差，证实了本文算法确实可以实现更小的误差.

4.3 全局布局结果

全局布局在宏单元固定的基础上将标准单元逐步分散，确定其在版图中的位置.图4展示了本实验采用的数据集DAC 2012中一个测试基准SB2的布局过程，其中橘色区域表示预先放置好的宏单元，蓝色代表需进行布局的标准单元.从图中可以看出， 图4（a）的初始状态阶段，标准单元集中分布；在布局迭代过程中，布局器将集中摆放的标准单元逐渐分散摆放，如图4（b）、图4（c）所示，并最终得到了标准单元均匀摆放布局结果，如图4（d）所示.

本文全局布局器的实验结果见表4.表4的左侧介绍了数据集DAC 2012的基本信息，由表可知该数据集涵盖了从523k门到1 014k门的设计，具有代表性.表4的右侧展示了本文算法与当下最先进的线长驱动全局布局器DREAMPlace的对比实验结果.可见与最先进的布局器相比，采用本文所提SaWAWL 模型的布局器实现了更优的布局结果：在开源基准上实现了HPWL 最多3.69%的减少.实验结果证明了本文所提出的加权平均线长模型的优越性.

5 结 论

本文提出了一种适用于超大规模集成电路全局布局的新型自适应加权平均线长模型.该模型在设计中每个连线可根据其实际线长自适应地调整\gamma值，在全局布局过程中精确地拟合HPWL.仿真结果表明，与最先进的WAWL模型相比，本文所提出的模型可实现更小的拟合误差.基于DAC 2012开源基准的全局布局实验结果表明，基于 SaWAWL的全局布局器相比基于WAWL的DREAMPlace可取得更好的布局结果，证明了所提出的模型的有效性.

本文实现的线长驱动的布局算法（wirelength-driven placement， WDP）综合考虑物理设计中的各项指标，如时序、功耗、可布线性等，通过追求总体最短的连线长度近似优化以上指标，但未落实到具体的性能指标，下一步将聚焦于探索具体指标如时序驱动的布局算法（timing-driven placement， TDP）研究.

参考文献

[1] DONATH W E， DONATH W E ．Complexity theory and design automation［C］//Proceedings of the 17th Design Automation Conference. Minneapolis，Minnesota，USA. ACM，1980：412-419．

[2] TAGHAVI T， YANG X J， CHOI B K ．Dragon2005：large-scale mixed-size placement tool［C］//Proceedings of the 2005 International Symposium on Physical Design．San Francisco， California， USA． ACM，2005：245-247．

[3] ROY J A， PAPA D A， ADYA S N，et al ．Capo：robust and scalable open-source Min-cut floorplacer［C］//Proceedings of the 2005 International Symposium on Physical Design．San Francisco California， USA． ACM，2005：224-226．

[4] JIANG Z W， CHENY T C， HSUY T C，et al ．NTUplace2：a hybrid placer using partitioning and analytical techniques［C］//Proceedings of the 2006 International Symposium on Physical Design．San Jose， California， USA． ACM，2006：215-217．

[5] KAHNG A B， REDA S， WANG Q K ．Architecture and details of a high quality，large-scale analytical placer［C］//ICCAD-2005．IEEE/ACM International Conference on Computer-Aided Design，2005． San Jose，CA，USA． IEEE，2005：891-898．

[6] CHAN T， CONG J，SZE K ．Multilevel generalized force-directed method for circuit placement［C］//Proceedings of the 2005 International Symposium on Physical Design．San Francisco， California， USA． ACM，2005：185-192．

[7] KAHNG A B， WANG Q K ．A faster implementation of APlace［C］//Proceedings of the 2006 International Symposium on Physical Design．San Jose， California， USA． ACM，2006：218-220．

[8] CHEN T C， JIANG Z W， HSU T C，et al. NTUplace3：an analytical placer for large-scale mixed-size designs with preplaced blocks and density constraints［J］. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems，2008，27（7）：1228-1240．

[9] HSU M K， CHEN Y F， HUANG C C， et al. NTUplace4h： a novel routability-driven placement algorithm for hierarchical mixed-size circuit designs［J］. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems， 2014， 33（12）： 1914-1927．

[10] LU J W， CHEN P W， CHANG C C， et al. ePlace：electrostatics-based placement using fast Fourier transform and nesterov’s method［J］. ACM Transactions on Design Automation of Electronic Systems，2015，20（2）：1-34．

[11] LU J W， ZHUANG H， CHEN P W，et al ．ePlace-MS：electrostatics-based placement for mixed-size circuits［J］．IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems，2015，34（5）：685-698．

[12] ZHU Z R， CHEN J L， PENG Z，et al ．Generalized augmented Lagrangian and its applications to VLSI global placement［C］//2018 55th ACM/ESDA/IEEE Design Automation Conference （DAC）． San Francisco，CA，USA． IEEE，2018：1-6．

[13] HE X， HUANG T， XIAO L F，et al ．Ripple：a robust and effective routability-driven placer［J］．IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems，2013，32（10）：1546-1556．

[14] LIN T， CHU C， WU G ．POLAR 3.0：an ultrafast global placement engine［C］//2015 IEEE/ACM International Conference on Computer-Aided Design （ICCAD）. Austin，TX，USA. IEEE，2015： 520-527．

[15] CHANG Y W， JIANG Z W， CHEN T C. Essential issues in analytical placement algorithms［J］. IPSJ Transactions on System LSI Design Methodology， 2009， 2： 145-166.

[16] ALPERT C J， MEHTA D P， SAPATNEKAR S S ．Handbook of algorithms for physical design automation［M］. Boca Raton， Fla：Auerbach Publications，2008.

[17] KAHNG A B， WANG Q K. A faster implementation of APlace［C］//Proceedings of the 2006 International Symposium on Physical Design. San Jose， California， USA. ACM， 2006： 218-220．

[18] VISWANATHAN N， PAN M， CHU C ．FastPlace 3.0：a fast multilevel quadratic placement algorithm with placement congestion control［C］//2007 Asia and South Pacific Design Automation Conference. Yokohama，Japan． IEEE，2007：135-140．

[19] BHRAMAR RAY B N，DAS S， HAZRA K，et al ．An optimized HPWL model for VLSI analytical placement［C］//2015 International Conference on Information Technology （ICIT）. Bhubaneswar， India. IEEE， 2015： 7-12．

[20] HSU M K， CHANG Y W， BALABANOV V. TSV-aware analytical placement for 3D IC designs［C］//Proceedings of the 48th Design Automation Conference. San Diego， California，USA. ACM，2011： 664-669．

[21] LIN Y B， JIANG Z X， GU J Q， et al. DREAMPlace：deep learning toolkit-enabled GPU acceleration for modern VLSI placement［J］. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems， 2021， 40（4）： 748-761．

[22] KIM M C， VISWANATHAN N， ALPERT C J，et al ．MAPLE：multilevel adaptive placement for mixed-size designs［C］//Proceedings of the 2012 ACM International Symposium on International Symposium on Physical Design. Napa， California， USA. ACM， 2012： 193-220．

[23] KIM M C， LEE D J， MARKOV I L ．SimPL：an effective placement algorithm［C］//2010 IEEE/ACM International Conference on Computer-Aided Design （ICCAD）. San Jose，CA，USA． IEEE，2010：649-656．

[24] LIN T， CHU C， SHINNERL J R，et al ．POLAR：a high performance mixed-size wirelengh-driven placer with density constraints［J］．IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems，2015，34（3）：447-459．

[25] LI W X， LIN Y B， PAN D Z ．elfPlace：electrostatics-based placement for large-scale heterogeneous FPGAs［C］//2019 IEEE/ACM International Conference on Computer-Aided Design （ICCAD）. Westminster，CO，USA． IEEE，2019：1-8．

[26] VISWANATHAN N， ALPERT C，SZE C，et al ．The DAC 2012 routability-driven placement contest and benchmark suite［C］//DAC Design Automation Conference 2012． San Francisco，CA，USA. IEEE， 2012： 774-782．

基金资助

国家自然科学基金资助项目(U21A20504)

National Natural Science