背景
超大规模集成电路（VLSI，Very Large Scale Integration）将大量电路单元集 成于单一芯片。随着设计复杂度增加，如今开展 VLSI 设计已离不开电子设计自 动化（EDA ，Electronic Design Automation）工具的支持。EDA 作为算法密集型 产业，需要对数千种情境进行快速设计探索，是国家关键技术领域。其中，电路单元的自动布局是 EDA 研究的核心问题之一。
电路单元的自动布局旨在矩形布局区域内确定所有电路单元位置，以最小化 单元之间总连接线长并避免单元重叠。由于这是一个 NP-难问题，通常分为全局 布局和详细布局两个步骤。全局布局大致确定单元位置，允许单元重叠；详细布 局则消除重叠并进一步优化。本问题聚焦于全局布局，将电路单元视为不同大小 的矩形，矩形内分散有若干个连线接口，电路单元之间通过连线接口形成若干组 连接关系。全局布局的目标是最小化总连接线长，同时满足单元密度约束。总连 接线长等于每组有连接关系的电路单元的线长之和。由于布局阶段尚未实际布线， 每组线长通常可通过半周长线长（HPWL ，Half-Perimeter Wirelength）或直线型 斯坦纳最小树（RSMT，Rectilinear Steiner Minimal Tree）估计，要求连线水平或 竖直。HPWL 为连线接口外接矩形周长的一半，RSMT 为通过插入斯坦纳点构建 的线段长度之和。单元密度约束通过将矩形布局区域网格化后计算。每个网格的 单元密度等于与网格重叠的电路单元面积和网格面积的比值，限制不超过特定阈 值。附件 1 提供全局布局的中间状态，包括每组有连接关系的电路单元及其连线 接口名称、连线接口坐标和对应的 HPWL 和 RSMT 线长。附件 2 给出布局区域 尺寸、网格划分粒度和密度阈值、电路单元的尺寸、坐标及其连线接口的基本信息。
请建立数学模型解决以下问题：
- 问题 1 图 2 展示了 3 组具有不同连线接口数的 HPWL 和 RSMT 线长估计示 意图。RSMT 是布局阶段理想的线长表征，但是构建斯坦纳树是 NP 难问题。 HPWL 简单有效，但对多连线接口情形估计偏小。根据附件 1 提供的信息，请设 计一个与电路单元连线接口坐标相关的线长评估模型。该模型应满足：（1）每组 估计线长与对应 RSMT 的差值尽可能小；（2）能应用于评估附件 1 中的总连接线长。
- 问题 2 图 3 展示了单元密度计算示意图，请以此设计一个与电路单元坐标 相关的网格密度评估模型。应用问题 1 构建的线长评估模型，整合密度计算，建 立一个数学模型，目标为：（1）最小化总连接线长；（2）满足单元密度约束。根 据附件 1 和附件 2 提供的信息，应用此模型完成全局布局，输出总连接线长（HPWL），并可视化结果（电路单元的位置）。
- 问题 3 除了连接线长和单元密度，布线密度也是衡量布局质量的重要指标 之一。分析图 4 所示的网格布线密度计算模型，找出其存在的问题。针对发现的 问题，提出改进方案。应用改进后的布线密度模型，计算问题 2 中更新后的全局布局结果的布线密度，并对结果（网格布线密度）进行可视化。
- 问题 4 除了最小化总连接线长和满足单元密度约束外，希望网格布线密度 的最大值越小越好。请在问题 3 的基础上，修正问题 2 所建立的数学模型。根据 附件 1 和附件 2 提供的信息，应用修正后的模型完成全局布局，输出总连接线长（HPWL），并可视化结果（电路单元的位置和网格布线密度）。
文件格式说明
附件 1
(请下载附件1.txt)
组名称，（电路单元名称：连线接口名称），（对应连线接口坐标），HPWL，RSMT
Group1,(Cell94:ZN,Cell11:A2,Cell7:A1),((22704,21807),(25499,24186),(25633,24095)),5308,5308
Group2,(Cell89:Z,Cell8:I,Cell5:A1),((31596,22332),(29577,24007),(28894,24037)),4407,4407
Group3,(Cell5:ZN,Cell97:A2,Cell96:A1,Cell11:A1,Cell7:A2),((28994,23885),(26971,
24240),(26971,24321),(25809,24078),(25878,24474)),3774,4017
……
附件 1.txt 解释：
- 有五列，分别是：组名称，（电路单元名称：连线接口名称），（对应连线接口 坐标），HPWL ，RSMT。
- 组名称：表示具有连接关系的电路单元组，有多少个组编号表示有多少组具 有连接关系的电路单元。每组可以通过线长评估模型算出线长值。总连接线 长等于所有组的线长值总和。
- （电路单元名称：连线接口名称）：表示由哪些单元的连线接口构成该组连接。 例如 (Cell94:ZN,Cell11:A2,Cell7:A1)表示电路单元名称为 Cell94 上有名为 ZN 的连线接口，同理 Cell11 上有名为 A2 的连线接口，Cell7 上有名为 A1
的连线接口，三者会形成一组连接关系，连线方向只能水平或者竖直。 - （对应连线接口坐标）：与第二列一一对应，表示对应电路单元连线接口的位 置坐标（x，y）。例如 Cell94:ZN 对应的坐标是(22704,21807)，Cell11:A2 对应
的坐标是(25499,24186) ，Cell7:A1 对应的坐标是(25633,24095)。 - HPWL：表示用 HPWL 线长模型算得的该组电路单元连线长度。以 Group1 为 例 ， 连 线 接 口 形 成 的 外 接 矩 形 宽 度 为 25633-22704=2929 ， 高 度 为 24186-21807=2379 ，因此 HPWL=2929+2379=5308。
- RSMT：表示用 RSMT 线长模型算得的该组电路单元连线长度。
/home/lixingquan/OSCC/ieda-website/src/.vuepress/public/res/dataset/MCM_contest-24/appendix2.txt
附件 2
(请下载附件2.txt)
布局区域宽度，布局区域高度，水平方向网格数，竖直方向网格数，密度阈值：38080，37800，64，60，0.9
电路单元名称,(左下角 X,Y 坐标), 宽度,高度,(连线接口名称),(对应连线接口相对单元左下角的偏置坐标)
Cell1,(28431,23878), 1120, 1800,(A2,B,A1),((630, 1051),(910,870),(385,672))
Cell2,(29042,24255),560, 1800,(I),((205,860))
Cell3,(28483,24118),840, 1800,(A1,A2),((505, 1002),(195,880))
……
附件 2.txt 解释：
分为两个部分
- 布局区域信息：
表示布局区域的水平方向取值范围为[0,38080] ，竖直方向取 值范围为[0 ，37800]；整个布局区域划分为 64*60 个网格，每个网格的宽度 为 38080/64=595 ，高度为 37800/60=630；每个网格的单元密度不超过 0.9。 - 电路单元信息：
以 Cell1,(28431,23878), 1120, 1800,(A2,B,A1),((630, 1051),(910,870),(385,672)) 为例，解释含义。电路单元 Cell1，左下角坐标为(28431,23878) ，宽高分别为 1120 和 1800，有三个连线接口名为 A2,B,A1，这三个连线接口的坐标与 Cell1 左下角坐标的偏移量是(630, 1051),(910,870),(385,672) ，据此可以分别算出这 三 个 连 线 接 口 的 绝 对 坐 标 ， 例 如 Cell1:A2 的 绝 对 坐 标 是 (28431+630=29061,23878+1051=24929) 。注意，所有连线接口在电路单元中 的偏移量是固定值，不会随电路单元的位置变化而变化；因此，若知道电路单元的位置，就可以根据连线接口的偏移量算出其绝对坐标，进而计算线长。