超大规模集成电路(VLSI，Very Large Scale Integration)将大量电路单元集成于单一芯片。随着设计复杂度增加，如今开展VLSI设计已离不开电子设计自动化(EDA，Electronic DesignAutomation)工具的支持。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)，并可视化结果(电路单元的位置)。
问题三：除了连接线长和单元密度，布线密度也是衡量布局质量的重要指标之一。分析图4所示的网格布线密度计算模型，找出其存在的问题。针对发现的问题，提出改进方案。应用改进后的布线密度模型，计算问题2中更新后的全局布局结果的布线密度，并对结果(网格布线密度)进行可视化。
问题四：除了最小化总连接线长和满足单元密度约束外，希望网格布线密度的最大值越小越好。请在问题3的基础上，修正问题2所建立的数学模型。根据附件1和附件2提供的信息，应用修正后的模型完成全局布局，输出总连接线长(HPWL)，并可视化结果(电路单元的位置和网格布线密度)。
超大规模集成电路自动布局优化模型研究
摘 要
随着集成电路设计的日益复杂化，传统的手工设计方法已无法满足现代超大规模集成电路(VLSI)设计的需求。电子设计自动化(EDA)工具在其中扮演了至关重要的角色。本文聚焦于VLSI设计中的自动布局问题，探讨了全局布局和详细布局的优化策略，以实现更高效的电路设计和更低的功耗。本研究建立了多个数学模型，对电路单元的布局进行了深入分析和优化。
针对问题一，我们建立了基于电路单元连线接口坐标的线长评估模型，解决了传统HPWL估计在多连线接口情况下偏小的问题，并通过与RSMT的比较，验证了模型的准确性和有效性。
针对问题二，我们开发了网格密度评估模型，并结合问题一中的线长评估模型，构建了一个综合数学模型。该模型最小化了总连接线长，同时满足了单元密度约束，并通过优化算法完成了全局布局，得到了电路单元位置的优化布局方案。
针对问题三，我们分析了现有网格布线密度计算模型的不足，并提出了改进方案。通过引入连线权重和改进网格划分，我们建立了一个新的布线密度模型，该模型能更准确地反映实际布线情况，并通过可视化手段展示了更新后的布线密度。
针对问题四，我们在问题三的基础上进一步优化了布局，修正了问题二中的数学模型，不仅最小化了总连接线长和满足了单元密度约束，还优化了网格布线密度的最大值，实现了更高效、更均衡的布局效果。
关键词：超大规模集成电路；自动布局；电子设计自动化；全局布局；布线密度；优化模型
完整内容获取：
