基于图论的超大规模集成电路布线研究

The design of very large scale integrated circuits is one of the areas in which the methods of graph theory can be applied. Some problems of VLSI(Very Large Scale Integration) can be solved by the methods of graph theory. The main purpose of this project lies in studying the channel routing problem with 2-layer Manhattan model, the width (number of tracks required for routing) of a channel be minimized. Moreover, we consider efficient algorithms for via minimization problem. Finally, we study Gallai's path decomposition conjecture, which has some connection with edge-disjoint routing problem. The constraints of a channel routing problem can be represented by a horizontal constraint graph and a vertical constraint graph, then a routing problem can be made to a graph theory problem. We can use the methods of graph theory to solve routing problems. We want solve these problems and get the most small width of the channel routing problem with 2-layer Manhattan model, then we get the efficient algorithms for via minimization problem, which can be used in the actual wiring process. Finally, we want to prove Gallai's path decomposition conjecture is true in some special planar graphs. This project consider some problems with VLSI, the research will help to develop the theory of path decomposition and solve some 2-layer routing problems of VLSI.

图论在超大规模集成电路设计中有广泛的应用，运用图论的思想方法，可以解决超大规模集成电路设计中的布线问题。本项目运用有向图和图着色理论来处理超大规模集成电路布线中的问题：包括具有曼哈顿模型的两层通道布线的轨道高度上界，具有一般适用性的通道布线通孔最少化算法，与边不交布线问题有关的路分解猜想的理论问题。通道布线中结点的关系可以用水平约束图和垂直约束图来刻画，这样把通道布线问题转化为图论中的问题，进而利用图论的思想方法，通过研究这两个图的性质来设计布线轨道高度算法和通孔最少化算法。力求解决上述布线中的几个问题，确定具有曼哈顿模型的两层通道布线轨道高度的最优上界并设计出相对应的算法，设计出能运用到实际布线工艺中的通道布线通孔最少化算法，证明路分解算法在特殊平面图上的正确性。本项目所研究的问题是超大规模集成电路布线中的关键问题，问题的解决对超大规模集成电路两层通道布线问题的发展有较大的促进作用。

物理设计是超大规模集成电路设计的关键步骤，涉及到许多图论和组合优化模型与算法，研究用图论的方法来解决集成电路问题，不仅能大力促进图论与信息学科的融合，而且能为集成电路实际工艺提供指导。图论在超大规模集成电路设计中有广泛的应用，运用图论的思想方法，可以解决超大规模集成电路设计中的布线问题。本项目运用有向图和图着色理论来处理超大规模集成电路布线中的问题：包括具有曼哈顿模型的两层通道布线的轨道高度上界，具有一般适用性的通道布线通孔最少化算法，与边不交布线问题有关的路分解猜想的理论问题。通道布线中结点的关系可以用水平约束图和垂直约束图来刻画，这样把通道布线问题转化为图论中的问题，进而利用图论的思想方法，通过研究这两个图的性质来设计布线轨道高度算法和通孔最少化算法。经过三年的研究，课题组解决了上述布线中的几个问题，确定了具有曼哈顿模型的两层通道布线轨道高度的最优上界并设计出相对应的算法，设计出能运用到实际布线工艺中的通道布线通孔最少化算法，证明了路分解算法在特殊平面图上的正确性。本项目所研究的问题是超大规模集成电路布线中的关键问题，问题的解决对超大规模集成电路两层通道布线问题的发展有较大的促进作用。