2020年研究生组优秀论文A题：集成电路通道布线

简介：
本文为2020年研究生组关于集成电路通道布线问题的研究成果。文中深入探讨了在设计复杂集成电路时如何高效且合理地进行通道布局，以优化信号传输速度和降低功耗，最终提升芯片性能。该论文对于推动集成电路领域的技术创新具有重要意义。 在集成电路设计过程中，通道布线是一项至关重要的物理设计步骤。它涉及到将电子元件通过金属线路连接起来以确保电路的性能与可靠性。本段落主要探讨了三种不同情况下的通道布线优化问题：单层金属层、多层金属层以及带有通孔约束的多层金属层。 对于单层金属层面，研究重点在于二维平面上的问题解决策略。我们建立了一个坐标系来表示布线区域中的方格位置，并通过集合的形式表示各个方格之间的连接可能性，确保所有线路只能沿着直线或直角方向铺设。目标是使总布线长度达到最小化，这与传统的最短路径问题有所关联。通过对传统最短路模型的改进，我们特别考虑了多对引脚间的最短路径和线路不相交的要求，并建立了一个混合整数规划（MIP）模型。通过Python调用Gurobi求解器对该模型进行了优化处理，但仅有一个测试案例有可行结果。同时，我们也采用了一种基于改进A*算法的方法来解决这个问题，得到了相同的结果。如果引脚对之间存在同侧合法边界相交，则问题无解。 进入多层金属层面的布线优化研究中，我们允许不同金属线路共享同一方格以避免短路现象的发生。首先将所有层次映射到最底层建立二维模型，并进一步扩展至三维空间考虑更多的约束条件。基于改进后的最短路径算法构建了两个用于解决多层三维布线问题的新模型，同时引入通孔电阻的考量因素。同样地，我们使用Gurobi求解器对这些模型进行了优化处理，发现所有测试案例都有可行的结果，并且计算效率较高。此外，还利用了一种改进遗传算法来进一步提高算法性能，在结果上与前述方法一致。 在第三部分的研究中，我们在多层金属布线的基础上增加了通孔间距的约束条件：任意两个通孔之间的距离至少为2个格点。通过定义这种新的间距规则并进行位置分析后建立了新模型。在这种严格条件下，只有三个测试案例中的一个被认为是可行的。 综上所述，本段落深入探讨了集成电路通道布线优化策略的研究进展，从单层到多层再到带有通孔约束条件下的多层布线问题提出了多种数学建模和算法解决方案。这些研究成果对于提高集成电路设计效率与质量、降低信号延迟以及减少功耗等方面具有重要的意义。文中涉及的关键技术包括最短路径问题的求解方法、混合整数规划（MIP）、Gurobi求解器的应用，改进A*搜索算法及遗传算法等工具和技术，在解决复杂的布线优化挑战中发挥了重要作用。