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

项目名称： 基于图论的超大规模集成电路布线研究

项目编号： No.11401008

项目类型： 青年科学基金项目

立项/批准年度： 2014

项目学科： 数理科学和化学

项目作者： 耿显亚

作者单位： 安徽理工大学

项目金额： 23万元

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

中文关键词： 路分解；通道布线；通孔最少化；有向图；

英文摘要： 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

英文关键词： path decomposition；channel routing；via minimizat；directed graph；