不等间距通道布线算法在集成电路设计中的应用

"不等间距通道布线的一种有效算法 (1984年) - 清华大学自动化系陈允康、王健生与骊山微电子公司谢文广" 集成电路布图设计中的通道布线是一项核心算法，尤其是在1982年，Yoshimura和Kuh（葛守仁）提出了一种高效的算法。本文主要针对他们的工作进行了扩展，使其适用于出线端不等间距的复杂情况。这种改进的算法使用FORTRAN编程语言实现，并在骊山微电子公司的NOVA(A)系统上运行，利用该系统的自动绘图功能，能够直接生成实际的双层通道布线图。 通道布线在集成电路布图设计中占有重要地位，因为它简单有效，尤其在通道宽度可变且无闭环垂直约束时，可以确保100%的布通率。因此，无论是对于均匀结构如门阵列或单元胞结构，还是不均匀结构如积木块结构，通道布线算法都是理想选择。过去的研究中，Yoshimura和Kuh的算法被认为是最优的，它们基于图论，已在多个实例中取得最佳结果。这些算法已经被推广应用于各种复杂场景，包括有闭环垂直约束、不规则边界通道、三层通道以及两维通道布线。 本文提出的算法进一步打破了传统的限制，允许出线端不等间距地任意排列，而不局限于等间距且上下对齐。算法的独特之处在于，它接受实际出线端的坐标作为输入，使得可以直接生成反映真实布局的双层通道布线图。这在实际布线中具有更高的灵活性和实用性。 通道布线问题的基本设定是，元胞沿通道两侧排列，每个元胞的出线端都有特定的线号。目标是通过线网连接相同线号的出线端，通常水平线段位于一层，垂直线段位于另一层。在解决这个问题时，算法需要考虑如何有效地分配线网路径，同时避免线路交叉和拥堵，以达到最佳的布线效率和密度。 为了实现这一目标，算法首先会对出线端进行排序和组织，然后采用图论中的策略来规划线网路径，确保连接正确且路径最短。在不等间距的情况下，算法需要处理更多的变量，如不同出线端之间的距离差异，这可能增加了计算的复杂性。然而，通过精心设计的数据结构和搜索策略，算法可以高效地找到最优解。 这篇论文不仅提供了对现有通道布线算法的扩展，还展示了如何将理论算法转化为实际应用，特别是在实际的计算机辅助设计(CAD)系统中。这种方法的实施对于提高集成电路设计的效率和精度具有重要意义，为不规则和复杂结构的布线提供了新的解决方案。