布局初始化算法的最新结果

∗𝑥⊤𝐺𝑥 = 𝑐1,𝑦⊤𝐺𝑦 = 𝑐2,𝑥⊤𝐺𝑦 = 𝑐3(2), 𝑥 = 𝑥1,𝑥2 ⊤0最新结果：通过投影特征向量算法进行布局初始化0Pengwen Chenpengwen@email.nchu.edu.tw国立中兴大学0Chung-Kuan Chengckcheng@eng.ucsd.edu加利福尼亚大学圣地亚哥分校0Albert Chernalchern@eng.ucsd.edu加利福尼亚大学圣地亚哥分校0chholtz@eng.ucsd.edu加利福尼亚大学圣地亚哥分校0Aoxi Li aoli@ucsd.edu加利福尼亚大学圣地亚哥分校0Yucheng Wangyuw132@ucsd.edu加利福尼亚大学圣地亚哥分校0摘要0VLSI设计的分析布局的规范方法依赖于解非线性规划以最小化线长和单元重叠。我们的重点是产生初始布局，使得全局分析布局器与现有的启发式方法相比表现更好。我们将初始化问题简化为一个二次约束二次规划。我们的公式考虑到了固定宏单元。我们提出了一种高效的算法，可以快速生成具有数百万个单元的测试用例的初始化。我们展示了我们的参数初始化方法相对于详细布局线长的卓越性能。1 引言0给定一个电路和一个布局区域，布局问题是将每个电路模块分配到布局区域的某个特定位置。由于典型布局问题的固有非凸性，不能保证该过程在有限的时间内收敛到最优或者好的坐标分配，变量的初始化起着重要的作用 [ 4]。初始化的典型方法包括在没有二阶约束的情况下最小化线长[4]，将单元坐标均匀分配到原点，或者分配小的随机值[3]。在这项工作中，我们探讨了“是否有可能改进大规模布局引擎的随机初始化？”我们研究了一种新颖的固定节点感知的公式，并提出了一种快速算法来解决它。我们通过使用最先进的布局流程 [ 3 ]在详细布局和合法化之后演示了收敛到优越的布局解决方案。我们将初始化作为一个二次约束二次规划（QCQP）来进行。通过对电网图的分解，固定节点约束被集成进去。我们的代码可在GitHub上找到 10设  �,�  ∈  R � 是与  � 组件的坐标对应的向量，使得  � -th组件的坐标编码在  [ �  :  � ] 的第  � -th 行中；  [ �  :  � ] �。我们的目标是分配坐标，使得所得到的布局具有较小的累积线长。02.1 全局分析布局0传统的全局布局策略在密度约束下最小化线长。密度约束通常与目标一起集成，以产生无约束的松弛 [1]:0� 对应作者 1https://github.com/choltz95/null-space-rayleigh-quotient-iteration0最小化 �,� ( � � = ( �,� ) ∈E �� ( � ; �,� ) +  �� ( �,� )) (1)0其中  E  表示给定的电网集合，  �� (∙ ;  ∙)  是一个函数，它以电网实例  �为输入并返回累积线长，  � (∙)是一个密度惩罚。在IC布局的背景下，电网的线长通常用其半周长线长（HPWL）或平滑的替代方法来建模，  �  是一个平滑的密度 [ 4]。重叠约束通常在布局过程中通过逐渐增加  �来满足，但这会增加线长。当前最先进的IC布局算法 [ 1 ,  3 ,  4]以这种方式解决问题1。注意，用于建模密度的传统模型导致问题1是非凸的。02.2 谱布局0通过首先将网表超图通过各种模型（例如团，星等）折叠到组件图中，将 VLSI布局问题简化为图布局问题。然后得到图连接性的矩阵表示——图拉普拉斯矩阵。相关特征值问题的解近似于最稀疏切割问题的解[2]，而顶点投影到由第一个非平凡特征值张成的空间中的聚类对应于图的高度连接组件。我们使用这些坐标来初始化全局布局。更具体地说，我们解决以下问题，其中  �  和  �  是单元坐标，  � �  是常数，  �是单元面积的矢量，  �  =  diag ( � ) ，而  �  是图拉普拉斯矩阵；  �  =  � −  � ，其中  �  是（加权）邻接矩阵，而  �  是相关度矩阵。0最小化 �,� � � ��  +  � � �� s.t.  � � �  =  0 , � � �  =  0 ,0直观上，目标是最小化二维布局的加权平方线长。线性和二次约束使布局在 �  和  �轴上居中和分布。固定节点约束。许多布局涉及对一部分单元的约束，通常是大型宏单元。我们展示了固定节点约束如何自然地导致方程式2中的 � ， �  和 �  项的分解。我们将固定节点的坐标表示为  � 1 ， � 1。同样，让可移动节点为  � 2 ，  � 2  然后，我们可以表示0� ,  � , 和  �  用这些指数表示：  �  = �  � 11  � 12 � 21  � 220（对于  �  也是如此）通过将  � 1  和  � 1视为常数，可以重新编写问题2中描述的目标（忽略常数）：0最小化 � 2 ,� 2 � � 2 � 22 � 2  +  � � 2 � 22 � 2  +  2 � � � 2  +  2 � � �2 (3)0DAC '22，2022年7月10日至14日，美国加利福尼亚州旧金山，版权所有©2022 由所有者/作者持有。ACM ISBN978-1-4503-9142-9/22/07。https://doi.org/10.1145/3489517.353062013980本作品采用知识共享署名国际4.0许可协议进行许可。adaptec1211K29K221K73.2484.3973.2374.3170.36 (3.9%)63.861.56adaptec2255K21K266K82.51189.4682.24172.9181.68 (1.0%)162.491.47adaptec3452K25K467K194.12314.54193.87309.88189.13 (2.5%)313.293.02adaptec4496K29K516K174.43371.72174.16354.16171.73 (1.5%)372.142.81bigblue1278K11K284K89.43112.6489.43107.5687.32 (2.3%)94.112.07bigblue2558K141K577K136.69387.94136.69361.75132.49 (3.0%)327.142.51bigblue3558K37K1123K303.991064.63303.991047.66298.47 (1.8%)847.036.15bigblue42177K170K2230K743.751534.11743.751500.70726.71 (2.2%)1372.4925.6613990Chen 等0表1：布局和合法化的 HPWL 和运行时间。我们报告相对于随机初始化的改进百分比（括号内）。0设计 #自由单元 #固定引脚 #网络 随机最小线长 我们的0HPWL GP 运行时间 (s) HPWL GP 运行时间 (s) HPWL GP 运行时间 (s) 初始化运行时间 (m)0其中  �  =  � 12 � 1  和  �  =  � 12 � 1 。03 特征向量方法和投影0我们首先重新编写了等式3中定义的目标（将  � 22 写为“ � ”）。令  � =  [ � 2 ,� 2 ]  和  � 0  =  [ �,� ] ∈  R � × 2 。令  �  =  �  −  �� � 为R � 的正交子空间上的投影。假设  �是单位向量。目标可以重新编写为：0最小化 � { �  ( � )  =  tr ( �  � ( ����  +  2 �� 0 ))} (4)0满足 � � � = � 和 � � � = [0, 0] 的约束。不失一般性，用 �� 0 替换 �0，我们可以假设 � � � 0 = [0, 0]。通过引入�，我们强制满足线性约束。我们提出了一个两步算法：（1）首先解决广义特征值问题 min � tr (� � ���) subject to � � � =�，（2）调用投影操作来共同解决约束 � � � = �并适当转换解决方案，以最小化 2 � � �� 0。阶段1. 虽然 �可能非常稀疏，便于应用稀疏特征向量算法，但 ���可能过于密集。为了解决这个问题，我们采用了一种仅依赖于矩阵-向量乘法和使用迭代方法（如共轭梯度法）高效计算 � − 1 � 的Rayleigh商迭代方法。在高层次上，该方法通过重复以下更新步骤进行：0� � − 1 = �� � − 1 /|| �� � − 1 || (5)0从 � (�) �� � = � � − 1 (6) 解出 �� �0阶段2. 我们陈述以下结果：0命题1（投影）。设 � 1 是一个中间解，� 1 := � � 1 � 1，� � 0。0对 � 1 进行投影，[� 1]+ := arg min � {� (�) = ||� - � 1|| 2 �0= tr (�) + tr (� 1) - 2 max ��,� 1�}0s.t. � � � = �. 对 � 1 / 2 � 1 / 2 1 进行奇异值分解，� Σ � � = � 1 / 2 �/ 2 1. 然后，最小化器 � = [� 1]+ 给出如下结果0� = � 1 � − 1 / 2 1 �� � � 1 / 2 (7)0以下命题意味着保持特征向量结构的正交变换（即旋转/反射），同时最小化固定引脚和自由单元之间的线长。0命题2（负定的 � 选择）。注意，� 的第一项满足不变性 tr (� � ����) = ���˜�)，其中 ˜� = �� 对于任意正交矩阵 � ∈ R 2 × 2。如果 �是一个局部极小值点，则 −� � � 0 � 0 并且对称。计算 � � � 0 的奇异值= � � � � � � �。令 � = −� � � � �。然后，tr ((��) � � 0) = −tr (� �04 实验0算法参数。为了生成IC网络列表的图形布局，我们采用了混合网络模型[6]——团和星模型的组合。每个网络根据网络的大小转换为星形图或团图——即具有三个或更少引脚的网络被建模为团，具有四个或更多引脚的网络被建模为星形图，并引入一个自由伪引脚变量。为了设置�，我们考虑单元格的表面积，使其分布以1为中心，并归一化为总和为1。 � �根据自由布局空间确定。我们将我们的方法应用于ISPD'05竞赛套件[5]中的八个基准测试，并测量了合法化后的累积HPWL。数值结果见表1。我们发现原点初始化方法始终表现不佳，而我们的方法始终产生更好的HPWL结果，高达4%。在图1中，我们绘制了全局布局算法的一个中间迭代结果，以展示全局布局算法保持种子布局提供的全局和局部结构。0图1：Adaptec1布局。（左）：种子布局的投影和聚类（k-均值）特征向量。（右）：中间DREAMPLACE结果。请注意，聚类保持在一0我们感谢NSFCCF-2110419和台湾科技部110-2115-M-005-007-M0[1] C. Cheng, A. B. Kahng, I. Kang, and L. Wang. 2018. RePlAce:提高全局布局的解决方案质量和可布线性验证. IEEE TCAD. [2] Kenneth M. Hall. 1970.一种r维二次放置算法. 管理科学17. [3] Yibo Lin, Shounak Dhar, Wuxi Li, Haoxing Ren,Brucek Khailany, and David Z. Pan. 2019. DREAMPlace:基于深度学习工具的现代VLSI布局的GPU加速. In DAC. [4] Jingwei Lu, Pengwen Chen,Chin-Chih Chang, Lu Sha, Dennis Jen-Hsin Huang, Chin-Chi Teng, and Chung-KuanCheng. 2015. ePlace: 基于快速傅里叶变换和Nesterov方法的静电场布局. ACM TODAES20. [5] Gi-Joon Nam, Charles J. Alpert, Paul Villarrubia, Bruce Winter, and MehmetYildiz. 2005. ISPD2005布局竞赛和基准套件. In ISPD. ACM. [6] N Viswanathan and C.Chu. 2004. FastPlace: 使用单元移动、迭代局部优化和混合网络模型的高效分析布局. IEEETCAD, 26–33.